Commits

Paweł Wieczorek  committed 11b5f2d Draft

Added modules

  • Participants
  • Parent commits 8f02063

Comments (0)

Files changed (5)

  * Copyrights(C) 2013 by Pawel Wieczorek <wieczyk at gmail>
  *)
 
+module Make (M : Set.OrderedType) = struct
 
 (*********************************************************************************************************************
  * Types
  ********************************************************************************************************************)
 
-type 'a avl
-    = 'a node ref
-and 'a node
+type avl
+    = node ref
+and node
     = Empty
-    | Node of 'a avl * 'a avl * int ref * 'a ref
+    | Node of avl * avl * int ref * M.t ref
 
 
 (*********************************************************************************************************************
 
 let make_empty () = ref Empty
 
-
 let make_leaf_node a = 
     Node (make_empty (), make_empty (), ref 1, ref a)
 
         avl := make_leaf_node a
 
     | Node(left_avl, right_avl, node_depth, b) ->
-        begin match compare a !b with
+        begin match M.compare a !b with
             | n when n < 0 ->
                 raw_insert balance_strategy allow_dup a left_avl
 
  * Find
  ********************************************************************************************************************)
 
-let rec raw_find selection_strategy avl = match !avl with
+let rec raw_find_bound selection_strategy avl = match !avl with
     | Empty ->
         raise Not_found
 
         if is_empty selected_avl then
             !a
         else
-            raw_find selection_strategy selected_avl
+            raw_find_bound selection_strategy selected_avl
         
 let find_max avl =
     let selection_strategy left_avl right_avl = right_avl in
-    raw_find selection_strategy
+    raw_find_bound selection_strategy
 
 let find_min avl =
     let selection_strategy left_avl right_avl = left_avl in
-    raw_find selection_strategy
+    raw_find_bound selection_strategy
+
+let rec mem a avl = match !avl with
+    | Empty ->
+        false
+
+    | Node (left_avl, right_avl, node_depth, b) ->
+        match M.compare a !b with
+            | n when n < 0 ->
+                mem a left_avl
+
+            | n when n > 0 ->
+                mem a right_avl
+
+            | _ ->
+                true
 
 (*********************************************************************************************************************
  * Remove
     | Empty ->
         ()
 
-    | Node (left_avl, right_avl, node_depth, b) when !node_depth = 1 && compare a b = 0 ->
+    | Node (left_avl, right_avl, node_depth, b) when !node_depth = 1 && M.compare a !b = 0 ->
         avl := Empty
 
-    | Node (left_avl, right_avl, node_depth, b) when is_empty left_avl && compare a b = 0 ->
+    | Node (left_avl, right_avl, node_depth, b) when is_empty left_avl && M.compare a !b = 0 ->
         avl := !right_avl
 
-    | Node (left_avl, right_avl, node_depth, b) when is_empty right_avl && compare a b = 0 ->
+    | Node (left_avl, right_avl, node_depth, b) when is_empty right_avl && M.compare a !b = 0 ->
         avl := !left_avl
 
     | Node (left_avl, right_avl, node_depth, b) ->
-        begin match compare a b with
+        begin match M.compare a !b with
             | n when n < 0 ->
                 raw_remove balance_strategy stop_after_first a left_avl;
 
 
 let alter (f : 'a -> 'a option) avl = 
     let new_avl = make_empty () in
-    let g x  =
+    let g x =
         match f x with
             | None ->
                 ()
         print_endline (prefix ^ "  |");
         printer print_value (prefix ^ "   ") left_avl
 
-let printer_int = printer (fun r -> string_of_int !r) "" 
+
+end
+(*
+ * MutableDataStructures
+ *
+ * Copyrights(C) 2013 by Pawel Wieczorek <wieczyk at gmail>
+ *)
+
+module Make (M : Set.OrderedType) = struct
+
+module AVL = AVL.Make(M)
+
+(*********************************************************************************************************************
+ * Types
+ ********************************************************************************************************************)
+
+type t = AVL.avl
+
+(*********************************************************************************************************************
+ * Operations
+ ********************************************************************************************************************)
+
+let make_empty () = AVL.make_empty ()
+
+let singleton a = AVL.make_leaf a
+
+let insert a t = AVL.insert a t
+
+let remove a t = AVL.remove a t
+
+let max t = AVL.find_max t
+
+let min t = AVL.find_min t
+
+let extract_max t = AVL.extract_max t
+
+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
+
+let substract t1 t2 = AVL.substract t1 t2
+
+let diff t1 t2 = 
+    let tclone = clone t1 in
+    substract tclone t2
+
+let update f t = AVL.update f t
+
+let alter f t = AVL.alter f t
+
+end

File src/MSet.mli

+(*
+ * MutableDataStructures
+ *
+ * Copyrights(C) 2013 by Pawel Wieczorek <wieczyk at gmail>
+ *)
+
+
+module Make : functor (M : Set.OrderedType) ->
+    sig
+      type t 
+      val make_empty : unit -> 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 extract_max : t -> M.t
+      val extract_min : t -> M.t
+      val size : t -> int
+      val clone : t -> t
+      val from_list : M.t list -> unit
+      val to_list : t -> M.t list
+      val fold : ('a -> M.t -> 'a) -> 'a -> t -> 'a
+      val substract : t -> t -> unit
+      val diff : t -> t -> unit
+      val update : (M.t -> M.t) -> t -> t
+      val alter : (M.t -> M.t option) -> t -> t
+    end

File src/MutableDataStructures.mlpack

 AVL
-Set
+MSet

File src/Set.ml

-(*
- * MutableDataStructures
- *
- * Copyrights(C) 2013 by Pawel Wieczorek <wieczyk at gmail>
- *)
-
-(*********************************************************************************************************************
- * Types
- ********************************************************************************************************************)
-
-type 'a t = 'a AVL.avl
-
-(*********************************************************************************************************************
- * Operations
- ********************************************************************************************************************)
-
-let make_empty () = AVL.make_empty ()
-
-let singleton a = AVL.make_leaf a
-
-let insert a t = AVL.insert a t
-
-let remove a t = AVL.remove a t
-
-let max t = AVL.find_max t
-
-let min t = AVL.find_min t
-
-let extract_max t = AVL.extract_max t
-
-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
-
-let substract t1 t2 = AVL.substract t1 t2
-
-let diff t1 t2 = 
-    let tclone = clone t1 in
-    substract tclone t2
-
-let update f t = AVL.update f t
-
-let alter f t = AVL.alter f t