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/Tree.java | 276 +++++++++++----------- 1 file changed, 142 insertions(+), 134 deletions(-) (limited to 'BJC-Utils2/src/main/java/bjc/utils/data/Tree.java') 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 implements ITree { 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 implements ITree { } /** - * 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> childrn) { this(leaf); @@ -59,12 +61,13 @@ public class Tree implements ITree { } /** - * 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... childrn) { @@ -76,7 +79,7 @@ public class Tree implements ITree { children = new FunctionalList<>(); - for(ITree child : childrn) { + for (ITree child : childrn) { children.add(child); childCount++; @@ -85,7 +88,7 @@ public class Tree implements ITree { @Override public void addChild(ITree child) { - if(hasChildren == false) { + if (hasChildren == false) { hasChildren = true; children = new FunctionalList<>(); @@ -97,27 +100,92 @@ public class Tree implements ITree { } @Override - public ReturnedType collapse(Function leafTransform, - Function, NewType>> nodeCollapser, - Function resultTransformer) { - - return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + public void prependChild(ITree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.prepend(child); } @Override public void doForChildren(Consumer> action) { - if(childCount > 0) { + if (childCount > 0) { children.forEach(action); } } + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public int revFind(Predicate> 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 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 ReturnedType collapse(Function leafTransform, + Function> nodeCollapser, + Function resultTransformer) { + return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + } + @Override public ITree flatMapTree(Function> mapper) { - if(hasChildren) { + if (hasChildren) { ITree flatMappedData = mapper.apply(data); - children.map((child) -> child.flatMapTree(mapper)) - .forEach((child) -> flatMappedData.addChild(child)); + IList> mappedChildren = children.map((child) -> child.flatMapTree(mapper)); + mappedChildren.forEach((child) -> flatMappedData.addChild(child)); return flatMappedData; } @@ -125,14 +193,9 @@ public class Tree implements ITree { return mapper.apply(data); } - @Override - public int getChildrenCount() { - return childCount; - } - protected NewType internalCollapse(Function leafTransform, - Function, NewType>> nodeCollapser) { - if(hasChildren) { + Function> nodeCollapser) { + if (hasChildren) { Function, NewType> nodeTransformer = nodeCollapser.apply(data); IList collapsedChildren = children.map((child) -> { @@ -149,7 +212,7 @@ public class Tree implements ITree { } 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 implements ITree { builder.append(data == null ? "(null)" : data.toString()); builder.append("\n"); - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> { - ((Tree) child).internalToString(builder, indentLevel + 1, false); + if (child instanceof Tree) { + Tree kid = (Tree) 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 implements ITree { @Override public ITree rebuildTree(Function leafTransformer, Function operatorTransformer) { - if(hasChildren) { + if (hasChildren) { IList> mappedChildren = children.map((child) -> { return child.rebuildTree(leafTransformer, operatorTransformer); }); @@ -182,7 +255,7 @@ public class Tree implements ITree { @Override public void selectiveTransform(Predicate nodePicker, UnaryOperator transformer) { - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> child.selectiveTransform(nodePicker, transformer)); } else { data = transformer.apply(data); @@ -194,13 +267,15 @@ public class Tree implements ITree { UnaryOperator> transformer) { TopDownTransformResult transformResult = transformPicker.apply(data); - switch(transformResult) { + switch (transformResult) { case PASSTHROUGH: ITree result = new Tree<>(data); - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> { - result.addChild(child.topDownTransform(transformPicker, transformer)); + ITree kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); }); } @@ -214,9 +289,11 @@ public class Tree implements ITree { case PUSHDOWN: result = new Tree<>(data); - if(hasChildren) { + if (hasChildren) { children.forEach((child) -> { - result.addChild(child.topDownTransform(transformPicker, transformer)); + ITree kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); }); } @@ -227,7 +304,9 @@ public class Tree implements ITree { result = new Tree<>(intermediateResult.getHead()); intermediateResult.doForChildren((child) -> { - result.addChild(child.topDownTransform(transformPicker, transformer)); + ITree kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); }); return result; @@ -237,24 +316,15 @@ public class Tree implements ITree { } } - @Override - public String toString() { - StringBuilder builder = new StringBuilder(); - - internalToString(builder, 1, true); - - builder.deleteCharAt(builder.length() - 1); - - return builder.toString(); - } - @Override public TransformedType transformChild(int childNo, Function, 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 selectedKid = children.getByIndex(childNo); + + return transformer.apply(selectedKid); } @Override @@ -262,51 +332,6 @@ public class Tree implements ITree { return transformer.apply(data); } - @Override - public ITree transformTree(Function transformer) { - if(hasChildren) { - IList> 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 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; @@ -320,51 +345,34 @@ public class Tree implements ITree { } @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> 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 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 -- cgit v1.2.3