| Branch of int * int * 'a * 'a
module rec Node : Hcons.S with type data = Data.t = HCB(Data)
- and Data : Common_sig.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 =
let leaf k = Node.make (Leaf k)
- (* To enforce the invariant that a branch contains two non empty
- sub-trees *)
+ (* To enforce the invariant that a branch contains two non empty sub-trees *)
let branch_ne p m t0 t1 =
if (is_empty t0) then t1
else if is_empty t1 then t0 else branch p m t0 t1
- (******** from here on, only use the smart constructors ************)
+ (******** from here on, only use the smart constructors ************)
let singleton k = leaf k
let kid = Uid.to_int (H.uid k) in
let rec ins n = match n.Node.node with
| Empty -> leaf k
- | Leaf j -> if j == k then n else join kid (leaf k) (Uid.to_int (H.uid j)) n
+ | Leaf j -> if j == k then n else join kid (leaf k) (Uid.to_int (H.uid j)) n
| Branch (p,m,t0,t1) ->
if match_prefix kid p m then
if zero_bit kid m then
in
rmv t
- (* should run in O(1) thanks to hash consing *)
+ (* runs in O(1) thanks to hash consing *)
let equal a b = a == b
let union s1 s2 = merge s1 s2
- (* Todo replace with e Memo Module *)
+ (* Todo replace with e Memo Module *)
let rec inter s1 s2 =
if equal s1 s2