Commits

Paweł Wieczorek committed e2101bc Draft

another fixes

  • Participants
  • Parent commits d29570d

Comments (0)

Files changed (2)

     | Node (left_avl, right_avl, node_depth, a) ->
         node_depth := succ (max (depth left_avl) (depth right_avl))
 
+let rec size avl = match !avl with
+    | Empty ->
+        0
+
+    | Node (left_avl, right_avl, node_depth, a) ->
+        size left_avl + size right_avl + 1
+
 (*********************************************************************************************************************
  * Creators
  ********************************************************************************************************************)
 let fold_revorder f acc avl = fold revorder_fold_strategy f acc avl
 
 
+let rec iter f avl = match !avl with
+    | Empty ->
+        ()
+
+    | Node (left_avl, right_avl, depth, a) ->
+        iter f left_avl;
+        f !a;
+        iter f right_avl
+
 let rec check_invariant avl =
     match !avl with
         | Empty ->
             rotate_left left_avl;
             rotate_right avl
 
-let single_rebalance avl = match !avl with
+let single_rebalance avl = begin match !avl with
     | Empty ->
         ()
 
                 balance_ll avl
 
         | _ ->
-            recalculate_depth avl
+            ()
+
+        end;
+        recalculate_depth avl
 
 let no_rebalance avl = recalculate_depth avl
 
 
 let remove ?(stop_after_first=true) a avl = raw_remove single_rebalance stop_after_first a avl
 
+
+let remove_many ?(stop_after_first=true) xs avl = 
+    List.iter (fun x -> raw_remove no_rebalance stop_after_first x avl) xs;
+    rebalance avl
+
+(*********************************************************************************************************************
+ * Substract
+ ********************************************************************************************************************)
+
+let substract ?(stop_after_first=true) avl1 avl2 =
+    iter (fun x -> raw_remove no_rebalance stop_after_first x avl1) avl2;
+    rebalance avl1
+
+(*********************************************************************************************************************
+ * Merge
+ ********************************************************************************************************************)
+
+let merge ?(allow_dup=false) avl1 avl2 =
+    iter (fun x -> insert_bst x avl1) avl2;
+    rebalance avl1
+
 (*********************************************************************************************************************
  * To/From list
  ********************************************************************************************************************)
 let to_list_flatten avl =
     fold_inorder (fun acc a -> a::acc) [] avl
 
-let to_from_list xs =
+let from_list xs =
     let avl = make_empty () in
-    List.iter (fun x -> insert x avl) xs
+    insert_many xs avl
 
 (*********************************************************************************************************************
  * print
 
 let extract_min t = AVL.extract_min t
 
+let size t = AVL.size t
 
+let clone t = AVL.clone t
+
+let from_list t = AVL.from_list t
+
+let to_list t = AVL.to_list t
+
+let fold f acc t = AVL.fold_preorder f acc t
+