X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=blobdiff_plain;f=src%2Fptset.ml;h=779d24f1ee2d975040cf5592116558ff026dabc2;hp=87ca2a5e81cfc12d18484fcfdd92a9310c41498e;hb=35abea737ead2d4fd121d0cb8bdbda38cfcaa8d3;hpb=cd25399e8ac95c48630a18000e797062db66be05

diff --git a/src/ptset.ml b/src/ptset.ml
index 87ca2a5..779d24f 100644
--- 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)
-                            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 =
@@ -67,13 +69,12 @@ struct
 
   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
 
@@ -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
-    | 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
@@ -177,7 +178,7 @@ struct
     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
 
@@ -231,7 +232,7 @@ struct
 
 
   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
@@ -289,11 +290,17 @@ struct
   | 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
-  | 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