From 4ca0bc9a5bf2519c0e2cff2e988a6a7ffc6c7d9e Mon Sep 17 00:00:00 2001 From: adam Date: Sat, 15 Jul 2006 02:13:49 -0400 Subject: [PATCH] checkpoint darcs-hash:20060715061349-5007d-b25ab8b30dc59657025911f0107769412b8e0da9.gz --- src/edu/berkeley/sbp/Forest.java | 142 +++++----------------------- src/edu/berkeley/sbp/util/TreeBuilder.java | 4 +- 2 files changed, 25 insertions(+), 121 deletions(-) diff --git a/src/edu/berkeley/sbp/Forest.java b/src/edu/berkeley/sbp/Forest.java index 634d6ad..00f826a 100644 --- a/src/edu/berkeley/sbp/Forest.java +++ b/src/edu/berkeley/sbp/Forest.java @@ -7,51 +7,14 @@ import java.util.*; import java.lang.reflect.*; /** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */ -public abstract class Forest /*extends PrintableTree>*/ - implements Visitable>, - IntegerMappable, +public abstract class Forest /*extends PrintableTree>*/ + implements IntegerMappable, GraphViz.ToGraphViz { private static int master_idx = 0; private final int idx = master_idx++; public int toInt() { return idx; } - public abstract void expand(TaskList tl, HashSet> ht); - public abstract void gather(TaskList tl, HashSet>[] ht, HashSet> target); - - public static class TaskList extends ArrayList { - public interface Task { - public void perform(); - } - public class ExpandTask implements Task { - private Forest f; - private HashSet hs; - public ExpandTask(Forest f, HashSet hs) { this.f = f; this.hs = hs; } - public void perform() { f.expand(TaskList.this, hs); } - } - public class GatherTask implements Task { - private Forest f; - private HashSet[] ht; - private HashSet hs; - public GatherTask(Forest f, HashSet>[] ht, HashSet> hs) { this.f = f; this.hs = hs; this.ht = ht;} - public void perform() { f.gather(TaskList.this, ht, hs); } - } - public void expand(Forest f, HashSet hs) { - add(new ExpandTask(f, hs)); - } - public void gather(Forest f, HashSet[] ht, HashSet hs) { - add(new GatherTask(f, ht, hs)); - } - public void run() { - while(true) { - if (isEmpty()) return; - Task task = get(size()-1); - remove(size()-1); - task.perform(); - } - } - } - /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */ public final Tree expand1() throws Ambiguous, ParseFailed { try { @@ -62,13 +25,10 @@ public abstract class Forest /*extends PrintableTree>*/ } /** expand this forest into a set of trees */ + public abstract void expand(HashSet> ht); public HashSet> expand(boolean toss) { - TaskList tl = new TaskList(); HashSet> ret = new HashSet>(); - tl.expand(this, ret); - tl.run(); - - if (toss && ret.size() > 1) throw new InnerAmbiguous(this); + expand(ret); return ret; } @@ -79,16 +39,13 @@ public abstract class Forest /*extends PrintableTree>*/ static Forest leaf(Input.Region loc, T tag) { return create(loc, tag, null, false); } public static Forest create(Input.Region loc, T tag, Forest[] tokens, boolean unwrap) { - return new MyBody(loc, tag, tokens, unwrap); + return new Body(loc, tag, tokens, unwrap); } // Body ////////////////////////////////////////////////////////////////////////////// - public /*protected*/ static interface Body extends GraphViz.ToGraphViz { - void expand(int i, TreeBuilder h); - } public abstract void edges(GraphViz.Node n); public boolean ambiguous() { return false; } - public /*protected*/ static class MyBody extends Forest implements Body /* extends PrintableTree> implements */ { + public /*protected*/ static class Body extends Forest /* extends PrintableTree> implements */ { private final Input.Region location; private final T tag; @@ -119,11 +76,7 @@ public abstract class Forest /*extends PrintableTree>*/ } } - public void visit(Invokable,B,C> ivbc, B b, C c) { - ivbc.invoke(this, b, c); - } - - private MyBody(Input.Region loc, T tag, Forest[] tokens, boolean unwrap) { + private Body(Input.Region loc, T tag, Forest[] tokens, boolean unwrap) { this.location = loc; this.tag = tag; this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length]; @@ -131,63 +84,21 @@ public abstract class Forest /*extends PrintableTree>*/ if (tokens != null) for(int i=0; i>[] ht, HashSet> target) { - gather(tl, ht, target, new Tree[ht.length], 0); + + public void expand(HashSet> ht) { + expand(0, new Tree[tokens.length], ht); } - private void gather(TaskList tl, HashSet>[] ht, HashSet> target, Tree[] trees, int i) { - if (i==ht.length) { - target.add(new Tree(location, tag, trees, unwrap)); + public void expand(final int i, Tree[] ta, HashSet> ht) { + if (i==tokens.length) { + ht.add(new Tree(location, tag, ta, unwrap)); return; } - for(Tree tree : ht[i]) { - /* - if (unwrap && i==trees.length-1) { - // I think this is wrong - Tree[] trees2 = new Tree[trees.length - 1 + tree.numChildren()]; - System.arraycopy(trees, 0, trees2, 0, trees.length-1); - for(int j=0; j(location, tag, trees2)); - } else { - */ - trees[i] = tree; - gather(tl, ht, target, trees, i+1); - trees[i] = null; - //} - } - } - public void expand(TaskList tl, HashSet> ht) { - HashSet>[] children = new HashSet[tokens.length]; - tl.gather(this, children, ht); - for(int i=0; i>(); - tl.expand(tokens[i], children[i]); - } - } - - public void expand(final int i, final TreeBuilder h) { - if (i==0) h.start(tag, location); - - if (i==tokens.length) { - h.finish(tag, location); - - /* - } else if (unwrap && i==tokens.length-1) { - if (tokens[i] != null) - tokens[i].visit(h, null, 0); - */ - - } else { - tokens[i].visit(new TreeBuilder(h.toss) { - public void start(T head, Input.Region loc) { } - public void addTree(Tree t) { toks.add(t); } - public void finish(T head, Input.Region loc) { - int old = h.toks.size(); - h.addTree(new Tree(loc, head, toks.toArray(tree_hint), unwrap)); - expand(i+1, h); - while(h.toks.size() > old) h.toks.remove(h.toks.size()-1); - } - }, null, null); + HashSet> ht2 = new HashSet>(); + tokens[i].expand(ht2); + for(Tree tc : ht2) { + ta[i] = tc; + expand(i+1, ta, ht); + ta[i] = null; } } @@ -207,11 +118,9 @@ public abstract class Forest /*extends PrintableTree>*/ * viewed, it becomes immutable */ static class Ref extends Forest { - public void expand(TaskList tl, HashSet> ht) { - for (Forest f : hp) f.expand(tl, ht); - } - public void gather(TaskList tl, HashSet>[] ht, HashSet> target) { - throw new Error(); + public void expand(HashSet> ht) { + for (Forest f : hp) + f.expand(ht); } public HashSet parents = new HashSet(); public boolean contains(Forest f) { @@ -247,16 +156,9 @@ public abstract class Forest /*extends PrintableTree>*/ return n; } - public void visit(Invokable,B,C> ivbc, B b, C c) { - if (hp==null) return; - for(Forest f : hp) - f.visit(ivbc, b, c); - } public Forest resolve() { return this; } } - public abstract void visit(Invokable,B,C> ivbc, B b, C c); - // Statics ////////////////////////////////////////////////////////////////////////////// private static Tree[] tree_hint = new Tree[0]; diff --git a/src/edu/berkeley/sbp/util/TreeBuilder.java b/src/edu/berkeley/sbp/util/TreeBuilder.java index 9fae34f..7284018 100644 --- a/src/edu/berkeley/sbp/util/TreeBuilder.java +++ b/src/edu/berkeley/sbp/util/TreeBuilder.java @@ -2,7 +2,8 @@ package edu.berkeley.sbp.util; import edu.berkeley.sbp.*; import java.util.*; -public abstract class TreeBuilder implements Invokable,Boolean,Integer> { +public abstract class TreeBuilder /*implements Invokable,Boolean,Integer>*/ { + /* public ArrayList> toks = new ArrayList>(); public boolean toss; protected T head; @@ -20,4 +21,5 @@ public abstract class TreeBuilder implements Invokable,Boolean bod.expand(i, this); } } + */ } -- 1.7.10.4