X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=6aecefa48260ef50cfeb0f4dbaef01c094b2a389;hp=4feac2bb99b7cf9feac53c98664108645cccffde;hb=c1a7dcf0dd5b839d82215263d0f57470e905a73d;hpb=36d88939587827b1cea9ab842ec70bd168a08be1

diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java
index 4feac2b..6aecefa 100644
--- a/src/edu/berkeley/sbp/Node.java
+++ b/src/edu/berkeley/sbp/Node.java
@@ -15,6 +15,34 @@ abstract class Node<OtherNode extends Node>
                GraphViz.ToGraphViz,
                Iterable<OtherNode> {
 
+    private final GSS.Phase phase;
+    private final GSS.Phase predecessorPhase;
+    protected boolean destroyed        = false;
+    private int numNonDoomedSuccessors = 0;
+    private boolean hasPathToRoot      = false;
+
+    private       FastSet<OtherNode> predecessors = new FastSet<OtherNode>();
+    private       FastSet<OtherNode> successors = new FastSet<OtherNode>();
+    //protected       HashSet<OtherNode> predecessors = new HashSet<OtherNode>();
+    //protected       HashSet<OtherNode> successors = new HashSet<OtherNode>();
+
+    public GSS.Phase phase() { return phase; }
+    public GSS.Phase predecessorPhase() { return predecessorPhase; }
+    public boolean hasPredecessors() { return predecessors.size() > 0; }
+    public boolean hasSuccessors() { return successors.size() > 0; }
+    public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; }
+
+    public boolean hasPathToRoot() { return hasPathToRoot; }
+    public void updatePathsToRootAfterRemoval() {
+        if (!hasPathToRoot()) return;
+        for(OtherNode on : predecessors)
+            if (on.hasPathToRoot())
+                return;
+        hasPathToRoot = false;
+        for(OtherNode on : successors)
+            on.updatePathsToRootAfterRemoval();
+    }
+
     /**
      *  Every Node has a phase; StateNodes belong to the phase in
      *  which they were shifted, ResultNodes belong to the phase of
@@ -26,21 +54,13 @@ abstract class Node<OtherNode extends Node>
         this.predecessorPhase = predecessorPhase;
     }
 
-    private final GSS.Phase phase;
-    private final GSS.Phase predecessorPhase;
-    public GSS.Phase phase() { return phase; }
-    public GSS.Phase predecessorPhase() { return predecessorPhase; }
-    protected boolean destroyed = false;
-    private int numNonDoomedSuccessors = 0;
-    public boolean hasSuccessors() { return successors.size() > 0; }
-    public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; }
-
     /** only to be invoked (or overridden as public) by the subclass */
     protected void addPred(OtherNode pred) {
         if (predecessors.contains(pred)) throw new Error("a predecessor was added twice");
         if (pred.phase() != predecessorPhase()) throw new Error();
         predecessors.add(pred);
         pred.addSucc(this);
+        if (pred.hasPathToRoot()) hasPathToRoot = true;
     }
     public void addSucc(OtherNode succ) {
         if (successors.contains(succ)) throw new Error("a predecessor was added twice");
@@ -48,46 +68,41 @@ abstract class Node<OtherNode extends Node>
         numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1;
         if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error();
     }
-    public void removeSucc(OtherNode succ) {
-        if (!successors.contains(succ)) return;
-        successors.remove(succ);
-        numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1;
-        check();
-    }
 
     protected void destroy() {
         destroyed = true;
-        while(predecessors.size() > 0)
-            for(OtherNode pred : predecessors) {
-                removePred(pred);
-                pred.removeSucc(this);
-                break;
-            }
+        while(predecessors.size() > 0) {
+            OtherNode pred = predecessors.first();
+            removePred(pred);
+            pred.removeSucc(this);
+        }
         predecessors = null;
-        while(successors.size() > 0)
-            for(OtherNode succ : successors) {
-                removeSucc(succ);
-                succ.removePred(this);
-                break;
-            }
+        while(successors.size() > 0) {
+            OtherNode succ = successors.first();
+            removeSucc(succ);
+            succ.removePred(this);
+        }
         successors = null;
     }
-
-    public abstract boolean isDoomedState();
-    protected abstract void check();
-
+    public void removeSucc(OtherNode succ) {
+        if (!successors.contains(succ)) return;
+        successors.remove(succ);
+        numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1;
+        check();
+    }
     public void removePred(OtherNode pred) {
         if (!predecessors.contains(pred)) return;
         predecessors.remove(pred);
+        updatePathsToRootAfterRemoval();
         check();
     }
 
-    protected       FastSet<OtherNode> predecessors = new FastSet<OtherNode>();
-    protected       FastSet<OtherNode> successors = new FastSet<OtherNode>();
-    //private       HashSet<OtherNode> predecessors = new HashSet<OtherNode>();
-    //private       HashSet<OtherNode> successors = new HashSet<OtherNode>();
+
+    public abstract boolean isDoomedState();
+    protected abstract void check();
 
     public Iterator<OtherNode> iterator() { return predecessors.iterator(); }
+    public Iterable<OtherNode> successors() { return successors; }
 
     public boolean noSuccessors() { return successors.size()==0; }
     public boolean predecessorsContains(OtherNode n) {