change naming: use pred/succ rather than parent/child

darcs-hash:20070909040532-5007d-c6d328dbf8e4605fd402ef8350fc94434ec4f487.gz

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 27eb279..bf58e64 100644 (file)
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -77,15 +77,15 @@ class GSS {
             while(!reductionQueue.isEmpty()) {
                 Reduction r = reductionQueue.poll();
                 //System.out.println("- " + r);
-                if (r.parentPhase() != null)
-                    if (r.parentPhase().pos > minPhasePos)
+                if (r.predPhase() != null)
+                    if (r.predPhase().pos > minPhasePos)
                         throw new Error();
                 r.perform();
-                if (r.parentPhase() != null) {
-                    if (r.parentPhase().pos < minPhasePos) {
-                        minPhasePos = r.parentPhase().pos;
+                if (r.predPhase() != null) {
+                    if (r.predPhase().pos < minPhasePos) {
+                        minPhasePos = r.predPhase().pos;
                         best = r;
-                    } else if (r.parentPhase().pos == minPhasePos) {
+                    } else if (r.predPhase().pos == minPhasePos) {
                         /*
                         if (best != null && Parser.mastercache.comparePositions(r.reduction(), best.reduction()) < 0)
                             throw new Error("\n"+r+"\n"+best+"\n"+
@@ -130,8 +130,7 @@ class GSS {
                         finalResult.merge(r.getForest());
                 }
                 if (token == null) continue;
-                Result result = new Result(f, null, null);
-                result.addParent(n);
+                Result result = new Result(f, n, null);
                 n.state().invokeShifts(token, this, result);
             }
             numNewNodes = next==null ? 0 : next.hash.size();

diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java
index 100f89f..ccc2516 100644 (file)
--- a/src/edu/berkeley/sbp/Node.java
+++ b/src/edu/berkeley/sbp/Node.java
@@ -29,31 +29,31 @@ final class Node
     public void check() {
         if (destroyed) return;
         boolean dead = true;
-        // - all nodes must have a parent
+        // - all nodes must have a predecessor
         // - 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;
-        else for(Result r : children)
+        else for(Result r : successors)
                  if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } }
                  else              { if (r.usedByNonDoomedNode()) { dead = false; break; } }
         dead |= results.size()==0;
         if (!dead) return;
         destroyed = true;
-        while(children.size()>0)
-            for(Result r : children) {
-                children.remove(r);
+        while(successors.size()>0)
+            for(Result r : successors) {
+                successors.remove(r);
                 r.destroy();
                 break;
             }
         while(results.size()>0)
             for(Result r : results) {
                 results.remove(r);
-                r.removeChild(this);
+                r.removeSucc(this);
                 break;
             }
         results = null;
-        children = null;
+        successors = null;
     }
 
     //////////////////////////////////////////////////////////////////////
@@ -66,7 +66,7 @@ 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>();
+    private       HashSet<Result> successors = new HashSet<Result>();
 
     public final void invoke(Pos r, Result only) {
         boolean emptyProductions = only==null;
@@ -84,12 +84,12 @@ final class Node
         if (results==null) return;   // FIXME: this should not happen
         for(Result res : results)
             if (only == null || res == only) {
-                Node child = res.parent();
+                Node pred = res.pred();
                 holder[pos] = res.getForest();
-                if (pos>0)  child.reduce(r, pos-1, target, null);
+                if (pos>0)  pred.reduce(r, pos-1, target, null);
                 else {
-                    Input.Region region = child.phase().getLocation().createRegion(target.getLocation());
-                    new Reduction(child, r, r.rewrite(region), target);
+                    Input.Region region = pred.phase().getLocation().createRegion(target.getLocation());
+                    new Reduction(pred, r, r.rewrite(region), target);
                 }
             }
         holder[pos] = old;
@@ -105,11 +105,11 @@ final class Node
         state.invokeEpsilonReductions(phase().token, this);
     }
 
-    // Add/Remove Children/Results //////////////////////////////////////////////////////////////////////////////
+    // Add/Remove Successors/Results //////////////////////////////////////////////////////////////////////////////
 
-    public void removeChild(Result child)   {
-        if (children==null) return;
-        children.remove(child);
+    public void removeSucc(Result succ)   {
+        if (successors==null) return;
+        successors.remove(succ);
         check();
     }
     public void removeResult(Result result) {
@@ -117,14 +117,14 @@ final class Node
         results.remove(result);
         check();
     }
-    public void addChild(Result child)      {
-        if (children==null) return;   // FIXME: this should not happen
-        children.add(child);
+    public void addSucc(Result succ)      {
+        if (successors==null) return;   // FIXME: this should not happen
+        successors.add(succ);
     }
     public void addResult(Result r) {
         if (results.contains(r)) return;
         results.add(r);
-        r.addChild(this);
+        r.addSucc(this);
         if (!fromEmptyReduction) state.invokeReductions(phase().getToken(), this, r);
     }
 
@@ -136,7 +136,7 @@ final class Node
         GraphViz.Node n = gv.createNode(this);
         n.label = "state["+state.toInt()+"]";
         n.shape = "rectangle";
-        boolean hasparents = false;
+        boolean haspreds = false;
         for(Result r : results) n.edge(r, "");
         n.color = state.doomed ? "red" : "green";
         ((GraphViz.Group)phase().toGraphViz(gv)).add(n);

diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java
index cdf681d..5eb3f63 100644 (file)
--- a/src/edu/berkeley/sbp/Reduction.java
+++ b/src/edu/berkeley/sbp/Reduction.java
@@ -9,22 +9,22 @@ final class Reduction implements Comparable<Reduction> {
     private Pos reduction;
     private GSS.Phase phase;
     private Forest forest;
-    private Node parent;
+    private Node pred;
     
-    public Reduction(Node parent, Pos reduction, Forest forest, GSS.Phase target) {
+    public Reduction(Node pred, Pos reduction, Forest forest, GSS.Phase target) {
         this.reduction = reduction;
         this.forest = forest;
         this.phase = target;
-        this.parent = parent;
+        this.pred = pred;
         target.addReduction(this);
     }
 
     public int compareTo(Reduction r) {
-        if (parent.phase()!=null || r.parent.phase()!=null) {
-            if (parent.phase()==null) return 1;
-            if (r.parent.phase()==null) return -1;
-            if (parent.phase().pos < r.parent.phase().pos) return 1;
-            if (parent.phase().pos > r.parent.phase().pos) return -1;
+        if (pred.phase()!=null || r.pred.phase()!=null) {
+            if (pred.phase()==null) return 1;
+            if (r.pred.phase()==null) return -1;
+            if (pred.phase().pos < r.pred.phase().pos) return 1;
+            if (pred.phase().pos > r.pred.phase().pos) return -1;
         }
         /*
         int master = Parser.mastercache.comparePositions(reduction(), r.reduction());
@@ -40,9 +40,9 @@ final class Reduction implements Comparable<Reduction> {
         return 1;
     }
 
-    public void perform() { new Result(forest, parent, reduction, phase); }
-    public GSS.Phase parentPhase() { return parent.phase(); }
+    public void perform() { new Result(forest, pred, reduction, phase); }
+    public GSS.Phase predPhase() { return pred.phase(); }
     public Pos reduction() { return reduction; }
     public GSS.Phase targetPhase() { return phase; }
-    public String toString() { return (parent.phase()==null ? 0 : parent.phase().pos) + ":"+reduction; }
+    public String toString() { return (pred.phase()==null ? 0 : pred.phase().pos) + ":"+reduction; }
 }

diff --git a/src/edu/berkeley/sbp/Result.java b/src/edu/berkeley/sbp/Result.java
index 6054fa1..efaad4c 100644 (file)
--- a/src/edu/berkeley/sbp/Result.java
+++ b/src/edu/berkeley/sbp/Result.java
@@ -9,53 +9,53 @@ import java.util.*;
 final class Result implements GraphViz.ToGraphViz {
 
     private Forest f;
-    private Node parent;
-    private HashSet<Node> children = new HashSet<Node>();
+    private Node pred;
+    private HashSet<Node> successors = new HashSet<Node>();
     private boolean destroyed = false;
     private int usedByNonDoomedNode = 0;
 
-    public GSS.Phase phase() { return parent==null ? null : parent.phase(); }
+    public GSS.Phase phase() { return pred==null ? null : pred.phase(); }
     public Forest getForest() { return f; }
-    public Node parent() { return parent; }
-    public void addChild(Node child) {
-        children.add(child);
-        usedByNonDoomedNode += child.state().doomed ? 0 : 1;
+    public Node pred() { return pred; }
+    public void addSucc(Node succ) {
+        successors.add(succ);
+        usedByNonDoomedNode += succ.state().doomed ? 0 : 1;
     }
-    public void removeChild(Node child) {
-        if (!children.contains(child)) return;
-        children.remove(child);
-        usedByNonDoomedNode -= child.state().doomed ? 0 : 1;
+    public void removeSucc(Node succ) {
+        if (!successors.contains(succ)) return;
+        successors.remove(succ);
+        usedByNonDoomedNode -= succ.state().doomed ? 0 : 1;
         check();
     }
 
-    public boolean usedByAnyNode() { return children.size() > 0; }
+    public boolean usedByAnyNode() { return successors.size() > 0; }
     public boolean usedByNonDoomedNode() { return usedByNonDoomedNode > 0; }
 
-    public String toString() { return super.toString()+"->"+parent(); }
+    public String toString() { return super.toString()+"->"+pred(); }
 
-    public void check() { if (children.size()==0) destroy(); }
+    public void check() { if (successors.size()==0) destroy(); }
     public void destroy() {
         if (destroyed) return;
-        if (parent==null) return;  // never destroy the "primordeal" result
+        if (pred==null) return;  // never destroy the "primordeal" result
         destroyed = true;
-        parent.removeChild(this);
-        while(children.size() > 0)
-            for(Node n : children) {
-                removeChild(n);
+        pred.removeSucc(this);
+        while(successors.size() > 0)
+            for(Node n : successors) {
+                removeSucc(n);
                 n.removeResult(this);
                 break;
             }
     }
 
-    public Result(Forest f, Node parent, Pos reduction) {
-        this(f, parent, reduction, null);
+    public Result(Forest f, Node pred, Pos reduction) {
+        this(f, pred, reduction, null);
     }
-    public Result(Forest f, Node parent, Pos reduction, GSS.Phase target) {
+    public Result(Forest f, Node pred, Pos reduction, GSS.Phase target) {
         this.f = f;
-        this.parent = parent;
-        if (parent != null) parent.addChild(this);
+        this.pred = pred;
+        if (pred != null) pred.addSucc(this);
         if (reduction == null) return;
-        Parser.Table.State state0 = (Parser.Table.State)parent.state().gotoSetNonTerminals.get(reduction);
+        Parser.Table.State state0 = (Parser.Table.State)pred.state().gotoSetNonTerminals.get(reduction);
         target.newNodeFromReduction(this, state0, reduction);
     }
 
@@ -66,7 +66,7 @@ final class Result implements GraphViz.ToGraphViz {
         GraphViz.Node n = gv.createNode(this);
         n.label = ""+f;
         n.shape = "rectangle";
-        if (parent()!=null) n.edge(parent, "");
+        if (pred()!=null) n.edge(pred, "");
         n.color = "blue";
         if (phase() != null)
             ((GraphViz.Group)phase().toGraphViz(gv)).add(n);