diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata/bst')
6 files changed, 130 insertions, 127 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 b595946..b3772a4 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 @@ -14,29 +14,29 @@ import bjc.utils.funcdata.IList; * @author ben * * @param <T> - * The data type stored in the node. + * The data type stored in the node. */ public class BinarySearchTree<T> { /* * The comparator for use in ordering items */ - private Comparator<T> comparator; + private Comparator<T> comparator; /* * The current count of elements in the tree */ - private int elementCount; + private int elementCount; /* * The root element of the tree */ - private ITreePart<T> root; + private ITreePart<T> root; /** * Create a new tree using the specified way to compare elements. * * @param cmp - * The thing to use for comparing elements + * The thing to use for comparing elements */ public BinarySearchTree(Comparator<T> cmp) { if (cmp == null) { @@ -51,7 +51,7 @@ public class BinarySearchTree<T> { * Add a node to the binary search tree. * * @param element - * The data to add to the binary search tree. + * The data to add to the binary search tree. */ public void addNode(T element) { elementCount++; @@ -67,11 +67,11 @@ public class BinarySearchTree<T> { * Check if an adjusted pivot falls with the bounds of a list * * @param elements - * The list to get bounds from + * The list to get bounds from * @param pivot - * The pivot + * The pivot * @param pivotAdjustment - * The distance from the pivot + * The distance from the pivot * @return Whether the adjusted pivot is with the list */ private boolean adjustedPivotInBounds(IList<T> elements, int pivot, int pivotAdjustment) { @@ -102,7 +102,8 @@ public class BinarySearchTree<T> { // Create a new root element root = new BinarySearchTreeNode<>(elements.getByIndex(pivot), null, null); } else { - // Add the left and right elements in a balanced manner + // Add the left and right elements in a balanced + // manner root.add(elements.getByIndex(pivot + pivotAdjustment), comparator); root.add(elements.getByIndex(pivot - pivotAdjustment), comparator); @@ -123,11 +124,11 @@ public class BinarySearchTree<T> { /** * 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-deleted nodes stay in the tree until trim()/balance() is + * invoked, and are not included in traversals/finds. * * @param element - * The node to delete + * The node to delete */ public void deleteNode(T element) { elementCount--; @@ -148,7 +149,7 @@ public class BinarySearchTree<T> { * Check if a node is in the tree * * @param element - * The node to check the presence of for the tree. + * The node to check the presence of for the tree. * @return Whether or not the node is in the tree. */ public boolean isInTree(T element) { @@ -159,9 +160,9 @@ public class BinarySearchTree<T> { * Traverse the tree in a specified way until the function fails * * @param linearizationMethod - * The way to linearize the tree for traversal + * The way to linearize the tree for traversal * @param traversalPredicate - * The function to use until it fails + * The function to use until it fails */ public void traverse(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (linearizationMethod == null) { 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 d647742..04765b4 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 @@ -11,24 +11,24 @@ import java.util.function.Predicate; * @author ben * * @param <T> - * The data stored in the tree. + * The data stored in the tree. */ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { /** * The data held in this tree leaf */ - protected T data; + protected T data; /** * Whether this node is soft-deleted or not */ - protected boolean isDeleted; + protected boolean isDeleted; /** * Create a new leaf holding the specified data. * * @param element - * The data for the leaf to hold. + * The data for the leaf to hold. */ public BinarySearchTreeLeaf(T element) { data = element; @@ -72,14 +72,14 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { } 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; + case SUCCESS: + return true; + // We don't have any children to care about + case FAILURE: + case LEFT: + case RIGHT: + default: + return false; } } 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 fa3add0..46a89f2 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 @@ -16,31 +16,30 @@ import java.util.function.Predicate; * @author ben * * @param <T> - * The data type stored in the tree. + * The data type stored in the tree. */ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { /* * The left child of this node */ - private ITreePart<T> left; + private ITreePart<T> left; /* * The right child of this node */ - private ITreePart<T> right; + private ITreePart<T> right; /** * Create a new node with the specified data and children. * * @param element - * The data to store in this node. + * The data to store in this node. * @param lft - * The left child of this node. + * The left child of this node. * @param rght - * The right child of this node. + * The right child of this node. */ - public BinarySearchTreeNode(T element, ITreePart<T> lft, - ITreePart<T> rght) { + public BinarySearchTreeNode(T element, ITreePart<T> lft, ITreePart<T> rght) { super(element); this.left = lft; this.right = rght; @@ -53,29 +52,29 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } 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"); + 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"); } } @@ -118,14 +117,14 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { 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; + case -1: + return LEFT; + case 0: + return isDeleted ? FAILURE : SUCCESS; + case 1: + return RIGHT; + default: + return FAILURE; } }); } @@ -138,15 +137,15 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { 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; + case -1: + return left == null ? FAILURE : LEFT; + case 0: + isDeleted = true; + return FAILURE; + case 1: + return right == null ? FAILURE : RIGHT; + default: + return FAILURE; } }); } @@ -158,16 +157,16 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } 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; + case SUCCESS: + return true; + case LEFT: + return left.directedWalk(treeWalker); + case RIGHT: + return right.directedWalk(treeWalker); + case FAILURE: + return false; + default: + return false; } } @@ -180,20 +179,19 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } 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"); + 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( TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { + private boolean inorderTraverse(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) { return false; } @@ -209,7 +207,8 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { return true; } - private boolean postorderTraverse(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { + private boolean postorderTraverse(TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) { return false; } @@ -254,7 +253,8 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { return nodeSuccesfullyTraversed; } - private boolean traverseLeftBranch(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { + private boolean traverseLeftBranch(TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { boolean leftSuccesfullyTraversed; if (left == null) { @@ -266,7 +266,8 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { return leftSuccesfullyTraversed; } - private boolean traverseRightBranch(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) { + private boolean traverseRightBranch(TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { boolean rightSuccesfullyTraversed; if (right == null) { diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java index 3f12fb6..e68bef6 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java @@ -6,7 +6,7 @@ package bjc.utils.funcdata.bst; * @author ben * * @param <T> - * The type of element stored in the walked tree + * The type of element stored in the walked tree */ @FunctionalInterface public interface DirectedWalkFunction<T> { @@ -22,7 +22,8 @@ public interface DirectedWalkFunction<T> { */ FAILURE, /** - * Specifies that the function wants to move left in the tree next. + * Specifies that the function wants to move left in the tree + * next. */ LEFT, /** @@ -41,7 +42,7 @@ public interface DirectedWalkFunction<T> { * Perform a directed walk on a node of a tree. * * @param element - * The data stored in the node currently being visited + * 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/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java index c574196..c648001 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 @@ -11,17 +11,17 @@ import java.util.function.Predicate; * @author ben * * @param <T> - * The data contained in this part of the tree. + * 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 + * 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. + * The thing to use for comparing values to find where to + * insert the tree part. */ public void add(T element, Comparator<T> comparator); @@ -30,25 +30,25 @@ public interface ITreePart<T> { * underlying tree. * * @param <E> - * The type of the final collapsed value + * The type of the final collapsed value * * @param nodeCollapser - * The function to use to transform data into mapped form. + * 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. + * 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); + 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. + * The data item to look for. * @param comparator - * The comparator to use to search for the data item + * 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. */ @@ -65,9 +65,9 @@ public interface ITreePart<T> { * Remove the given node from this tree part and any of its children. * * @param element - * The data item to remove. + * The data item to remove. * @param comparator - * The comparator to use to search for the data item. + * The comparator to use to search for the data item. */ public void delete(T element, Comparator<T> comparator); @@ -75,7 +75,8 @@ public interface ITreePart<T> { * Execute a directed walk through the tree. * * @param walker - * The function to use to direct the walk through the tree. + * The function to use to direct the walk through the + * tree. * @return Whether the directed walk finished successfully. */ public boolean directedWalk(DirectedWalkFunction<T> walker); @@ -85,12 +86,11 @@ public interface ITreePart<T> { * completes for * * @param linearizationMethod - * The way to linearize the tree for executing + * The way to linearize the tree for executing * @param predicate - * The predicate to apply to each element, where it returning - * false terminates traversal early + * 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); + public boolean forEach(TreeLinearizationMethod linearizationMethod, Predicate<T> predicate); } diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java index eedb189..f7d6280 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java @@ -8,8 +8,8 @@ package bjc.utils.funcdata.bst; */ public enum TreeLinearizationMethod { /** - * Visit the left side of this tree part, the tree part itself, and - * then the right part. + * Visit the left side of this tree part, the tree part itself, and then + * the right part. */ INORDER, /** @@ -18,8 +18,8 @@ public enum TreeLinearizationMethod { */ POSTORDER, /** - * Visit the tree part itself, then the left side of tthis tree part - * and then the right part. + * 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 |