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