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 ! *)
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
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
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