X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=6aecefa48260ef50cfeb0f4dbaef01c094b2a389;hp=871086302859d6f4627b4d18d4afb8771b9ece68;hb=HEAD;hpb=4850d43495402e368e495707388e157a9cef9484 diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 8710863..6aecefa 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -1,103 +1,142 @@ -// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license +// Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license package edu.berkeley.sbp; import edu.berkeley.sbp.*; import edu.berkeley.sbp.util.*; import edu.berkeley.sbp.Parser.Table.*; -import edu.berkeley.sbp.Sequence.Position; +import edu.berkeley.sbp.Sequence.Pos; +import edu.berkeley.sbp.Sequence.Pos; import java.io.*; import java.util.*; import java.lang.reflect.*; -/** a node in the GSS */ -final class Node - implements Invokable, - IntegerMappable, +abstract class Node + implements IntegerMappable, GraphViz.ToGraphViz, - Iterable { + Iterable { - /** which GSS.Phase this Node belongs to */ - public GSS.Phase phase() { return phase; } - public Iterator iterator() { return results.iterator(); } - public Parser.Table.State state() { return state; } - - public int toInt() { return idx; } - - public boolean merge(Result r) { - if (results.contains(r)) return true; - results.add(r); - if (fromEmptyReduction) return false; - state.invokeReductions(phase().getToken(), this, false, r); - return false; + private final GSS.Phase phase; + private final GSS.Phase predecessorPhase; + protected boolean destroyed = false; + private int numNonDoomedSuccessors = 0; + private boolean hasPathToRoot = false; + + private FastSet predecessors = new FastSet(); + private FastSet successors = new FastSet(); + //protected HashSet predecessors = new HashSet(); + //protected HashSet successors = new HashSet(); + + 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(); } - ////////////////////////////////////////////////////////////////////// - - private static int node_idx = 0; - private final int idx = node_idx++; - - private final GSS.Phase phase; - private final Parser.Table.State state; - private final boolean fromEmptyReduction; - //private FastSet results = new FastSet(); - private HashSet results = new HashSet(); - - public final void invoke(Position r, Boolean emptyProductions, Result only) { - if (emptyProductions != (r.pos==0)) return; - if (r.pos==0) finish(r, r.zero(phase().getLocation().createRegion(phase().getLocation())), phase()); - else reduce(r, r.pos-1, phase(), only); + /** + * 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 void reduce(Position r, int pos, GSS.Phase target, Result only) { - Forest[] holder = r.holder; - Forest old = holder[pos]; - for(Result res : results) - if (only == null || res == only) { - Node child = res.parent(); - holder[pos] = res.getForest(); - if (pos>0) child.reduce(r, pos-1, target, null); - else new Reduction(child, r, r.rewrite(child.phase().getLocation().createRegion(target.getLocation())), target); - } - holder[pos] = old; + /** 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"); + successors.add(succ); + numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1; + if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error(); } - void finish(Position r, Forest forest, GSS.Phase target) { - Parser.Table.State state0 = (Parser.Table.State)state.gotoSetNonTerminals.get(r.owner()); - Result result = new Result(forest, this, r); - target.newNodeFromReduction(result, state0, r.pos<=0, r); + protected void destroy() { + destroyed = true; + while(predecessors.size() > 0) { + OtherNode pred = predecessors.first(); + removePred(pred); + pred.removeSucc(this); + } + predecessors = null; + while(successors.size() > 0) { + OtherNode succ = successors.first(); + removeSucc(succ); + succ.removePred(this); + } + successors = null; + } + 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(); } - Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) { - this.phase = phase; - this.state = state; - this.fromEmptyReduction = fromEmptyReduction; - results.add(result); - 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); - - state.invokeReductions(phase().token, this, true, null); - if (!fromEmptyReduction) - state.invokeReductions(phase().getToken(), this, false, null); + + public abstract boolean isDoomedState(); + protected abstract void check(); + + public Iterator iterator() { return predecessors.iterator(); } + public Iterable successors() { return successors; } + + public boolean noSuccessors() { return successors.size()==0; } + public boolean predecessorsContains(OtherNode n) { + return predecessors.contains(n); } // GraphViz ////////////////////////////////////////////////////////////////////////////// - public GraphViz.Node toGraphViz(GraphViz gv) { - if (results.size()==0) return null; + public GraphViz.StateNode toGraphViz(GraphViz gv) { if (gv.hasNode(this)) return gv.createNode(this); - GraphViz.Node n = gv.createNode(this); - n.label = ""+state.toStringx(); + GraphViz.StateNode n = gv.createNode(this); + /* + n.label = ""+f; + n.shape = "rectangle"; + //if (pred()!=null) n.edge(pred, ""); + n.color = "blue"; + if (phase() != null) + ((GraphViz.Group)phase().toGraphViz(gv)).add(n); + n.label = "state["+state.toInt()+"]"; n.shape = "rectangle"; - boolean hasparents = false; - for(Result r : results) n.edge(r, ""); + boolean haspreds = false; + for(ResultNode r : results) n.edge(r, ""); n.color = state.doomed ? "red" : "green"; ((GraphViz.Group)phase().toGraphViz(gv)).add(n); + */ return n; } public boolean isTransparent() { return false; } public boolean isHidden() { return false; } -} + // IntegerMappable //////////////////////////////////////////////////////////// + + private static int node_idx = 0; + private final int idx = node_idx++; + public int toInt() { return idx; } + +} \ No newline at end of file