From 843329de434bb334d90927c4d22345373a388530 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Tue, 2 Jul 2019 18:05:22 -0400 Subject: Rename package root The package root is now bjc, not io.github.bculkin2442. --- .../java/bjc/funcdata/bst/BinarySearchTree.java | 224 ++++++++++++++++ .../bjc/funcdata/bst/BinarySearchTreeLeaf.java | 115 ++++++++ .../bjc/funcdata/bst/BinarySearchTreeNode.java | 295 +++++++++++++++++++++ .../bjc/funcdata/bst/DirectedWalkFunction.java | 44 +++ src/main/java/bjc/funcdata/bst/ITreePart.java | 104 ++++++++ .../bjc/funcdata/bst/TreeLinearizationMethod.java | 24 ++ 6 files changed, 806 insertions(+) create mode 100644 src/main/java/bjc/funcdata/bst/BinarySearchTree.java create mode 100644 src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java create mode 100644 src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java create mode 100644 src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java create mode 100644 src/main/java/bjc/funcdata/bst/ITreePart.java create mode 100644 src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java (limited to 'src/main/java/bjc/funcdata/bst') diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTree.java b/src/main/java/bjc/funcdata/bst/BinarySearchTree.java new file mode 100644 index 0000000..d0319e4 --- /dev/null +++ b/src/main/java/bjc/funcdata/bst/BinarySearchTree.java @@ -0,0 +1,224 @@ +package bjc.funcdata.bst; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.function.Predicate; + +import bjc.funcdata.FunctionalList; +import bjc.funcdata.IList; + +/** + * A binary search tree, with some mild support for functional traversal. + * + * @author ben + * + * @param + * The data type stored in the node. + */ +public class BinarySearchTree { + /* The comparator for use in ordering items */ + private final Comparator comparator; + + /* The current count of elements in the tree */ + private int elementCount; + + /* The root element of the tree */ + private ITreePart 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 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 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 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 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 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 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/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java b/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java new file mode 100644 index 0000000..dfad3d9 --- /dev/null +++ b/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java @@ -0,0 +1,115 @@ +package bjc.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 + * The data stored in the tree. + */ +public class BinarySearchTreeLeaf implements ITreePart { + /** 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 comparator) { + throw new IllegalArgumentException("Can't add to a leaf."); + } + + @Override + public E collapse(final Function leafTransformer, final BiFunction 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 comparator) { + return this.data.equals(element); + } + + @Override + public T data() { + return data; + } + + @Override + public void delete(final T element, final Comparator comparator) { + if(data.equals(element)) { + isDeleted = true; + } + } + + @Override + public boolean directedWalk(final DirectedWalkFunction 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 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/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java new file mode 100644 index 0000000..0453f80 --- /dev/null +++ b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java @@ -0,0 +1,295 @@ +package bjc.funcdata.bst; + +import static bjc.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.FAILURE; +import static bjc.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.LEFT; +import static bjc.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.RIGHT; +import static bjc.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 + * The data type stored in the tree. + */ +public class BinarySearchTreeNode extends BinarySearchTreeLeaf { + /* The left child of this node */ + private ITreePart left; + + /* The right child of this node */ + private ITreePart 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 lft, final ITreePart rght) { + super(element); + this.left = lft; + this.right = rght; + } + + @Override + public void add(final T element, final Comparator 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 collapse(final Function nodeCollapser, final BiFunction 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 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 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 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 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 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 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 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 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 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 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/src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java b/src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java new file mode 100644 index 0000000..ac2b918 --- /dev/null +++ b/src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java @@ -0,0 +1,44 @@ +package bjc.funcdata.bst; + +/** + * Represents a function for doing a directed walk of a binary tree. + * + * @author ben + * + * @param + * The type of element stored in the walked tree + */ +@FunctionalInterface +public interface DirectedWalkFunction { + /** + * 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/src/main/java/bjc/funcdata/bst/ITreePart.java b/src/main/java/bjc/funcdata/bst/ITreePart.java new file mode 100644 index 0000000..903965f --- /dev/null +++ b/src/main/java/bjc/funcdata/bst/ITreePart.java @@ -0,0 +1,104 @@ +package bjc.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 + * The data contained in this part of the tree. + */ +public interface ITreePart { + /** + * 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 comparator); + + /** + * Collapses this tree part into a single value. + * + * Does not change the underlying tree. + * + * @param + * 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 collapse(Function nodeCollapser, BiFunction 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 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 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 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 predicate); +} diff --git a/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java b/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java new file mode 100644 index 0000000..35b116b --- /dev/null +++ b/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java @@ -0,0 +1,24 @@ +package bjc.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 +} -- cgit v1.2.3