diff options
Diffstat (limited to 'base/src/main/java/bjc/utils/funcdata/bst')
6 files changed, 797 insertions, 0 deletions
diff --git a/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java b/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java new file mode 100644 index 0000000..8acd477 --- /dev/null +++ b/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java @@ -0,0 +1,221 @@ +package bjc.utils.funcdata.bst; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.function.Predicate; + +import bjc.utils.funcdata.FunctionalList; +import bjc.utils.funcdata.IList; + +/** + * A binary search tree, with some mild support for functional traversal. + * + * @author ben + * + * @param <T> + * The data type stored in the node. + */ +public class BinarySearchTree<T> { + /* + * The comparator for use in ordering items + */ + private final Comparator<T> comparator; + + /* + * The current count of elements in the tree + */ + private int elementCount; + + /* + * The root element of the tree + */ + private ITreePart<T> root; + + /** + * Create a new tree using the specified way to compare elements. + * + * @param cmp + * The thing to use for comparing elements + */ + public BinarySearchTree(final Comparator<T> cmp) { + if (cmp == null) throw new NullPointerException("Comparator must not be null"); + + elementCount = 0; + comparator = cmp; + } + + /** + * Add a node to the binary search tree. + * + * @param element + * The data to add to the binary search tree. + */ + public void addNode(final T element) { + elementCount++; + + if (root == null) { + root = new BinarySearchTreeNode<>(element, null, null); + } else { + root.add(element, comparator); + } + } + + /** + * Check if an adjusted pivot falls with the bounds of a list + * + * @param elements + * The list to get bounds from + * @param pivot + * The pivot + * @param pivotAdjustment + * The distance from the pivot + * @return Whether the adjusted pivot is with the list + */ + private boolean adjustedPivotInBounds(final IList<T> elements, final int pivot, final int pivotAdjustment) { + return pivot - pivotAdjustment >= 0 && pivot + pivotAdjustment < elements.getSize(); + } + + /** + * Balance the tree, and remove soft-deleted nodes for free. + * + * Takes O(N) time, but also O(N) space. + */ + public void balance() { + final IList<T> elements = new FunctionalList<>(); + + // Add each element to the list in sorted order + root.forEach(TreeLinearizationMethod.INORDER, element -> elements.add(element)); + + // Clear the tree + root = null; + + // Set up the pivot and adjustment for readding elements + final int pivot = elements.getSize() / 2; + int pivotAdjustment = 0; + + // Add elements until there aren't any left + while (adjustedPivotInBounds(elements, pivot, pivotAdjustment)) { + if (root == null) { + // Create a new root element + root = new BinarySearchTreeNode<>(elements.getByIndex(pivot), null, null); + } else { + // Add the left and right elements in a balanced + // manner + root.add(elements.getByIndex(pivot + pivotAdjustment), comparator); + + root.add(elements.getByIndex(pivot - pivotAdjustment), comparator); + } + + // Increase the distance from the pivot + pivotAdjustment++; + } + + // Add any trailing unbalanced elements + if (pivot - pivotAdjustment >= 0) { + root.add(elements.getByIndex(pivot - pivotAdjustment), comparator); + } else if (pivot + pivotAdjustment < elements.getSize()) { + root.add(elements.getByIndex(pivot + pivotAdjustment), comparator); + } + } + + /** + * Soft-delete a node from the tree. + * + * Soft-deleted nodes stay in the tree until trim()/balance() is + * invoked, and are not included in traversals/finds. + * + * @param element + * The node to delete + */ + public void deleteNode(final T element) { + elementCount--; + + root.delete(element, comparator); + } + + /** + * Get the root of the tree. + * + * @return The root of the tree. + */ + public ITreePart<T> getRoot() { + return root; + } + + /** + * Check if a node is in the tree + * + * @param element + * The node to check the presence of for the tree. + * @return Whether or not the node is in the tree. + */ + public boolean isInTree(final T element) { + return root.contains(element, comparator); + } + + /** + * Traverse the tree in a specified way until the function fails + * + * @param linearizationMethod + * The way to linearize the tree for traversal + * @param traversalPredicate + * The function to use until it fails + */ + public void traverse(final TreeLinearizationMethod linearizationMethod, final Predicate<T> traversalPredicate) { + if (linearizationMethod == null) + throw new NullPointerException("Linearization method must not be null"); + else if (traversalPredicate == null) throw new NullPointerException("Predicate must not be nulls"); + + root.forEach(linearizationMethod, traversalPredicate); + } + + /** + * Remove all soft-deleted nodes from the tree. + */ + public void trim() { + final List<T> nodes = new ArrayList<>(elementCount); + + // Add all non-soft deleted nodes to the tree in insertion order + traverse(TreeLinearizationMethod.PREORDER, node -> { + nodes.add(node); + return true; + }); + + // Clear the tree + root = null; + + // Add the nodes to the tree in the order they were inserted + nodes.forEach(node -> addNode(node)); + } + + @Override + public String toString() { + return String.format("BinarySearchTree [elementCount=%s, root='%s']", elementCount, root); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + elementCount; + result = prime * result + (root == null ? 0 : root.hashCode()); + return result; + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof BinarySearchTree<?>)) return false; + + final BinarySearchTree<?> other = (BinarySearchTree<?>) obj; + + if (elementCount != other.elementCount) return false; + if (root == null) { + if (other.root != null) return false; + } else if (!root.equals(other.root)) return false; + + return true; + } +} diff --git a/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java b/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java new file mode 100644 index 0000000..8c4f3f0 --- /dev/null +++ b/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java @@ -0,0 +1,119 @@ +package bjc.utils.funcdata.bst; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A leaf in a tree. + * + * @author ben + * + * @param <T> + * The data stored in the tree. + */ +public class BinarySearchTreeLeaf<T> implements ITreePart<T> { + /** + * The data held in this tree leaf + */ + protected T data; + + /** + * Whether this node is soft-deleted or not + */ + protected boolean isDeleted; + + /** + * Create a new leaf holding the specified data. + * + * @param element + * The data for the leaf to hold. + */ + public BinarySearchTreeLeaf(final T element) { + data = element; + } + + @Override + public void add(final T element, final Comparator<T> comparator) { + throw new IllegalArgumentException("Can't add to a leaf."); + } + + @Override + public <E> E collapse(final Function<T, E> leafTransformer, final BiFunction<E, E, E> branchCollapser) { + if (leafTransformer == null) throw new NullPointerException("Transformer must not be null"); + + return leafTransformer.apply(data); + } + + @Override + public boolean contains(final T element, final Comparator<T> comparator) { + return this.data.equals(element); + } + + @Override + public T data() { + return data; + } + + @Override + public void delete(final T element, final Comparator<T> comparator) { + if (data.equals(element)) { + isDeleted = true; + } + } + + @Override + public boolean directedWalk(final DirectedWalkFunction<T> treeWalker) { + if (treeWalker == null) throw new NullPointerException("Tree walker must not be null"); + + switch (treeWalker.walk(data)) { + case SUCCESS: + return true; + // We don't have any children to care about + case FAILURE: + case LEFT: + case RIGHT: + default: + return false; + } + } + + @Override + public boolean forEach(final TreeLinearizationMethod linearizationMethod, + final Predicate<T> traversalPredicate) { + if (traversalPredicate == null) throw new NullPointerException("Predicate must not be null"); + + return traversalPredicate.test(data); + } + + @Override + public String toString() { + return String.format("BinarySearchTreeLeaf [data='%s', isDeleted=%s]", data, isDeleted); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + (data == null ? 0 : data.hashCode()); + result = prime * result + (isDeleted ? 1231 : 1237); + return result; + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof BinarySearchTreeLeaf<?>)) return false; + + final BinarySearchTreeLeaf<?> other = (BinarySearchTreeLeaf<?>) obj; + + if (data == null) { + if (other.data != null) return false; + } else if (!data.equals(other.data)) return false; + if (isDeleted != other.isDeleted) return false; + + return true; + } +} diff --git a/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java b/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java new file mode 100644 index 0000000..9f45c17 --- /dev/null +++ b/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java @@ -0,0 +1,287 @@ +package bjc.utils.funcdata.bst; + +import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.FAILURE; +import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.LEFT; +import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.RIGHT; +import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.SUCCESS; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A binary node in a tree. + * + * @author ben + * + * @param <T> + * The data type stored in the tree. + */ +public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { + /* + * The left child of this node + */ + private ITreePart<T> left; + + /* + * The right child of this node + */ + private ITreePart<T> right; + + /** + * Create a new node with the specified data and children. + * + * @param element + * The data to store in this node. + * @param lft + * The left child of this node. + * @param rght + * The right child of this node. + */ + public BinarySearchTreeNode(final T element, final ITreePart<T> lft, final ITreePart<T> rght) { + super(element); + this.left = lft; + this.right = rght; + } + + @Override + public void add(final T element, final Comparator<T> comparator) { + if (comparator == null) throw new NullPointerException("Comparator must not be null"); + + switch (comparator.compare(data, element)) { + case -1: + if (left == null) { + left = new BinarySearchTreeNode<>(element, null, null); + } else { + left.add(element, comparator); + } + break; + case 0: + if (isDeleted) { + isDeleted = false; + } else throw new IllegalArgumentException("Can't add duplicate values"); + break; + case 1: + if (right == null) { + right = new BinarySearchTreeNode<>(element, null, null); + } else { + right.add(element, comparator); + } + break; + default: + throw new IllegalStateException("Error: Comparator yielded invalid value"); + } + } + + @Override + public <E> E collapse(final Function<T, E> nodeCollapser, final BiFunction<E, E, E> branchCollapser) { + if (nodeCollapser == null || branchCollapser == null) + throw new NullPointerException("Collapser must not be null"); + + final E collapsedNode = nodeCollapser.apply(data); + + if (left != null) { + final E collapsedLeftBranch = left.collapse(nodeCollapser, branchCollapser); + + if (right != null) { + final E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser); + + final E collapsedBranches = branchCollapser.apply(collapsedLeftBranch, + collapsedRightBranch); + + return branchCollapser.apply(collapsedNode, collapsedBranches); + } + + return branchCollapser.apply(collapsedNode, collapsedLeftBranch); + } + + if (right != null) { + final E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser); + + return branchCollapser.apply(collapsedNode, collapsedRightBranch); + } + + return collapsedNode; + } + + @Override + public boolean contains(final T element, final Comparator<T> comparator) { + if (comparator == null) throw new NullPointerException("Comparator must not be null"); + + return directedWalk(currentElement -> { + switch (comparator.compare(element, currentElement)) { + case -1: + return LEFT; + case 0: + return isDeleted ? FAILURE : SUCCESS; + case 1: + return RIGHT; + default: + return FAILURE; + } + }); + } + + @Override + public void delete(final T element, final Comparator<T> comparator) { + if (comparator == null) throw new NullPointerException("Comparator must not be null"); + + directedWalk(currentElement -> { + switch (comparator.compare(data, element)) { + case -1: + return left == null ? FAILURE : LEFT; + case 0: + isDeleted = true; + return FAILURE; + case 1: + return right == null ? FAILURE : RIGHT; + default: + return FAILURE; + } + }); + } + + @Override + public boolean directedWalk(final DirectedWalkFunction<T> treeWalker) { + if (treeWalker == null) throw new NullPointerException("Walker must not be null"); + + switch (treeWalker.walk(data)) { + case SUCCESS: + return true; + case LEFT: + return left.directedWalk(treeWalker); + case RIGHT: + return right.directedWalk(treeWalker); + case FAILURE: + return false; + default: + return false; + } + } + + @Override + public boolean forEach(final TreeLinearizationMethod linearizationMethod, + final Predicate<T> traversalPredicate) { + if (linearizationMethod == null) + throw new NullPointerException("Linearization method must not be null"); + else if (traversalPredicate == null) throw new NullPointerException("Predicate must not be null"); + + switch (linearizationMethod) { + case PREORDER: + return preorderTraverse(linearizationMethod, traversalPredicate); + case INORDER: + return inorderTraverse(linearizationMethod, traversalPredicate); + case POSTORDER: + return postorderTraverse(linearizationMethod, traversalPredicate); + default: + throw new IllegalArgumentException( + "Passed an incorrect TreeLinearizationMethod " + linearizationMethod + ". WAT"); + } + } + + private boolean inorderTraverse(final TreeLinearizationMethod linearizationMethod, + final Predicate<T> traversalPredicate) { + if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false; + + if (!traverseElement(traversalPredicate)) return false; + + if (!traverseRightBranch(linearizationMethod, traversalPredicate)) return false; + + return true; + } + + private boolean postorderTraverse(final TreeLinearizationMethod linearizationMethod, + final Predicate<T> traversalPredicate) { + if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false; + + if (!traverseRightBranch(linearizationMethod, traversalPredicate)) return false; + + if (!traverseElement(traversalPredicate)) return false; + + return true; + + } + + private boolean preorderTraverse(final TreeLinearizationMethod linearizationMethod, + final Predicate<T> traversalPredicate) { + if (!traverseElement(traversalPredicate)) return false; + + if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false; + + if (!traverseRightBranch(linearizationMethod, traversalPredicate)) return false; + + return true; + } + + private boolean traverseElement(final Predicate<T> traversalPredicate) { + boolean nodeSuccesfullyTraversed; + + if (isDeleted) { + nodeSuccesfullyTraversed = true; + } else { + nodeSuccesfullyTraversed = traversalPredicate.test(data); + } + + return nodeSuccesfullyTraversed; + } + + private boolean traverseLeftBranch(final TreeLinearizationMethod linearizationMethod, + final Predicate<T> traversalPredicate) { + boolean leftSuccesfullyTraversed; + + if (left == null) { + leftSuccesfullyTraversed = true; + } else { + leftSuccesfullyTraversed = left.forEach(linearizationMethod, traversalPredicate); + } + + return leftSuccesfullyTraversed; + } + + private boolean traverseRightBranch(final TreeLinearizationMethod linearizationMethod, + final Predicate<T> traversalPredicate) { + boolean rightSuccesfullyTraversed; + + if (right == null) { + rightSuccesfullyTraversed = true; + } else { + rightSuccesfullyTraversed = right.forEach(linearizationMethod, traversalPredicate); + } + + return rightSuccesfullyTraversed; + } + + @Override + public String toString() { + return String.format("BinarySearchTreeNode [left='%s', right='%s']", left, right); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = super.hashCode(); + result = prime * result + (left == null ? 0 : left.hashCode()); + result = prime * result + (right == null ? 0 : right.hashCode()); + return result; + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) return true; + if (!super.equals(obj)) return false; + if (!(obj instanceof BinarySearchTreeNode<?>)) return false; + + final BinarySearchTreeNode<?> other = (BinarySearchTreeNode<?>) obj; + + if (left == null) { + if (other.left != null) return false; + } else if (!left.equals(other.left)) return false; + + if (right == null) { + if (other.right != null) return false; + } else if (!right.equals(other.right)) return false; + + return true; + } +} diff --git a/base/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java b/base/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java new file mode 100644 index 0000000..e11524a --- /dev/null +++ b/base/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java @@ -0,0 +1,49 @@ +package bjc.utils.funcdata.bst; + +/** + * Represents a function for doing a directed walk of a binary tree. + * + * @author ben + * + * @param <T> + * The type of element stored in the walked tree + */ +@FunctionalInterface +public interface DirectedWalkFunction<T> { + /** + * Represents the results used to direct a walk in a binary tree. + * + * @author ben + * + */ + public enum DirectedWalkResult { + /** + * Specifies that the function has failed. + */ + FAILURE, + /** + * Specifies that the function wants to move left in the tree + * next. + */ + LEFT, + /** + * Specifies that the function wants to move right in the tree + * next. + */ + RIGHT, + /** + * Specifies that the function has succesfully completed + * + */ + SUCCESS + } + + /** + * Perform a directed walk on a node of a tree. + * + * @param element + * The data stored in the node currently being visited + * @return The way the function wants the walk to go next. + */ + public DirectedWalkResult walk(T element); +} diff --git a/base/src/main/java/bjc/utils/funcdata/bst/ITreePart.java b/base/src/main/java/bjc/utils/funcdata/bst/ITreePart.java new file mode 100644 index 0000000..3aa8880 --- /dev/null +++ b/base/src/main/java/bjc/utils/funcdata/bst/ITreePart.java @@ -0,0 +1,96 @@ +package bjc.utils.funcdata.bst; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A interface for the fundamental things that want to be part of a tree. + * + * @author ben + * + * @param <T> + * The data contained in this part of the tree. + */ +public interface ITreePart<T> { + /** + * Add a element below this tree part somewhere. + * + * @param element + * The element to add below this tree part + * @param comparator + * The thing to use for comparing values to find where to + * insert the tree part. + */ + public void add(T element, Comparator<T> comparator); + + /** + * Collapses this tree part into a single value. Does not change the + * underlying tree. + * + * @param <E> + * The type of the final collapsed value + * + * @param nodeCollapser + * The function to use to transform data into mapped + * form. + * @param branchCollapser + * The function to use to collapse data in mapped form + * into a single value. + * @return A single value from collapsing the tree. + */ + public <E> E collapse(Function<T, E> nodeCollapser, BiFunction<E, E, E> branchCollapser); + + /** + * Check if this tre part or below it contains the specified data item + * + * @param element + * The data item to look for. + * @param comparator + * The comparator to use to search for the data item + * @return Whether or not the given item is contained in this tree part + * or its children. + */ + public boolean contains(T element, Comparator<T> comparator); + + /** + * Get the data associated with this tree part. + * + * @return The data associated with this tree part. + */ + public T data(); + + /** + * Remove the given node from this tree part and any of its children. + * + * @param element + * The data item to remove. + * @param comparator + * The comparator to use to search for the data item. + */ + public void delete(T element, Comparator<T> comparator); + + /** + * Execute a directed walk through the tree. + * + * @param walker + * The function to use to direct the walk through the + * tree. + * @return Whether the directed walk finished successfully. + */ + public boolean directedWalk(DirectedWalkFunction<T> walker); + + /** + * Execute a provided function for each element of tree it succesfully + * completes for + * + * @param linearizationMethod + * The way to linearize the tree for executing + * @param predicate + * The predicate to apply to each element, where it + * returning false terminates traversal early + * @return Whether the traversal finished succesfully + */ + public boolean forEach(TreeLinearizationMethod linearizationMethod, Predicate<T> predicate); +} diff --git a/base/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java b/base/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java new file mode 100644 index 0000000..0c83867 --- /dev/null +++ b/base/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java @@ -0,0 +1,25 @@ +package bjc.utils.funcdata.bst; + +/** + * Represents the ways to linearize a tree for traversal. + * + * @author ben + * + */ +public enum TreeLinearizationMethod { + /** + * Visit the left side of this tree part, the tree part itself, and then + * the right part. + */ + INORDER, + /** + * Visit the left side of this tree part, the right side, and then the + * tree part itself. + */ + POSTORDER, + /** + * Visit the tree part itself, then the left side of tthis tree part and + * then the right part. + */ + PREORDER +}
\ No newline at end of file |