From 0a8f34c27c6ef93c5c94d17728af62c7607e225f Mon Sep 17 00:00:00 2001 From: Ben Culkin Date: Thu, 3 Dec 2020 19:21:38 -0500 Subject: Rename types to match Java style This renames several interfaces that had names like IWhatever, since that isn't a style that Java uses --- src/main/java/bjc/data/SimpleTree.java | 446 +++++++++++++++++++++++++++++++++ 1 file changed, 446 insertions(+) create mode 100644 src/main/java/bjc/data/SimpleTree.java (limited to 'src/main/java/bjc/data/SimpleTree.java') diff --git a/src/main/java/bjc/data/SimpleTree.java b/src/main/java/bjc/data/SimpleTree.java new file mode 100644 index 0000000..7d9fb6d --- /dev/null +++ b/src/main/java/bjc/data/SimpleTree.java @@ -0,0 +1,446 @@ +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.FunctionalList; +import bjc.funcdata.ListEx; +import bjc.funcdata.bst.TreeLinearizationMethod; + +/** + * A node in a homogeneous tree. + * + * @author ben + * + * @param + * The type contained in the tree. + */ +public class SimpleTree implements Tree { + /* The data/label for this node. */ + private ContainedType data; + + /* The children of this node. */ + private ListEx> children; + + /* Whether this node has children. */ + /* + * @NOTE Why have both this boolean and childCount? Why not just do a childCount + * == 0 whenever you'd check hasChildren? + * + * - Because hasChildren is set once and not reset, and really what it + * indicates is that children has been allocated. + */ + private boolean hasChildren; + /* The number of children this node has. */ + private int childCount = 0; + + /* The ID of this node. */ + private int ID; + /* The next ID to assign to a node. */ + private static int nextID = 0; + + /** + * Create a new leaf node in a tree. + */ + public SimpleTree() { + this(null); + } + + /** + * Create a new leaf node in a tree. + * + * @param leaf + * The data to store as a leaf node. + */ + public SimpleTree(final ContainedType leaf) { + data = leaf; + + hasChildren = false; + + ID = nextID++; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + public SimpleTree(final ContainedType leaf, final ListEx> childrn) { + this(leaf); + + hasChildren = true; + + childCount = childrn.getSize(); + + children = childrn; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + @SafeVarargs + public SimpleTree(final ContainedType leaf, final Tree... childrn) { + this(leaf); + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for (final Tree child : childrn) { + children.add(child); + + childCount++; + } + } + + @Override + public void addChild(final ContainedType child) { + addChild(new SimpleTree<>(child)); + } + + @Override + public void addChild(final Tree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public void prependChild(final Tree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.prepend(child); + } + + @Override + public void doForChildren(final Consumer> action) { + if (childCount > 0) children.forEach(action); + } + + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public int revFind(final Predicate> childPred) { + if (childCount == 0) return -1; + + for (int i = childCount - 1; i >= 0; i--) { + if (childPred.test(getChild(i))) return i; + } + + return -1; + } + + @Override + public void traverse(final TreeLinearizationMethod linearizationMethod, + final Consumer action) { + if (hasChildren) { + switch (linearizationMethod) { + case INORDER: + if (childCount != 2) { + final String msg = "Can only do in-order traversal for binary trees."; + + throw new IllegalArgumentException(msg); + } + + 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( + final Function leafTransform, + final BiFunction, NewType> nodeCollapser, + final Function resultTransformer) { + return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override + public Tree + flatMapTree(final Function> mapper) { + if (hasChildren) { + final Tree flatMappedData = mapper.apply(data); + + final ListEx> mappedChildren + = children.map(child -> child.flatMapTree(mapper)); + + mappedChildren.forEach(flatMappedData::addChild); + + return flatMappedData; + } + + return mapper.apply(data); + } + + /* + * Do a collapse of this tree. + */ + + private NewType internalCollapse( + final Function leafTransform, + final BiFunction, NewType> nodeCollapser) { + if (hasChildren) { + final ListEx collapsedChildren = children.map(child -> { + final NewType collapsed = child.collapse(leafTransform, nodeCollapser, + subTreeVal -> subTreeVal); + + return collapsed; + }); + + return nodeCollapser.apply(data, collapsedChildren); + } + + return leafTransform.apply(data); + } + + private void internalToString(final StringBuilder builder, final int indentLevel, + final boolean initial) { + if (!initial) { + for (int i = 0; i < indentLevel; i++) builder.append(">\t"); + } + + builder.append("Node #"); + builder.append(ID); + builder.append(": "); + builder.append(data == null ? "(null)" : data.toString()); + builder.append("\n"); + + if (hasChildren) { + children.forEach(child -> { + if (child instanceof SimpleTree) { + final SimpleTree kid = (SimpleTree) child; + + kid.internalToString(builder, indentLevel + 1, false); + } else { + for (int i = 0; i < indentLevel + 1; i++) { + builder.append(">\t"); + } + + builder.append("Unknown node of type "); + builder.append(child.getClass().getName()); + builder.append("\n"); + } + }); + } + } + + @Override + public Tree rebuildTree( + final Function leafTransformer, + final Function operatorTransformer) { + if (hasChildren) { + final ListEx> mappedChildren = + children.map(child -> + child.rebuildTree(leafTransformer, operatorTransformer)); + + final MappedType mapData = operatorTransformer.apply(data); + return new SimpleTree<>(mapData, mappedChildren); + } + + return new SimpleTree<>(leafTransformer.apply(data)); + } + + @Override + public void selectiveTransform(final Predicate nodePicker, + final UnaryOperator transformer) { + if (hasChildren) { + children.forEach(child -> child.selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public Tree topDownTransform( + final Function transformPicker, + final UnaryOperator> transformer) { + final TopDownTransformResult transformResult = transformPicker.apply(data); + + switch (transformResult) { + case PASSTHROUGH: + Tree result = new SimpleTree<>(data); + + if (hasChildren) { + children.forEach(child -> { + final Tree kid + = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + } + + return result; + case SKIP: + return this; + case TRANSFORM: + return transformer.apply(this); + case RTRANSFORM: + return transformer.apply(this).topDownTransform(transformPicker, transformer); + case PUSHDOWN: + result = new SimpleTree<>(data); + + if (hasChildren) { + children.forEach(child -> { + final Tree kid + = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + } + + return transformer.apply(result); + case PULLUP: + final Tree intermediateResult = transformer.apply(this); + + result = new SimpleTree<>(intermediateResult.getHead()); + + intermediateResult.doForChildren(child -> { + final Tree kid + = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + + return result; + default: + final String msg = String.format("Recieved unknown transform result type %s", + transformResult); + + throw new IllegalArgumentException(msg); + } + } + + @Override + public TransformedType transformChild(final int childNo, + final Function, TransformedType> transformer) { + if (childNo < 0 || childNo > childCount - 1) { + final String msg = String.format("Child index #%d is invalid", childNo); + + throw new IllegalArgumentException(msg); + } + + final Tree selectedKid = children.getByIndex(childNo); + + return transformer.apply(selectedKid); + } + + @Override + public Tree getChild(final int childNo) { + if (childNo < 0 || childNo > childCount - 1) { + final String msg = String.format("Child index #%d is invalid", childNo); + + throw new IllegalArgumentException(msg); + } + return children.getByIndex(childNo); + } + + @Override + public TransformedType + transformHead(final Function transformer) { + return transformer.apply(data); + } + + @Override + public void setHead(ContainedType dat) { + this.data = dat; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + childCount; + result = prime * result + (children == null ? 0 : children.hashCode()); + result = prime * result + (data == null ? 0 : data.hashCode()); + + return result; + } + + @Override + public String toString() { + final StringBuilder builder = new StringBuilder(); + + internalToString(builder, 1, true); + + /* Delete a trailing nl. */ + builder.deleteCharAt(builder.length() - 1); + + return builder.toString(); + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof SimpleTree)) return false; + + final SimpleTree other = (SimpleTree) 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; + } +} -- cgit v1.2.3