From c82e3b3b2de0633317ec8fc85925e91422820597 Mon Sep 17 00:00:00 2001 From: "Benjamin J. Culkin" Date: Sun, 8 Oct 2017 22:39:59 -0300 Subject: Start splitting into maven modules --- base/src/main/java/bjc/utils/data/Tree.java | 390 ++++++++++++++++++++++++++++ 1 file changed, 390 insertions(+) create mode 100644 base/src/main/java/bjc/utils/data/Tree.java (limited to 'base/src/main/java/bjc/utils/data/Tree.java') diff --git a/base/src/main/java/bjc/utils/data/Tree.java b/base/src/main/java/bjc/utils/data/Tree.java new file mode 100644 index 0000000..a52f699 --- /dev/null +++ b/base/src/main/java/bjc/utils/data/Tree.java @@ -0,0 +1,390 @@ +package bjc.utils.data; + +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.function.UnaryOperator; + +import bjc.utils.funcdata.FunctionalList; +import bjc.utils.funcdata.IList; +import bjc.utils.funcdata.bst.TreeLinearizationMethod; +import bjc.utils.functypes.ListFlattener; + +/** + * A node in a homogeneous tree. + * + * @author ben + * + * @param + */ +public class Tree implements ITree { + private ContainedType data; + + private IList> children; + private boolean hasChildren; + private int childCount = 0; + + private int ID; + private static int nextID = 0; + + /** + * Create a new leaf node in a tree. + * + * @param leaf + * The data to store as a leaf node. + */ + public Tree(final ContainedType leaf) { + data = leaf; + + hasChildren = false; + + ID = nextID++; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + public Tree(final ContainedType leaf, final IList> childrn) { + this(leaf); + + hasChildren = true; + + childCount = childrn.getSize(); + + children = childrn; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + @SafeVarargs + public Tree(final ContainedType leaf, final ITree... childrn) { + this(leaf); + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for (final ITree child : childrn) { + children.add(child); + + childCount++; + } + } + + @Override + public void addChild(final ITree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public void prependChild(final ITree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.prepend(child); + } + + @Override + public void doForChildren(final Consumer> action) { + if (childCount > 0) { + children.forEach(action); + } + } + + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public int revFind(final Predicate> childPred) { + if (childCount == 0) + return -1; + else { + for (int i = childCount - 1; i >= 0; i--) { + if (childPred.test(getChild(i))) return i; + } + } + + return -1; + } + + @Override + public void traverse(final TreeLinearizationMethod linearizationMethod, final Consumer action) { + if (hasChildren) { + switch (linearizationMethod) { + case INORDER: + if (childCount != 2) { + final String msg = "Can only do in-order traversal for binary trees."; + + throw new IllegalArgumentException(msg); + } + + children.getByIndex(0).traverse(linearizationMethod, action); + + action.accept(data); + + children.getByIndex(1).traverse(linearizationMethod, action); + break; + case POSTORDER: + children.forEach((child) -> child.traverse(linearizationMethod, action)); + + action.accept(data); + break; + case PREORDER: + action.accept(data); + + children.forEach((child) -> child.traverse(linearizationMethod, action)); + break; + default: + break; + + } + } else { + action.accept(data); + } + } + + @Override + public ReturnedType collapse(final Function leafTransform, + final Function> nodeCollapser, + final Function resultTransformer) { + return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override + public ITree flatMapTree(final Function> mapper) { + if (hasChildren) { + final ITree flatMappedData = mapper.apply(data); + + final IList> mappedChildren = children + .map(child -> child.flatMapTree(mapper)); + + mappedChildren.forEach(child -> flatMappedData.addChild(child)); + + return flatMappedData; + } + + return mapper.apply(data); + } + + protected NewType internalCollapse(final Function leafTransform, + final Function> nodeCollapser) { + if (hasChildren) { + final Function, NewType> nodeTransformer = nodeCollapser.apply(data); + + final IList collapsedChildren = children.map(child -> { + final NewType collapsed = child.collapse(leafTransform, nodeCollapser, + subTreeVal -> subTreeVal); + + return collapsed; + }); + + return nodeTransformer.apply(collapsedChildren); + } + + return leafTransform.apply(data); + } + + protected void internalToString(final StringBuilder builder, final int indentLevel, final boolean initial) { + for (int i = 0; i < indentLevel; i++) { + builder.append(">\t"); + } + + builder.append("Node #"); + builder.append(ID); + builder.append(": "); + builder.append(data == null ? "(null)" : data.toString()); + builder.append("\n"); + + if (hasChildren) { + children.forEach(child -> { + if (child instanceof Tree) { + final Tree kid = (Tree) child; + + kid.internalToString(builder, indentLevel + 1, false); + } else { + for (int i = 0; i < indentLevel + 1; i++) { + builder.append(">\t"); + } + + builder.append("Unknown node\n"); + } + }); + } + } + + @Override + public ITree rebuildTree(final Function leafTransformer, + final Function operatorTransformer) { + if (hasChildren) { + final IList> mappedChildren = children.map(child -> { + return child.rebuildTree(leafTransformer, operatorTransformer); + }); + + return new Tree<>(operatorTransformer.apply(data), mappedChildren); + } + + return new Tree<>(leafTransformer.apply(data)); + } + + @Override + public void selectiveTransform(final Predicate nodePicker, + final UnaryOperator transformer) { + if (hasChildren) { + children.forEach(child -> child.selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public ITree topDownTransform( + final Function transformPicker, + final UnaryOperator> transformer) { + final TopDownTransformResult transformResult = transformPicker.apply(data); + + switch (transformResult) { + case PASSTHROUGH: + ITree result = new Tree<>(data); + + if (hasChildren) { + children.forEach(child -> { + final ITree kid = child.topDownTransform(transformPicker, + transformer); + + result.addChild(kid); + }); + } + + return result; + case SKIP: + return this; + case TRANSFORM: + return transformer.apply(this); + case RTRANSFORM: + return transformer.apply(this).topDownTransform(transformPicker, transformer); + case PUSHDOWN: + result = new Tree<>(data); + + if (hasChildren) { + children.forEach(child -> { + final ITree kid = child.topDownTransform(transformPicker, + transformer); + + result.addChild(kid); + }); + } + + return transformer.apply(result); + case PULLUP: + final ITree intermediateResult = transformer.apply(this); + + result = new Tree<>(intermediateResult.getHead()); + + intermediateResult.doForChildren(child -> { + final ITree kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + + return result; + default: + final String msg = String.format("Recieved unknown transform result %s", transformResult); + + throw new IllegalArgumentException(msg); + } + } + + @Override + public TransformedType transformChild(final int childNo, + final Function, TransformedType> transformer) { + if (childNo < 0 || childNo > childCount - 1) { + final String msg = String.format("Child index #%d is invalid", childNo); + + throw new IllegalArgumentException(msg); + } + + final ITree selectedKid = children.getByIndex(childNo); + + return transformer.apply(selectedKid); + } + + @Override + public TransformedType transformHead( + final Function transformer) { + return transformer.apply(data); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + childCount; + result = prime * result + (children == null ? 0 : children.hashCode()); + result = prime * result + (data == null ? 0 : data.hashCode()); + + return result; + } + + @Override + public String toString() { + final StringBuilder builder = new StringBuilder(); + + internalToString(builder, 1, true); + + builder.deleteCharAt(builder.length() - 1); + + return builder.toString(); + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof Tree)) return false; + + final Tree other = (Tree) obj; + + if (data == null) { + if (other.data != null) return false; + } else if (!data.equals(other.data)) return false; + + if (childCount != other.childCount) return false; + + if (children == null) { + if (other.children != null) return false; + } else if (!children.equals(other.children)) return false; + + return true; + } +} \ No newline at end of file -- cgit v1.2.3