X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FForest.java;h=7fde86e681d3ec06854a39ec798576b0b9430559;hp=00f826a9e792fc2b8b42af5b14ee2786a82ea377;hb=a26089cd0d7c95cad657b745e836cb4cba35a97a;hpb=4ca0bc9a5bf2519c0e2cff2e988a6a7ffc6c7d9e

diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java
index 00f826a..7fde86e 100644
--- a/src/edu/berkeley/sbp/Forest.java
+++ b/src/edu/berkeley/sbp/Forest.java
@@ -16,35 +16,26 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
     public int toInt() { return idx; }
 
     /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
-    public final Tree<T> expand1() throws Ambiguous, ParseFailed {
-        try {
-            Iterator<Tree<T>> it = expand(true).iterator();
-            if (!it.hasNext()) throw new ParseFailed();
-            return it.next();
-        } catch (InnerAmbiguous ia) { throw new Ambiguous(ia.f); }
-    }
+    public abstract Tree<T> expand1() throws Ambiguous;
 
     /** expand this forest into a set of trees */
-    public abstract void expand(HashSet<Tree<T>> ht);
+    public void expand(HashSet<Tree<T>> ht) { expand(ht, new HashSet<Forest<T>>(), null); }
+    public abstract void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus);
+    public abstract void gather(HashSet<Forest<T>> ignore);
     public HashSet<Tree<T>> expand(boolean toss) {
         HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
         expand(ret);
         return ret;
     }
 
-    private static class InnerAmbiguous extends RuntimeException {
-        public final Forest<?> f;
-        public InnerAmbiguous(Forest<?> f) { this.f = f; }
-    }
-
-    static        <T> Forest<T> leaf(Input.Region loc, T tag) { return create(loc, tag, null, false); }
     public static <T> Forest<T> create(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
         return new Body<T>(loc, tag, tokens, unwrap);
     }
-    // Body //////////////////////////////////////////////////////////////////////////////
-
     public abstract void edges(GraphViz.Node n);
     public boolean ambiguous() { return false; }
+
+    // Body //////////////////////////////////////////////////////////////////////////////
+
     public /*protected*/ static class Body<T> extends Forest<T> /* extends PrintableTree<Forest<T>> implements */ {
 
         private final Input.Region      location;
@@ -52,6 +43,45 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
         private final Forest<T>[]       tokens;
         private final boolean           unwrap;
 
+        private Body(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
+            this.location = loc;
+            this.tag = tag;
+            this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
+            if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
+            if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
+            this.unwrap = unwrap;
+        }
+
+        public Tree<T> expand1() throws Ambiguous {
+            Tree<T>[] ret = new Tree[tokens.length];
+            for(int i=0; i<tokens.length; i++)
+                ret[i] = tokens[i].expand1();
+            return new Tree<T>(location, tag, ret, unwrap);
+        }
+        public void gather(HashSet<Forest<T>> hf) {
+            hf.add(this);
+            for(Forest<T> f : tokens) f.gather(hf);
+        }
+        public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
+            if (ignore.contains(this)) { ht.add(bogus); return; }
+            expand(0, new Tree[tokens.length], ht, ignore, bogus);
+        }
+        public void expand(final int i, Tree<T>[] ta, HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
+            if (i==tokens.length) {
+                ht.add(new Tree<T>(location, tag, ta, unwrap));
+            } else {
+                HashSet<Tree<T>> ht2 = new HashSet<Tree<T>>();
+                tokens[i].expand(ht2, ignore, bogus);
+                for(Tree<T> tc : ht2) {
+                    ta[i] = tc;
+                    expand(i+1, ta, ht, ignore, bogus);
+                    ta[i] = null;
+                }
+            }
+        }
+
+        // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
+
         public boolean isTransparent() { return false; }
         public boolean isHidden() { return false; }
         public GraphViz.Node toGraphViz(GraphViz gv) {
@@ -59,7 +89,6 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
             GraphViz.Node n = gv.createNode(this);
             n.label = headToString()==null?"":headToString();
             n.directed = true;
-            //n.comment = reduction==null?null:reduction+"";
             edges(n);
             return n;
         }
@@ -76,32 +105,6 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
             }
         }
 
-        private Body(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap) {
-            this.location = loc;
-            this.tag = tag;
-            this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
-            if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
-            if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
-            this.unwrap = unwrap;
-        }
-
-        public void expand(HashSet<Tree<T>> ht) {
-            expand(0, new Tree[tokens.length], ht);
-        }
-        public void expand(final int i, Tree<T>[] ta, HashSet<Tree<T>> ht) {
-            if (i==tokens.length) {
-                ht.add(new Tree<T>(location, tag, ta, unwrap));
-                return;
-            }
-            HashSet<Tree<T>> ht2 = new HashSet<Tree<T>>();
-            tokens[i].expand(ht2);
-            for(Tree<T> tc : ht2) {
-                ta[i] = tc;
-                expand(i+1, ta, ht);
-                ta[i] = null;
-            }
-        }
-
         protected String  headToString()         { return tag==null?null:tag.toString(); }
         protected String  headToJava()           { return "null"; }
         protected String  left()                 { return "{"; }
@@ -118,27 +121,40 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
      *  viewed, it becomes immutable
      */
     static class Ref<T> extends Forest<T> {
-        public void expand(HashSet<Tree<T>> ht) {
-            for (Forest<T> f : hp)
-                f.expand(ht);
-        }
         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
-        public boolean contains(Forest f) {
-            return hp.contains(f);
+        private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
+
+        public Ref() { }
+
+        public Tree<T> expand1() throws Ambiguous {
+            if (hp.size() > 1) throw new Ambiguous(this);
+            return hp.iterator().next().expand1();
+        }
+        
+        public void gather(HashSet<Forest<T>> ht) {
+            ht.add(this);
+            for(Forest<T> f : hp) f.gather(ht);
+        }
+
+        public Forest resolve() { return this; }
+        public void expand(HashSet<Tree<T>> ht, HashSet<Forest<T>> ignore, Tree<T> bogus) {
+            if (ignore.contains(this)) { ht.add(bogus); return; }
+            for (Forest<T> f : hp) f.expand(ht, ignore, bogus);
         }
+        public boolean contains(Forest f) { return hp.contains(f); }
+        public void merge(Forest p) { if (p!=this) hp.add(p, true); }
         public boolean ambiguous() {
             if (hp.size()==0) return false;
             if (hp.size()==1) return hp.iterator().next().ambiguous();
             return true;
         }
-        private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
-        public Ref() { }
+
+        // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
+
         public int toInt() {
             if (hp.size()==1) return hp.iterator().next().toInt();
             return super.toInt();
         }
-        public void merge(Forest p) { if (p!=this) hp.add(p, true); }
-
         public boolean isTransparent() { return hp.size()==1; }
         public boolean isHidden() { return hp.size()==0; }
         public void edges(GraphViz.Node n) {
@@ -155,8 +171,6 @@ public abstract class Forest<T> /*extends PrintableTree<Forest.Body<T>>*/
             for(Forest f : hp) n.edge(f, null);
             return n;
         }
-
-        public Forest resolve() { return this; }
     }
 
     // Statics //////////////////////////////////////////////////////////////////////////////