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 --- BJC-Utils2/src/main/java/bjc/utils/data/Tree.java | 390 ---------------------- 1 file changed, 390 deletions(-) delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/Tree.java (limited to 'BJC-Utils2/src/main/java/bjc/utils/data/Tree.java') diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java b/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java deleted file mode 100644 index a52f699..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java +++ /dev/null @@ -1,390 +0,0 @@ -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