diff options
3 files changed, 261 insertions, 199 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 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 <ContainedType> - * The type of data contained in the tree nodes + * The type of data contained in the tree nodes. * */ public interface ITree<ContainedType> { @@ -23,166 +24,202 @@ public interface ITree<ContainedType> { * @param child * The child to append to this node. */ - public void addChild(ITree<ContainedType> child); + void addChild(ITree<ContainedType> 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<ContainedType> child); - + /** - * Collapse a tree into a single version + * Collapse a tree into a single version. * * @param <NewType> - * The intermediate type being folded + * The intermediate type being folded. + * * @param <ReturnedType> - * 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 <NewType, ReturnedType> ReturnedType collapse(Function<ContainedType, NewType> leafTransform, - Function<ContainedType, Function<IList<NewType>, NewType>> nodeCollapser, + <NewType, ReturnedType> ReturnedType collapse(Function<ContainedType, NewType> leafTransform, + Function<ContainedType, ListFlattener<NewType>> nodeCollapser, Function<NewType, ReturnedType> 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<ITree<ContainedType>> 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<ContainedType> flatMapTree(Function<ContainedType, ITree<ContainedType>> mapper); + default ITree<ContainedType> flatMapTree(Function<ContainedType, ITree<ContainedType>> mapper) { + return topDownTransform((dat) -> TopDownTransformResult.PUSHDOWN, (node) -> { + if (node.getChildrenCount() > 0) { + ITree<ContainedType> 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<ContainedType> 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 <MappedType> - * 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 <MappedType> ITree<MappedType> rebuildTree(Function<ContainedType, MappedType> leafTransformer, + <MappedType> ITree<MappedType> rebuildTree(Function<ContainedType, MappedType> leafTransformer, Function<ContainedType, MappedType> 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<ContainedType> nodePicker, UnaryOperator<ContainedType> transformer); + void selectiveTransform(Predicate<ContainedType> nodePicker, UnaryOperator<ContainedType> 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<ContainedType> topDownTransform(Function<ContainedType, TopDownTransformResult> transformPicker, + ITree<ContainedType> topDownTransform(Function<ContainedType, TopDownTransformResult> transformPicker, UnaryOperator<ITree<ContainedType>> transformer); /** - * Transform one of this nodes children + * Transform one of this nodes children. * * @param <TransformedType> - * 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> TransformedType transformChild(int childNo, + <TransformedType> TransformedType transformChild(int childNo, Function<ITree<ContainedType>, TransformedType> transformer); /** - * Transform the value that is the head of this node + * Transform the value that is the head of this node. * * @param <TransformedType> - * 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> TransformedType transformHead(Function<ContainedType, TransformedType> transformer); + <TransformedType> TransformedType transformHead(Function<ContainedType, TransformedType> 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 <MappedType> - * 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 <MappedType> ITree<MappedType> transformTree(Function<ContainedType, MappedType> transformer); + default <MappedType> ITree<MappedType> transformTree(Function<ContainedType, MappedType> 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<ContainedType> action); + void traverse(TreeLinearizationMethod linearizationMethod, Consumer<ContainedType> action); /** * Find the farthest to right child that satisfies the given predicate. diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java b/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java index 3f8d258..d8e6e39 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java +++ b/BJC-Utils2/src/main/java/bjc/utils/data/Tree.java @@ -3,6 +3,7 @@ package bjc.utils.data; import bjc.utils.funcdata.FunctionalList; 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; @@ -27,10 +28,10 @@ public class Tree<ContainedType> implements ITree<ContainedType> { private static int nextID = 0; /** - * Create a new leaf node in a tree + * Create a new leaf node in a tree. * * @param leaf - * The data to store as a leaf node + * The data to store as a leaf node. */ public Tree(ContainedType leaf) { data = leaf; @@ -41,12 +42,13 @@ public class Tree<ContainedType> implements ITree<ContainedType> { } /** - * Create a new tree node with the specified children + * Create a new tree node with the specified children. * * @param leaf - * The data to hold in this node + * The data to hold in this node. + * * @param childrn - * A list of children for this node + * A list of children for this node. */ public Tree(ContainedType leaf, IList<ITree<ContainedType>> childrn) { this(leaf); @@ -59,12 +61,13 @@ public class Tree<ContainedType> implements ITree<ContainedType> { } /** - * Create a new tree node with the specified children + * Create a new tree node with the specified children. * * @param leaf - * The data to hold in this node + * The data to hold in this node. + * * @param childrn - * A list of children for this node + * A list of children for this node. */ @SafeVarargs public Tree(ContainedType leaf, ITree<ContainedType>... childrn) { @@ -76,7 +79,7 @@ public class Tree<ContainedType> implements ITree<ContainedType> { children = new FunctionalList<>(); - for(ITree<ContainedType> child : childrn) { + for (ITree<ContainedType> child : childrn) { children.add(child); childCount++; @@ -85,7 +88,7 @@ public class Tree<ContainedType> implements ITree<ContainedType> { @Override public void addChild(ITree<ContainedType> child) { - if(hasChildren == false) { + if (hasChildren == false) { hasChildren = true; children = new FunctionalList<>(); @@ -97,27 +100,92 @@ public class Tree<ContainedType> implements ITree<ContainedType> { } @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)); + public void prependChild(ITree<ContainedType> child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.prepend(child); } @Override public void doForChildren(Consumer<ITree<ContainedType>> action) { - if(childCount > 0) { + if (childCount > 0) { children.forEach(action); } } @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public int revFind(Predicate<ITree<ContainedType>> childPred) { + if (childCount == 0) { + return -1; + } else { + for (int i = childCount - 1; i >= 0; i--) { + if (childPred.test(getChild(i))) { + return i; + } + } + } + + return -1; + } + + @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); + } + } + + @Override + public <NewType, ReturnedType> ReturnedType collapse(Function<ContainedType, NewType> leafTransform, + Function<ContainedType, ListFlattener<NewType>> nodeCollapser, + Function<NewType, ReturnedType> resultTransformer) { + return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override public ITree<ContainedType> flatMapTree(Function<ContainedType, ITree<ContainedType>> mapper) { - if(hasChildren) { + if (hasChildren) { ITree<ContainedType> flatMappedData = mapper.apply(data); - children.map((child) -> child.flatMapTree(mapper)) - .forEach((child) -> flatMappedData.addChild(child)); + IList<ITree<ContainedType>> mappedChildren = children.map((child) -> child.flatMapTree(mapper)); + mappedChildren.forEach((child) -> flatMappedData.addChild(child)); return flatMappedData; } @@ -125,14 +193,9 @@ public class Tree<ContainedType> implements ITree<ContainedType> { 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<ContainedType, ListFlattener<NewType>> nodeCollapser) { + if (hasChildren) { Function<IList<NewType>, NewType> nodeTransformer = nodeCollapser.apply(data); IList<NewType> collapsedChildren = children.map((child) -> { @@ -149,7 +212,7 @@ public class Tree<ContainedType> implements ITree<ContainedType> { } protected void internalToString(StringBuilder builder, int indentLevel, boolean initial) { - for(int i = 0; i < indentLevel; i++) { + for (int i = 0; i < indentLevel; i++) { builder.append(">\t"); } @@ -159,9 +222,19 @@ public class Tree<ContainedType> implements ITree<ContainedType> { builder.append(data == null ? "(null)" : data.toString()); builder.append("\n"); - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> { - ((Tree<ContainedType>) child).internalToString(builder, indentLevel + 1, false); + if (child instanceof Tree<?>) { + Tree<ContainedType> kid = (Tree<ContainedType>) child; + + kid.internalToString(builder, indentLevel + 1, false); + } else { + for (int i = 0; i < indentLevel + 1; i++) { + builder.append(">\t"); + } + + builder.append("Unknown node\n"); + } }); } } @@ -169,7 +242,7 @@ public class Tree<ContainedType> implements ITree<ContainedType> { @Override public <MappedType> ITree<MappedType> rebuildTree(Function<ContainedType, MappedType> leafTransformer, Function<ContainedType, MappedType> operatorTransformer) { - if(hasChildren) { + if (hasChildren) { IList<ITree<MappedType>> mappedChildren = children.map((child) -> { return child.rebuildTree(leafTransformer, operatorTransformer); }); @@ -182,7 +255,7 @@ public class Tree<ContainedType> implements ITree<ContainedType> { @Override public void selectiveTransform(Predicate<ContainedType> nodePicker, UnaryOperator<ContainedType> transformer) { - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> child.selectiveTransform(nodePicker, transformer)); } else { data = transformer.apply(data); @@ -194,13 +267,15 @@ public class Tree<ContainedType> implements ITree<ContainedType> { UnaryOperator<ITree<ContainedType>> transformer) { TopDownTransformResult transformResult = transformPicker.apply(data); - switch(transformResult) { + switch (transformResult) { case PASSTHROUGH: ITree<ContainedType> result = new Tree<>(data); - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> { - result.addChild(child.topDownTransform(transformPicker, transformer)); + ITree<ContainedType> kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); }); } @@ -214,9 +289,11 @@ public class Tree<ContainedType> implements ITree<ContainedType> { case PUSHDOWN: result = new Tree<>(data); - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> { - result.addChild(child.topDownTransform(transformPicker, transformer)); + ITree<ContainedType> kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); }); } @@ -227,7 +304,9 @@ public class Tree<ContainedType> implements ITree<ContainedType> { result = new Tree<>(intermediateResult.getHead()); intermediateResult.doForChildren((child) -> { - result.addChild(child.topDownTransform(transformPicker, transformer)); + ITree<ContainedType> kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); }); return result; @@ -238,23 +317,14 @@ public class Tree<ContainedType> implements ITree<ContainedType> { } @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) + if (childNo < 0 || childNo > childCount - 1) throw new IllegalArgumentException("Child index #" + childNo + " is invalid"); - return transformer.apply(children.getByIndex(childNo)); + ITree<ContainedType> selectedKid = children.getByIndex(childNo); + + return transformer.apply(selectedKid); } @Override @@ -263,51 +333,6 @@ public class Tree<ContainedType> implements ITree<ContainedType> { } @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); - } - } - - @Override public int hashCode() { final int prime = 31; int result = 1; @@ -320,51 +345,34 @@ public class Tree<ContainedType> implements ITree<ContainedType> { } @Override - public boolean equals(Object obj) { - if(this == obj) return true; - if(obj == null) return false; - if(getClass() != obj.getClass()) return false; - - Tree<?> other = (Tree<?>) obj; - - if(data == null) { - if(other.data != null) return false; - } else if(!data.equals(other.data)) return false; - - if(childCount != other.childCount) return false; - - if(children == null) { - if(other.children != null) return false; - } else if(!children.equals(other.children)) return false; - - return true; + public String toString() { + StringBuilder builder = new StringBuilder(); + + internalToString(builder, 1, true); + + builder.deleteCharAt(builder.length() - 1); + + return builder.toString(); } @Override - public int revFind(Predicate<ITree<ContainedType>> childPred) { - if(childCount == 0) { - return -1; - } else { - for(int i = childCount - 1; i >= 0; i--) { - if(childPred.test(getChild(i))) { - return i; - } - } - } + public boolean equals(Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (getClass() != obj.getClass()) return false; - return -1; - } + Tree<?> other = (Tree<?>) obj; - @Override - public void prependChild(ITree<ContainedType> child) { - if(hasChildren == false) { - hasChildren = true; + if (data == null) { + if (other.data != null) return false; + } else if (!data.equals(other.data)) return false; - children = new FunctionalList<>(); - } + if (childCount != other.childCount) return false; - childCount++; + if (children == null) { + if (other.children != null) return false; + } else if (!children.equals(other.children)) return false; - children.prepend(child); + return true; } -} +}
\ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/functypes/ListFlattener.java b/BJC-Utils2/src/main/java/bjc/utils/functypes/ListFlattener.java new file mode 100644 index 0000000..a94e19f --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/functypes/ListFlattener.java @@ -0,0 +1,17 @@ +package bjc.utils.functypes; + +import java.util.function.Function; + +import bjc.utils.funcdata.IList; + +/** + * A function that flattens a list. + * + * @author bjculkin + * + * @param <S> + * The type of value in the list. + */ +public interface ListFlattener<S> extends Function<IList<S>, S> { + +} |