Source

ocamlspot / xset.ml

Diff from to
 
 module type S = sig
   include Set.S
-  val middle : t -> elt option
-  val find : elt -> t -> elt option
+  val unsafe_binary : t -> (t * elt * t) option
+  val unsafe_middle : t -> elt option
+  val unsafe_find : elt -> t -> elt option
 end
 
 module Make(Ord : OrderedType) : S with type elt = Ord.t = struct
   include Set.Make(Ord)
 
-  (* find the middle element in [t] *)
-  let middle t =
-    if is_empty t then None
-    else
-      let found = ref None in
-      try
-	ignore (filter (fun elt -> 
-	  found := Some elt;
-	  raise Exit) t);
-	assert false
-      with
-      | Exit -> !found
+  (* Warning! Unsafe operation!
+     Currently, there is no easy way to get the binary tree structure from a set,
+     though it is very handy for efficient binary search.
+     The following easily breaks when the internal implementation of Set.t is changed. 
+     If the program 
+  *) 
+  type t_internal = Empty | Node of t * elt * t * int
+  let unsafe_internal t = (Obj.magic t : t_internal) 
 
-  (* find the "same" element as [elt] in [t] *)
-  let rec find elt t =
-    match middle t with
-    | None -> None
-    | Some elt' ->
+  let _dummy () =  [Empty ; Node (assert false, assert false, assert false, 0)]
+
+  let unsafe_binary t = match unsafe_internal t with
+    | Empty -> None
+    | Node (left, v, right, _) -> Some (left, v, right)
+
+  let unsafe_middle t = match unsafe_internal t with
+    | Empty -> None
+    | Node (_, v, _, _) -> Some v
+
+  let rec unsafe_find elt t = match unsafe_internal t with
+    | Empty -> None
+    | Node (left, elt', right, _) -> 
 	match Ord.compare elt elt' with 
-	| 0 -> Some elt'
-	| -1 ->
-	    let l, present, _ = split elt' t in
-	    assert present;
-	    find elt l
-	| 1 -> 
-	    let _, present, r = split elt' t in
-	    assert present;
-	    find elt r
-	| _ -> assert false
+	| 0  -> Some elt'
+	| -1 -> unsafe_find elt left
+	| 1  -> unsafe_find elt right
+	| _  -> assert false
 end
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.