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/ITree.java | 234 +++++++++++++++++++++++++++ 1 file changed, 234 insertions(+) create mode 100644 base/src/main/java/bjc/utils/data/ITree.java (limited to 'base/src/main/java/bjc/utils/data/ITree.java') diff --git a/base/src/main/java/bjc/utils/data/ITree.java b/base/src/main/java/bjc/utils/data/ITree.java new file mode 100644 index 0000000..ff374e8 --- /dev/null +++ b/base/src/main/java/bjc/utils/data/ITree.java @@ -0,0 +1,234 @@ +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.bst.TreeLinearizationMethod; +import bjc.utils.functypes.ListFlattener; + +/** + * 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); + + /** + * 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, + Function> 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 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 operatorTransformer + * The function to use to transform internal tokens. + * + * @return The tree, with the nodes changed. + */ + ITree rebuildTree(Function leafTransformer, + Function 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. + */ + 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); +} -- cgit v1.2.3