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 final Tree<T> expand1() throws Ambiguous, ParseFailed {
  20         try {
  21             Iterator<Tree<T>> it = expand(true).iterator();
  22             if (!it.hasNext()) throw new ParseFailed();
  23             return it.next();
  24         } catch (InnerAmbiguous ia) { throw new Ambiguous(ia.f); }
  25     }
  26
  27     /** expand this forest into a set of trees */
  28     public abstract void expand(HashSet<Tree<T>> ht);
  29     public HashSet<Tree<T>> expand(boolean toss) {
  30         HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
  31         expand(ret);
  32         return ret;
  33     }
  34
  35     private static class InnerAmbiguous extends RuntimeException {
  36         public final Forest<?> f;
  37         public InnerAmbiguous(Forest<?> f) { this.f = f; }
  38     }
  39
  40     static        <T> Forest<T> leaf(Input.Region loc, T tag) { return create(loc, tag, null, false); }
  41     public static <T> Forest<T> create(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
  42         return new Body<T>(loc, tag, tokens, unwrap);
  43     }
  44     // Body //////////////////////////////////////////////////////////////////////////////
  45
  46     public abstract void edges(GraphViz.Node n);
  47     public boolean ambiguous() { return false; }
  48     public /*protected*/ static class Body<T> extends Forest<T> /* extends PrintableTree<Forest<T>> implements */ {
  49
  50         private final Input.Region      location;
  51         private final T                 tag;
  52         private final Forest<T>[]       tokens;
  53         private final boolean           unwrap;
  54
  55         public boolean isTransparent() { return false; }
  56         public boolean isHidden() { return false; }
  57         public GraphViz.Node toGraphViz(GraphViz gv) {
  58             if (gv.hasNode(this)) return gv.createNode(this);
  59             GraphViz.Node n = gv.createNode(this);
  60             n.label = headToString()==null?"":headToString();
  61             n.directed = true;
  62             //n.comment = reduction==null?null:reduction+"";
  63             edges(n);
  64             return n;
  65         }
  66         boolean edges = false;
  67         public void edges(GraphViz.Node n) {
  68             if (edges) return;
  69             edges = true;
  70             for(int i=0; i<tokens.length; i++) {
  71                 if (i==tokens.length-1 && unwrap && !tokens[i].ambiguous()) {
  72                     tokens[i].edges(n);
  73                 } else {
  74                     n.edge(tokens[i], null);
  75                 }
  76             }
  77         }
  78
  79         private Body(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
  80             this.location = loc;
  81             this.tag = tag;
  82             this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
  83             if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
  84             if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
  85             this.unwrap = unwrap;
  86         }
  87
  88         public void expand(HashSet<Tree<T>> ht) {
  89             expand(0, new Tree[tokens.length], ht);
  90         }
  91         public void expand(final int i, Tree<T>[] ta, HashSet<Tree<T>> ht) {
  92             if (i==tokens.length) {
  93                 ht.add(new Tree<T>(location, tag, ta, unwrap));
  94                 return;
  95             }
  96             HashSet<Tree<T>> ht2 = new HashSet<Tree<T>>();
  97             tokens[i].expand(ht2);
  98             for(Tree<T> tc : ht2) {
  99                 ta[i] = tc;
 100                 expand(i+1, ta, ht);
 101                 ta[i] = null;
 102             }
 103         }
 104
 105         protected String  headToString()         { return tag==null?null:tag.toString(); }
 106         protected String  headToJava()           { return "null"; }
 107         protected String  left()                 { return "{"; }
 108         protected String  right()                { return "}"; }
 109         protected boolean ignoreSingleton()      { return false; }
 110     }
 111
 112
 113     // Ref //////////////////////////////////////////////////////////////////////////////
 114
 115     /**
 116      *  This class represents a partially complete collection of
 117      *  forests to be viewed as a forest at some later date; once
 118      *  viewed, it becomes immutable
 119      */
 120     static class Ref<T> extends Forest<T> {
 121         public void expand(HashSet<Tree<T>> ht) {
 122             for (Forest<T> f : hp)
 123                 f.expand(ht);
 124         }
 125         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
 126         public boolean contains(Forest f) {
 127             return hp.contains(f);
 128         }
 129         public boolean ambiguous() {
 130             if (hp.size()==0) return false;
 131             if (hp.size()==1) return hp.iterator().next().ambiguous();
 132             return true;
 133         }
 134         private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
 135         public Ref() { }
 136         public int toInt() {
 137             if (hp.size()==1) return hp.iterator().next().toInt();
 138             return super.toInt();
 139         }
 140         public void merge(Forest p) { if (p!=this) hp.add(p, true); }
 141
 142         public boolean isTransparent() { return hp.size()==1; }
 143         public boolean isHidden() { return hp.size()==0; }
 144         public void edges(GraphViz.Node n) {
 145             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 146             for(Forest f : hp) f.edges(n);
 147         }
 148         public GraphViz.Node toGraphViz(GraphViz gv) {
 149             //if (hp.size()==0) return null;
 150             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 151             if (gv.hasNode(this)) return gv.createNode(this);
 152             GraphViz.Node n = gv.createNode(this);
 153             n.label = "?";
 154             n.color = "red";
 155             for(Forest f : hp) n.edge(f, null);
 156             return n;
 157         }
 158
 159         public Forest resolve() { return this; }
 160     }
 161
 162     // Statics //////////////////////////////////////////////////////////////////////////////
 163
 164     private static Tree[] tree_hint = new Tree[0];
 165     private static String[] string_hint = new String[0];
 166     private static final Forest[] emptyForestArray = new Forest[0];
 167
 168     protected String  headToString()    { return null; }
 169     protected String  headToJava()      { return "null"; }
 170     protected String  left()            { return "<?"; }
 171     protected String  right()           { return "?>"; }
 172     protected boolean ignoreSingleton() { return true; }
 173 }