Staturate the set of state of the current node to avoid some traversal.

[tatoo.git] / src / auto / eval.ml

diff --git a/src/auto/eval.ml b/src/auto/eval.ml
index 5c346d0..19bcf6f 100644 (file)
--- a/src/auto/eval.ml
+++ b/src/auto/eval.ml
@@ -14,7 +14,7 @@
 (***********************************************************************)
 
 (*
-  Time-stamp: <Last modified on 2013-03-13 18:27:13 CET by Kim Nguyen>
+  Time-stamp: <Last modified on 2013-03-13 19:02:13 CET by Kim Nguyen>
 *)
 
 INCLUDE "utils.ml"
@@ -27,12 +27,10 @@ module Make (T : Tree.Sig.S) :
   end
  = struct
 
-  type cache = (int, StateSet.t) Hashtbl.t
-  let get c t n =
-    try Hashtbl.find c (T.preorder t n)
-    with Not_found -> StateSet.empty
+  type cache = StateSet.t Cache.N1.t
+  let get c t n = Cache.N1.find c (T.preorder t n)
 
-  let set c t n v = Hashtbl.replace c (T.preorder t n) v
+  let set c t n v = Cache.N1.add c (T.preorder t n) v
 
   module Info = struct
     type t = { is_left : bool;
@@ -79,27 +77,34 @@ module Make (T : Tree.Sig.S) :
     loop phi
 
   let eval_trans cache ltrs node_info fcs nss ps ss =
-    let i = (ltrs.Ata.TransList.id :> int)
-    and j = (node_info.NodeInfo.id :> int)
+    let j = (node_info.NodeInfo.id :> int)
     and k = (fcs.StateSet.id :> int)
     and l = (nss.StateSet.id :> int)
-    and m = (ps.StateSet.id :> int)
+    and m = (ps.StateSet.id :> int) in
+  let rec loop ltrs ss =
+    let i = (ltrs.Ata.TransList.id :> int)
     and n = (ss.StateSet.id :> int) in
-    let res = Cache.N6.find cache i j k l m n in
-    if res == Cache.N6.dummy cache then
-      let res =
-        Ata.TransList.fold (fun trs (acct, accs) ->
-          let q, _, phi = Ata.Transition.node trs in
-          if StateSet.mem q accs then (acct, accs) else
-            if eval_form phi node_info fcs nss ps accs then
-              (acct, StateSet.add q accs)
-            else
-              (Ata.TransList.cons trs acct, accs)
-        ) ltrs (Ata.TransList.nil, ss) 
-      in
-      Cache.N6.add cache i j k l m n res; res
-    else
-      res
+    let (new_ltrs, new_ss) as res =
+      let res = Cache.N6.find cache i j k l m n in
+      if res == Cache.N6.dummy cache then
+        let res =
+          Ata.TransList.fold (fun trs (acct, accs) ->
+            let q, _, phi = Ata.Transition.node trs in
+            if StateSet.mem q accs then (acct, accs) else
+              if eval_form phi node_info fcs nss ps accs then
+                (acct, StateSet.add q accs)
+              else
+                (Ata.TransList.cons trs acct, accs)
+          ) ltrs (Ata.TransList.nil, ss)
+        in
+        Cache.N6.add cache i j k l m n res; res
+      else
+        res
+    in
+    if new_ss == ss then res else
+      loop new_ltrs new_ss
+  in
+  loop ltrs ss
 
   let top_down_run auto tree node cache _i =
     let redo = ref false in
@@ -176,7 +181,7 @@ module Make (T : Tree.Sig.S) :
     loop node []
 
   let eval auto tree node =
-    let cache = Hashtbl.create 511 in
+    let cache = Cache.N1.create (T.size tree) StateSet.empty in
     let redo = ref true in
     let iter = ref 0 in
     while !redo do