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.MyBody<T>>*/
  11     implements Visitable<Forest.Body<T>>,
  12                IntegerMappable,
  13                GraphViz.ToGraphViz {
  14
  15     private static int master_idx = 0;
  16     private final int idx = master_idx++;
  17     public int toInt() { return idx; }
  18
  19     public abstract void expand(TaskList tl, HashSet<Tree<T>> ht);
  20     public abstract void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target);
  21
  22     public static class TaskList extends ArrayList<TaskList.Task> {
  23         public interface Task {
  24             public void perform();
  25         }
  26         public class ExpandTask implements Task {
  27             private Forest f;
  28             private HashSet hs;
  29             public ExpandTask(Forest f, HashSet hs) { this.f = f; this.hs = hs; }
  30             public void perform() { f.expand(TaskList.this, hs); }
  31         }
  32         public class GatherTask implements Task {
  33             private Forest f;
  34             private HashSet[] ht;
  35             private HashSet hs;
  36             public GatherTask(Forest f, HashSet<Tree<?>>[] ht, HashSet<Tree<?>> hs) { this.f = f; this.hs = hs; this.ht = ht;}
  37             public void perform() { f.gather(TaskList.this, ht, hs); }
  38         }
  39         public void expand(Forest f, HashSet hs) {
  40             add(new ExpandTask(f, hs));
  41         }
  42         public void gather(Forest f, HashSet[] ht, HashSet hs) {
  43             add(new GatherTask(f, ht, hs));
  44         }
  45         public void run() {
  46             while(true) {
  47                 if (isEmpty()) return;
  48                 Task task = get(size()-1);
  49                 remove(size()-1);
  50                 task.perform();
  51             }
  52         }
  53     }
  54
  55     /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
  56     public final Tree<T> expand1() throws Ambiguous, ParseFailed {
  57         try {
  58             Iterator<Tree<T>> it = expand(true).iterator();
  59             if (!it.hasNext()) throw new ParseFailed();
  60             return it.next();
  61         } catch (InnerAmbiguous ia) { throw new Ambiguous(ia.f); }
  62     }
  63
  64     /** expand this forest into a set of trees */
  65     public HashSet<Tree<T>> expand(boolean toss) {
  66         TaskList tl = new TaskList();
  67         HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
  68         tl.expand(this, ret);
  69         tl.run();
  70
  71         if (toss && ret.size() > 1) throw new InnerAmbiguous(this);
  72         return ret;
  73     }
  74
  75     private static class InnerAmbiguous extends RuntimeException {
  76         public final Forest<?> f;
  77         public InnerAmbiguous(Forest<?> f) { this.f = f; }
  78     }
  79
  80     static        <T> Forest<T> leaf(Input.Region loc, T tag, Position p) { return create(loc, tag, null, false, p); }
  81     public static <T> Forest<T> create(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap, Position p) {
  82         return new MyBody<T>(loc, tag, tokens, unwrap);
  83     }
  84     // Body //////////////////////////////////////////////////////////////////////////////
  85
  86     public /*protected*/ static interface Body<T> extends GraphViz.ToGraphViz {
  87         void expand(int i, TreeBuilder<T> h);
  88     }
  89     public abstract void edges(GraphViz.Node n);
  90     public boolean ambiguous() { return false; }
  91     public /*protected*/ static class MyBody<T> extends Forest<T> implements Body<T> /* extends PrintableTree<Forest<T>> implements */ {
  92
  93         public boolean isTransparent() { return false; }
  94         public boolean isHidden() { return false; }
  95         public GraphViz.Node toGraphViz(GraphViz gv) {
  96             if (gv.hasNode(this)) return gv.createNode(this);
  97             GraphViz.Node n = gv.createNode(this);
  98             n.label = headToString()==null?"":headToString();
  99             n.directed = true;
 100             //n.comment = reduction==null?null:reduction+"";
 101             edges(n);
 102             return n;
 103         }
 104         boolean edges = false;
 105         public void edges(GraphViz.Node n) {
 106             if (edges) return;
 107             edges = true;
 108             for(int i=0; i<tokens.length; i++) {
 109                 if (i==tokens.length-1 && unwrap && !tokens[i].ambiguous()) {
 110                     tokens[i].edges(n);
 111                 } else {
 112                     n.edge(tokens[i], null);
 113                 }
 114             }
 115         }
 116
 117         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 118             ivbc.invoke(this, b, c);
 119         }
 120
 121         private final Input.Region      location;
 122         private final T                 tag;
 123         private final Forest<T>[]       tokens;
 124         private final boolean           unwrap;
 125
 126         private MyBody(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
 127             this.location = loc;
 128             this.tag = tag;
 129             this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
 130             if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
 131             if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
 132             this.unwrap = unwrap;
 133         }
 134         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 135             gather(tl, ht, target, new Tree[ht.length], 0);
 136         }
 137         private void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target, Tree[] trees, int i) {
 138             if (i==ht.length) {
 139                 target.add(new Tree<T>(location, tag, trees));
 140                 return;
 141             }
 142             for(Tree<T> tree : ht[i]) {
 143                 if (unwrap && i==trees.length-1) {
 144                     // I think this is wrong
 145                     Tree[] trees2 = new Tree[trees.length - 1 + tree.numChildren()];
 146                     System.arraycopy(trees, 0, trees2, 0, trees.length-1);
 147                     for(int j=0; j<tree.numChildren(); j++)
 148                         trees2[trees.length-1+j] = tree.child(j);
 149                     target.add(new Tree<T>(location, tag, trees2));
 150                 } else {
 151                     trees[i] = tree;
 152                     gather(tl, ht, target, trees, i+1);
 153                     trees[i] = null;
 154                 }
 155             }
 156         }
 157         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 158             HashSet<Tree<T>>[] children = new HashSet[tokens.length];
 159             tl.gather(this, children, ht);
 160             for(int i=0; i<children.length; i++) {
 161                 children[i] = new HashSet<Tree<T>>();
 162                 tl.expand(tokens[i], children[i]);
 163             }
 164         }
 165
 166         public void expand(final int i, final TreeBuilder<T> h) {
 167             if (i==0) h.start(tag, location);
 168
 169             if (i==tokens.length) {
 170                 h.finish(tag, location);
 171
 172             } else if (unwrap && i==tokens.length-1) {
 173                 if (tokens[i] != null)
 174                     tokens[i].visit(h, null, 0);
 175
 176             } else {
 177                 tokens[i].visit(new TreeBuilder<T>(h.toss) {
 178                     public void start(T head, Input.Region loc) { }
 179                     public void addTree(Tree<T> t) { toks.add(t); }
 180                     public void finish(T head, Input.Region loc) {
 181                         int old = h.toks.size();
 182                         h.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint)));
 183                         expand(i+1, h);
 184                         while(h.toks.size() > old) h.toks.remove(h.toks.size()-1);
 185                     }
 186                 }, null, null);
 187             }
 188         }
 189
 190         protected String  headToString()         { return tag==null?null:tag.toString(); }
 191         protected String  headToJava()           { return "null"; }
 192         protected String  left()                 { return "{"; }
 193         protected String  right()                { return "}"; }
 194         protected boolean ignoreSingleton()      { return false; }
 195     }
 196
 197
 198     // Ref //////////////////////////////////////////////////////////////////////////////
 199
 200     /**
 201      *  This class represents a partially complete collection of
 202      *  forests to be viewed as a forest at some later date; once
 203      *  viewed, it becomes immutable
 204      */
 205     static class Ref<T> extends Forest<T> {
 206         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 207             for (Forest<T> f : hp) f.expand(tl, ht);
 208         }
 209         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 210             throw new Error();
 211         }
 212         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
 213         public boolean contains(Forest f) {
 214             return hp.contains(f);
 215         }
 216         public boolean ambiguous() {
 217             if (hp.size()==0) return false;
 218             if (hp.size()==1) return hp.iterator().next().ambiguous();
 219             return true;
 220         }
 221         private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
 222         public Ref() { }
 223         public int toInt() {
 224             if (hp.size()==1) return hp.iterator().next().toInt();
 225             return super.toInt();
 226         }
 227         public void merge(Forest p) { if (p!=this) hp.add(p, true); }
 228
 229         public boolean isTransparent() { return hp.size()==1; }
 230         public boolean isHidden() { return hp.size()==0; }
 231         public void edges(GraphViz.Node n) {
 232             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 233             for(Forest f : hp) f.edges(n);
 234         }
 235         public GraphViz.Node toGraphViz(GraphViz gv) {
 236             //if (hp.size()==0) return null;
 237             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 238             if (gv.hasNode(this)) return gv.createNode(this);
 239             GraphViz.Node n = gv.createNode(this);
 240             n.label = "?";
 241             n.color = "red";
 242             for(Forest f : hp) n.edge(f, null);
 243             return n;
 244         }
 245
 246         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 247             if (hp==null) return;
 248             for(Forest<T> f : hp)
 249                 f.visit(ivbc, b, c);
 250         }
 251         public Forest resolve() { return this; }
 252     }
 253
 254     public abstract <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c);
 255
 256     // Statics //////////////////////////////////////////////////////////////////////////////
 257
 258     private static Tree[] tree_hint = new Tree[0];
 259     private static String[] string_hint = new String[0];
 260     private static final Forest[] emptyForestArray = new Forest[0];
 261
 262     protected String  headToString()    { return null; }
 263     protected String  headToJava()      { return "null"; }
 264     protected String  left()            { return "<?"; }
 265     protected String  right()           { return "?>"; }
 266     protected boolean ignoreSingleton() { return true; }
 267 }