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> singleton(Input.Region loc, Position p) { return create(loc, null, new Forest[] { }, false, p); }
  81     static        <T> Forest<T> singleton(Input.Region loc, Forest<T> body, Position p) { return body; }
  82     static        <T> Forest<T> leaf(Input.Region loc, T tag, Position p) { return create(loc, tag, null, false, p); }
  83     public static <T> Forest<T> create(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap, Position p) {
  84         return new MyBody<T>(loc, tag, tokens, unwrap, p);
  85     }
  86     // Body //////////////////////////////////////////////////////////////////////////////
  87
  88     public /*protected*/ static interface Body<T> extends GraphViz.ToGraphViz {
  89         void expand(int i, TreeBuilder<T> h);
  90     }
  91     public abstract void edges(GraphViz.Node n);
  92     public boolean ambiguous() { return false; }
  93     public /*protected*/ static class MyBody<T> extends Forest<T> implements Body<T> /* extends PrintableTree<Forest<T>> implements */ {
  94
  95         public boolean isTransparent() { return false; }
  96         public boolean isHidden() { return false; }
  97         public GraphViz.Node toGraphViz(GraphViz gv) {
  98             if (gv.hasNode(this)) return gv.createNode(this);
  99             GraphViz.Node n = gv.createNode(this);
 100             n.label = headToString()==null?"":headToString();
 101             n.directed = true;
 102             n.comment = reduction==null?null:reduction+"";
 103             edges(n);
 104             return n;
 105         }
 106         boolean edges = false;
 107         public void edges(GraphViz.Node n) {
 108             if (edges) return;
 109             edges = true;
 110             for(int i=0; i<tokens.length; i++) {
 111                 if (i==tokens.length-1 && unwrap && !tokens[i].ambiguous()) {
 112                     tokens[i].edges(n);
 113                 } else {
 114                     n.edge(tokens[i], null);
 115                 }
 116             }
 117         }
 118
 119         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 120             ivbc.invoke(this, b, c);
 121         }
 122
 123         private final Input.Region      location;
 124         private final T                 tag;
 125         private final Forest<T>[]       tokens;
 126         private final boolean           unwrap;
 127         private final Sequence.Position reduction;
 128
 129         private MyBody(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap, Position reduction) {
 130             this.location = loc;
 131             this.tag = tag;
 132             this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
 133             if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
 134             if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
 135             this.unwrap = unwrap;
 136             this.reduction = reduction;
 137         }
 138         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 139             gather(tl, ht, target, new Tree[ht.length], 0);
 140         }
 141         private void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target, Tree[] trees, int i) {
 142             if (i==ht.length) {
 143                 target.add(new Tree<T>(location, tag, trees));
 144                 return;
 145             }
 146             for(Tree<T> tree : ht[i]) {
 147                 if (unwrap && i==trees.length-1) {
 148                     // I think this is wrong
 149                     Tree[] trees2 = new Tree[trees.length - 1 + tree.numChildren()];
 150                     System.arraycopy(trees, 0, trees2, 0, trees.length-1);
 151                     for(int j=0; j<tree.numChildren(); j++)
 152                         trees2[trees.length-1+j] = tree.child(j);
 153                     target.add(new Tree<T>(location, tag, trees2));
 154                 } else {
 155                     trees[i] = tree;
 156                     gather(tl, ht, target, trees, i+1);
 157                     trees[i] = null;
 158                 }
 159             }
 160         }
 161         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 162             HashSet<Tree<T>>[] children = new HashSet[tokens.length];
 163             tl.gather(this, children, ht);
 164             for(int i=0; i<children.length; i++) {
 165                 children[i] = new HashSet<Tree<T>>();
 166                 tl.expand(tokens[i], children[i]);
 167             }
 168         }
 169
 170         public void expand(final int i, final TreeBuilder<T> h) {
 171             if (i==0) h.start(tag, location);
 172
 173             if (i==tokens.length) {
 174                 h.finish(tag, location);
 175
 176             } else if (unwrap && i==tokens.length-1) {
 177                 if (tokens[i] != null)
 178                     tokens[i].visit(h, null, 0);
 179
 180             } else {
 181                 tokens[i].visit(new TreeBuilder<T>(h.toss) {
 182                     public void start(T head, Input.Region loc) { }
 183                     public void addTree(Tree<T> t) { toks.add(t); }
 184                     public void finish(T head, Input.Region loc) {
 185                         int old = h.toks.size();
 186                         h.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint)));
 187                         expand(i+1, h);
 188                         while(h.toks.size() > old) h.toks.remove(h.toks.size()-1);
 189                     }
 190                 }, null, null);
 191             }
 192         }
 193
 194         protected String  headToString()         { return tag==null?null:tag.toString(); }
 195         protected String  headToJava()           { return "null"; }
 196         protected String  left()                 { return "{"; }
 197         protected String  right()                { return "}"; }
 198         protected boolean ignoreSingleton()      { return false; }
 199     }
 200
 201
 202     // Ref //////////////////////////////////////////////////////////////////////////////
 203
 204     /**
 205      *  This class represents a partially complete collection of
 206      *  forests to be viewed as a forest at some later date; once
 207      *  viewed, it becomes immutable
 208      */
 209     static class Ref<T> extends Forest<T> {
 210         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 211             for (Forest<T> f : hp) f.expand(tl, ht);
 212         }
 213         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 214             throw new Error();
 215         }
 216         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
 217         public boolean contains(Forest f) {
 218             return hp.contains(f);
 219         }
 220         public boolean ambiguous() {
 221             if (hp.size()==0) return false;
 222             if (hp.size()==1) return hp.iterator().next().ambiguous();
 223             return true;
 224         }
 225         private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
 226         public Ref() { }
 227         public int toInt() {
 228             if (hp.size()==1) return hp.iterator().next().toInt();
 229             return super.toInt();
 230         }
 231         public void merge(Forest p) { if (p!=this) hp.add(p, true); }
 232
 233         public boolean isTransparent() { return hp.size()==1; }
 234         public boolean isHidden() { return hp.size()==0; }
 235         public void edges(GraphViz.Node n) {
 236             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 237             for(Forest f : hp) f.edges(n);
 238         }
 239         public GraphViz.Node toGraphViz(GraphViz gv) {
 240             //if (hp.size()==0) return null;
 241             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 242             if (gv.hasNode(this)) return gv.createNode(this);
 243             GraphViz.Node n = gv.createNode(this);
 244             n.label = "?";
 245             n.color = "red";
 246             for(Forest f : hp) n.edge(f, null);
 247             return n;
 248         }
 249
 250         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 251             if (hp==null) return;
 252             for(Forest<T> f : hp)
 253                 f.visit(ivbc, b, c);
 254         }
 255         public Forest resolve() { return this; }
 256     }
 257
 258     public abstract <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c);
 259
 260     // Statics //////////////////////////////////////////////////////////////////////////////
 261
 262     private static Tree[] tree_hint = new Tree[0];
 263     private static String[] string_hint = new String[0];
 264     private static final Forest[] emptyForestArray = new Forest[0];
 265
 266     protected String  headToString()    { return null; }
 267     protected String  headToJava()      { return "null"; }
 268     protected String  left()            { return "<?"; }
 269     protected String  right()           { return "?>"; }
 270     protected boolean ignoreSingleton() { return true; }
 271 }