summaryrefslogtreecommitdiff
path: root/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst
diff options
context:
space:
mode:
authorEVE <EVE@EVE-PC>2017-03-14 12:07:14 -0400
committerEVE <EVE@EVE-PC>2017-03-14 12:07:14 -0400
commit504ca816530efdff06bc202e0432ebd354aec304 (patch)
tree4836932fb81d1d625470502c78c94d202c9a7420 /BJC-Utils2/src/main/java/bjc/utils/funcdata/bst
parent5c1163df17c46f7d3e15b6c7949c38843ec56146 (diff)
Cleanup
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.java44
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java20
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java106
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java8
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java18
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java2
6 files changed, 79 insertions, 119 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 b3772a4..060b3f5 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
@@ -1,16 +1,16 @@
package bjc.utils.funcdata.bst;
+import bjc.utils.funcdata.FunctionalList;
+import bjc.utils.funcdata.IList;
+
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 <T>
@@ -34,14 +34,12 @@ public class BinarySearchTree<T> {
/**
* Create a new tree using the specified way to compare elements.
- *
+ *
* @param cmp
* 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;
@@ -49,14 +47,14 @@ public class BinarySearchTree<T> {
/**
* Add a node to the binary search tree.
- *
+ *
* @param element
* The data to add to the binary search tree.
*/
public void addNode(T element) {
elementCount++;
- if (root == null) {
+ if(root == null) {
root = new BinarySearchTreeNode<>(element, null, null);
} else {
root.add(element, comparator);
@@ -65,7 +63,7 @@ public class BinarySearchTree<T> {
/**
* Check if an adjusted pivot falls with the bounds of a list
- *
+ *
* @param elements
* The list to get bounds from
* @param pivot
@@ -75,7 +73,7 @@ public class BinarySearchTree<T> {
* @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();
+ return pivot - pivotAdjustment >= 0 && pivot + pivotAdjustment < elements.getSize();
}
/**
@@ -97,8 +95,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 {
@@ -114,9 +112,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);
}
}
@@ -126,7 +124,7 @@ public class BinarySearchTree<T> {
*
* 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
*/
@@ -138,7 +136,7 @@ public class BinarySearchTree<T> {
/**
* Get the root of the tree.
- *
+ *
* @return The root of the tree.
*/
public ITreePart<T> getRoot() {
@@ -147,7 +145,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.
* @return Whether or not the node is in the tree.
@@ -158,18 +156,16 @@ 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
* @param traversalPredicate
* 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);
}
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 04765b4..2696577 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
@@ -7,7 +7,7 @@ import java.util.function.Predicate;
/**
* A leaf in a tree.
- *
+ *
* @author ben
*
* @param <T>
@@ -26,7 +26,7 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> {
/**
* Create a new leaf holding the specified data.
- *
+ *
* @param element
* The data for the leaf to hold.
*/
@@ -41,9 +41,7 @@ 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);
}
@@ -60,18 +58,16 @@ 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
@@ -85,9 +81,7 @@ 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);
}
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 46a89f2..4fe9de3 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
@@ -1,18 +1,18 @@
package bjc.utils.funcdata.bst;
-import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.FAILURE;
-import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.LEFT;
-import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.RIGHT;
-import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.SUCCESS;
-
import java.util.Comparator;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
+import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.FAILURE;
+import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.LEFT;
+import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.RIGHT;
+import static bjc.utils.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.SUCCESS;
+
/**
* A binary node in a tree.
- *
+ *
* @author ben
*
* @param <T>
@@ -31,7 +31,7 @@ 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.
* @param lft
@@ -47,27 +47,24 @@ 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 {
+ } 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);
@@ -80,16 +77,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);
@@ -100,7 +96,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);
@@ -111,12 +107,10 @@ 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:
@@ -131,12 +125,10 @@ 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:
@@ -152,11 +144,9 @@ 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:
@@ -172,13 +162,11 @@ 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:
@@ -192,51 +180,33 @@ 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;
}
@@ -244,7 +214,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);
@@ -257,7 +227,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);
@@ -270,7 +240,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);
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 e68bef6..e11524a 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
@@ -2,7 +2,7 @@ package bjc.utils.funcdata.bst;
/**
* Represents a function for doing a directed walk of a binary tree.
- *
+ *
* @author ben
*
* @param <T>
@@ -12,7 +12,7 @@ package bjc.utils.funcdata.bst;
public interface DirectedWalkFunction<T> {
/**
* Represents the results used to direct a walk in a binary tree.
- *
+ *
* @author ben
*
*/
@@ -33,14 +33,14 @@ public interface DirectedWalkFunction<T> {
RIGHT,
/**
* Specifies that the function has succesfully completed
- *
+ *
*/
SUCCESS
}
/**
* Perform a directed walk on a node of a tree.
- *
+ *
* @param element
* The data stored in the node currently being visited
* @return The way the function wants the walk to go next.
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 c648001..3aa8880 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
@@ -7,7 +7,7 @@ import java.util.function.Predicate;
/**
* A interface for the fundamental things that want to be part of a tree.
- *
+ *
* @author ben
*
* @param <T>
@@ -16,7 +16,7 @@ import java.util.function.Predicate;
public interface ITreePart<T> {
/**
* Add a element below this tree part somewhere.
- *
+ *
* @param element
* The element to add below this tree part
* @param comparator
@@ -28,10 +28,10 @@ public interface ITreePart<T> {
/**
* Collapses this tree part into a single value. Does not change the
* underlying tree.
- *
+ *
* @param <E>
* The type of the final collapsed value
- *
+ *
* @param nodeCollapser
* The function to use to transform data into mapped
* form.
@@ -44,7 +44,7 @@ public interface ITreePart<T> {
/**
* Check if this tre part or below it contains the specified data item
- *
+ *
* @param element
* The data item to look for.
* @param comparator
@@ -56,14 +56,14 @@ public interface ITreePart<T> {
/**
* Get the data associated with this tree part.
- *
+ *
* @return The data associated with this tree part.
*/
public T data();
/**
* Remove the given node from this tree part and any of its children.
- *
+ *
* @param element
* The data item to remove.
* @param comparator
@@ -73,7 +73,7 @@ public interface ITreePart<T> {
/**
* Execute a directed walk through the tree.
- *
+ *
* @param walker
* The function to use to direct the walk through the
* tree.
@@ -84,7 +84,7 @@ public interface ITreePart<T> {
/**
* Execute a provided function for each element of tree it succesfully
* completes for
- *
+ *
* @param linearizationMethod
* The way to linearize the tree for executing
* @param 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 f7d6280..0c83867 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
@@ -2,7 +2,7 @@ package bjc.utils.funcdata.bst;
/**
* Represents the ways to linearize a tree for traversal.
- *
+ *
* @author ben
*
*/