projects
/
tatoo.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
* Seal the representation of states
[tatoo.git]
/
src
/
ptset.ml
diff --git
a/src/ptset.ml
b/src/ptset.ml
index
87ca2a5
..
4dbd1a3
100644
(file)
--- a/
src/ptset.ml
+++ b/
src/ptset.ml
@@
-38,7
+38,9
@@
struct
| Branch of int * int * 'a * 'a
module rec Node : Hcons.S with type data = Data.t = HCB(Data)
| 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 =
struct
type t = Node.t set
let equal x y =
@@
-67,13
+69,12
@@
struct
let leaf k = Node.make (Leaf k)
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
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 singleton k = leaf k
@@
-149,7
+150,7
@@
struct
let kid = Uid.to_int (H.uid k) in
let rec ins n = match n.Node.node with
| Empty -> 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
| Branch (p,m,t0,t1) ->
if match_prefix kid p m then
if zero_bit kid m then
@@
-177,7
+178,7
@@
struct
in
rmv t
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 equal a b = a == b
@@
-231,7
+232,7
@@
struct
let union s1 s2 = merge s1 s2
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
let rec inter s1 s2 =
if equal s1 s2
@@
-289,11
+290,17
@@
struct
| Leaf k -> f k
| Branch (_,_,t0,t1) -> iter f t0; iter f t1
| Leaf k -> f k
| Branch (_,_,t0,t1) -> iter f t0; iter f t1
- let rec fold f s accu = match s.Node.node with
+ let rec fold
_left
f s accu = match s.Node.node with
| Empty -> accu
| Leaf k -> f k accu
| Empty -> accu
| Leaf k -> f k accu
- | Branch (_,_,t0,t1) -> fold
f t1 (fold
f t0 accu)
+ | Branch (_,_,t0,t1) -> fold
_left f t1 (fold_left
f t0 accu)
+ let rec fold_right f s accu = match s.Node.node with
+ | Empty -> accu
+ | Leaf k -> f k accu
+ | Branch (_,_,t0,t1) -> fold_right f t0 (fold_right f t1 accu)
+
+ let fold f s accu = fold_left f s accu
let rec for_all p n = match n.Node.node with
| Empty -> true
let rec for_all p n = match n.Node.node with
| Empty -> true
@@
-367,7
+374,7
@@
struct
include Make(Hcons.PosInt)
let print ppf s =
Format.pp_print_string ppf "{ ";
include Make(Hcons.PosInt)
let print ppf s =
Format.pp_print_string ppf "{ ";
- iter (fun i -> Format.fprintf ppf "%i "
i
) s;
+ iter (fun i -> Format.fprintf ppf "%i "
(i :> int)
) s;
Format.pp_print_string ppf "}";
Format.pp_print_flush ppf ()
end
Format.pp_print_string ppf "}";
Format.pp_print_flush ppf ()
end