X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FForest.java;h=e675f635ff03468bece3501935cd1cfa24c409df;hp=5c091706b196b5ff0405778f62caffbfe9a233bc;hb=526da96dd06e152d194ec92c9ef9df6085a1251b;hpb=f33c05adc5aa3dd324c5352cdbd6f4b55359acad diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index 5c09170..e675f63 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -18,8 +18,7 @@ public abstract class Forest { /** expand this forest into a set of trees */ public abstract HashSet> expand(boolean toss); - - abstract boolean valid(); + public abstract boolean empty(); static Forest singleton(Token.Location loc, Sequence creator) { return create(loc, null, new Forest[] { }, creator, false, true); } static Forest singleton(Token.Location loc, Forest body, Sequence creator) { return create(loc, null, new Forest[] { body }, creator, false, true); } @@ -63,16 +62,15 @@ public abstract class Forest { b.expand(toss, toks, 0, h); } else { - if (tokens[i]!=null) { - HashSet> exp = tokens[i].expand(toss); - if (exp != null) - for(Tree r : exp) { - int old = toks.size(); - toks.add(r); - expand(toss, toks, i+1, h); - while(toks.size() > old) toks.remove(toks.size()-1); - } + boolean hit = false; + for(Tree r : tokens[i].expand(toss)) { + hit = true; + int old = toks.size(); + toks.add(r); + expand(toss, toks, i+1, h); + while(toks.size() > old) toks.remove(toks.size()-1); } + //if (!hit) throw new Error(); } return h; } @@ -85,24 +83,6 @@ public abstract class Forest { else for(Body b : (IterableForest)tokens[0]) b.addTo(h); } - private boolean kcache = false; - private boolean keep = false; - public boolean keep() { - if (kcache) return keep; - kcache = true; - for(Forest token : tokens) if (!token.valid()) return keep = false; - return keep = creator==null || (creator.needs.size()==0 && creator.hates.size()==0); - } - public boolean keep(Iterable> h) { - if (keep()) return true; - for(Forest token : tokens) if (!token.valid()) return false; - int needs = 0; - for(Body b : h) { - if (creator.hates.contains(b.creator) && b.keep(h)) return false; - if (creator.needs.contains(b.creator) && b.keep(h)) needs--; - } - return needs <= -1 * creator.needs.size(); - } private boolean rep = false; public String toString() { @@ -140,47 +120,30 @@ public abstract class Forest { * viewed, it becomes immutable */ static class Ref extends IterableForest { + public boolean empty() { + if (res!=null) return res.empty(); + for(Forest f : hp) if (!f.empty()) return false; + return true; + } private FastSet hp = new FastSet(); private Forest res = null; - public boolean valid = false; public Ref() { } public void merge(Forest p) { - //if (p==null) throw new Error("bad evil bad!"); if (res != null) throw new Error("already resolved!"); if (p==null) throw new Error(); if (p!=this) hp.add(p, true); } public Iterator> iterator() { return ((IterableForest)resolve()).iterator(); } public HashSet> expand(boolean toss) { return resolve().expand(toss); } - public boolean valid() { if (valid) return true; resolve(); return valid; } public String toString() { return resolve().toString(); } public Forest resolve() { if (hp==null) return res; - HashSet results = null; FastSet nh = new FastSet(); for(Forest p : hp) - for(Body b : (IterableForest)p) { - if (b.keep() && (b.creator==null || !b.creator.lame)) { - valid = true; - b.addTo(nh); - } else { - results = new HashSet(); - } - } - if (results != null) { - for(Forest p : hp) - for(Body b : (IterableForest)p) - results.add(b); - for(Body b : results) { - if (b.keep() && (b.creator==null || !b.creator.lame)) continue; - if (b.creator!=null && b.creator.lame) continue; - if (!b.keep(results)) continue; - valid = true; + for(Body b : (IterableForest)p) b.addTo(nh); - } - } + res = new MultiForest(nh); hp = null; - res = new MultiForest(nh, valid); return res; } } @@ -188,13 +151,11 @@ public abstract class Forest { // Implementations ////////////////////////////////////////////////////////////////////////////// private static class MultiForest extends IterableForest { + public boolean empty() { return results.size()>0; } private final FastSet> results; - private boolean valid; - public boolean valid() { return valid; } - private MultiForest(FastSet> results, boolean valid) { this.results = results; this.valid = valid; } + private MultiForest(FastSet> results) { this.results = results; } public MultiForest(Token.Location loc, T tag, Forest[] tokens, Sequence creator, boolean unwrap, boolean singleton) { this.results = new FastSet>(new Body(loc, tag, tokens, creator, unwrap, singleton)); - this.valid = true; } public Iterator> iterator() { return results.iterator(); }