Paweł Wieczorek avatar Paweł Wieczorek committed 8e65b7f Draft

fixes

Comments (0)

Files changed (1)

 
 let rec is_empty r = is_empty_node !r
 and is_empty_node = function
-    | Empty -> false
-    | Node _ -> true
+    | Empty -> true
+    | Node _ -> false
 
 let alter_depth diff = function
     | Empty ->
         | Node (left_avl, right_avl, depth, a) ->
             let is_balanced = abs (balance_factor avl) < 2 in
             is_balanced && check_invariant left_avl && check_invariant right_avl
-            
 
 (*********************************************************************************************************************
  * Rotate
                     a     := !y;
 
                     recalculate_depth avl;
-                    recalculate_depth left_avl
+                    recalculate_depth left_avl;
+                    recalculate_depth right_avl
 
 
             end
                     a     := !x;
 
                     recalculate_depth avl;
+                    recalculate_depth left_avl;
                     recalculate_depth right_avl
 
             end
                 balance_ll avl
 
         | _ ->
-            ()
+            recalculate_depth avl
 
-let no_rebalance _ = ()
+let no_rebalance avl = recalculate_depth
 
 let rec rebalance avl = match !avl with
     | Empty ->
-        ()
+        recalculate_depth avl
 
     | Node (left_avl, right_avl, _, _) ->
         rebalance left_avl;
 
 and raw_insert balance_strategy allow_dup a avl = match !avl with
     | Empty ->
-        avl := make_leaf_node a
+        avl := make_leaf_node a;
+        true
 
     | Node(left_avl, right_avl, node_depth, b) ->
-        begin match compare a !b with
-            | n when n < 0 ->
-                raw_insert balance_strategy allow_dup a left_avl
+        let result = match compare a !b with
+                | n when n < 0 ->
+                    raw_insert balance_strategy allow_dup a left_avl
 
-            | n when n > 0 ->
-                raw_insert balance_strategy allow_dup a right_avl
+                | n when n > 0 ->
+                    raw_insert balance_strategy allow_dup a right_avl
 
-            | _ ->
-                if allow_dup then
-                    raw_insert balance_strategy allow_dup a left_avl
-        end;
-        incr node_depth;
-        balance_strategy avl
+                | _ ->
+                    if allow_dup then
+                        ignore (raw_insert balance_strategy allow_dup a left_avl);
+                    allow_dup
+                        
+            in
+        balance_strategy avl;
+        result
 
 let insert ?(allow_dup=false) a = raw_insert single_rebalance allow_dup a
 
 let insert_bst ?(allow_dup=false) a = raw_insert no_rebalance allow_dup a
 
 let insert_many ?(allow_dup=false) xs avl =
-    List.iter (fun a -> raw_insert no_rebalance allow_dup a avl) xs;
+    List.iter (fun a -> ignore (raw_insert no_rebalance allow_dup a avl)) xs;
     rebalance avl
 
 (*********************************************************************************************************************
         let (selected_avl, other_avl) = selection_strategy left_avl right_avl in
         if is_empty selected_avl then begin
             avl := !other_avl;
-            a
+            balance_strategy avl;
+            !a
         end else
             let extracted = raw_extract balance_strategy selection_strategy selected_avl in
             balance_strategy avl;
 let extract_min avl = raw_extract_min single_rebalance avl
 
 (*********************************************************************************************************************
+ * Find
+ ********************************************************************************************************************)
+
+let rec raw_find selection_strategy avl = match !avl with
+    | Empty ->
+        raise Not_found
+
+    | Node (left_avl, right_avl, node_depth, a) ->
+        let selected_avl = selection_strategy left_avl right_avl in
+        if is_empty selected_avl then
+            !a
+        else
+            raw_find selection_strategy selected_avl
+        
+let find_max avl =
+    let selection_strategy left_avl right_avl = right_avl in
+    raw_find selection_strategy
+
+let find_min avl =
+    let selection_strategy left_avl right_avl = left_avl in
+    raw_find selection_strategy
+
+(*********************************************************************************************************************
  * Remove
  ********************************************************************************************************************)
 
                     raw_remove balance_strategy stop_after_first a left_avl;
                     raw_remove balance_strategy stop_after_first a right_avl
                 end;
-                let left_max = raw_extract_max balance_strategy left_avl in
-                avl := Node (left_avl, right_avl, node_depth, left_max)
+                b := raw_extract_max balance_strategy left_avl;
         end
 
 
         print_endline (prefix ^ "- []")
 
     | Node (left_avl, right_avl, depth, a) ->
-        print_endline (prefix ^ "- " ^ print_value a);
+        print_endline (prefix ^ "- " ^ print_value a ^ " [depth = " ^ string_of_int !depth ^ "]");
         printer print_value (prefix ^ "  |") right_avl;
         print_endline (prefix ^ "  |");
         printer print_value (prefix ^ "   ") left_avl
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.