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         /*
  67         final HashSetTreeConsumer<T> ret = new HashSetTreeConsumer<T>();
  68         visit(new TreeMaker2<T>(toss, ret), null, null);
  69         */
  70         TaskList tl = new TaskList();
  71         HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
  72         tl.expand(this, ret);
  73         tl.run();
  74
  75         if (toss && ret.size() > 1) throw new InnerAmbiguous(this);
  76         return ret;
  77     }
  78
  79     private static class InnerAmbiguous extends RuntimeException {
  80         public final Forest<?> f;
  81         public InnerAmbiguous(Forest<?> f) { this.f = f; }
  82     }
  83
  84     static interface TreeConsumer<T> {
  85         public void addTree(Tree<T> t);
  86     }
  87     static class HashSetTreeConsumer<T> extends HashSet<Tree<T>> implements TreeConsumer<T> {
  88         public void addTree(Tree<T> t) {
  89             super.add(t);
  90         }
  91     }
  92
  93     static        <T> Forest<T> singleton(Input.Location loc, Position p) {
  94         return create(loc, null, new Forest[] { }, new Object[0], false, true, p); }
  95     static        <T> Forest<T> singleton(Input.Location loc, Forest<T> body, Position p) {
  96         //return create(loc, null, new Forest[] { body },  false, true, p);
  97         return body;
  98     }
  99     static        <T> Forest<T> leaf(Input.Location loc, T tag, Position p) { return create(loc, tag, null, null, false, false, p); }
 100     public static <T> Forest<T> create(Input.Location loc, T tag, Forest<T>[] tokens, Object[] labels, boolean unwrap, boolean singleton, Position p) {
 101         return new MyBody<T>(loc, tag, tokens, labels, unwrap, singleton, p);
 102     }
 103     // Body //////////////////////////////////////////////////////////////////////////////
 104
 105     protected static interface Body<T> extends GraphViz.ToGraphViz {
 106         void expand(int i, TreeMaker<T> h);
 107     }
 108     public abstract void edges(GraphViz.Node n);
 109     public boolean ambiguous() { return false; }
 110     protected static class MyBody<T> extends Forest<T> implements Body<T> /* extends PrintableTree<Forest<T>> implements */ {
 111
 112         public boolean isTransparent() { return false; }
 113         public boolean isHidden() { return false; }
 114         public GraphViz.Node toGraphViz(GraphViz gv) {
 115             if (gv.hasNode(this)) return gv.createNode(this);
 116             GraphViz.Node n = gv.createNode(this);
 117             n.label = headToString()==null?"":headToString();
 118             n.directed = true;
 119             n.comment = reduction==null?null:reduction+"";
 120             edges(n);
 121             return n;
 122         }
 123         boolean edges = false;
 124         public void edges(GraphViz.Node n) {
 125             if (edges) return;
 126             edges = true;
 127             for(int i=0; i<tokens.length; i++) {
 128                 if (i==tokens.length-1 && unwrap && !tokens[i].ambiguous()) {
 129                     tokens[i].edges(n);
 130                 } else {
 131                     n.edge(tokens[i], labels==null?null:labels[i]);
 132                 }
 133             }
 134         }
 135
 136         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 137             ivbc.invoke(this, b, c);
 138         }
 139
 140         private final Input.Location    location;
 141         private final T                 tag;
 142         private final Forest<T>[]       tokens;
 143         private final Object[]          labels;
 144         private final boolean           unwrap;
 145         private final boolean           singleton;
 146         private final Sequence.Position reduction;
 147
 148         private MyBody(Input.Location loc, T tag, Forest<T>[] tokens, Object[] labels, boolean unwrap, boolean singleton, Position reduction) {
 149             this.location = loc;
 150             this.tag = tag;
 151             this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
 152             if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
 153             if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
 154             this.unwrap = unwrap;
 155             this.singleton = singleton;
 156             this.reduction = reduction;
 157             this.labels = labels;
 158         }
 159         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 160             gather(tl, ht, target, new Tree[ht.length], 0);
 161         }
 162         private void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target, Tree[] trees, int i) {
 163             if (i==ht.length) {
 164                 target.add(new Tree<T>(null, tag, trees));
 165                 return;
 166             }
 167             for(Tree<T> tree : ht[i]) {
 168                 if (unwrap && i==trees.length-1) {
 169                     // I think this is wrong
 170                     Tree[] trees2 = new Tree[trees.length - 1 + tree.numChildren()];
 171                     System.arraycopy(trees, 0, trees2, 0, trees.length-1);
 172                     for(int j=0; j<tree.numChildren(); j++)
 173                         trees2[trees.length-1+j] = tree.child(j);
 174                     target.add(new Tree<T>(null, tag, trees2));
 175                 } else {
 176                     trees[i] = tree;
 177                     gather(tl, ht, target, trees, i+1);
 178                     trees[i] = null;
 179                 }
 180             }
 181         }
 182         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 183             if (singleton) {
 184                 tokens[0].expand(tl, ht);
 185                 return;
 186             }
 187             HashSet<Tree<T>>[] children = new HashSet[tokens.length];
 188             tl.gather(this, children, ht);
 189             for(int i=0; i<children.length; i++) {
 190                 children[i] = new HashSet<Tree<T>>();
 191                 tl.expand(tokens[i], children[i]);
 192             }
 193         }
 194
 195         public void expand(final int i, final TreeMaker<T> h) {
 196             if (singleton) {
 197                 tokens[0].visit(h, null, i);
 198                 return;
 199             }
 200             if (i==0) h.start(tag, location);
 201
 202             if (i==tokens.length) {
 203                 h.finish(tag, location);
 204
 205             } else if (unwrap && i==tokens.length-1) {
 206                 if (tokens[i] != null)
 207                     tokens[i].visit(h, null, 0);
 208
 209             } else {
 210                 tokens[i].visit(new TreeMaker<T>(h.toss) {
 211                     public void start(T head, Input.Location loc) { }
 212                     public void addTree(Tree<T> t, Object label) { toks.add(t); labs.add(label); }
 213                     public void finish(T head, Input.Location loc) {
 214                         int old = h.toks.size();
 215                         h.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint), labs.toArray(string_hint)), labels==null?null:labels[i]);
 216                         expand(i+1, h);
 217                         while(h.toks.size() > old) h.toks.remove(h.toks.size()-1);
 218                         while(h.labs.size() > old) h.labs.remove(h.labs.size()-1);
 219                     }
 220                 }, null, null);
 221             }
 222         }
 223
 224         protected String  headToString()         { return tag==null?null:tag.toString(); }
 225         protected String  headToJava()           { return "null"; }
 226         protected String  left()                 { return "{"; }
 227         protected String  right()                { return "}"; }
 228         protected boolean ignoreSingleton()      { return false; }
 229     }
 230
 231
 232     // Ref //////////////////////////////////////////////////////////////////////////////
 233
 234     /**
 235      *  This class represents a partially complete collection of
 236      *  forests to be viewed as a forest at some later date; once
 237      *  viewed, it becomes immutable
 238      */
 239     static class Ref<T> extends Forest<T> {
 240         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 241             for (Forest<T> f : hp) f.expand(tl, ht);
 242         }
 243         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 244             throw new Error();
 245         }
 246         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
 247         public boolean contains(Forest f) {
 248             return hp.contains(f);
 249         }
 250         public boolean ambiguous() {
 251             if (hp.size()==0) return false;
 252             if (hp.size()==1) return hp.iterator().next().ambiguous();
 253             return true;
 254         }
 255         private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
 256         public Ref() { }
 257         public int toInt() {
 258             if (hp.size()==1) return hp.iterator().next().toInt();
 259             return super.toInt();
 260         }
 261         public void merge(Forest p) { if (p!=this) hp.add(p, true); }
 262
 263         public boolean isTransparent() { return hp.size()==1; }
 264         public boolean isHidden() { return hp.size()==0; }
 265         public void edges(GraphViz.Node n) {
 266             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 267             for(Forest f : hp) f.edges(n);
 268         }
 269         public GraphViz.Node toGraphViz(GraphViz gv) {
 270             //if (hp.size()==0) return null;
 271             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 272             if (gv.hasNode(this)) return gv.createNode(this);
 273             GraphViz.Node n = gv.createNode(this);
 274             n.label = "?";
 275             n.color = "red";
 276             for(Forest f : hp) n.edge(f, null);
 277             return n;
 278         }
 279
 280         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 281             if (hp==null) return;
 282             for(Forest<T> f : hp)
 283                 f.visit(ivbc, b, c);
 284         }
 285         public Forest resolve() { return this; }
 286     }
 287
 288     public abstract <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c);
 289     private static class TreeMaker2<T> extends TreeMaker<T> {
 290         private TreeConsumer<T> tc;
 291         public TreeMaker2(boolean toss, TreeConsumer<T> tc) { super(toss); this.tc = tc; }
 292         public void finish(T head, Input.Location loc) { tc.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint), labs.toArray(string_hint)));; }
 293         public void start(T head, Input.Location loc) { }
 294         public void addTree(Tree<T> t, Object label) { toks.add(t); labs.add(label); }
 295     }
 296     private static abstract class TreeMaker<T> implements Invokable<Forest.Body<T>,Boolean,Integer>/*, TreeConsumer<T>*/ {
 297         public ArrayList<Tree<T>> toks = new ArrayList<Tree<T>>();
 298         public ArrayList<Object>  labs = new ArrayList<Object>();
 299         private boolean toss;
 300         protected T head;
 301         public TreeMaker(boolean toss) { this.toss = toss; }
 302         public abstract void start(T head, Input.Location loc);
 303         public abstract void finish(T head, Input.Location loc);
 304         public abstract void addTree(Tree<T> t, Object label);
 305         public void invoke(Forest.Body<T> bod, Boolean o, Integer i) {
 306             if (i==null) {
 307                 ArrayList<Tree<T>> toks = this.toks;
 308                 this.toks = new ArrayList<Tree<T>>();
 309                 ArrayList<Object> labs = this.labs;
 310                 this.labs = new ArrayList<Object>();
 311                 bod.expand(0, this);
 312                 this.toks = toks;
 313                 this.labs = labs;
 314             } else {
 315                 bod.expand(i, this);
 316             }
 317         }
 318     }
 319
 320     // Statics //////////////////////////////////////////////////////////////////////////////
 321
 322     private static Tree[] tree_hint = new Tree[0];
 323     private static String[] string_hint = new String[0];
 324     private static final Forest[] emptyForestArray = new Forest[0];
 325
 326     protected String  headToString()    { return null; }
 327     protected String  headToJava()      { return "null"; }
 328     protected String  left()            { return "<?"; }
 329     protected String  right()           { return "?>"; }
 330     protected boolean ignoreSingleton() { return true; }
 331 }