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     /**
  19      *  Every Node has a phase; StateNodes belong to the phase in
  20      *  which they were shifted, ResultNodes belong to the phase of
  21      *  their predecessors.  All of the predecessors of a given node
  22      *  must belong to the same phase
  23      */
  24     public Node(GSS.Phase phase, GSS.Phase predecessorPhase) {
  25         this.phase = phase;
  26         this.predecessorPhase = predecessorPhase;
  27     }
  28
  29     private final GSS.Phase phase;
  30     private final GSS.Phase predecessorPhase;
  31     public GSS.Phase phase() { return phase; }
  32     public GSS.Phase predecessorPhase() { return predecessorPhase; }
  33     protected boolean destroyed = false;
  34     private int numNonDoomedSuccessors = 0;
  35     public boolean hasSuccessors() { return successors.size() > 0; }
  36     public boolean hasNonDoomedSuccessors() { return numNonDoomedSuccessors > 0; }
  37
  38     /** only to be invoked (or overridden as public) by the subclass */
  39     protected void addPred(OtherNode pred) {
  40         if (predecessors.contains(pred)) throw new Error("a predecessor was added twice");
  41         if (pred.phase() != predecessorPhase()) throw new Error();
  42         predecessors.add(pred);
  43         pred.addSucc(this);
  44     }
  45     public void addSucc(OtherNode succ) {
  46         if (successors.contains(succ)) throw new Error("a predecessor was added twice");
  47         successors.add(succ);
  48         numNonDoomedSuccessors += succ.isDoomedState() ? 0 : 1;
  49         if (predecessors.size() > 1 && (((Object)this) instanceof ResultNode)) throw new Error();
  50     }
  51     public void removeSucc(OtherNode succ) {
  52         if (!successors.contains(succ)) return;
  53         successors.remove(succ);
  54         numNonDoomedSuccessors -= succ.isDoomedState() ? 0 : 1;
  55         check();
  56     }
  57
  58     protected void destroy() {
  59         destroyed = true;
  60         while(predecessors.size() > 0)
  61             for(OtherNode pred : predecessors) {
  62                 removePred(pred);
  63                 pred.removeSucc(this);
  64                 break;
  65             }
  66         predecessors = null;
  67         while(successors.size() > 0)
  68             for(OtherNode succ : successors) {
  69                 removeSucc(succ);
  70                 succ.removePred(this);
  71                 break;
  72             }
  73         successors = null;
  74     }
  75
  76     public abstract boolean isDoomedState();
  77     protected abstract void check();
  78
  79     public void removePred(OtherNode pred) {
  80         if (!predecessors.contains(pred)) return;
  81         predecessors.remove(pred);
  82         check();
  83     }
  84
  85     protected       FastSet<OtherNode> predecessors = new FastSet<OtherNode>();
  86     protected       FastSet<OtherNode> successors = new FastSet<OtherNode>();
  87     //private       HashSet<OtherNode> predecessors = new HashSet<OtherNode>();
  88     //private       HashSet<OtherNode> successors = new HashSet<OtherNode>();
  89
  90     public Iterator<OtherNode> iterator() { return predecessors.iterator(); }
  91
  92     public boolean noSuccessors() { return successors.size()==0; }
  93     public boolean predecessorsContains(OtherNode n) {
  94         return predecessors.contains(n);
  95     }
  96
  97     // GraphViz //////////////////////////////////////////////////////////////////////////////
  98
  99     public GraphViz.StateNode toGraphViz(GraphViz gv) {
 100         if (gv.hasNode(this)) return gv.createNode(this);
 101         GraphViz.StateNode n = gv.createNode(this);
 102         /*
 103         n.label = ""+f;
 104         n.shape = "rectangle";
 105         //if (pred()!=null) n.edge(pred, "");
 106         n.color = "blue";
 107         if (phase() != null)
 108             ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
 109         n.label = "state["+state.toInt()+"]";
 110         n.shape = "rectangle";
 111         boolean haspreds = false;
 112         for(ResultNode r : results) n.edge(r, "");
 113         n.color = state.doomed ? "red" : "green";
 114         ((GraphViz.Group)phase().toGraphViz(gv)).add(n);
 115         */
 116         return n;
 117     }
 118     public boolean isTransparent() { return false; }
 119     public boolean isHidden() { return false; }
 120
 121     // IntegerMappable ////////////////////////////////////////////////////////////
 122
 123     private static int node_idx = 0;
 124     private final int idx = node_idx++;
 125     public int toInt() { return idx; }
 126
 127 }