diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata/bst')
4 files changed, 100 insertions, 187 deletions
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 index 865f4d6..b595946 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java @@ -17,20 +17,20 @@ import bjc.utils.funcdata.IList; * The data type stored in the node. */ public class BinarySearchTree<T> { - /** + /* * The comparator for use in ordering items */ private Comparator<T> comparator; - /** + /* * The current count of elements in the tree */ private int elementCount; - /** + /* * The root element of the tree */ - private ITreePart<T> rootElement; + private ITreePart<T> root; /** * Create a new tree using the specified way to compare elements. @@ -56,10 +56,10 @@ public class BinarySearchTree<T> { public void addNode(T element) { elementCount++; - if (rootElement == null) { - rootElement = new BinarySearchTreeNode<>(element, null, null); + if (root == null) { + root = new BinarySearchTreeNode<>(element, null, null); } else { - rootElement.add(element, comparator); + root.add(element, comparator); } } @@ -74,25 +74,23 @@ public class BinarySearchTree<T> { * The distance from the pivot * @return Whether the adjusted pivot is with the list */ - private boolean adjustedPivotInBounds(IList<T> elements, int pivot, - int pivotAdjustment) { - return (pivot - pivotAdjustment) >= 0 - && (pivot + pivotAdjustment) < elements.getSize(); + private boolean adjustedPivotInBounds(IList<T> elements, int pivot, 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. + * Balance the tree, and remove soft-deleted nodes for free. + * + * Takes O(N) time, but also O(N) space. */ public void balance() { IList<T> elements = new FunctionalList<>(); // Add each element to the list in sorted order - rootElement.forEach(TreeLinearizationMethod.INORDER, - element -> elements.add(element)); + root.forEach(TreeLinearizationMethod.INORDER, element -> elements.add(element)); // Clear the tree - rootElement = null; + root = null; // Set up the pivot and adjustment for readding elements int pivot = elements.getSize() / 2; @@ -100,19 +98,14 @@ public class BinarySearchTree<T> { // Add elements until there aren't any left while (adjustedPivotInBounds(elements, pivot, pivotAdjustment)) { - if (rootElement == null) { + if (root == null) { // Create a new root element - rootElement = new BinarySearchTreeNode<>( - elements.getByIndex(pivot), null, null); + root = new BinarySearchTreeNode<>(elements.getByIndex(pivot), null, null); } else { // Add the left and right elements in a balanced manner - rootElement.add( - elements.getByIndex(pivot + pivotAdjustment), - comparator); + root.add(elements.getByIndex(pivot + pivotAdjustment), comparator); - rootElement.add( - elements.getByIndex(pivot - pivotAdjustment), - comparator); + root.add(elements.getByIndex(pivot - pivotAdjustment), comparator); } // Increase the distance from the pivot @@ -121,18 +114,17 @@ public class BinarySearchTree<T> { // Add any trailing unbalanced elements if ((pivot - pivotAdjustment) >= 0) { - rootElement.add(elements.getByIndex(pivot - pivotAdjustment), - comparator); + root.add(elements.getByIndex(pivot - pivotAdjustment), comparator); } else if ((pivot + pivotAdjustment) < elements.getSize()) { - rootElement.add(elements.getByIndex(pivot + pivotAdjustment), - comparator); + 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. + * 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 @@ -140,7 +132,7 @@ public class BinarySearchTree<T> { public void deleteNode(T element) { elementCount--; - rootElement.delete(element, comparator); + root.delete(element, comparator); } /** @@ -149,7 +141,7 @@ public class BinarySearchTree<T> { * @return The root of the tree. */ public ITreePart<T> getRoot() { - return rootElement; + return root; } /** @@ -160,7 +152,7 @@ public class BinarySearchTree<T> { * @return Whether or not the node is in the tree. */ public boolean isInTree(T element) { - return rootElement.contains(element, comparator); + return root.contains(element, comparator); } /** @@ -171,16 +163,14 @@ public class BinarySearchTree<T> { * @param traversalPredicate * The function to use until it fails */ - public void traverse(TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { + public void traverse(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (linearizationMethod == null) { - throw new NullPointerException( - "Linearization method must not be null"); + throw new NullPointerException("Linearization method must not be null"); } else if (traversalPredicate == null) { throw new NullPointerException("Predicate must not be nulls"); } - rootElement.forEach(linearizationMethod, traversalPredicate); + root.forEach(linearizationMethod, traversalPredicate); } /** @@ -196,9 +186,9 @@ public class BinarySearchTree<T> { }); // Clear the tree - rootElement = null; + root = null; // Add the nodes to the tree in the order they were inserted nodes.forEach(node -> addNode(node)); } -}
\ No newline at end of file +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java index 8ceb554..d647742 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java @@ -34,27 +34,13 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { data = element; } - /* - * Can't add things to a leaf. (non-Javadoc) - * - * @see bjc.utils.data.bst.ITreePart#add(java.lang.Object, - * java.util.Comparator) - */ @Override public void add(T element, Comparator<T> comparator) { throw new IllegalArgumentException("Can't add to a leaf."); } - /* - * Just transform our data. (non-Javadoc) - * - * @see - * bjc.utils.data.bst.ITreePart#collapse(java.util.function.Function, - * java.util.function.BiFunction) - */ @Override - public <E> E collapse(Function<T, E> leafTransformer, - BiFunction<E, E, E> branchCollapser) { + public <E> E collapse(Function<T, E> leafTransformer, BiFunction<E, E, E> branchCollapser) { if (leafTransformer == null) { throw new NullPointerException("Transformer must not be null"); } @@ -62,33 +48,16 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { return leafTransformer.apply(data); } - /* - * Only check our data. (non-Javadoc) - * - * @see bjc.utils.data.bst.ITreePart#contains(java.lang.Object, - * java.util.Comparator) - */ @Override public boolean contains(T element, Comparator<T> comparator) { return this.data.equals(element); } - /* - * Just get the data (non-Javadoc) - * - * @see bjc.utils.data.bst.ITreePart#data() - */ @Override public T data() { return data; } - /* - * Just mark ourselves as "not here" (non-Javadoc) - * - * @see bjc.utils.data.bst.ITreePart#delete(java.lang.Object, - * java.util.Comparator) - */ @Override public void delete(T element, Comparator<T> comparator) { if (data.equals(element)) { @@ -96,13 +65,6 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { } } - /* - * Just walk our data and only succede if the walk does, because - * there's nowhere left to go. (non-Javadoc) - * - * @see bjc.utils.data.bst.ITreePart#directedWalk(bjc.utils.data.bst. - * DirectedWalkFunction) - */ @Override public boolean directedWalk(DirectedWalkFunction<T> treeWalker) { if (treeWalker == null) { @@ -121,16 +83,8 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { } } - /* - * Just check our data. (non-Javadoc) - * - * @see - * bjc.utils.data.bst.ITreePart#forEach(bjc.utils.data.bst.ITreePart. - * TreeLinearizationMethod, java.util.function.Predicate) - */ @Override - public boolean forEach(TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { + public boolean forEach(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (traversalPredicate == null) { throw new NullPointerException("Predicate must not be null"); } diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java index 9817f91..fa3add0 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java @@ -19,39 +19,33 @@ import java.util.function.Predicate; * The data type stored in the tree. */ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { - /** + /* * The left child of this node */ - private ITreePart<T> leftBranch; + private ITreePart<T> left; - /** + /* * The right child of this node */ - private ITreePart<T> rightBranch; + private ITreePart<T> right; /** * Create a new node with the specified data and children. * * @param element * The data to store in this node. - * @param left + * @param lft * The left child of this node. - * @param right + * @param rght * The right child of this node. */ - public BinarySearchTreeNode(T element, ITreePart<T> left, - ITreePart<T> right) { + public BinarySearchTreeNode(T element, ITreePart<T> lft, + ITreePart<T> rght) { super(element); - this.leftBranch = left; - this.rightBranch = right; + this.left = lft; + this.right = rght; } - /* - * Either adds it to the left/right, or undeletes itself. (non-Javadoc) - * - * @see bjc.utils.data.bst.TreeLeaf#add(java.lang.Object, - * java.util.Comparator) - */ @Override public void add(T element, Comparator<T> comparator) { if (comparator == null) { @@ -60,65 +54,57 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { switch (comparator.compare(data, element)) { case -1: - if (leftBranch == null) { - leftBranch = new BinarySearchTreeNode<>(element, null, - null); + if (left == null) { + left = new BinarySearchTreeNode<>(element, null, null); } else { - leftBranch.add(element, comparator); + left.add(element, comparator); } + break; case 0: if (isDeleted) { isDeleted = false; } else { - throw new IllegalArgumentException( - "Can't add duplicate values"); + throw new IllegalArgumentException("Can't add duplicate values"); } + break; case 1: - if (rightBranch == null) { - rightBranch = new BinarySearchTreeNode<>(element, null, - null); + if (right == null) { + right = new BinarySearchTreeNode<>(element, null, null); } else { - rightBranch.add(element, comparator); + right.add(element, comparator); } + break; default: - throw new IllegalStateException( - "Error: Comparator yielded invalid value"); + throw new IllegalStateException("Error: Comparator yielded invalid value"); } } @Override - public <E> E collapse(Function<T, E> nodeCollapser, - BiFunction<E, E, E> branchCollapser) { + public <E> E collapse(Function<T, E> nodeCollapser, BiFunction<E, E, E> branchCollapser) { if (nodeCollapser == null || branchCollapser == null) { throw new NullPointerException("Collapser must not be null"); } E collapsedNode = nodeCollapser.apply(data); - if (leftBranch != null) { - E collapsedLeftBranch = leftBranch.collapse(nodeCollapser, - branchCollapser); - if (rightBranch != null) { - E collapsedRightBranch = rightBranch - .collapse(nodeCollapser, branchCollapser); + if (left != null) { + E collapsedLeftBranch = left.collapse(nodeCollapser, branchCollapser); - E collapsedBranches = branchCollapser - .apply(collapsedLeftBranch, collapsedRightBranch); + if (right != null) { + E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser); - return branchCollapser.apply(collapsedNode, - collapsedBranches); + E collapsedBranches = branchCollapser.apply(collapsedLeftBranch, collapsedRightBranch); + + return branchCollapser.apply(collapsedNode, collapsedBranches); } - return branchCollapser.apply(collapsedNode, - collapsedLeftBranch); + return branchCollapser.apply(collapsedNode, collapsedLeftBranch); } - if (rightBranch != null) { - E collapsedRightBranch = rightBranch.collapse(nodeCollapser, - branchCollapser); + if (right != null) { + E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser); - return branchCollapser.apply(collapsedNode, - collapsedRightBranch); + return branchCollapser.apply(collapsedNode, collapsedRightBranch); } return collapsedNode; @@ -153,12 +139,12 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { directedWalk(currentElement -> { switch (comparator.compare(data, element)) { case -1: - return leftBranch == null ? FAILURE : LEFT; + return left == null ? FAILURE : LEFT; case 0: isDeleted = true; return FAILURE; case 1: - return rightBranch == null ? FAILURE : RIGHT; + return right == null ? FAILURE : RIGHT; default: return FAILURE; } @@ -175,9 +161,9 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { case SUCCESS: return true; case LEFT: - return leftBranch.directedWalk(treeWalker); + return left.directedWalk(treeWalker); case RIGHT: - return rightBranch.directedWalk(treeWalker); + return right.directedWalk(treeWalker); case FAILURE: return false; default: @@ -186,25 +172,20 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } @Override - public boolean forEach(TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { + public boolean forEach(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (linearizationMethod == null) { - throw new NullPointerException( - "Linearization method must not be 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); + return preorderTraverse(linearizationMethod, traversalPredicate); case INORDER: - return inorderTraverse(linearizationMethod, - traversalPredicate); + return inorderTraverse(linearizationMethod, traversalPredicate); case POSTORDER: - return postorderTraverse(linearizationMethod, - traversalPredicate); + return postorderTraverse(linearizationMethod, traversalPredicate); default: throw new IllegalArgumentException( "Passed an incorrect TreeLinearizationMethod " @@ -212,10 +193,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } } - private boolean inorderTraverse( - TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { - + private boolean inorderTraverse( TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) { return false; } @@ -224,24 +202,19 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { return false; } - if (!traverseRightBranch(linearizationMethod, - traversalPredicate)) { + if (!traverseRightBranch(linearizationMethod, traversalPredicate)) { return false; } return true; } - private boolean postorderTraverse( - TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { - + private boolean postorderTraverse(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) { return false; } - if (!traverseRightBranch(linearizationMethod, - traversalPredicate)) { + if (!traverseRightBranch(linearizationMethod, traversalPredicate)) { return false; } @@ -253,10 +226,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } - private boolean preorderTraverse( - TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { - + private boolean preorderTraverse(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (!traverseElement(traversalPredicate)) { return false; } @@ -265,8 +235,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { return false; } - if (!traverseRightBranch(linearizationMethod, - traversalPredicate)) { + if (!traverseRightBranch(linearizationMethod, traversalPredicate)) { return false; } @@ -275,37 +244,37 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { private boolean traverseElement(Predicate<T> traversalPredicate) { boolean nodeSuccesfullyTraversed; + if (isDeleted) { nodeSuccesfullyTraversed = true; } else { nodeSuccesfullyTraversed = traversalPredicate.test(data); } + return nodeSuccesfullyTraversed; } - private boolean traverseLeftBranch( - TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { + private boolean traverseLeftBranch(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { boolean leftSuccesfullyTraversed; - if (leftBranch == null) { + + if (left == null) { leftSuccesfullyTraversed = true; } else { - leftSuccesfullyTraversed = leftBranch - .forEach(linearizationMethod, traversalPredicate); + leftSuccesfullyTraversed = left.forEach(linearizationMethod, traversalPredicate); } + return leftSuccesfullyTraversed; } - private boolean traverseRightBranch( - TreeLinearizationMethod linearizationMethod, - Predicate<T> traversalPredicate) { + private boolean traverseRightBranch(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { boolean rightSuccesfullyTraversed; - if (rightBranch == null) { + + if (right == null) { rightSuccesfullyTraversed = true; } else { - rightSuccesfullyTraversed = rightBranch - .forEach(linearizationMethod, traversalPredicate); + rightSuccesfullyTraversed = right.forEach(linearizationMethod, traversalPredicate); } + return rightSuccesfullyTraversed; } -}
\ No newline at end of file +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java index cbd7229..c574196 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java @@ -74,11 +74,11 @@ public interface ITreePart<T> { /** * Execute a directed walk through the tree. * - * @param treeWalker + * @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> treeWalker); + public boolean directedWalk(DirectedWalkFunction<T> walker); /** * Execute a provided function for each element of tree it succesfully @@ -86,11 +86,11 @@ public interface ITreePart<T> { * * @param linearizationMethod * The way to linearize the tree for executing - * @param traversalPredicate - * The function to apply to each element, where it returning + * @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> traversalPredicate); + Predicate<T> predicate); } |