From d96df56ee69e62c4d4d6dfe3786ea4853e5120eb Mon Sep 17 00:00:00 2001 From: adam Date: Mon, 3 Mar 2008 23:02:01 -0500 Subject: [PATCH] refactoring of Node class and more stringent checks darcs-hash:20080304040201-5007d-923f135031ca007d8aa7f46281dd4fea2e36f10e.gz --- src/edu/berkeley/sbp/Node.java | 69 +++++++++++++++++++++++++++++- src/edu/berkeley/sbp/ResultNode.java | 77 ++++++---------------------------- src/edu/berkeley/sbp/StateNode.java | 69 ++++++++---------------------- 3 files changed, 97 insertions(+), 118 deletions(-) diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 1168c78..4feac2b 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -10,11 +10,78 @@ import java.io.*; import java.util.*; import java.lang.reflect.*; -class Node +abstract class Node implements IntegerMappable, GraphViz.ToGraphViz, Iterable { + /** + * Every Node has a phase; StateNodes belong to the phase in + * which they were shifted, ResultNodes belong to the phase of + * their predecessors. All of the predecessors of a given node + * must belong to the same phase + */ + public Node(GSS.Phase phase, GSS.Phase predecessorPhase) { + this.phase = phase; + 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); + } + public void addSucc(OtherNode succ) { + if (successors.contains(succ)) throw new Error("a predecessor was added twice"); + successors.add(succ); + 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; + } + predecessors = null; + while(successors.size() > 0) + for(OtherNode succ : successors) { + removeSucc(succ); + succ.removePred(this); + break; + } + successors = null; + } + + public abstract boolean isDoomedState(); + protected abstract void check(); + + public void removePred(OtherNode pred) { + if (!predecessors.contains(pred)) return; + predecessors.remove(pred); + check(); + } + protected FastSet predecessors = new FastSet(); protected FastSet successors = new FastSet(); //private HashSet predecessors = new HashSet(); diff --git a/src/edu/berkeley/sbp/ResultNode.java b/src/edu/berkeley/sbp/ResultNode.java index e22bd45..579a868 100644 --- a/src/edu/berkeley/sbp/ResultNode.java +++ b/src/edu/berkeley/sbp/ResultNode.java @@ -10,90 +10,37 @@ final class ResultNode extends Node { private Forest.Many f = new Forest.Many(); - private boolean destroyed = false; - private boolean primordeal; - private int usedByNonDoomedNode = 0; private Pos reduction; - private GSS.Phase predPhase; + public void merge(Forest newf) { this.f.merge(newf); } public Pos reduction() { return reduction; } - public void merge(Forest newf) { - this.f.merge(newf); - /* - if (predecessors.contains(pred)) return; - addPred(pred); - if (fromEmptyReduction) return; - n.state().invokeReductions(n.phase().getToken(), n, this); - */ - } - - public GSS.Phase phase() { return predPhase; } + public boolean isDoomedState() { /* this is irrelevant */ return false; } public Forest getForest() { return f; } - public void addSucc(StateNode succ) { - if (successors.contains(succ)) return; - successors.add(succ); - usedByNonDoomedNode += succ.state().doomed ? 0 : 1; - if (predecessors.size() > 1) throw new Error(); - } - public void removeSucc(StateNode succ) { - if (!successors.contains(succ)) return; - successors.remove(succ); - usedByNonDoomedNode -= succ.state().doomed ? 0 : 1; - check(); - } - - public boolean usedByAnyNode() { return successors.size() > 0; } - public boolean usedByNonDoomedNode() { return usedByNonDoomedNode > 0; } - - public String toString() { return super.toString()+"->"+predPhase; } + public String toString() { return super.toString()+"->"+phase(); } public void check() { + if (destroyed) return; if (successors.size()==0) destroy(); else if (predecessors.size()==0) destroy(); } - public void destroy() { + protected void destroy() { if (destroyed) return; - if (primordeal) return; // never destroy the "primordeal" result - destroyed = true; - while(predecessors.size() > 0) - for(StateNode pred : predecessors) { - removePred(pred); - pred.removeSucc(this); - break; - } - predecessors = null; - while(successors.size() > 0) - for(StateNode succ : successors) { - removeSucc(succ); - succ.removePred(this); - break; - } - successors = null; - } - - public void removePred(StateNode pred) { - if (!predecessors.contains(pred)) return; - predecessors.remove(pred); - check(); + if (predecessorPhase()==null) return; // never destroy the "primordeal" result + super.destroy(); } public void addPred(StateNode pred) { - if (predPhase==null) predPhase = pred.phase(); - if (predPhase != pred.phase()) throw new Error(); - predecessors.add(pred); - pred.addSucc(this); + super.addPred(pred); + // results have only one predecessor if (predecessors.size() > 1) throw new Error(); } - public ResultNode() { - this(null, null, null); - this.primordeal = true; - } + public ResultNode() { this(null, null, null); } public ResultNode(Forest f, Pos reduction, StateNode pred) { + super(pred==null ? null : pred.phase(), + pred==null ? null : pred.phase()); this.f.merge(f); this.reduction = reduction; if (pred != null) addPred(pred); } - - } \ No newline at end of file diff --git a/src/edu/berkeley/sbp/StateNode.java b/src/edu/berkeley/sbp/StateNode.java index bb461cb..af1a3e9 100644 --- a/src/edu/berkeley/sbp/StateNode.java +++ b/src/edu/berkeley/sbp/StateNode.java @@ -15,12 +15,13 @@ final class StateNode extends Node implements Invokable { + private final Parser.Table.State state; + private boolean fromEmptyReduction; + /** which GSS.Phase this StateNode belongs to */ - public GSS.Phase phase() { return phase; } public Iterator iterator() { return predecessors.iterator(); } public Parser.Table.State state() { return state; } - - boolean destroyed = false; + public boolean isDoomedState() { return state.doomed; } public void check() { if (destroyed) return; @@ -29,38 +30,17 @@ final class StateNode // - 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; + if (phase().isFrontier()) dead = false; else for(ResultNode r : successors) - if (state.doomed) { if (r.usedByAnyNode()) { dead = false; break; } } - else { if (r.usedByNonDoomedNode()) { dead = false; break; } } + if (state.doomed) { if (r.hasSuccessors()) { dead = false; break; } } + else { if (r.hasNonDoomedSuccessors()) { dead = false; break; } } dead |= predecessors.size()==0; if (!dead) return; - destroyed = true; if (phase() != null && phase().hash != null) - phase().hash.remove(state, predPhase); - while(successors.size()>0) - for(ResultNode r : successors) { - successors.remove(r); - r.removePred(this); - break; - } - while(predecessors.size()>0) - for(ResultNode r : predecessors) { - predecessors.remove(r); - r.removeSucc(this); - break; - } - predecessors = null; - successors = null; + phase().hash.remove(state, predecessorPhase()); + destroy(); } - ////////////////////////////////////////////////////////////////////// - - private final GSS.Phase phase; - private final GSS.Phase predPhase; - private final Parser.Table.State state; - private boolean fromEmptyReduction; - public final void invoke(Pos r, ResultNode only, Object o) { boolean emptyProductions = only==null; if (emptyProductions != (r.numPops()==0)) return; @@ -94,43 +74,28 @@ final class StateNode this(phase, new ResultNode(f, reduction, pred), state, fromEmptyReduction); } StateNode(GSS.Phase phase, ResultNode pred, State state, boolean fromEmptyReduction) { - this.phase = phase; + super(phase, pred.phase()); this.state = state; this.fromEmptyReduction = fromEmptyReduction; if (phase.hash.get(state, pred.phase()) != null) throw new Error("severe problem!"); - this.predPhase = pred.phase(); phase.hash.put(state, pred.phase(), this); - - predecessors.add(pred); - pred.addSucc(this); - if (!fromEmptyReduction) - state.invokeReductions(phase().getToken(), this, pred); - + addPred(pred); state.invokeEpsilonReductions(phase().token, this); } // Add/Remove Successors/Predecessors ////////////////////////////////////////////////////////////////////////////// - public void removeSucc(ResultNode succ) { - successors.remove(succ); - check(); - } - public void removePred(ResultNode result) { - predecessors.remove(result); - check(); - } - public void addSucc(ResultNode succ) { - successors.add(succ); - } public void addPred(Forest f, Pos reduction, StateNode pred) { for(ResultNode r : predecessors) if (r.predecessorsContains(pred)) { r.merge(f); return; } - ResultNode result = new ResultNode(f, reduction, pred); - predecessors.add(result); - result.addSucc(this); - if (!this.fromEmptyReduction) state.invokeReductions(phase().getToken(), this, result); + addPred(new ResultNode(f, reduction, pred)); + } + protected void addPred(ResultNode result) { + super.addPred(result); + if (!this.fromEmptyReduction) + state.invokeReductions(phase().getToken(), this, result); } } -- 1.7.10.4