X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FNode.java;h=09718afdce0d970fc521ba769c670ce7025b4460;hp=1d5e05a7206796b83605604a8493b0bb533d7463;hb=c404939a6dfed4dcfdca5ede08db99b3e5ef0c91;hpb=fe637b465179cf2a217bbfc76d12bc41551b4ac4 diff --git a/src/edu/berkeley/sbp/Node.java b/src/edu/berkeley/sbp/Node.java index 1d5e05a..09718af 100644 --- a/src/edu/berkeley/sbp/Node.java +++ b/src/edu/berkeley/sbp/Node.java @@ -1,140 +1,52 @@ -// 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, - GraphViz.ToGraphViz, - Iterable { +class Node + implements IntegerMappable, + GraphViz.ToGraphViz { - /** 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); - r.addChild(this); - if (fromEmptyReduction) return false; - state.invokeReductions(phase().getToken(), this, false, r); - return false; - } - - private boolean destroyed = false; - public boolean check() { - boolean dead = true; - // - all nodes must have a parent - // - 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; - for(Result r : children) - if (state.doomed) { if (r.usedByAnyNode()) dead = false; } - else { if (r.usedByNonDoomedNode()) dead = false; } - dead |= results.size()==0; - if (!dead || destroyed) return dead; - destroyed = true; - while(children.size()>0) - for(Result r : children) { - children.remove(r); - r.destroy(); - break; - } - while(results.size()>0) - for(Result r : results) { - results.remove(r); - r.removeChild(this); - r.check(); - break; - } - return dead; - } - - ////////////////////////////////////////////////////////////////////// - - 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(); - private HashSet children = new HashSet(); - public void removeChild(Result child) { children.remove(child); } - public void removeResult(Result result) { results.remove(result); } - public void addChild(Result child) { children.add(child); } - - 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); - } - - 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; - } - - 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); - } - - Node(GSS.Phase phase, Result result, State state, boolean fromEmptyReduction) { - this.phase = phase; - this.state = state; - this.fromEmptyReduction = fromEmptyReduction; - results.add(result); - result.addChild(this); - 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(new Result(null, this, null), (State)s, fromEmptyReduction); - - state.invokeReductions(phase().token, this, true, null); - if (!fromEmptyReduction) - state.invokeReductions(phase().getToken(), this, false, null); - } + protected FastSet predecessors = new FastSet(); + protected FastSet successors = new FastSet(); + //private HashSet predecessors = new HashSet(); + //private HashSet successors = new HashSet(); // 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