+ /** Depth-first expansion, handling .One and .Many without recursion. */
+ private static <NodeType> Tree<NodeType> expand1ForOneAndMany(
+ Forest<NodeType> forest) throws Ambiguous {
+ List<Tree<NodeType>> nodes = new ArrayList<Tree<NodeType>>();
+ List<Tree<NodeType>> build = new ArrayList<Tree<NodeType>>();
+
+ // path stack
+ List<Forest.One<NodeType>> path = new ArrayList<Forest.One<NodeType>>();
+ List<Integer> sizes = new ArrayList<Integer>(),
+ poss = new ArrayList<Integer>();
+
+ // handle the left-most leaf
+ expand1Descend(path, nodes, sizes, poss, forest);
+
+ for (Forest.One<NodeType> f; path.size() > 0;) {
+ // up one
+ f = pop(path);
+ int size = pop(sizes) + 1;
+ int pos = pop(poss) + 1;
+ Forest<NodeType>[] children = f.children;
+ if (pos < children.length) {
+ // down the next branch
+ path.add(f);
+ sizes.add(new Integer(size));
+ poss.add(new Integer(pos));
+
+ // handle the left-most leaf
+ expand1Descend(path, nodes, sizes, poss, children[pos]);
+ } else {
+ if (path.size() > 0 && peek(path).lifts[peek(poss)]) {
+ // skip assembling this node, lift children
+ sizes.add(pop(sizes) + size - 1);
+ continue;
+ }
+ // assemble this node
+ for (int i=size; i > 0; i--)
+ build.add(nodes.remove(nodes.size() - i));
+ nodes.add(new Tree<NodeType>(f.location, f.head, build));
+ build.clear();
+ }
+ }
+
+ return pop(nodes);
+ }
+
+ /** Descend to the left-most leaf, building the path. */
+ private static <NodeType> void expand1Descend(
+ List<Forest.One<NodeType>> path, List<Tree<NodeType>> nodes,
+ List<Integer> sizes, List<Integer> poss, Forest<NodeType> f)
+ throws Ambiguous {
+ while (true) {
+ if (f instanceof Forest.Many)
+ f = ((Forest.Many<NodeType>)f).simplify();
+ else if (f instanceof Forest.One) {
+ Forest.One<NodeType> one = (Forest.One<NodeType>)f;
+ if (one.children.length == 0)
+ break;
+ path.add(one);
+ sizes.add(0);
+ poss.add(0);
+ f = one.children[0];
+ } else {
+ nodes.add(f.expand1());
+ return;
+ }
+ }
+
+ if (path.size() > 0 && peek(path).lifts[peek(poss)])
+ sizes.add(pop(sizes) - 1); // ignore lifted leafs
+ else
+ nodes.add(f.expand1());
+ }
+
+ private static <T> T pop(List<T> list) {
+ return list.remove(list.size() - 1); }
+ private static <T> T peek(List<T> list) {
+ return list.get(list.size() - 1); }
+