src/edu/berkeley/sbp/Forest.java

   1 package edu.berkeley.sbp;
   2 import edu.berkeley.sbp.*;
   3 import edu.berkeley.sbp.Sequence.Position;
   4 import edu.berkeley.sbp.util.*;
   5 import java.io.*;
   6 import java.util.*;
   7 import java.lang.reflect.*;
   8
   9 /**
  10  *   An efficient representation of a collection of trees (Tomita's
  11  *   shared packed parse forest).
  12  */
  13 public abstract class Forest<T> implements GraphViz.ToGraphViz {
  14
  15
  16     /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
  17     public abstract Tree<T> expand1() throws Ambiguous;
  18
  19     /** expand this forest into a set of trees */
  20     public void expand(HashSet<Tree<T>> ht) { expand(ht, new HashSet<Forest<T>>(), null); }
  21
  22     /** create a new forest */
  23     public static <T> Forest<T> create(Input.Region loc, T head, Forest<T>[] children, boolean unwrap) {
  24         return new One<T>(loc, head, children, unwrap);
  25     }
  26
  27
  28     // Package-Private //////////////////////////////////////////////////////////////////////////////
  29
  30     abstract void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus);
  31     abstract void gather(HashSet<Forest<T>> ignore);
  32     boolean ambiguous() { return false; }
  33
  34     public abstract void edges(GraphViz.Node n);
  35
  36
  37     // One //////////////////////////////////////////////////////////////////////////////
  38
  39     /** A "single" forest with a head and child subforests */
  40     public static class One<T> extends Forest<T> {
  41
  42         private final Input.Region      location;
  43         private final T                 head;
  44         private final Forest<T>[]       children;
  45
  46         /** if true, the last child's children are considered children of this node */
  47         private final boolean           unwrap;
  48
  49         private One(Input.Region loc, T head, Forest<T>[] children, boolean unwrap) {
  50             this.location = loc;
  51             this.head = head;
  52             this.children = children==null ? emptyForestArray : new Forest[children.length];
  53             if (children != null) System.arraycopy(children, 0, this.children, 0, children.length);
  54             if (children != null) for(int i=0; i<children.length; i++) if (children[i]==null) throw new Error(i+"");
  55             this.unwrap = unwrap;
  56         }
  57
  58         public Tree<T> expand1() throws Ambiguous {
  59             Tree<T>[] ret = new Tree[children.length];
  60             for(int i=0; i<children.length; i++) ret[i] = children[i].expand1();
  61             return new Tree<T>(location, head, ret, unwrap);
  62         }
  63
  64         public void gather(HashSet<Forest<T>> hf) {
  65             hf.add(this);
  66             for(Forest<T> f : children) f.gather(hf);
  67         }
  68         public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
  69             if (ignore.contains(this)) { ht.add(bogus); return; }
  70             expand(0, new Tree[children.length], ht, ignore, bogus);
  71         }
  72         private void expand(final int i, Tree<T>[] ta, HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
  73             if (i==children.length) {
  74                 ht.add(new Tree<T>(location, head, ta, unwrap));
  75             } else {
  76                 HashSet<Tree<T>> ht2 = new HashSet<Tree<T>>();
  77                 children[i].expand(ht2, ignore, bogus);
  78                 for(Tree<T> tc : ht2) {
  79                     ta[i] = tc;
  80                     expand(i+1, ta, ht, ignore, bogus);
  81                     ta[i] = null;
  82                 }
  83             }
  84         }
  85
  86         // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
  87
  88         public boolean isTransparent() { return false; }
  89         public boolean isHidden() { return false; }
  90         public GraphViz.Node toGraphViz(GraphViz gv) {
  91             if (gv.hasNode(this)) return gv.createNode(this);
  92             GraphViz.Node n = gv.createNode(this);
  93             n.label = headToString()==null?"":headToString();
  94             n.directed = true;
  95             edges(n);
  96             return n;
  97         }
  98         boolean edges = false;
  99         public void edges(GraphViz.Node n) {
 100             if (edges) return;
 101             edges = true;
 102             for(int i=0; i<children.length; i++) {
 103                 if (i==children.length-1 && unwrap && !children[i].ambiguous()) {
 104                     children[i].edges(n);
 105                 } else {
 106                     n.edge(children[i], null);
 107                 }
 108             }
 109         }
 110
 111         protected String  headToString()         { return head==null?null:head.toString(); }
 112         protected String  headToJava()           { return "null"; }
 113         protected String  left()                 { return "{"; }
 114         protected String  right()                { return "}"; }
 115         protected boolean ignoreSingleton()      { return false; }
 116     }
 117
 118
 119     // Many //////////////////////////////////////////////////////////////////////////////
 120
 121     /** An "ambiguity node"; this is immutable once it has been "looked at" */
 122     public static class Many<T> extends Forest<T> {
 123
 124         HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
 125         private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
 126         private boolean touched = false;
 127
 128         public Many() { }
 129
 130         public Iterator<One<T>> iterator() {
 131             touched();
 132             return (Iterator<One<T>>)hp.iterator();    // FIXME: fastset's iterator is not safe!
 133         }
 134
 135         public Tree<T> expand1() throws Ambiguous {
 136             touched();
 137             if (hp.size() > 1) {
 138                 HashSet<Forest<T>> hf0 = new HashSet<Forest<T>>();
 139                 Iterator<Forest<T>> ih = hp.iterator();
 140                 ih.next().gather(hf0);
 141                 for(Forest<T> f : hp) {
 142                     HashSet<Forest<T>> hf1 = new HashSet<Forest<T>>();
 143                     f.gather(hf1);
 144                     hf0.retainAll(hf1);
 145                 }
 146                 HashSet<Tree<T>> ht = new HashSet<Tree<T>>();
 147                 expand(ht, hf0, new Tree(null, "*"));
 148                 throw new Ambiguous((Forest<?>)this,
 149                                     (HashSet<Tree<?>>)(Object)ht);
 150             }
 151             return hp.iterator().next().expand1();
 152         }
 153
 154         public void gather(HashSet<Forest<T>> ht) {
 155             touched();
 156             ht.add(this);
 157             for(Forest<T> f : hp) f.gather(ht);
 158         }
 159
 160         private void touched() {
 161             if (touched) return;
 162             touched = true;
 163             FastSet<Forest<T>> f2 = new FastSet<Forest<T>>();
 164             for(Forest f : hp)
 165                 if (f instanceof Forest.One) f2.add(f);
 166                 else for(Forest ff : ((Forest.Many)f))
 167                     f2.add(ff);
 168             hp = f2;
 169         }
 170         public boolean contains(Forest f) {
 171             touched();
 172             return hp.contains(f);
 173         }
 174         public void merge(Forest p) {
 175             if (touched) throw new RuntimeException("attempt to merge() on a Forest.Many that has already been examined");
 176             if (p==this) throw new RuntimeException("attempt to merge() a Forest.Many to itself!");
 177             hp.add(p, true);
 178         }
 179         boolean ambiguous() {
 180             touched();
 181             if (hp.size()==0) return false;
 182             if (hp.size()==1) return hp.iterator().next().ambiguous();
 183             return true;
 184         }
 185
 186         public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
 187             touched();
 188             if (ignore.contains(this)) { ht.add(bogus); return; }
 189             for (Forest<T> f : hp) f.expand(ht, ignore, bogus);
 190         }
 191
 192
 193         // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
 194
 195         public boolean isTransparent() { return hp.size()==1; }
 196         public boolean isHidden() { return hp.size()==0; }
 197         public void edges(GraphViz.Node n) {
 198             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 199             for(Forest f : hp) f.edges(n);
 200         }
 201         public GraphViz.Node toGraphViz(GraphViz gv) {
 202             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 203             if (gv.hasNode(this)) return gv.createNode(this);
 204             GraphViz.Node n = gv.createNode(this);
 205             n.label = "?";
 206             n.color = "red";
 207             for(Forest f : hp) n.edge(f, null);
 208             return n;
 209         }
 210     }
 211
 212     // Statics //////////////////////////////////////////////////////////////////////////////
 213
 214     private static Tree[] tree_hint = new Tree[0];
 215     private static String[] string_hint = new String[0];
 216     private static final Forest[] emptyForestArray = new Forest[0];
 217
 218     protected String  headToString()    { return null; }
 219     protected String  headToJava()      { return "null"; }
 220     protected String  left()            { return "<?"; }
 221     protected String  right()           { return "?>"; }
 222     protected boolean ignoreSingleton() { return true; }
 223 }