summaryrefslogtreecommitdiff
path: root/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java')
-rw-r--r--src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java126
1 files changed, 76 insertions, 50 deletions
diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java
index 0453f80..a73f81a 100644
--- a/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java
+++ b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java
@@ -16,7 +16,7 @@ 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 */
@@ -29,15 +29,16 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
* 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(final T element, final ITreePart<T> lft, final ITreePart<T> rght) {
+ public BinarySearchTreeNode(final T element, final ITreePart<T> lft,
+ final ITreePart<T> rght) {
super(element);
this.left = lft;
this.right = rght;
@@ -45,24 +46,25 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public void add(final T element, final Comparator<T> comparator) {
- if(comparator == null) throw new NullPointerException("Comparator must not be null");
+ if (comparator == null)
+ throw new NullPointerException("Comparator must not be null");
- switch(comparator.compare(data, element)) {
+ switch (comparator.compare(data, element)) {
case -1:
- if(left == null) {
+ if (left == null) {
left = new BinarySearchTreeNode<>(element, null, null);
} else {
left.add(element, comparator);
}
break;
case 0:
- if(isDeleted) {
+ if (isDeleted) {
isDeleted = false;
} else
throw new IllegalArgumentException("Can't add duplicate values");
break;
case 1:
- if(right == null) {
+ if (right == null) {
right = new BinarySearchTreeNode<>(element, null, null);
} else {
right.add(element, comparator);
@@ -74,17 +76,19 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
}
@Override
- public <E> E collapse(final Function<T, E> nodeCollapser, final BiFunction<E, E, E> branchCollapser) {
- if(nodeCollapser == null || branchCollapser == null)
+ 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) {
+ if (left != null) {
final E collapsedLeftBranch = left.collapse(nodeCollapser, branchCollapser);
- if(right != null) {
- final E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser);
+ if (right != null) {
+ final E collapsedRightBranch
+ = right.collapse(nodeCollapser, branchCollapser);
final E collapsedBranches = branchCollapser.apply(collapsedLeftBranch,
collapsedRightBranch);
@@ -95,7 +99,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
return branchCollapser.apply(collapsedNode, collapsedLeftBranch);
}
- if(right != null) {
+ if (right != null) {
final E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser);
return branchCollapser.apply(collapsedNode, collapsedRightBranch);
@@ -106,10 +110,11 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public boolean contains(final T element, final Comparator<T> comparator) {
- if(comparator == null) throw new NullPointerException("Comparator must not be null");
+ if (comparator == null)
+ throw new NullPointerException("Comparator must not be null");
return directedWalk(currentElement -> {
- switch(comparator.compare(element, currentElement)) {
+ switch (comparator.compare(element, currentElement)) {
case -1:
return LEFT;
case 0:
@@ -124,10 +129,11 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public void delete(final T element, final Comparator<T> comparator) {
- if(comparator == null) throw new NullPointerException("Comparator must not be null");
+ if (comparator == null)
+ throw new NullPointerException("Comparator must not be null");
directedWalk(currentElement -> {
- switch(comparator.compare(data, element)) {
+ switch (comparator.compare(data, element)) {
case -1:
return left == null ? FAILURE : LEFT;
case 0:
@@ -143,9 +149,10 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public boolean directedWalk(final DirectedWalkFunction<T> treeWalker) {
- if(treeWalker == null) throw new NullPointerException("Walker must not be null");
+ if (treeWalker == null)
+ throw new NullPointerException("Walker must not be null");
- switch(treeWalker.walk(data)) {
+ switch (treeWalker.walk(data)) {
case SUCCESS:
return true;
case LEFT:
@@ -161,13 +168,13 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public boolean forEach(final TreeLinearizationMethod linearizationMethod,
final Predicate<T> traversalPredicate) {
- if(linearizationMethod == null) {
+ if (linearizationMethod == null) {
throw new NullPointerException("Linearization method must not be null");
- } else if(traversalPredicate == null) {
+ } else if (traversalPredicate == null) {
throw new NullPointerException("Predicate must not be null");
}
- switch(linearizationMethod) {
+ switch (linearizationMethod) {
case PREORDER:
return preorderTraverse(linearizationMethod, traversalPredicate);
case INORDER:
@@ -175,8 +182,9 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
case POSTORDER:
return postorderTraverse(linearizationMethod, traversalPredicate);
default:
- String msg = String.format("Passed an incorrect TreeLinearizationMethod %s. WAT",
- linearizationMethod);
+ String msg
+ = String.format("Passed an incorrect TreeLinearizationMethod %s. WAT",
+ linearizationMethod);
throw new IllegalArgumentException(msg);
}
@@ -185,11 +193,14 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
/* Do an in-order traversal. */
private boolean inorderTraverse(final TreeLinearizationMethod linearizationMethod,
final Predicate<T> traversalPredicate) {
- if(!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false;
+ if (!traverseLeftBranch(linearizationMethod, traversalPredicate))
+ return false;
- if(!traverseElement(traversalPredicate)) return false;
+ if (!traverseElement(traversalPredicate))
+ return false;
- if(!traverseRightBranch(linearizationMethod, traversalPredicate)) return false;
+ if (!traverseRightBranch(linearizationMethod, traversalPredicate))
+ return false;
return true;
}
@@ -197,11 +208,14 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
/* Do a post-order traversal. */
private boolean postorderTraverse(final TreeLinearizationMethod linearizationMethod,
final Predicate<T> traversalPredicate) {
- if(!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false;
+ if (!traverseLeftBranch(linearizationMethod, traversalPredicate))
+ return false;
- if(!traverseRightBranch(linearizationMethod, traversalPredicate)) return false;
+ if (!traverseRightBranch(linearizationMethod, traversalPredicate))
+ return false;
- if(!traverseElement(traversalPredicate)) return false;
+ if (!traverseElement(traversalPredicate))
+ return false;
return true;
@@ -210,11 +224,14 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
/* Do a pre-order traversal. */
private boolean preorderTraverse(final TreeLinearizationMethod linearizationMethod,
final Predicate<T> traversalPredicate) {
- if(!traverseElement(traversalPredicate)) return false;
+ if (!traverseElement(traversalPredicate))
+ return false;
- if(!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false;
+ if (!traverseLeftBranch(linearizationMethod, traversalPredicate))
+ return false;
- if(!traverseRightBranch(linearizationMethod, traversalPredicate)) return false;
+ if (!traverseRightBranch(linearizationMethod, traversalPredicate))
+ return false;
return true;
}
@@ -223,7 +240,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
private boolean traverseElement(final Predicate<T> traversalPredicate) {
boolean nodeSuccesfullyTraversed;
- if(isDeleted) {
+ if (isDeleted) {
nodeSuccesfullyTraversed = true;
} else {
nodeSuccesfullyTraversed = traversalPredicate.test(data);
@@ -237,10 +254,11 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
final Predicate<T> traversalPredicate) {
boolean leftSuccesfullyTraversed;
- if(left == null) {
+ if (left == null) {
leftSuccesfullyTraversed = true;
} else {
- leftSuccesfullyTraversed = left.forEach(linearizationMethod, traversalPredicate);
+ leftSuccesfullyTraversed
+ = left.forEach(linearizationMethod, traversalPredicate);
}
return leftSuccesfullyTraversed;
@@ -251,10 +269,11 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
final Predicate<T> traversalPredicate) {
boolean rightSuccesfullyTraversed;
- if(right == null) {
+ if (right == null) {
rightSuccesfullyTraversed = true;
} else {
- rightSuccesfullyTraversed = right.forEach(linearizationMethod, traversalPredicate);
+ rightSuccesfullyTraversed
+ = right.forEach(linearizationMethod, traversalPredicate);
}
return rightSuccesfullyTraversed;
@@ -276,19 +295,26 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public boolean equals(final Object obj) {
- if(this == obj) return true;
- if(!super.equals(obj)) return false;
- if(!(obj instanceof BinarySearchTreeNode<?>)) return false;
+ 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 (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;
+ if (right == null) {
+ if (other.right != null)
+ return false;
+ } else if (!right.equals(other.right))
+ return false;
return true;
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 10:17:06 +0000