summaryrefslogtreecommitdiff
path: root/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst
diff options
context:
space:
mode:
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata/bst')
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java54
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java49
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java114
3 files changed, 174 insertions, 43 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 060b3f5..e85ae34 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
@@ -39,7 +39,8 @@ public class BinarySearchTree<T> {
* The thing to use for comparing elements
*/
public BinarySearchTree(Comparator<T> cmp) {
- if(cmp == null) throw new NullPointerException("Comparator must not be null");
+ if (cmp == null)
+ throw new NullPointerException("Comparator must not be null");
elementCount = 0;
comparator = cmp;
@@ -54,7 +55,7 @@ public class BinarySearchTree<T> {
public void addNode(T element) {
elementCount++;
- if(root == null) {
+ if (root == null) {
root = new BinarySearchTreeNode<>(element, null, null);
} else {
root.add(element, comparator);
@@ -95,8 +96,8 @@ public class BinarySearchTree<T> {
int pivotAdjustment = 0;
// Add elements until there aren't any left
- while(adjustedPivotInBounds(elements, pivot, pivotAdjustment)) {
- if(root == null) {
+ while (adjustedPivotInBounds(elements, pivot, pivotAdjustment)) {
+ if (root == null) {
// Create a new root element
root = new BinarySearchTreeNode<>(elements.getByIndex(pivot), null, null);
} else {
@@ -112,9 +113,9 @@ public class BinarySearchTree<T> {
}
// Add any trailing unbalanced elements
- if(pivot - pivotAdjustment >= 0) {
+ if (pivot - pivotAdjustment >= 0) {
root.add(elements.getByIndex(pivot - pivotAdjustment), comparator);
- } else if(pivot + pivotAdjustment < elements.getSize()) {
+ } else if (pivot + pivotAdjustment < elements.getSize()) {
root.add(elements.getByIndex(pivot + pivotAdjustment), comparator);
}
}
@@ -163,9 +164,10 @@ public class BinarySearchTree<T> {
* The function to use until it fails
*/
public void traverse(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) {
- if(linearizationMethod == null)
+ if (linearizationMethod == null)
throw new NullPointerException("Linearization method must not be null");
- else if(traversalPredicate == null) throw new NullPointerException("Predicate must not be nulls");
+ else if (traversalPredicate == null)
+ throw new NullPointerException("Predicate must not be nulls");
root.forEach(linearizationMethod, traversalPredicate);
}
@@ -188,4 +190,40 @@ public class BinarySearchTree<T> {
// 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(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (!(obj instanceof BinarySearchTree<?>))
+ return false;
+
+ 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/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java
index 2696577..fe30dad 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
@@ -41,7 +41,8 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> {
@Override
public <E> E collapse(Function<T, E> leafTransformer, BiFunction<E, E, E> branchCollapser) {
- if(leafTransformer == null) throw new NullPointerException("Transformer must not be null");
+ if (leafTransformer == null)
+ throw new NullPointerException("Transformer must not be null");
return leafTransformer.apply(data);
}
@@ -58,16 +59,17 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> {
@Override
public void delete(T element, Comparator<T> comparator) {
- if(data.equals(element)) {
+ if (data.equals(element)) {
isDeleted = true;
}
}
@Override
public boolean directedWalk(DirectedWalkFunction<T> treeWalker) {
- if(treeWalker == null) throw new NullPointerException("Tree walker must not be null");
+ if (treeWalker == null)
+ throw new NullPointerException("Tree walker must not be null");
- switch(treeWalker.walk(data)) {
+ switch (treeWalker.walk(data)) {
case SUCCESS:
return true;
// We don't have any children to care about
@@ -81,8 +83,45 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> {
@Override
public boolean forEach(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) {
- if(traversalPredicate == null) throw new NullPointerException("Predicate must not be null");
+ 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(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (!(obj instanceof BinarySearchTreeLeaf<?>))
+ return false;
+
+ 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/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java
index 4fe9de3..527f221 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
@@ -47,24 +47,25 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public void add(T element, 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);
@@ -77,15 +78,15 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public <E> E collapse(Function<T, E> nodeCollapser, BiFunction<E, E, E> branchCollapser) {
- if(nodeCollapser == null || branchCollapser == null)
+ if (nodeCollapser == null || branchCollapser == null)
throw new NullPointerException("Collapser must not be null");
E collapsedNode = nodeCollapser.apply(data);
- if(left != null) {
+ if (left != null) {
E collapsedLeftBranch = left.collapse(nodeCollapser, branchCollapser);
- if(right != null) {
+ if (right != null) {
E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser);
E collapsedBranches = branchCollapser.apply(collapsedLeftBranch, collapsedRightBranch);
@@ -96,7 +97,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
return branchCollapser.apply(collapsedNode, collapsedLeftBranch);
}
- if(right != null) {
+ if (right != null) {
E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser);
return branchCollapser.apply(collapsedNode, collapsedRightBranch);
@@ -107,10 +108,11 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public boolean contains(T element, 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:
@@ -125,10 +127,11 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public void delete(T element, 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:
@@ -144,9 +147,10 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public boolean directedWalk(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:
@@ -162,11 +166,12 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
@Override
public boolean forEach(TreeLinearizationMethod linearizationMethod, Predicate<T> traversalPredicate) {
- if(linearizationMethod == null)
+ if (linearizationMethod == null)
throw new NullPointerException("Linearization method must not be null");
- else if(traversalPredicate == null) throw new NullPointerException("Predicate must not be 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:
@@ -180,33 +185,42 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
}
private boolean inorderTraverse(TreeLinearizationMethod linearizationMethod, 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;
}
private boolean postorderTraverse(TreeLinearizationMethod linearizationMethod,
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;
}
private boolean preorderTraverse(TreeLinearizationMethod linearizationMethod, 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;
}
@@ -214,7 +228,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
private boolean traverseElement(Predicate<T> traversalPredicate) {
boolean nodeSuccesfullyTraversed;
- if(isDeleted) {
+ if (isDeleted) {
nodeSuccesfullyTraversed = true;
} else {
nodeSuccesfullyTraversed = traversalPredicate.test(data);
@@ -227,7 +241,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
Predicate<T> traversalPredicate) {
boolean leftSuccesfullyTraversed;
- if(left == null) {
+ if (left == null) {
leftSuccesfullyTraversed = true;
} else {
leftSuccesfullyTraversed = left.forEach(linearizationMethod, traversalPredicate);
@@ -240,7 +254,7 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
Predicate<T> traversalPredicate) {
boolean rightSuccesfullyTraversed;
- if(right == null) {
+ if (right == null) {
rightSuccesfullyTraversed = true;
} else {
rightSuccesfullyTraversed = right.forEach(linearizationMethod, traversalPredicate);
@@ -248,4 +262,44 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> {
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(Object obj) {
+ if (this == obj)
+ return true;
+ if (!super.equals(obj))
+ return false;
+ if (!(obj instanceof BinarySearchTreeNode<?>))
+ return false;
+
+ 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;
+ }
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 09:33:27 +0000