src/edu/berkeley/sbp/Node.java

   1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
   2
   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;
   9 import java.io.*;
  10 import java.util.*;
  11 import java.lang.reflect.*;
  12
  13 abstract class Node<OtherNode extends Node>
  14     implements IntegerMappable,
  15                GraphViz.ToGraphViz,
  16                Iterable<OtherNode> {
  17
  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;
  23
  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>();
  28
  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; }
  34
  35     public boolean hasPathToRoot() { return hasPathToRoot; }
  36     public void updatePathsToRootAfterRemoval() {
  37         if (!hasPathToRoot()) return;
  38         for(OtherNode on : predecessors)
  39             if (on.hasPathToRoot())
  40                 return;
  41         hasPathToRoot = false;
  42         for(OtherNode on : successors)
  43             on.updatePathsToRootAfterRemoval();
  44     }
  45
  46     /**
  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
  51      */
  52     public Node(GSS.Phase phase, GSS.Phase predecessorPhase) {
  53         this.phase = phase;
  54         this.predecessorPhase = predecessorPhase;
  55     }
  56
  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);
  62         pred.addSucc(this);
  63         if (pred.hasPathToRoot()) hasPathToRoot = true;
  64     }
  65     public void addSucc(OtherNode succ) {
  66         if (successors.contains(succ)) throw new Error("a predecessor was added twice");
  67         successors.add(succ);
  68         numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1;
  69         if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error();
  70     }
  71
  72     protected void destroy() {
  73         destroyed = true;
  74         while(predecessors.size() > 0) {
  75             OtherNode pred = predecessors.first();
  76             removePred(pred);
  77             pred.removeSucc(this);
  78         }
  79         predecessors = null;
  80         while(successors.size() > 0) {
  81             OtherNode succ = successors.first();
  82             removeSucc(succ);
  83             succ.removePred(this);
  84         }
  85         successors = null;
  86     }
  87     public void removeSucc(OtherNode succ) {
  88         if (!successors.contains(succ)) return;
  89         successors.remove(succ);
  90         numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1;
  91         check();
  92     }
  93     public void removePred(OtherNode pred) {
  94         if (!predecessors.contains(pred)) return;
  95         predecessors.remove(pred);
  96         updatePathsToRootAfterRemoval();
  97         check();
  98     }
  99
 100
 101     public abstract boolean isDoomedState();
 102     protected abstract void check();
 103
 104     public Iterator<OtherNode> iterator() { return predecessors.iterator(); }
 105     public Iterable<OtherNode> successors() { return successors; }
 106
 107     public boolean noSuccessors() { return successors.size()==0; }
 108     public boolean predecessorsContains(OtherNode n) {
 109         return predecessors.contains(n);
 110     }
 111
 112     // GraphViz //////////////////////////////////////////////////////////////////////////////
 113
 114     public GraphViz.StateNode toGraphViz(GraphViz gv) {
 115         if (gv.hasNode(this)) return gv.createNode(this);
 116         GraphViz.StateNode n = gv.createNode(this);
 117         /*
 118         n.label = ""+f;
 119         n.shape = "rectangle";
 120         //if (pred()!=null) n.edge(pred, "");
 121         n.color = "blue";
 122         if (phase() != null)
 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);
 130         */
 131         return n;
 132     }
 133     public boolean isTransparent() { return false; }
 134     public boolean isHidden() { return false; }
 135
 136     // IntegerMappable ////////////////////////////////////////////////////////////
 137
 138     private static int node_idx = 0;
 139     private final int idx = node_idx++;
 140     public int toInt() { return idx; }
 141
 142 }