diff options
Diffstat (limited to 'base/src/main/java/bjc/utils/funcdata/bst')
6 files changed, 0 insertions, 806 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 deleted file mode 100644 index 6631834..0000000 --- a/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java +++ /dev/null @@ -1,224 +0,0 @@ -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 deleted file mode 100644 index 762288f..0000000 --- a/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java +++ /dev/null @@ -1,115 +0,0 @@ -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 deleted file mode 100644 index eb7b6b5..0000000 --- a/base/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java +++ /dev/null @@ -1,295 +0,0 @@ -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: - 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: - String msg = String.format("Passed an incorrect TreeLinearizationMethod %s. WAT", - linearizationMethod); - - throw new IllegalArgumentException(msg); - } - } - - /* Do an in-order traversal. */ - 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; - } - - /* Do a post-order traversal. */ - 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; - - } - - /* Do a pre-order traversal. */ - 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; - } - - /* Traverse an element. */ - private boolean traverseElement(final Predicate<T> traversalPredicate) { - boolean nodeSuccesfullyTraversed; - - if(isDeleted) { - nodeSuccesfullyTraversed = true; - } else { - nodeSuccesfullyTraversed = traversalPredicate.test(data); - } - - return nodeSuccesfullyTraversed; - } - - /* Traverse the left branch of a tree. */ - 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; - } - - /* Traverse the right branch of a tree. */ - 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 deleted file mode 100644 index e341320..0000000 --- a/base/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java +++ /dev/null @@ -1,44 +0,0 @@ -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 deleted file mode 100644 index f9b3d4a..0000000 --- a/base/src/main/java/bjc/utils/funcdata/bst/ITreePart.java +++ /dev/null @@ -1,104 +0,0 @@ -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 deleted file mode 100644 index 80afaf2..0000000 --- a/base/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java +++ /dev/null @@ -1,24 +0,0 @@ -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 -} |