1. Paweł Wieczorek
  2. ocaml-mutable-data-structures

Commits

Paweł Wieczorek  committed d5babb6 Draft

better map

  • Participants
  • Parent commits e2101bc
  • Branches default

Comments (0)

Files changed (2)

File src/AVL.ml

View file
  * Copyrights(C) 2013 by Pawel Wieczorek <wieczyk at gmail>
  *)
 
+
 (*********************************************************************************************************************
  * Types
  ********************************************************************************************************************)
 let make_leaf a = ref (make_leaf_node a)
 
 (*********************************************************************************************************************
- * Map, folds, etc
+ * folds, etc
  ********************************************************************************************************************)
 
-let rec map f r = ref (map_node f !r)
-and map_node f = function
-    | Empty ->
-        Empty
-
-    | Node (left_avl, right_avl, depth, a) ->
-        Node (map f left_avl, map f right_avl, depth, f a)
-
 let rec fold strategy f acc r = fold_node strategy f acc !r
 and fold_node strategy (f : 'a -> 'acc -> 'b) acc = function
     | Empty ->
     | Node (left_avl, right_avl, depth, a) ->
         let do_left acc'  = fold strategy f acc' left_avl in
         let do_right acc'  = fold strategy f acc' right_avl in
-        strategy f acc do_left a do_right
+        strategy f acc do_left !a do_right
 
 let preorder_fold_strategy f acc do_left a do_right =
     do_right (f (do_left acc) a)
             let is_balanced = abs (balance_factor avl) < 2 in
             is_balanced && check_invariant left_avl && check_invariant right_avl
 
+
 (*********************************************************************************************************************
  * Rotate
  ********************************************************************************************************************)
     rebalance avl1
 
 (*********************************************************************************************************************
- * Merge
+ * Map
  ********************************************************************************************************************)
 
-let merge ?(allow_dup=false) avl1 avl2 =
-    iter (fun x -> insert_bst x avl1) avl2;
-    rebalance avl1
+let map f avl = 
+    let new_avl = make_empty () in
+    iter (fun x -> insert (f x) new_avl) avl;
+    new_avl
+
+(*********************************************************************************************************************
+ * 
+ ********************************************************************************************************************)
 
 (*********************************************************************************************************************
  * To/From list

File src/Set.ml

View file
 
 let fold f acc t = AVL.fold_preorder f acc t
 
+let substract t1 t2 = AVL.substract t1 t2
+
+let diff t1 t2 = 
+    let tclone = clone t1 in
+    substract tclone t2
+
+let map f t = AVL.map f t
+
+let update f t = AVL.update f t
+
+let alter f t = AVL.alter f t