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 /** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */
  10 public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
  11     implements IntegerMappable,
  12                GraphViz.ToGraphViz {
  13
  14     private static int master_idx = 0;
  15     private final int idx = master_idx++;
  16     public int toInt() { return idx; }
  17
  18     /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
  19     public abstract Tree<T> expand1() throws Ambiguous;
  20
  21     /** expand this forest into a set of trees */
  22     public void expand(HashSet<Tree<T>> ht) { expand(ht, new HashSet<Forest<T>>(), null); }
  23     public abstract void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus);
  24     public abstract void gather(HashSet<Forest<T>> ignore);
  25     public HashSet<Tree<T>> expand(boolean toss) {
  26         HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
  27         expand(ret);
  28         return ret;
  29     }
  30
  31     public static <T> Forest<T> create(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
  32         return new Body<T>(loc, tag, tokens, unwrap);
  33     }
  34     public abstract void edges(GraphViz.Node n);
  35     public boolean ambiguous() { return false; }
  36
  37     // Body //////////////////////////////////////////////////////////////////////////////
  38
  39     public /*protected*/ static class Body<T> extends Forest<T> /* extends PrintableTree<Forest<T>> implements */ {
  40
  41         private final Input.Region      location;
  42         private final T                 tag;
  43         private final Forest<T>[]       tokens;
  44         private final boolean           unwrap;
  45
  46         private Body(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
  47             this.location = loc;
  48             this.tag = tag;
  49             this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
  50             if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
  51             if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
  52             this.unwrap = unwrap;
  53         }
  54
  55         public Tree<T> expand1() throws Ambiguous {
  56             Tree<T>[] ret = new Tree[tokens.length];
  57             for(int i=0; i<tokens.length; i++)
  58                 ret[i] = tokens[i].expand1();
  59             return new Tree<T>(location, tag, ret, unwrap);
  60         }
  61         public void gather(HashSet<Forest<T>> hf) {
  62             hf.add(this);
  63             for(Forest<T> f : tokens) f.gather(hf);
  64         }
  65         public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
  66             if (ignore.contains(this)) { ht.add(bogus); return; }
  67             expand(0, new Tree[tokens.length], ht, ignore, bogus);
  68         }
  69         public void expand(final int i, Tree<T>[] ta, HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
  70             if (i==tokens.length) {
  71                 ht.add(new Tree<T>(location, tag, ta, unwrap));
  72             } else {
  73                 HashSet<Tree<T>> ht2 = new HashSet<Tree<T>>();
  74                 tokens[i].expand(ht2, ignore, bogus);
  75                 for(Tree<T> tc : ht2) {
  76                     ta[i] = tc;
  77                     expand(i+1, ta, ht, ignore, bogus);
  78                     ta[i] = null;
  79                 }
  80             }
  81         }
  82
  83         // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
  84
  85         public boolean isTransparent() { return false; }
  86         public boolean isHidden() { return false; }
  87         public GraphViz.Node toGraphViz(GraphViz gv) {
  88             if (gv.hasNode(this)) return gv.createNode(this);
  89             GraphViz.Node n = gv.createNode(this);
  90             n.label = headToString()==null?"":headToString();
  91             n.directed = true;
  92             edges(n);
  93             return n;
  94         }
  95         boolean edges = false;
  96         public void edges(GraphViz.Node n) {
  97             if (edges) return;
  98             edges = true;
  99             for(int i=0; i<tokens.length; i++) {
 100                 if (i==tokens.length-1 && unwrap && !tokens[i].ambiguous()) {
 101                     tokens[i].edges(n);
 102                 } else {
 103                     n.edge(tokens[i], null);
 104                 }
 105             }
 106         }
 107
 108         protected String  headToString()         { return tag==null?null:tag.toString(); }
 109         protected String  headToJava()           { return "null"; }
 110         protected String  left()                 { return "{"; }
 111         protected String  right()                { return "}"; }
 112         protected boolean ignoreSingleton()      { return false; }
 113     }
 114
 115
 116     // Ref //////////////////////////////////////////////////////////////////////////////
 117
 118     /**
 119      *  This class represents a partially complete collection of
 120      *  forests to be viewed as a forest at some later date; once
 121      *  viewed, it becomes immutable
 122      */
 123     static class Ref<T> extends Forest<T> {
 124         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
 125         private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
 126
 127         public Ref() { }
 128
 129         public Tree<T> expand1() throws Ambiguous {
 130             if (hp.size() > 1) {
 131                 HashSet<Forest<T>> hf0 = new HashSet<Forest<T>>();
 132                 Iterator<Forest<T>> ih = hp.iterator();
 133                 ih.next().gather(hf0);
 134                 for(Forest<T> f : hp) {
 135                     HashSet<Forest<T>> hf1 = new HashSet<Forest<T>>();
 136                     f.gather(hf1);
 137                     hf0.retainAll(hf1);
 138                 }
 139                 HashSet<Tree<T>> ht = new HashSet<Tree<T>>();
 140                 expand(ht, hf0, new Tree(null, "*"));
 141                 throw new Ambiguous((Forest<?>)this,
 142                                     (HashSet<Tree<?>>)(Object)ht);
 143             }
 144             return hp.iterator().next().expand1();
 145         }
 146
 147         public void gather(HashSet<Forest<T>> ht) {
 148             ht.add(this);
 149             for(Forest<T> f : hp) f.gather(ht);
 150         }
 151
 152         public Forest resolve() { return this; }
 153         public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
 154             if (ignore.contains(this)) { ht.add(bogus); return; }
 155             for (Forest<T> f : hp) f.expand(ht, ignore, bogus);
 156         }
 157         public boolean contains(Forest f) { return hp.contains(f); }
 158         public void merge(Forest p) { if (p!=this) hp.add(p, true); }
 159         public boolean ambiguous() {
 160             if (hp.size()==0) return false;
 161             if (hp.size()==1) return hp.iterator().next().ambiguous();
 162             return true;
 163         }
 164
 165         // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
 166
 167         public int toInt() {
 168             if (hp.size()==1) return hp.iterator().next().toInt();
 169             return super.toInt();
 170         }
 171         public boolean isTransparent() { return hp.size()==1; }
 172         public boolean isHidden() { return hp.size()==0; }
 173         public void edges(GraphViz.Node n) {
 174             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 175             for(Forest f : hp) f.edges(n);
 176         }
 177         public GraphViz.Node toGraphViz(GraphViz gv) {
 178             //if (hp.size()==0) return null;
 179             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 180             if (gv.hasNode(this)) return gv.createNode(this);
 181             GraphViz.Node n = gv.createNode(this);
 182             n.label = "?";
 183             n.color = "red";
 184             for(Forest f : hp) n.edge(f, null);
 185             return n;
 186         }
 187     }
 188
 189     // Statics //////////////////////////////////////////////////////////////////////////////
 190
 191     private static Tree[] tree_hint = new Tree[0];
 192     private static String[] string_hint = new String[0];
 193     private static final Forest[] emptyForestArray = new Forest[0];
 194
 195     protected String  headToString()    { return null; }
 196     protected String  headToJava()      { return "null"; }
 197     protected String  left()            { return "<?"; }
 198     protected String  right()           { return "?>"; }
 199     protected boolean ignoreSingleton() { return true; }
 200 }