From 0040f420f5cc9a8daf8e7ebb2899dec88fdd7214 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Sun, 26 Mar 2017 23:00:10 -0400 Subject: Update trees --- BJC-Utils2/src/main/java/bjc/utils/data/ITree.java | 167 +++++++++++++-------- 1 file changed, 102 insertions(+), 65 deletions(-) (limited to 'BJC-Utils2/src/main/java/bjc/utils/data/ITree.java') diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/ITree.java b/BJC-Utils2/src/main/java/bjc/utils/data/ITree.java index 30d5558..2ccebae 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/data/ITree.java +++ b/BJC-Utils2/src/main/java/bjc/utils/data/ITree.java @@ -1,7 +1,7 @@ package bjc.utils.data; -import bjc.utils.funcdata.IList; import bjc.utils.funcdata.bst.TreeLinearizationMethod; +import bjc.utils.functypes.ListFlattener; import java.util.function.Consumer; import java.util.function.Function; @@ -9,11 +9,12 @@ import java.util.function.Predicate; import java.util.function.UnaryOperator; /** - * A node in a homogeneous tree with a unlimited amount of children + * A node in a homogeneous tree with a unlimited amount of children. * * @author ben + * * @param - * The type of data contained in the tree nodes + * The type of data contained in the tree nodes. * */ public interface ITree { @@ -23,166 +24,202 @@ public interface ITree { * @param child * The child to append to this node. */ - public void addChild(ITree child); + void addChild(ITree child); /** * Prepend a child to this node. * - * @param child The child to prepend to this node. + * @param child + * The child to prepend to this node. */ void prependChild(ITree child); - + /** - * Collapse a tree into a single version + * Collapse a tree into a single version. * * @param - * The intermediate type being folded + * The intermediate type being folded. + * * @param - * The type that is the end result + * The type that is the end result. + * * @param leafTransform - * The function to use to convert leaf values + * The function to use to convert leaf values. + * * @param nodeCollapser * The function to use to convert internal nodes and - * their children + * their children. + * * @param resultTransformer * The function to use to convert a state to the returned - * version - * @return The final transformed state + * version. + * + * @return The final transformed state. */ - public ReturnedType collapse(Function leafTransform, - Function, NewType>> nodeCollapser, + ReturnedType collapse(Function leafTransform, + Function> nodeCollapser, Function resultTransformer); /** - * Execute a given action for each of this tree's children + * Execute a given action for each of this tree's children. * * @param action - * The action to execute for each child + * 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 + * 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 + * The function to use to map values into trees. + * + * @return A tree, with some nodes expanded into trees. */ - public ITree flatMapTree(Function> mapper); + default ITree flatMapTree(Function> mapper) { + return topDownTransform((dat) -> TopDownTransformResult.PUSHDOWN, (node) -> { + if (node.getChildrenCount() > 0) { + ITree parent = node.transformHead(mapper); + + node.doForChildren(parent::addChild); + + return parent; + } + + return node.transformHead(mapper); + }); + } /** - * Get the specified child of this tree + * Get the specified child of this tree. * * @param childNo - * The number of the child to get - * @return The specified child of this tree + * The number of the child to get. + * + * @return The specified child of this tree. */ default ITree getChild(int childNo) { return transformChild(childNo, (child) -> child); } /** - * Get a count of the number of direct children this node has + * Get a count of the number of direct children this node has. * - * @return The number of direct children this node has + * @return The number of direct children this node has. */ - public int getChildrenCount(); + int getChildrenCount(); /** - * Get the data stored in this node + * Get the data stored in this node. * - * @return 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 + * Rebuild the tree with the same structure, but different nodes. * * @param - * The type of the new tree + * The type of the new tree. + * * @param leafTransformer - * The function to use to transform leaf tokens + * 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 + * The function to use to transform internal tokens. + * + * @return The tree, with the nodes changed. */ - public ITree rebuildTree(Function leafTransformer, + ITree rebuildTree(Function leafTransformer, Function operatorTransformer); /** - * Transform some of the nodes in this tree + * Transform some of the nodes in this tree. * * @param nodePicker - * The predicate to use to pick nodes to transform + * The predicate to use to pick nodes to transform. + * * @param transformer - * The function to use to transform picked nodes + * The function to use to transform picked nodes. */ - public void selectiveTransform(Predicate nodePicker, UnaryOperator transformer); + void selectiveTransform(Predicate nodePicker, UnaryOperator transformer); /** - * Do a top-down transform of the tree + * Do a top-down transform of the tree. * * @param transformPicker - * The function to use to pick how to progress + * 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 + * The function used to transform picked subtrees. + * + * @return The tree with the transform applied to picked subtrees. */ - public ITree topDownTransform(Function transformPicker, + ITree topDownTransform(Function transformPicker, UnaryOperator> transformer); /** - * Transform one of this nodes children + * Transform one of this nodes children. * * @param - * The type of the transformed value + * The type of the transformed value. + * * @param childNo - * The number of the child to transform + * The number of the child to transform. + * * @param transformer - * The function to use to transform the value - * @return The transformed value + * The function to use to transform the value. + * + * @return The transformed value. * * @throws IllegalArgumentException * if the childNo is out of bounds (0 <= childNo <= - * childCount()) + * childCount()). */ - public TransformedType transformChild(int childNo, + TransformedType transformChild(int childNo, Function, TransformedType> transformer); /** - * Transform the value that is the head of this node + * Transform the value that is the head of this node. * * @param - * The type of the transformed value + * The type of the transformed value. + * * @param transformer - * The function to use to transform the value - * @return The transformed value + * The function to use to transform the value. + * + * @return The transformed value. */ - public TransformedType transformHead(Function transformer); + TransformedType transformHead(Function transformer); /** - * Transform the tree into a tree with a different type of token + * Transform the tree into a tree with a different type of token. * * @param - * The type of the new tree + * The type of the new tree. + * * @param transformer - * The function to use to transform tokens - * @return A tree with the token types transformed + * The function to use to transform tokens. + * + * @return A tree with the token types transformed. */ - public ITree transformTree(Function transformer); + default ITree transformTree(Function transformer) { + return rebuildTree(transformer, transformer); + } /** - * Perform an action on each part of the tree + * Perform an action on each part of the tree. * * @param linearizationMethod - * The way to traverse the tree + * The way to traverse the tree. + * * @param action - * The action to perform on each tree node + * The action to perform on each tree node. */ - public void traverse(TreeLinearizationMethod linearizationMethod, Consumer action); + void traverse(TreeLinearizationMethod linearizationMethod, Consumer action); /** * Find the farthest to right child that satisfies the given predicate. -- cgit v1.2.3