X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=1d5e05a7206796b83605604a8493b0bb533d7463;hb=61539aaf02d0537fd1df08b5d5bd03189992cf1e;hp=5c0f023558e93dc7ddaf1b1b25f0bb4fd1d24413;hpb=e84029a8b861075d6d0ed5040f919b2e4da4c98f;p=sbp.git

diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java
index 5c0f023..1d5e05a 100644
--- 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;
@@ -56,13 +92,8 @@ final class Node
                 Node child = res.parent();
                 holder[pos] = res.getForest();
                 if (pos>0)  child.reduce(r, pos-1, target, null);
-                else {
-                    Reduction reduction =
-                        new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
-                    target.reductionQueue.add(reduction);
-                }
+                else new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target);
             }
-
         holder[pos] = old;
     }
 
@@ -77,11 +108,12 @@ 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);
 
         for(Object s : state.also)
-            phase.newNode(result, (State)s, fromEmptyReduction);
+            phase.newNode(new Result(null, this, null), (State)s, fromEmptyReduction);
 
         state.invokeReductions(phase().token, this, true, null);
         if (!fromEmptyReduction)
@@ -91,14 +123,14 @@ final class Node
     // GraphViz //////////////////////////////////////////////////////////////////////////////
 
     public GraphViz.Node toGraphViz(GraphViz gv) {
+        if (results.size()==0) return null;
         if (gv.hasNode(this)) return gv.createNode(this);
         GraphViz.Node n = gv.createNode(this);
         n.label = ""+state.toStringx();
         n.shape = "rectangle";
         boolean hasparents = false;
-        //for(Node parent : parents()) { hasparents = true; n.edge(parent, ""); }
-        //for(Forest result : resultMap) n.edge(result, "");
-        n.color = !hasparents ? "blue" : /*state.evil ? "red" :*/ "green";
+        for(Result r : results) n.edge(r, "");
+        n.color = state.doomed ? "red" : "green";
         ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
         return n;
     }