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. --- src/main/java/bjc/data/ITree.java | 278 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 278 insertions(+) create mode 100644 src/main/java/bjc/data/ITree.java (limited to 'src/main/java/bjc/data/ITree.java') diff --git a/src/main/java/bjc/data/ITree.java b/src/main/java/bjc/data/ITree.java new file mode 100644 index 0000000..4088c10 --- /dev/null +++ b/src/main/java/bjc/data/ITree.java @@ -0,0 +1,278 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.function.UnaryOperator; + +import bjc.funcdata.IList; +import bjc.funcdata.bst.TreeLinearizationMethod; + +/** + * A node in a homogeneous tree with a unlimited amount of children. + * + * @author ben + * + * @param + * The type of data contained in the tree nodes. + * + */ +public interface ITree { + /** + * Append a child to this node. + * + * @param child + * The child to append to this node. + */ + void addChild(ITree child); + + /** + * Append a child to this node. + * + * @param child + * The child to append to this node. + */ + void addChild(ContainedType child); + + /** + * Prepend a child to this node. + * + * @param child + * The child to prepend to this node. + */ + void prependChild(ITree child); + + /** + * Collapse a tree into a single version. + * + * @param + * The intermediate type being folded. + * + * @param + * 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. + */ + ReturnedType collapse(Function leafTransform, + BiFunction, NewType> nodeCollapser, + Function resultTransformer); + + /** + * Execute a given action for each of this tree's children. + * + * @param action + * The action to execute for each child. + */ + void doForChildren(Consumer> 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. + */ + default ITree flatMapTree(final Function> mapper) { + return topDownTransform(dat -> TopDownTransformResult.PUSHDOWN, node -> { + if(node.getChildrenCount() > 0) { + final ITree parent = node.transformHead(mapper); + + node.doForChildren(parent::addChild); + + return parent; + } + + return node.transformHead(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 getChild(final 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. + */ + int getChildrenCount(); + + /** + * Get a count of the number of direct children this node has. + * + * @return The number of direct children this node has. + */ + default int size() { + return 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 + * The type of the new tree. + * + * @param leafTransformer + * The function to use to transform leaf tokens. + * + * @param internalTransformer + * The function to use to transform internal tokens. + * + * @return The tree, with the nodes changed. + */ + ITree rebuildTree(Function leafTransformer, + Function internalTransformer); + + /** + * 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. + */ + void selectiveTransform(Predicate nodePicker, UnaryOperator 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. + */ + ITree topDownTransform(Function transformPicker, + UnaryOperator> transformer); + + /** + * Transform one of this nodes children. + * + * @param + * 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()). + */ + TransformedType transformChild(int childNo, + Function, TransformedType> transformer); + + /** + * Transform the value that is the head of this node. + * + * @param + * The type of the transformed value. + * + * @param transformer + * The function to use to transform the value. + * + * @return The transformed value. + */ + TransformedType transformHead(Function transformer); + + /** + * Transform the tree into a tree with a different type of token. + * + * @param + * The type of the new tree. + * + * @param transformer + * The function to use to transform tokens. + * + * @return A tree with the token types transformed. + */ + default ITree transformTree(final Function transformer) { + return rebuildTree(transformer, 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. + */ + void traverse(TreeLinearizationMethod linearizationMethod, Consumer action); + + /** + * Find the farthest to right child that satisfies the given predicate. + * + * @param childPred + * The predicate to satisfy. + * + * @return The index of the right-most child that satisfies the + * predicate, or -1 if one doesn't exist. + */ + int revFind(Predicate> childPred); + + /** + * Check if this tree contains any nodes that satisfy the predicate. + * + * @param pred + * The predicate to look for. + * + * @return Whether or not any items satisfied the predicate. + */ + default boolean containsMatching(Predicate pred) { + Toggle tog = new OneWayToggle<>(false, true); + + traverse(TreeLinearizationMethod.POSTORDER, (val) -> { + if(pred.test(val)) tog.get(); + }); + + return tog.get(); + } + + /** + * Set the head of the tree. + * + * @param dat + * The value to set as the head of the tree. + */ + void setHead(ContainedType dat); +} -- cgit v1.2.3