Commits

Paweł Wieczorek committed a9972de Draft

Added safe finders

Comments (0)

Files changed (3)

         rebalance right_avl;
         single_rebalance avl
         
+let exception_to_option f = 
+    try
+        Some (f ())
+    with Not_found ->
+        None
 
 (*********************************************************************************************************************
  * Insert
  ********************************************************************************************************************)
 
-and raw_insert balance_strategy allow_dup a avl = match !avl with
+let rec raw_insert balance_strategy allow_dup a avl = match !avl with
     | Empty ->
         avl := make_leaf_node a
 
 
 let rec raw_extract balance_strategy selection_strategy avl = match !avl with
     | Empty ->
-        failwith "Cannot extract from empty AVL tree"
+        raise Not_found
 
     | Node (left_avl, right_avl, node_depth, a) ->
         let (selected_avl, other_avl) = selection_strategy left_avl right_avl in
 let extract_max avl = raw_extract_max single_rebalance avl
 let extract_min avl = raw_extract_min single_rebalance avl
 
+let extract_max_opt avl = exception_to_option (fun () -> raw_extract_max single_rebalance avl)
+let extract_min_opt avl = exception_to_option (fun () ->  raw_extract_min single_rebalance avl)
+
 (*********************************************************************************************************************
  * Find
  ********************************************************************************************************************)
         
 let find_max avl =
     let selection_strategy left_avl right_avl = right_avl in
-    raw_find_bound selection_strategy
+    raw_find_bound selection_strategy avl
 
 let find_min avl =
     let selection_strategy left_avl right_avl = left_avl in
-    raw_find_bound selection_strategy
+    raw_find_bound selection_strategy avl
+
+
+let find_max_opt avl = exception_to_option (fun () -> find_max avl)
+let find_min_opt avl = exception_to_option (fun () -> find_min avl)
+
 
 let rec mem a avl = match !avl with
     | Empty ->
     rebalance avl1
 
 (*********************************************************************************************************************
- * Map
- ********************************************************************************************************************)
-let map f avl = 
-    let new_avl = make_empty () in
-    iter (fun x -> insert (f x) new_avl) avl;
-    new_avl
-
-(*********************************************************************************************************************
- * Update
- ********************************************************************************************************************)
-
-let update (f : 'a -> 'a) avl = 
-    let new_avl = make_empty () in
-    iter (fun x -> insert (f x) new_avl) avl;
-    new_avl
-
-(*********************************************************************************************************************
  * Alter
  ********************************************************************************************************************)
 
     new_avl
 
 (*********************************************************************************************************************
+ * Update
+ ********************************************************************************************************************)
+
+let update f avl =
+    alter (fun x -> Some (f x)) avl
+
+(*********************************************************************************************************************
  * To/From list
  ********************************************************************************************************************)
 
 
 let extract_min t = AVL.extract_min t
 
+let max_opt t = AVL.find_max_opt t
+
+let min_opt t = AVL.find_min_opt t
+
+let extract_max_opt t = AVL.extract_max_opt t
+
+let extract_min_opt t = AVL.extract_min_opt t
+
 let size t = AVL.size t
 
 let clone t = AVL.clone t
       val singleton : M.t -> t
       val insert : M.t -> t -> unit
       val remove : M.t -> t -> unit
-      val max : 'a -> t -> M.t
-      val min : 'a -> t -> M.t
+      val max : t -> M.t
+      val min : t -> M.t
+      val max_opt : t -> M.t option
+      val min_opt : t -> M.t option
       val extract_max : t -> M.t
       val extract_min : t -> M.t
+      val extract_max_opt : t -> M.t option
+      val extract_min_opt : t -> M.t option
       val size : t -> int
       val clone : t -> t
       val from_list : M.t list -> unit