(* *)
(***********************************************************************)
-(*
- Time-stamp: <Last modified on 2013-01-30 19:07:53 CET by Kim Nguyen>
-*)
-
(* Modified by Kim Nguyen *)
(* The Patricia trees are themselves deeply hash-consed. The module
provides a Make (and Weak) functor to build hash-consed patricia
INCLUDE "utils.ml"
-include Sigs.PTSET
+include Ptset_sig
module type HConsBuilder =
- functor (H : Sigs.AUX.HashedType) -> Hcons.S with type data = H.t
+ functor (H : Common_sig.HashedType) -> Hcons.S with type data = H.t
module Builder (HCB : HConsBuilder) (H : Hcons.Abstract) :
S with type elt = H.t =
| Branch of int * int * 'a * 'a
module rec Node : Hcons.S with type data = Data.t = HCB(Data)
- and Data : Sigs.AUX.HashedType with type t = Node.t set =
+ and Data : Common_sig.HashedType with type t = Node.t set =
struct
type t = Node.t set
let equal x y =
| Branch(b1,i1,l1,r1), Branch(b2,i2,l2,r2) ->
b1 == b2 && i1 == i2 && (Node.equal l1 l2) && (Node.equal r1 r2)
- | _ -> false
+ | (Empty|Leaf _|Branch _), _ -> false
let hash = function
| Empty -> 0
let singleton k = leaf k
let is_singleton n =
- match Node.node n with Leaf _ -> true
- | _ -> false
+ match Node.node n with
+ | Leaf _ -> true
+ | Branch _ | Empty -> false
let mem (k:elt) n =
let kid = Uid.to_int (H.uid k) in
| Branch (p1,m1,l1,r1), Branch (p2,m2,l2,r2) ->
if m1 == m2 && p1 == p2 then
intersect l1 l2 || intersect r1 r2
- else if m1 < m2 && match_prefix p2 p1 m1 then
+ else if m1 > m2 && match_prefix p2 p1 m1 then
intersect (if zero_bit p2 m1 then l1 else r1) s2
- else if m1 > m2 && match_prefix p1 p2 m2 then
+ else if m1 < m2 && match_prefix p1 p2 m2 then
intersect s1 (if zero_bit p1 m2 then l2 else r2)
else
false