From c82e3b3b2de0633317ec8fc85925e91422820597 Mon Sep 17 00:00:00 2001 From: "Benjamin J. Culkin" Date: Sun, 8 Oct 2017 22:39:59 -0300 Subject: Start splitting into maven modules --- .../bjc/utils/funcdata/bst/BinarySearchTree.java | 221 --------------------- 1 file changed, 221 deletions(-) delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java') diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java deleted file mode 100644 index 8acd477..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java +++ /dev/null @@ -1,221 +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 - * 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; - } -} -- cgit v1.2.3