diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/data')
3 files changed, 555 insertions, 0 deletions
diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/ITree.java b/BJC-Utils2/src/main/java/bjc/utils/data/ITree.java new file mode 100644 index 0000000..7d5988f --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/ITree.java @@ -0,0 +1,189 @@ +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.IList; +import bjc.utils.funcdata.bst.TreeLinearizationMethod; + +/** + * A node in a homogenous tree with a unlimited amount of children + * + * @author ben + * @param <ContainedType> + * The type of data contained in the tree nodes + * + */ +public interface ITree<ContainedType> { + /** + * Add a child to this node + * + * @param child + * The child to add to this node + */ + public void addChild(ITree<ContainedType> child); + + /** + * Collapse a tree into a single version + * + * @param <NewType> + * The intermediate type being folded + * @param <ReturnedType> + * The type that is the end result + * @param leafTransform + * The function to use to convert leaf values + * @param nodeCollapser + * The function to use to convert internal nodes and their + * children + * @param resultTransformer + * The function to use to convert a state to the returned + * version + * @return The final transformed state + */ + public <NewType, ReturnedType> ReturnedType collapse( + Function<ContainedType, NewType> leafTransform, + Function<ContainedType, + Function<IList<NewType>, NewType>> nodeCollapser, + Function<NewType, ReturnedType> resultTransformer); + + /** + * Execute a given action for each of this tree's children + * + * @param action + * The action to execute for each child + */ + void doForChildren(Consumer<ITree<ContainedType>> action); + + /** + * Expand the nodes of a tree into trees, and then merge the contents + * of those trees into a single tree + * + * @param mapper + * The function to use to map values into trees + * @return A tree, with some nodes expanded into trees + */ + public ITree<ContainedType> flatMapTree( + Function<ContainedType, ITree<ContainedType>> mapper); + + /** + * Get the specified child of this tree + * + * @param childNo + * The number of the child to get + * @return The specified child of this tree + */ + default ITree<ContainedType> getChild(int childNo) { + return transformChild(childNo, (child) -> child); + } + + /** + * Get a count of the number of direct children this node has + * + * @return The number of direct children this node has + */ + public int getChildrenCount(); + + /** + * Get the data stored in this node + * + * @return The data stored in this node + */ + default ContainedType getHead() { + return transformHead((head) -> head); + } + + /** + * Rebuild the tree with the same structure, but different nodes + * + * @param <MappedType> + * The type of the new tree + * @param leafTransformer + * The function to use to transform leaf tokens + * @param operatorTransformer + * The function to use to transform internal tokens + * @return The tree, with the nodes changed + */ + public <MappedType> ITree<MappedType> rebuildTree( + Function<ContainedType, MappedType> leafTransformer, + Function<ContainedType, MappedType> operatorTransformer); + + /** + * Transform some of the nodes in this tree + * + * @param nodePicker + * The predicate to use to pick nodes to transform + * @param transformer + * The function to use to transform picked nodes + */ + public void selectiveTransform(Predicate<ContainedType> nodePicker, + UnaryOperator<ContainedType> transformer); + + /** + * Do a top-down transform of the tree + * + * @param transformPicker + * The function to use to pick how to progress + * @param transformer + * The function used to transform picked subtrees + * @return The tree with the transform applied to picked subtrees + */ + public ITree<ContainedType> topDownTransform( + Function<ContainedType, + TopDownTransformResult> transformPicker, + UnaryOperator<ITree<ContainedType>> transformer); + + /** + * Transform one of this nodes children + * + * @param <TransformedType> + * The type of the transformed value + * @param childNo + * The number of the child to transform + * @param transformer + * The function to use to transform the value + * @return The transformed value + * + * @throws IllegalArgumentException + * if the childNo is out of bounds (0 <= childNo <= + * childCount()) + */ + public <TransformedType> TransformedType transformChild(int childNo, + Function<ITree<ContainedType>, TransformedType> transformer); + + /** + * Transform the value that is the head of this node + * + * @param <TransformedType> + * The type of the transformed value + * @param transformer + * The function to use to transform the value + * @return The transformed value + */ + public <TransformedType> TransformedType transformHead( + Function<ContainedType, TransformedType> transformer); + + /** + * Transform the tree into a tree with a different type of token + * + * @param <MappedType> + * The type of the new tree + * @param transformer + * The function to use to transform tokens + * @return A tree with the token types transformed + */ + public <MappedType> ITree<MappedType> transformTree( + Function<ContainedType, MappedType> transformer); + + /** + * Perform an action on each part of the tree + * + * @param linearizationMethod + * The way to traverse the tree + * @param action + * The action to perform on each tree node + */ + public void traverse(TreeLinearizationMethod linearizationMethod, + Consumer<ContainedType> action); +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/TopDownTransformResult.java b/BJC-Utils2/src/main/java/bjc/utils/data/TopDownTransformResult.java new file mode 100644 index 0000000..a2448d2 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/TopDownTransformResult.java @@ -0,0 +1,30 @@ +package bjc.utils.data; + +/** + * Represents the results for doing a top-down transform of a tree + * + * @author ben + * + */ +public enum TopDownTransformResult { + /** + * Do not do anything to this node, and ignore it's children + */ + SKIP, + /** + * Transform this node, and don't touch its children + */ + TRANSFORM, + /** + * Ignore this node, and traverse its children + */ + PASSTHROUGH, + /** + * Traverse this nodes children, then transform it + */ + PUSHDOWN, + /** + * Transform this node, then traverse its children + */ + PULLUP; +} 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 <ContainedType> + */ +public class Tree<ContainedType> implements ITree<ContainedType> { + private ContainedType data; + private IList<ITree<ContainedType>> 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<ITree<ContainedType>> 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<ContainedType>... childrn) { + data = leafToken; + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for (ITree<ContainedType> child : childrn) { + children.add(child); + + childCount++; + } + } + + @Override + public void addChild(ITree<ContainedType> child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public <NewType, ReturnedType> ReturnedType collapse( + Function<ContainedType, NewType> leafTransform, + Function<ContainedType, + Function<IList<NewType>, NewType>> nodeCollapser, + Function<NewType, ReturnedType> resultTransformer) { + + return resultTransformer + .apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override + public void doForChildren(Consumer<ITree<ContainedType>> action) { + children.forEach(action); + } + + @Override + public ITree<ContainedType> flatMapTree( + Function<ContainedType, ITree<ContainedType>> mapper) { + if (hasChildren) { + ITree<ContainedType> 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> NewType internalCollapse( + Function<ContainedType, NewType> leafTransform, + Function<ContainedType, + Function<IList<NewType>, NewType>> nodeCollapser) { + if (hasChildren) { + Function<IList<NewType>, + NewType> nodeTransformer = nodeCollapser.apply(data); + + IList<NewType> collapsedChildren = (IList<NewType>) 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<ContainedType>) child).internalToString(builder, + indentLevel + 2, false); + }); + } + } + + @Override + public <MappedType> ITree<MappedType> rebuildTree( + Function<ContainedType, MappedType> leafTransformer, + Function<ContainedType, MappedType> operatorTransformer) { + if (hasChildren) { + IList<ITree<MappedType>> 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<ContainedType> nodePicker, + UnaryOperator<ContainedType> transformer) { + if (hasChildren) { + children.forEach((child) -> child + .selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public ITree<ContainedType> topDownTransform( + Function<ContainedType, + TopDownTransformResult> transformPicker, + UnaryOperator<ITree<ContainedType>> transformer) { + TopDownTransformResult transformResult = transformPicker + .apply(data); + + switch (transformResult) { + case PASSTHROUGH: + ITree<ContainedType> 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<ContainedType> 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> TransformedType transformChild(int childNo, + Function<ITree<ContainedType>, 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> TransformedType transformHead( + Function<ContainedType, TransformedType> transformer) { + return transformer.apply(data); + } + + @Override + public <MappedType> ITree<MappedType> transformTree( + Function<ContainedType, MappedType> transformer) { + if (hasChildren) { + IList<ITree<MappedType>> 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<ContainedType> 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); + } + } +} |