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 Tree<T> expand1() throws Ambiguous {
 131             touched();
 132             if (hp.size() > 1) {
 133                 HashSet<Forest<T>> hf0 = new HashSet<Forest<T>>();
 134                 Iterator<Forest<T>> ih = hp.iterator();
 135                 ih.next().gather(hf0);
 136                 for(Forest<T> f : hp) {
 137                     HashSet<Forest<T>> hf1 = new HashSet<Forest<T>>();
 138                     f.gather(hf1);
 139                     hf0.retainAll(hf1);
 140                 }
 141                 HashSet<Tree<T>> ht = new HashSet<Tree<T>>();
 142                 expand(ht, hf0, new Tree(null, "*"));
 143                 throw new Ambiguous((Forest<?>)this,
 144                                     (HashSet<Tree<?>>)(Object)ht);
 145             }
 146             return hp.iterator().next().expand1();
 147         }
 148
 149         public void gather(HashSet<Forest<T>> ht) {
 150             touched();
 151             ht.add(this);
 152             for(Forest<T> f : hp) f.gather(ht);
 153         }
 154
 155         private void touched() {
 156             touched = true;
 157         }
 158         public boolean contains(Forest f) {
 159             touched();
 160             return hp.contains(f);
 161         }
 162         public void merge(Forest p) {
 163             if (touched) throw new RuntimeException("attempt to merge() on a Forest.Many that has already been examined");
 164             if (p==this) throw new RuntimeException("attempt to merge() a Forest.Many to itself!");
 165             hp.add(p, true);
 166         }
 167         boolean ambiguous() {
 168             touched();
 169             if (hp.size()==0) return false;
 170             if (hp.size()==1) return hp.iterator().next().ambiguous();
 171             return true;
 172         }
 173
 174         public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
 175             touched();
 176             if (ignore.contains(this)) { ht.add(bogus); return; }
 177             for (Forest<T> f : hp) f.expand(ht, ignore, bogus);
 178         }
 179
 180
 181         // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
 182
 183         public boolean isTransparent() { return hp.size()==1; }
 184         public boolean isHidden() { return hp.size()==0; }
 185         public void edges(GraphViz.Node n) {
 186             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 187             for(Forest f : hp) f.edges(n);
 188         }
 189         public GraphViz.Node toGraphViz(GraphViz gv) {
 190             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 191             if (gv.hasNode(this)) return gv.createNode(this);
 192             GraphViz.Node n = gv.createNode(this);
 193             n.label = "?";
 194             n.color = "red";
 195             for(Forest f : hp) n.edge(f, null);
 196             return n;
 197         }
 198     }
 199
 200     // Statics //////////////////////////////////////////////////////////////////////////////
 201
 202     private static Tree[] tree_hint = new Tree[0];
 203     private static String[] string_hint = new String[0];
 204     private static final Forest[] emptyForestArray = new Forest[0];
 205
 206     protected String  headToString()    { return null; }
 207     protected String  headToJava()      { return "null"; }
 208     protected String  left()            { return "<?"; }
 209     protected String  right()           { return "?>"; }
 210     protected boolean ignoreSingleton() { return true; }
 211 }