add killing of doomed nodes via Node.check()/Result.check() methods

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

diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java
index b360071..1d5e05a 100644 (file)
--- a/src/edu/berkeley/sbp/Node.java
+++ b/src/edu/berkeley/sbp/Node.java
@@ -26,11 +26,43 @@ final class Node
     public boolean merge(Result r) {
         if (results.contains(r)) return true;
         results.add(r);
+        r.addChild(this);
         if (fromEmptyReduction) return false;
         state.invokeReductions(phase().getToken(), this, false, r);
         return false;
     }
 
+    private boolean destroyed = false;
+    public boolean check() {
+        boolean dead = true;
+        // - all nodes must have a parent
+        // - non-doomed nodes must either:
+        //      - be on the frontier or
+        //      - have a non-doomed node closer to the frontier than themself
+
+        if (phase.isFrontier()) dead = false;
+        for(Result r : children)
+            if (state.doomed) { if (r.usedByAnyNode()) dead = false; }
+            else              { if (r.usedByNonDoomedNode()) dead = false; }
+        dead |= results.size()==0;
+        if (!dead || destroyed) return dead;
+        destroyed = true;
+        while(children.size()>0)
+            for(Result r : children) {
+                children.remove(r);
+                r.destroy();
+                break;
+            }
+        while(results.size()>0)
+            for(Result r : results) {
+                results.remove(r);
+                r.removeChild(this);
+                r.check();
+                break;
+            }
+        return dead;
+    }
+
     //////////////////////////////////////////////////////////////////////
 
     private static int node_idx = 0;
@@ -41,6 +73,10 @@ final class Node
     private final boolean fromEmptyReduction;
     //private       FastSet<Result> results = new FastSet<Result>();
     private       HashSet<Result> results = new HashSet<Result>();
+    private       HashSet<Result> children = new HashSet<Result>();
+    public void removeChild(Result child) { children.remove(child); }
+    public void removeResult(Result result) { results.remove(result); }
+    public void addChild(Result child) { children.add(child); }
 
     public final void invoke(Position r, Boolean emptyProductions, Result only) {
         if (emptyProductions != (r.pos==0)) return;
@@ -72,6 +108,7 @@ final class Node
         this.state = state;
         this.fromEmptyReduction = fromEmptyReduction;
         results.add(result);
+        result.addChild(this);
         if (phase.hash.get(state, result.phase()) != null) throw new Error("severe problem!");
         phase.hash.put(state, result.phase(), this);