X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=ptset.ml;fp=ptset.ml;h=e16cc2c2483dceda4281aa6323051a9586d72713;hb=7489c542a7b7357a1c2bbc436d1d77c601833d3b;hp=4b2c84564428ea4f1f8c324ea2aaa85af9b79dd4;hpb=d4342e4bb9c853114de295567cd91ec86bb9e68f;p=SXSI%2Fxpathcomp.git

diff --git a/ptset.ml b/ptset.ml
index 4b2c845..e16cc2c 100644
--- a/ptset.ml
+++ b/ptset.ml
@@ -45,13 +45,7 @@ module Node =
   end
 
 module WH =Weak.Make(Node) 
-(* struct 
-  include Hashtbl.Make(Node)
-    let merge h v =
-      if mem h v then v
-      else (add h v v;v)
-end
-*)
+
 let pool = WH.create 4093
 
 (* Neat trick thanks to Alain Frisch ! *)
@@ -89,6 +83,9 @@ let branch_ne = function
 let zero_bit k m = (k land m) == 0
 
 let singleton k = leaf k
+let is_singleton n = 
+  match n.node with Leaf _ -> true
+    | _ -> false
 
 let rec mem k n = match n.node with
   | Empty -> false
@@ -186,35 +183,38 @@ let rec min_elt n = match n.node with
 
   let compare a b = if a == b then 0 else a.id - b.id
 
+  let h_merge = Hashtbl.create 4097
+  let com_hash x y = (x*y - (x+y)) land max_int
 
   let rec merge s t = 
     if (equal s t) (* This is cheap thanks to hash-consing *)
     then s
     else
-      match s.node,t.node with
-	| Empty, _  -> t
-	| _, Empty  -> s
-	| Leaf k, _ -> add k t
-	| _, Leaf k -> add k s
-	| Branch (p,m,s0,s1), Branch (q,n,t0,t1) ->
-	    if m == n && match_prefix q p m then
-	      branch p  m  (merge s0 t0) (merge s1 t1)
-	    else if m > n && match_prefix q p m then
-	      if zero_bit q m then 
-		branch p m (merge s0 t) s1
-              else 
-		branch p m s0 (merge s1 t)
-	    else if m < n && match_prefix p q n then     
-	      if zero_bit p n then
-		branch q n (merge s t0) t1
-	      else
-		branch q n t0 (merge s t1)
+    match s.node,t.node with
+      | Empty, _  -> t
+      | _, Empty  -> s
+      | Leaf k, _ -> add k t
+      | _, Leaf k -> add k s
+      | Branch (p,m,s0,s1), Branch (q,n,t0,t1) ->
+	  if m == n && match_prefix q p m then
+	    branch p  m  (merge s0 t0) (merge s1 t1)
+	  else if m > n && match_prefix q p m then
+	    if zero_bit q m then 
+	      branch p m (merge s0 t) s1
+            else 
+	      branch p m s0 (merge s1 t)
+	  else if m < n && match_prefix p q n then     
+	    if zero_bit p n then
+	      branch q n (merge s t0) t1
 	    else
-	      (* The prefixes disagree. *)
-	      join p s q t
-	    
-
-
+	      branch q n t0 (merge s t1)
+	  else
+	    (* The prefixes disagree. *)
+	    join p s q t
+	       
+	
+	       
+	       
   let rec subset s1 s2 = (equal s1 s2) ||
     match (s1.node,s2.node) with
       | Empty, _ -> true
@@ -232,8 +232,10 @@ let rec min_elt n = match n.node with
 	  else
 	    false
 
-  let union s t = 
-      merge s t
+
+	      
+
+  let union s1 s2 = merge s1 s2
 	      
   let rec inter s1 s2 = 
     if equal s1 s2