From b0516949d7577b809c75d7267df77bff2cdb078b Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Mon, 3 Oct 2016 09:11:55 -0400 Subject: Minor reorganization --- BJC-Utils2/src/main/java/bjc/utils/data/Tree.java | 336 ++++++++++++++++++++++ 1 file changed, 336 insertions(+) create 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 new file mode 100644 index 0000000..46fb1a6 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java @@ -0,0 +1,336 @@ +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.funcutils.StringUtils; + +/** + * A node in a homogenous tree. + * + * @author ben + * + * @param + */ +public class Tree implements ITree { + private ContainedType data; + private IList> children; + + private boolean hasChildren; + + private int childCount = 0; + + /** + * Create a new leaf node in a tree + * + * @param leafToken + * The data to store as a leaf node + */ + public Tree(ContainedType leafToken) { + data = leafToken; + + hasChildren = false; + } + + /** + * Create a new tree node with the specified children + * + * @param leafToken + * The data to hold in this node + * @param childrn + * A list of children for this node + */ + public Tree(ContainedType leafToken, + IList> childrn) { + data = leafToken; + + hasChildren = true; + + childCount = childrn.getSize(); + + children = childrn; + } + + /** + * Create a new tree node with the specified children + * + * @param leafToken + * The data to hold in this node + * @param childrn + * A list of children for this node + */ + @SafeVarargs + public Tree(ContainedType leafToken, ITree... childrn) { + data = leafToken; + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for (ITree child : childrn) { + children.add(child); + + childCount++; + } + } + + @Override + public void addChild(ITree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public ReturnedType collapse( + Function leafTransform, + Function, NewType>> nodeCollapser, + Function resultTransformer) { + + return resultTransformer + .apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override + public void doForChildren(Consumer> action) { + children.forEach(action); + } + + @Override + public ITree flatMapTree( + Function> mapper) { + if (hasChildren) { + ITree flatMappedData = mapper.apply(data); + + children.map((child) -> child.flatMapTree(mapper)) + .forEach((child) -> flatMappedData.addChild(child)); + + return flatMappedData; + } + + return mapper.apply(data); + } + + @Override + public int getChildrenCount() { + return childCount; + } + + protected NewType internalCollapse( + Function leafTransform, + Function, NewType>> nodeCollapser) { + if (hasChildren) { + Function, + NewType> nodeTransformer = nodeCollapser.apply(data); + + IList collapsedChildren = (IList) children + .map((child) -> { + return child.collapse(leafTransform, nodeCollapser, + (subTreeVal) -> subTreeVal); + }); + + return nodeTransformer.apply(collapsedChildren); + } + + return leafTransform.apply(data); + } + + protected void internalToString(StringBuilder builder, int indentLevel, + boolean initial) { + if (!initial) { + StringUtils.indentNLevels(builder, indentLevel); + } + + builder.append("Node: "); + builder.append(data == null ? "(null)" : data.toString()); + builder.append("\n"); + + if (hasChildren) { + children.forEach((child) -> { + ((Tree) child).internalToString(builder, + indentLevel + 2, false); + }); + } + } + + @Override + public ITree rebuildTree( + Function leafTransformer, + Function operatorTransformer) { + if (hasChildren) { + 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(Predicate nodePicker, + UnaryOperator transformer) { + if (hasChildren) { + children.forEach((child) -> child + .selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public ITree topDownTransform( + Function transformPicker, + UnaryOperator> transformer) { + TopDownTransformResult transformResult = transformPicker + .apply(data); + + switch (transformResult) { + case PASSTHROUGH: + ITree result = new Tree<>(data); + + if (hasChildren) { + children.forEach((child) -> { + result.addChild(child.topDownTransform( + transformPicker, transformer)); + }); + } + + return result; + case SKIP: + return this; + case TRANSFORM: + return transformer.apply(this); + case PUSHDOWN: + result = new Tree<>(data); + + if (hasChildren) { + children.forEach((child) -> { + result.addChild(child.topDownTransform( + transformPicker, transformer)); + }); + } + + return transformer.apply(result); + case PULLUP: + ITree intermediateResult = transformer + .apply(this); + + result = new Tree<>(intermediateResult.getHead()); + + intermediateResult.doForChildren((child) -> { + result.addChild(child.topDownTransform(transformPicker, + transformer)); + }); + + return result; + default: + throw new IllegalArgumentException( + "Recieved unknown transform result " + + transformResult); + + } + } + + @Override + public String toString() { + StringBuilder builder = new StringBuilder(); + + internalToString(builder, 1, true); + + builder.deleteCharAt(builder.length() - 1); + + return builder.toString(); + } + + @Override + public TransformedType transformChild(int childNo, + Function, TransformedType> transformer) { + if (childNo < 0 || childNo > (childCount - 1)) { + throw new IllegalArgumentException( + "Child index #" + childNo + " is invalid"); + } + + return transformer.apply(children.getByIndex(childNo)); + } + + @Override + public TransformedType transformHead( + Function transformer) { + return transformer.apply(data); + } + + @Override + public ITree transformTree( + Function transformer) { + if (hasChildren) { + IList> transformedChildren = children + .map((child) -> child.transformTree(transformer)); + + return new Tree<>(transformer.apply(data), + transformedChildren); + } + + return new Tree<>(transformer.apply(data)); + } + + @Override + public void traverse(TreeLinearizationMethod linearizationMethod, + Consumer action) { + if (hasChildren) { + switch (linearizationMethod) { + case INORDER: + if (childCount != 2) { + throw new IllegalArgumentException( + "Can only do in-order traversal for binary trees."); + } + + 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); + } + } +} -- cgit v1.2.3