From 33d7b8fa4974bad96108c11e5548b354cf10ecb8 Mon Sep 17 00:00:00 2001 From: adam Date: Sun, 9 Sep 2007 00:05:32 -0400 Subject: [PATCH] change naming: use pred/succ rather than parent/child darcs-hash:20070909040532-5007d-c6d328dbf8e4605fd402ef8350fc94434ec4f487.gz --- src/edu/berkeley/sbp/GSS.java | 15 +++++----- src/edu/berkeley/sbp/Node.java | 42 ++++++++++++++-------------- src/edu/berkeley/sbp/Reduction.java | 22 +++++++-------- src/edu/berkeley/sbp/Result.java | 52 +++++++++++++++++------------------ 4 files changed, 65 insertions(+), 66 deletions(-) diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 27eb279..bf58e64 100644 --- 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 --- 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 results = new FastSet(); private HashSet results = new HashSet(); - private HashSet children = new HashSet(); + private HashSet successors = new HashSet(); 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 --- a/src/edu/berkeley/sbp/Reduction.java +++ b/src/edu/berkeley/sbp/Reduction.java @@ -9,22 +9,22 @@ final class Reduction implements Comparable { 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 { 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 --- 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 children = new HashSet(); + private Node pred; + private HashSet successors = new HashSet(); 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); -- 1.7.10.4