checkpoint

[sbp.git] / src / edu / berkeley / sbp / GSS.java

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 1d91f89..87bcf04 100644 (file)
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -10,6 +10,7 @@ import java.lang.reflect.*;
 /** implements Tomita's Graph Structured Stack */
 class GSS {
 
+    public static int count = 0;
     public GSS() { }
 
     private Phase.Node[] reducing_list = null;
@@ -20,12 +21,13 @@ class GSS {
     HashMapBag<Integer,Sequence>       expectedInhibit = new HashMapBag<Integer,Sequence>();
     HashMapBag<Sequence,Phase.Waiting> waiting         = new HashMapBag<Sequence,Phase.Waiting>();
     HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
+    HashMapBag<Integer,Sequence>       lastperformed   = new HashMapBag<Integer,Sequence>();
     
     /** FIXME */
     public  Forest.Ref finalResult;
 
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
-    public class Phase<Tok> implements Invokable<State, Forest, Phase<Tok>.Node>, IntegerMappable {
+    class Phase<Tok> implements Invokable<State, Forest, Phase<Tok>.Node>, IntegerMappable {
 
         public void invoke(State st, Forest result, Node n) {
             good |= next.newNode(n, result, st, false);
@@ -61,11 +63,14 @@ class GSS {
 
         public void reset() throws ParseFailed {
             waiting.clear();
+            lastperformed.clear();
+            lastperformed.addAll(performed);
             performed.clear();
             hash = new IntPairMap<Phase.Node>();
             singularReductions = new IntPairMap<Forest>();
             expectedInhibit.clear();
             expectedInhibit.addAll(inhibited);
+            reset = false;
             good = false;
             closed = false;
             reducing = false;
@@ -99,6 +104,14 @@ class GSS {
             int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
             Sequence owner = reduction==null ? null : reduction.owner();
             if (reduction!=null) {
+                if (owner.hates!=null) {
+                    for (Sequence s : lastperformed.getAll(pos))
+                        if (owner.hates.contains(s))
+                            return;
+                    for (Sequence s : performed.getAll(pos))
+                        if (owner.hates.contains(s))
+                            return;
+                }
                 if (inhibited.contains(pos, owner)) return;
                 if (owner.needs != null)
                     for(Sequence s : owner.needs)
@@ -106,14 +119,16 @@ class GSS {
                             waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
                             return;
                         }
+                /*
                 if ((owner.needed != null && owner.needed.size()>0) ||
                     (owner.hated != null && owner.hated.size()>0) ||
                     (owner.hates != null && owner.hates.size()>0))
                     performed.add(pos, owner);
+                */
             }
+            if (reduction!=null) uninhibit(reduction, parent==null?0:parent.phase().pos);
             if (!owner.lame)
                 newNode(parent, pending, state, fromEmptyReduction);
-            if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos);
             if (reduction != null) {
                 boolean redo = true;
                 while(redo) {
@@ -156,34 +171,32 @@ class GSS {
             return true;
         }
 
-        public void uninhibit(int p, Sequence s) {
+        public void inhibit(int p, Sequence s) {
+            //if (inhibited.contains(p, s)) return;
+            if (performed.contains(p, s)) throw new Reset();
+            /*
             if (s.hated!=null)
                 for(Sequence s2 : s.hated)
-                    inhibited.remove(p, s2);
+                    uninhibit(p, s2);
+            */
+            if (s.needed!=null)
+                for(Sequence s2 : s.needed)
+                    if (performed.contains(p, s2))
+                        throw new Reset();
+            if (performed.contains(p, s)) throw new Reset();
         }
 
-        public void inhibit(Position r, int p) {
-            if (r.owner().hated == null) return;
-            // remember that dead states are still allowed to shift -- just not allowed to reduce
-            boolean reset = false;
-            for(Sequence seq : r.owner().hated) {
-                if (performed.contains(p,seq)) {
-                    uninhibit(p, seq);
-                    //System.out.println("\nresetting due to " + r.owner() + " killing " + seq);
-                    //inhibited.clear();
-                    inhibited.add(p, seq);
-                    //inhibited = new HashMapBag<Integer,Sequence>();
-                    reset = true;
-                    resets++;
-                    throw new Reset();
-                }
-                inhibited.add(p, seq);
-                expectedInhibit.remove(p, seq);
-            }
+        public void uninhibit(Position r, int p) { uninhibit(p, r.owner()); }
+        public void uninhibit(int p, Sequence s) {
+            if (performed.contains(p, s)) return;
+            performed.add(p, s);
+            if (s.hated != null)
+                for(Sequence seq : s.hated)
+                    inhibit(p, seq);
         }
         
         /** perform all reduction operations */
-        public void reduce() throws ParseFailed{
+        public void reduce() throws ParseFailed {
             try {
                 reducing = true;
                 if (reducing_list==null || reducing_list.length < hash.size())
@@ -200,17 +213,30 @@ class GSS {
                     reducing_list[i] = null;
                     n.performReductions();
                 }
+                /*
                 if (expectedInhibit.size() > 0) {
+                    System.out.println("\n!!!!");
+                    for(int i : expectedInhibit)
+                        for(Sequence es : expectedInhibit.getAll(i))
+                            System.out.println("   " + i + ": " + es);
+                    System.out.println("");
                     inhibited.removeAll(expectedInhibit);
-                    System.out.println("\n!!!!\n");
                     throw new Reset();
                 }
+                */
+                if (reset) {
+                    reset = false;
+                    resets++;
+                    throw new Reset();
+                }                
             } catch (Reset r) {
                 reset();
                 reduce();
             }
+            count = 0;
         }
 
+        private boolean reset = false;
         class Reset extends RuntimeException { }
 
         /** perform all shift operations, adding promoted nodes to <tt>next</tt> */
@@ -245,7 +271,7 @@ class GSS {
         }
 
 
-        public class Waiting {
+        class Waiting {
             Node parent;
             Forest pending;
             State state;
@@ -268,7 +294,7 @@ class GSS {
         // Node /////////////////////////////////////////////////////////////////////////////////
 
         /** a node in the GSS */
-        public final class Node extends FastSet<Node> implements Invokable<Position, Node, Node>, IntegerMappable {
+        final class Node extends FastSet<Node> implements Invokable<Position, Node, Node>, IntegerMappable {
 
             private Forest.Ref holder = null;
             private boolean allqueued = false;