From: adam Date: Sun, 16 Jul 2006 07:02:29 +0000 (-0400) Subject: checkpoint X-Git-Tag: tag_for_25-Mar~130 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=297f374e023e781f38f3fb2d6122c951f224380e checkpoint darcs-hash:20060716070229-5007d-af87eb9afdb7e3872d52f07b30aa446958ed0abd.gz --- diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index 7d872ad..65a8095 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -6,7 +6,10 @@ import java.io.*; import java.util.*; import java.lang.reflect.*; -/** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */ +/** + * An efficient representation of a collection of trees (Tomita's + * shared packed parse forest). + */ public abstract class Forest implements GraphViz.ToGraphViz { @@ -16,29 +19,34 @@ public abstract class Forest implements GraphViz.ToGraphViz { /** expand this forest into a set of trees */ public void expand(HashSet> ht) { expand(ht, new HashSet>(), null); } - /** create a new forest node */ + /** create a new forest */ public static Forest create(Input.Region loc, T head, Forest[] children, boolean unwrap) { - return new Body(loc, head, children, unwrap); + return new One(loc, head, children, unwrap); } + // Package-Private ////////////////////////////////////////////////////////////////////////////// abstract void expand(HashSet> ht, HashSet> ignore, Tree bogus); abstract void gather(HashSet> ignore); + boolean ambiguous() { return false; } public abstract void edges(GraphViz.Node n); - public boolean ambiguous() { return false; } - // Body ////////////////////////////////////////////////////////////////////////////// - private static class Body extends Forest /* extends PrintableTree> implements */ { + // One ////////////////////////////////////////////////////////////////////////////// + + /** A "single" forest with a head and child subforests */ + public static class One extends Forest { private final Input.Region location; private final T head; private final Forest[] children; + + /** if true, the last child's children are considered children of this node */ private final boolean unwrap; - private Body(Input.Region loc, T head, Forest[] children, boolean unwrap) { + private One(Input.Region loc, T head, Forest[] children, boolean unwrap) { this.location = loc; this.head = head; this.children = children==null ? emptyForestArray : new Forest[children.length]; @@ -49,10 +57,10 @@ public abstract class Forest implements GraphViz.ToGraphViz { public Tree expand1() throws Ambiguous { Tree[] ret = new Tree[children.length]; - for(int i=0; i(location, head, ret, unwrap); } + public void gather(HashSet> hf) { hf.add(this); for(Forest f : children) f.gather(hf); @@ -61,7 +69,7 @@ public abstract class Forest implements GraphViz.ToGraphViz { if (ignore.contains(this)) { ht.add(bogus); return; } expand(0, new Tree[children.length], ht, ignore, bogus); } - public void expand(final int i, Tree[] ta, HashSet> ht, HashSet> ignore, Tree bogus) { + private void expand(final int i, Tree[] ta, HashSet> ht, HashSet> ignore, Tree bogus) { if (i==children.length) { ht.add(new Tree(location, head, ta, unwrap)); } else { @@ -108,20 +116,19 @@ public abstract class Forest implements GraphViz.ToGraphViz { } - // Ref ////////////////////////////////////////////////////////////////////////////// + // Many ////////////////////////////////////////////////////////////////////////////// + + /** An "ambiguity node"; this is immutable once it has been "looked at" */ + public static class Many extends Forest { - /** - * This class represents a partially complete collection of - * forests to be viewed as a forest at some later date; once - * viewed, it becomes immutable - */ - static class Ref extends Forest { - public HashSet parents = new HashSet(); + HashSet parents = new HashSet(); private FastSet> hp = new FastSet>(); + private boolean touched = false; - public Ref() { } + public Many() { } public Tree expand1() throws Ambiguous { + touched(); if (hp.size() > 1) { HashSet> hf0 = new HashSet>(); Iterator> ih = hp.iterator(); @@ -140,30 +147,39 @@ public abstract class Forest implements GraphViz.ToGraphViz { } public void gather(HashSet> ht) { + touched(); ht.add(this); for(Forest f : hp) f.gather(ht); } - public Forest resolve() { return this; } - public void expand(HashSet> ht, HashSet> ignore, Tree bogus) { - if (ignore.contains(this)) { ht.add(bogus); return; } - for (Forest f : hp) f.expand(ht, ignore, bogus); + private void touched() { + touched = true; + } + public boolean contains(Forest f) { + touched(); + return hp.contains(f); } - public boolean contains(Forest f) { return hp.contains(f); } - public void merge(Forest p) { if (p!=this) hp.add(p, true); } - public boolean ambiguous() { + public void merge(Forest p) { + if (touched) throw new RuntimeException("attempt to merge() on a Forest.Many that has already been examined"); + if (p==this) throw new RuntimeException("attempt to merge() a Forest.Many to itself!"); + hp.add(p, true); + } + boolean ambiguous() { + touched(); if (hp.size()==0) return false; if (hp.size()==1) return hp.iterator().next().ambiguous(); return true; } - // GraphViz, ToInt ////////////////////////////////////////////////////////////////////////////// - /* - public int toInt() { - if (hp.size()==1) return hp.iterator().next().toInt(); - return super.toInt(); + public void expand(HashSet> ht, HashSet> ignore, Tree bogus) { + touched(); + if (ignore.contains(this)) { ht.add(bogus); return; } + for (Forest f : hp) f.expand(ht, ignore, bogus); } - */ + + + // GraphViz, ToInt ////////////////////////////////////////////////////////////////////////////// + public boolean isTransparent() { return hp.size()==1; } public boolean isHidden() { return hp.size()==0; } public void edges(GraphViz.Node n) { @@ -171,7 +187,6 @@ public abstract class Forest implements GraphViz.ToGraphViz { for(Forest f : hp) f.edges(n); } public GraphViz.Node toGraphViz(GraphViz gv) { - //if (hp.size()==0) return null; if (hp.size()==1) return hp.iterator().next().toGraphViz(gv); if (gv.hasNode(this)) return gv.createNode(this); GraphViz.Node n = gv.createNode(this); diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java index 8412471..f85ec0b 100644 --- a/src/edu/berkeley/sbp/GSS.java +++ b/src/edu/berkeley/sbp/GSS.java @@ -27,7 +27,7 @@ public class GSS { HashMapBag expected = new HashMapBag(); /** FIXME */ - public Forest.Ref finalResult; + public Forest.Many finalResult; /** corresponds to a positions between tokens the input stream; same as Tomita's U_i's */ class Phase implements Invokable.Node>, IntegerMappable, GraphViz.ToGraphViz, Iterable { @@ -230,7 +230,7 @@ public class GSS { boolean ok = false; for(Phase.Node n : hash.values()) { if (token == null && n.state.isAccepting()) { - if (finalResult==null) finalResult = new Forest.Ref(); + if (finalResult==null) finalResult = new Forest.Many(); for(Object f : n.results()) finalResult.merge((Forest)f); } @@ -285,18 +285,18 @@ public class GSS { /** which Phase this Node belongs to (node that Node is also a non-static inner class of Phase) */ public Phase phase() { return Phase.this; } - private HashSet resultMap = new HashSet(); - public Iterable results() { return resultMap; } + private HashSet resultMap = new HashSet(); + public Iterable results() { return resultMap; } public FastSet parents() { return set; } public boolean merge(Node parent, Forest result) { // FIXME: inefficient! - for(Forest.Ref f : results()) { + for(Forest.Many f : results()) { if (f.parents.contains(parent) /* UGLY: */ && f.parents.size()==1) { f.merge(result); return true; } } - Forest.Ref f = new Forest.Ref(); + Forest.Many f = new Forest.Many(); f.parents.add(parent); f.merge(result); resultMap.add(f); @@ -341,7 +341,7 @@ public class GSS { HashSet rr = new HashSet(); for(Forest result : results()) rr.add(result); for(Forest result : rr) - for(Node child : ((Forest.Ref)result).parents) { + for(Node child : ((Forest.Many)result).parents) { if (only != null && child!=only) continue; holder[pos] = result; if (pos==0) child.finish(r, r.rewrite(new Input.Region(child.phase().getLocation(), phase().getLocation())), target); diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java index e5db6c8..091f7ae 100644 --- a/src/edu/berkeley/sbp/Sequence.java +++ b/src/edu/berkeley/sbp/Sequence.java @@ -80,10 +80,10 @@ public abstract class Sequence extends Element implements Iterable { } // DO NOT MESS WITH THE FOLLOWING LINE!!! - private Forest.Ref epsilonForm = null; + private Forest.Many epsilonForm = null; Forest epsilonForm() { if (epsilonForm!=null) return epsilonForm; - epsilonForm = new Forest.Ref(); + epsilonForm = new Forest.Many(); epsilonForm.merge(firstp().rewrite(null, false)); return epsilonForm; } diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java index 4595ebb..6cba89c 100644 --- a/src/edu/berkeley/sbp/Union.java +++ b/src/edu/berkeley/sbp/Union.java @@ -49,10 +49,10 @@ public class Union extends Element implements Iterable { static { epsilon.add(Sequence.empty); } // FIXME - private Forest.Ref epsilonForm = null; + private Forest.Many epsilonForm = null; Forest epsilonForm() { if (epsilonForm != null) return epsilonForm; - epsilonForm = new Forest.Ref(); + epsilonForm = new Forest.Many(); for(Sequence s : this) { // FIXME FIXME FIXME if (new Walk.Cache().possiblyEpsilon(s))