From 843329de434bb334d90927c4d22345373a388530 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Tue, 2 Jul 2019 18:05:22 -0400 Subject: Rename package root The package root is now bjc, not io.github.bculkin2442. --- .../java/bjc/data/TopDownTransformIterator.java | 272 +++++++++++++++++++++ 1 file changed, 272 insertions(+) create mode 100644 src/main/java/bjc/data/TopDownTransformIterator.java (limited to 'src/main/java/bjc/data/TopDownTransformIterator.java') diff --git a/src/main/java/bjc/data/TopDownTransformIterator.java b/src/main/java/bjc/data/TopDownTransformIterator.java new file mode 100644 index 0000000..5aa2409 --- /dev/null +++ b/src/main/java/bjc/data/TopDownTransformIterator.java @@ -0,0 +1,272 @@ +package bjc.data; + +import static bjc.data.TopDownTransformResult.RTRANSFORM; + +import java.util.Deque; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.NoSuchElementException; +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; + +/* + * @TODO 10/11/17 Ben Culkin :TopDownStep + * + * Figure out what is broken with this, and fix it so that step-wise + * iteration works correctly. + */ + +/** + * An iterative top-down transform of a tree. + * + * @author EVE + * + * @param + * The type of the nodes in the tree. + */ +public class TopDownTransformIterator implements Iterator> { + /** + * Alias type for a tree transformation. + * + * @author student + * + * @param + * The type contained in the tree. + */ + public interface TreeTransform + extends BiFunction, Consumer>>, ITree> { + + } + + /* + * The function that picks how to transform a given node + */ + private final Function picker; + /* + * The transform to apply to a given node. + */ + private final TreeTransform transform; + + private ITree preParent; + private ITree postParent; + + private final Deque> preChildren; + private final Deque> postChildren; + + private TopDownTransformIterator curChild; + + private boolean done; + private boolean initial; + + private final Deque>> toYield; + private Iterator> currYield; + + /** + * Create a new tree iterator. + * + * @param pickr + * The function to use to pick how to process nodes. + * @param transfrm + * The transform to apply to the nodes. + * @param tree + * The tree to transform. + */ + public TopDownTransformIterator(final Function pickr, + final TreeTransform transfrm, final ITree tree) { + preParent = tree; + + preChildren = new LinkedList<>(); + postChildren = new LinkedList<>(); + toYield = new LinkedList<>(); + + picker = pickr; + transform = transfrm; + + done = false; + initial = true; + } + + /** + * Add a set of nodes to yield. + * + * @param src + * The nodes to yield. + */ + public void addYield(final Iterator> src) { + if (currYield != null) { + toYield.push(currYield); + } + + currYield = src; + } + + @Override + public boolean hasNext() { + return !done; + } + + /** + * Get the next yielded value. + * + * @param val + * The sentinel value to yield. + * + * @return The next yielded value. + */ + public ITree flushYields(final ITree val) { + if (currYield != null) { + /* + * We have non-sentinel values to yield. + */ + + /* + * Add the sentinel to yield later. + */ + toYield.add(new SingleIterator<>(val)); + + if (currYield.hasNext()) { + return currYield.next(); + } + + while (toYield.size() != 0 && !currYield.hasNext()) { + currYield = toYield.pop(); + } + + if (toYield.size() == 0 && !currYield.hasNext()) { + currYield = null; + return val; + } + + return currYield.next(); + } + + return val; + } + + @Override + public ITree next() { + if (done) + throw new NoSuchElementException(); + + /* + * Flush any values that need to be yielded. + */ + if (currYield != null) { + ITree yeld = flushYields(null); + + if (yeld != null) + return yeld; + } + + if (initial) { + /* + * Get the way we are transforming. + */ + final TopDownTransformResult res = picker.apply(preParent.getHead()); + + switch (res) { + case PASSTHROUGH: + postParent = new Tree<>(preParent.getHead()); + + if (preParent.getChildrenCount() != 0) { + for (int i = 0; i < preParent.getChildrenCount(); i++) { + preChildren.add(preParent.getChild(i)); + } + + // Return whatever the first child is + break; + } + + done = true; + return flushYields(postParent); + case SKIP: + done = true; + return flushYields(preParent); + case TRANSFORM: + done = true; + return flushYields(transform.apply(preParent, this::addYield)); + case RTRANSFORM: + preParent = transform.apply(preParent, this::addYield); + return flushYields(preParent); + case PUSHDOWN: + if (preParent.getChildrenCount() != 0) { + for (int i = 0; i < preParent.getChildrenCount(); i++) { + preChildren.add(preParent.getChild(i)); + } + + // Return whatever the first child is + break; + } + + done = true; + return flushYields(transform.apply(new Tree<>(preParent.getHead()), this::addYield)); + case PULLUP: + final ITree intRes = transform.apply(preParent, this::addYield); + + postParent = new Tree<>(intRes.getHead()); + + if (intRes.getChildrenCount() != 0) { + for (int i = 0; i < intRes.getChildrenCount(); i++) { + preChildren.add(intRes.getChild(i)); + } + + // Return whatever the first child is + break; + } + + done = true; + return flushYields(postParent); + default: + throw new IllegalArgumentException("Unknown result type " + res); + } + + if (res != RTRANSFORM) { + initial = false; + } + } + + if (curChild == null || !curChild.hasNext()) { + if (preChildren.size() != 0) { + curChild = new TopDownTransformIterator<>(picker, transform, preChildren.pop()); + + final ITree res = curChild.next(); + //System.out.println("\t\tTRACE: adding node " + res + " to children"); + postChildren.add(res); + + return flushYields(res); + } + + ITree res = null; + + if (postParent == null) { + res = new Tree<>(preParent.getHead()); + + //System.out.println("\t\tTRACE: adding nodes " + postChildren + " to " + res); + + for (final ITree child : postChildren) { + res.addChild(child); + } + + // res = transform.apply(res, + // this::addYield); + } else { + res = postParent; + + //System.out.println("\t\tTRACE: adding nodes " + postChildren + " to " + res); + for (final ITree child : postChildren) { + res.addChild(child); + } + } + + done = true; + return flushYields(res); + } + + final ITree res = curChild.next(); + //System.out.println("\t\tTRACE: adding node " + res + " to children"); + postChildren.add(res); + + return flushYields(res); + } +} -- cgit v1.2.3