1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.*;
5 import edu.berkeley.sbp.util.*;
6 import edu.berkeley.sbp.Parser.Table.*;
7 import edu.berkeley.sbp.Sequence.Pos;
8 import edu.berkeley.sbp.Sequence.Pos;
11 import java.lang.reflect.*;
13 abstract class Node<OtherNode extends Node>
14 implements IntegerMappable,
18 private final GSS.Phase phase;
19 private final GSS.Phase predecessorPhase;
20 protected boolean destroyed = false;
21 private int numNonDoomedSuccessors = 0;
22 private boolean hasPathToRoot = false;
24 private FastSet<OtherNode> predecessors = new FastSet<OtherNode>();
25 private FastSet<OtherNode> successors = new FastSet<OtherNode>();
26 //protected HashSet<OtherNode> predecessors = new HashSet<OtherNode>();
27 //protected HashSet<OtherNode> successors = new HashSet<OtherNode>();
29 public GSS.Phase phase() { return phase; }
30 public GSS.Phase predecessorPhase() { return predecessorPhase; }
31 public boolean hasPredecessors() { return predecessors.size() > 0; }
32 public boolean hasSuccessors() { return successors.size() > 0; }
33 public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; }
35 public boolean hasPathToRoot() { return hasPathToRoot; }
36 public void updatePathsToRootAfterRemoval() {
37 if (!hasPathToRoot()) return;
38 for(OtherNode on : predecessors)
39 if (on.hasPathToRoot())
41 hasPathToRoot = false;
42 for(OtherNode on : successors)
43 on.updatePathsToRootAfterRemoval();
47 * Every Node has a phase; StateNodes belong to the phase in
48 * which they were shifted, ResultNodes belong to the phase of
49 * their predecessors. All of the predecessors of a given node
50 * must belong to the same phase
52 public Node(GSS.Phase phase, GSS.Phase predecessorPhase) {
54 this.predecessorPhase = predecessorPhase;
57 /** only to be invoked (or overridden as public) by the subclass */
58 protected void addPred(OtherNode pred) {
59 if (predecessors.contains(pred)) throw new Error("a predecessor was added twice");
60 if (pred.phase() != predecessorPhase()) throw new Error();
61 predecessors.add(pred);
63 if (pred.hasPathToRoot()) hasPathToRoot = true;
65 public void addSucc(OtherNode succ) {
66 if (successors.contains(succ)) throw new Error("a predecessor was added twice");
68 numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1;
69 if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error();
72 protected void destroy() {
74 while(predecessors.size() > 0) {
75 OtherNode pred = predecessors.first();
77 pred.removeSucc(this);
80 while(successors.size() > 0) {
81 OtherNode succ = successors.first();
83 succ.removePred(this);
87 public void removeSucc(OtherNode succ) {
88 if (!successors.contains(succ)) return;
89 successors.remove(succ);
90 numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1;
93 public void removePred(OtherNode pred) {
94 if (!predecessors.contains(pred)) return;
95 predecessors.remove(pred);
96 updatePathsToRootAfterRemoval();
101 public abstract boolean isDoomedState();
102 protected abstract void check();
104 public Iterator<OtherNode> iterator() { return predecessors.iterator(); }
105 public Iterable<OtherNode> successors() { return successors; }
107 public boolean noSuccessors() { return successors.size()==0; }
108 public boolean predecessorsContains(OtherNode n) {
109 return predecessors.contains(n);
112 // GraphViz //////////////////////////////////////////////////////////////////////////////
114 public GraphViz.StateNode toGraphViz(GraphViz gv) {
115 if (gv.hasNode(this)) return gv.createNode(this);
116 GraphViz.StateNode n = gv.createNode(this);
119 n.shape = "rectangle";
120 //if (pred()!=null) n.edge(pred, "");
123 ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
124 n.label = "state["+state.toInt()+"]";
125 n.shape = "rectangle";
126 boolean haspreds = false;
127 for(ResultNode r : results) n.edge(r, "");
128 n.color = state.doomed ? "red" : "green";
129 ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
133 public boolean isTransparent() { return false; }
134 public boolean isHidden() { return false; }
136 // IntegerMappable ////////////////////////////////////////////////////////////
138 private static int node_idx = 0;
139 private final int idx = node_idx++;
140 public int toInt() { return idx; }