diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata')
7 files changed, 287 insertions, 151 deletions
diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java index aabd3cd..9652469 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java @@ -551,7 +551,7 @@ public class FunctionalList<E> implements Cloneable { StringBuilder sb = new StringBuilder("("); // Append the string form of each element - forEach(s -> sb.append(s + ", ")); + forEach(strang -> sb.append(strang + ", ")); // Remove trailing space and comma sb.deleteCharAt(sb.length() - 1); diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java index d04510d..3c819cd 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalStringTokenizer.java @@ -55,11 +55,11 @@ public class FunctionalStringTokenizer { /** * Create a functional string tokenizer from a non-functional one * - * @param wrap + * @param toWrap * The non-functional string tokenizer to wrap */ - public FunctionalStringTokenizer(StringTokenizer wrap) { - this.input = wrap; + public FunctionalStringTokenizer(StringTokenizer toWrap) { + this.input = toWrap; } /** @@ -106,16 +106,16 @@ public class FunctionalStringTokenizer { * @param <E> * The type of the converted tokens * - * @param f + * @param tokenTransformer * The function to use to convert tokens. * @return A list containing all of the converted tokens. */ - public <E> FunctionalList<E> toList(Function<String, E> f) { + public <E> FunctionalList<E> toList(Function<String, E> tokenTransformer) { FunctionalList<E> returnList = new FunctionalList<>(); // Add each token to the list after transforming it - forEachToken(tk -> { - E transformedToken = f.apply(tk); + forEachToken(token -> { + E transformedToken = tokenTransformer.apply(token); returnList.add(transformedToken); }); 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 2785626..ec0e4df 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 @@ -20,41 +20,42 @@ public class BinarySearchTree<T> { /** * The comparator for use in ordering items */ - private Comparator<T> comp; + private Comparator<T> comparator; /** * The current count of elements in the tree */ - private int nCount; + private int elementCount; /** * The root element of the tree */ - private ITreePart<T> root; + private ITreePart<T> rootElement; /** * 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) { - nCount = 0; - comp = cmp; + elementCount = 0; + comparator = cmp; } /** * Add a node to the binary search tree. * - * @param dat + * @param element * The data to add to the binary search tree. */ - public void addNode(T dat) { - nCount++; + public void addNode(T element) { + elementCount++; - if (root == null) { - root = new BinarySearchTreeNode<>(dat, null, null); + if (rootElement == null) { + rootElement = new BinarySearchTreeNode<>(element, null, null); } else { - root.add(dat, comp); + rootElement.add(element, comparator); } } @@ -63,45 +64,79 @@ public class BinarySearchTree<T> { * time, but also O(N) space. */ public void balance() { - FunctionalList<T> elms = new FunctionalList<>(); + FunctionalList<T> elements = new FunctionalList<>(); - root.forEach(TreeLinearizationMethod.INORDER, e -> elms.add(e)); + // Add each element to the list in sorted order + rootElement.forEach(TreeLinearizationMethod.INORDER, + element -> elements.add(element)); - root = null; + // Clear the tree + rootElement = null; - int piv = elms.getSize() / 2; - int adj = 0; + // Set up the pivot and adjustment for readding elements + int pivot = elements.getSize() / 2; + int pivotAdjustment = 0; - while ((piv - adj) >= 0 && (piv + adj) < elms.getSize()) { - if (root == null) { - root = new BinarySearchTreeNode<>(elms.getByIndex(piv), - null, null); + // Add elements until there aren't any left + while (adjustedPivotInBounds(elements, pivot, pivotAdjustment)) { + if (rootElement == null) { + // Create a new root element + rootElement = new BinarySearchTreeNode<>( + elements.getByIndex(pivot), null, null); } else { - root.add(elms.getByIndex(piv + adj), comp); - root.add(elms.getByIndex(piv - adj), comp); + // Add the left and right elements in a balanced manner + rootElement.add( + elements.getByIndex(pivot + pivotAdjustment), + comparator); + + rootElement.add( + elements.getByIndex(pivot - pivotAdjustment), + comparator); } - adj++; + // Increase the distance from the pivot + pivotAdjustment++; } - if ((piv - adj) >= 0) { - root.add(elms.getByIndex(piv - adj), comp); - } else if ((piv + adj) < elms.getSize()) { - root.add(elms.getByIndex(piv + adj), comp); + // Add any trailing unbalanced elements + if ((pivot - pivotAdjustment) >= 0) { + rootElement.add(elements.getByIndex(pivot - pivotAdjustment), + comparator); + } else if ((pivot + pivotAdjustment) < elements.getSize()) { + rootElement.add(elements.getByIndex(pivot + pivotAdjustment), + comparator); } } /** + * Check if an adjusted pivot falls with the bounds of a list + * + * @param elements + * The list to get bounds from + * @param pivot + * The pivot + * @param pivotAdjustment + * The distance from the pivot + * @return Whether the adjusted pivot is with the list + */ + private boolean adjustedPivotInBounds(FunctionalList<T> elements, + int pivot, int pivotAdjustment) { + return (pivot - pivotAdjustment) >= 0 + && (pivot + pivotAdjustment) < elements.getSize(); + } + + /** * 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 dat + * @param element + * The node to delete */ - public void deleteNode(T dat) { - nCount--; + public void deleteNode(T element) { + elementCount--; - root.delete(dat, comp); + rootElement.delete(element, comparator); } /** @@ -110,45 +145,49 @@ public class BinarySearchTree<T> { * @return The root of the tree. */ public ITreePart<T> getRoot() { - return root; + return rootElement; } /** * Check if a node is in the tree * - * @param dat + * @param element * The node to check the presence of for the tree. * @return Whether or not the node is in the tree. */ - public boolean isInTree(T dat) { - return root.contains(dat, comp); + public boolean isInTree(T element) { + return rootElement.contains(element, comparator); } /** * Traverse the tree in a specified way until the function fails * - * @param tlm + * @param linearizationMethod * The way to linearize the tree for traversal - * @param p + * @param traversalPredicate * The function to use until it fails */ - public void traverse(TreeLinearizationMethod tlm, Predicate<T> p) { - root.forEach(tlm, p); + public void traverse(TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { + rootElement.forEach(linearizationMethod, traversalPredicate); } /** * Remove all soft-deleted nodes from the tree. */ public void trim() { - List<T> nds = new ArrayList<>(nCount); + List<T> nodes = new ArrayList<>(elementCount); - traverse(TreeLinearizationMethod.PREORDER, d -> { - nds.add(d); + // Add all non-soft deleted nodes to the tree in insertion order + traverse(TreeLinearizationMethod.PREORDER, node -> { + nodes.add(node); return true; }); - root = null; + // Clear the tree + rootElement = null; - nds.forEach(d -> addNode(d)); + // 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 370e70c..7e31328 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 @@ -22,16 +22,16 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { /** * Whether this node is soft-deleted or not */ - protected boolean deleted; + protected boolean isDeleted; /** * Create a new leaf holding the specified data. * - * @param dat + * @param element * The data for the leaf to hold. */ - public BinarySearchTreeLeaf(T dat) { - data = dat; + public BinarySearchTreeLeaf(T element) { + data = element; } /* @@ -41,7 +41,7 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { * java.util.Comparator) */ @Override - public void add(T dat, Comparator<T> comp) { + public void add(T element, Comparator<T> comparator) { throw new IllegalArgumentException("Can't add to a leaf."); } @@ -53,8 +53,9 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { * java.util.function.BiFunction) */ @Override - public <E> E collapse(Function<T, E> f, BiFunction<E, E, E> bf) { - return f.apply(data); + public <E> E collapse(Function<T, E> leafTransformer, + BiFunction<E, E, E> branchCollapser) { + return leafTransformer.apply(data); } /* @@ -64,8 +65,8 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { * java.util.Comparator) */ @Override - public boolean contains(T dat, Comparator<T> cmp) { - return this.data.equals(dat); + public boolean contains(T element, Comparator<T> comparator) { + return this.data.equals(element); } /* @@ -85,9 +86,9 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { * java.util.Comparator) */ @Override - public void delete(T dat, Comparator<T> cmp) { - if (data.equals(dat)) { - deleted = true; + public void delete(T element, Comparator<T> comparator) { + if (data.equals(element)) { + isDeleted = true; } } @@ -99,8 +100,8 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { * DirectedWalkFunction) */ @Override - public boolean directedWalk(DirectedWalkFunction<T> ds) { - switch (ds.walk(data)) { + public boolean directedWalk(DirectedWalkFunction<T> treeWalker) { + switch (treeWalker.walk(data)) { case SUCCESS: return true; default: @@ -116,7 +117,8 @@ public class BinarySearchTreeLeaf<T> implements ITreePart<T> { * TreeLinearizationMethod, java.util.function.Predicate) */ @Override - public boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c) { - return c.test(data); + public boolean forEach(TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { + 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 b51a9eb..77bb196 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,28 +19,28 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { /** * The left child of this node */ - private ITreePart<T> left; + private ITreePart<T> leftBranch; /** * The right child of this node */ - private ITreePart<T> right; + private ITreePart<T> rightBranch; /** * Create a new node with the specified data and children. * - * @param data + * @param element * The data to store in this node. * @param left * The left child of this node. * @param right * The right child of this node. */ - public BinarySearchTreeNode(T data, ITreePart<T> left, + public BinarySearchTreeNode(T element, ITreePart<T> left, ITreePart<T> right) { - super(data); - this.left = left; - this.right = right; + super(element); + this.leftBranch = left; + this.rightBranch = right; } /* @@ -50,58 +50,74 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { * java.util.Comparator) */ @Override - public void add(T dat, Comparator<T> comp) { - switch (comp.compare(data, dat)) { + public void add(T element, Comparator<T> comparator) { + switch (comparator.compare(data, element)) { case -1: - if (left == null) { - left = new BinarySearchTreeNode<>(dat, null, null); + if (leftBranch == null) { + leftBranch = new BinarySearchTreeNode<>(element, null, + null); } else { - left.add(dat, comp); + leftBranch.add(element, comparator); } case 0: - if (deleted) { - deleted = false; + if (isDeleted) { + isDeleted = false; } else { throw new IllegalArgumentException( "Can't add duplicate values"); } case 1: - if (right == null) { - right = new BinarySearchTreeNode<>(dat, null, null); + if (rightBranch == null) { + rightBranch = new BinarySearchTreeNode<>(element, null, + null); } else { - right.add(dat, comp); + rightBranch.add(element, comparator); } } } @Override - public <E> E collapse(Function<T, E> f, BiFunction<E, E, E> bf) { - E tm = f.apply(data); + public <E> E collapse(Function<T, E> nodeCollapser, + BiFunction<E, E, E> branchCollapser) { + E collapsedNode = nodeCollapser.apply(data); - if (left != null) { - if (right != null) { - return bf.apply(tm, bf.apply(left.collapse(f, bf), - right.collapse(f, bf))); + if (leftBranch != null) { + E collapsedLeftBranch = + leftBranch.collapse(nodeCollapser, branchCollapser); + if (rightBranch != null) { + E collapsedRightBranch = rightBranch + .collapse(nodeCollapser, branchCollapser); + + E collapsedBranches = branchCollapser + .apply(collapsedLeftBranch, collapsedRightBranch); + + return branchCollapser.apply(collapsedNode, + collapsedBranches); } else { - return bf.apply(tm, left.collapse(f, bf)); + return branchCollapser.apply(collapsedNode, + collapsedLeftBranch); } } else { - if (right != null) { - return bf.apply(tm, right.collapse(f, bf)); + if (rightBranch != null) { + E collapsedRightBranch = rightBranch + .collapse(nodeCollapser, branchCollapser); + + return branchCollapser.apply(collapsedNode, + collapsedRightBranch); } else { - return tm; + return collapsedNode; } } } @Override - public boolean contains(T dat, Comparator<T> cmp) { - return directedWalk(ds -> { - switch (cmp.compare(dat, ds)) { + public boolean contains(T element, Comparator<T> comparator) { + return directedWalk(currentElement -> { + switch (comparator.compare(element, currentElement)) { case -1: return LEFT; case 0: - return deleted ? FAILURE : SUCCESS; + return isDeleted ? FAILURE : SUCCESS; case 1: return RIGHT; default: @@ -111,16 +127,16 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } @Override - public void delete(T dat, Comparator<T> cmp) { - directedWalk(ds -> { - switch (cmp.compare(data, dat)) { + public void delete(T element, Comparator<T> comparator) { + directedWalk(currentElement -> { + switch (comparator.compare(data, element)) { case -1: - return left == null ? FAILURE : LEFT; + return leftBranch == null ? FAILURE : LEFT; case 0: - deleted = true; + isDeleted = true; return FAILURE; case 1: - return right == null ? FAILURE : RIGHT; + return rightBranch == null ? FAILURE : RIGHT; default: return FAILURE; } @@ -128,14 +144,14 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } @Override - public boolean directedWalk(DirectedWalkFunction<T> ds) { - switch (ds.walk(data)) { + public boolean directedWalk(DirectedWalkFunction<T> treeWalker) { + switch (treeWalker.walk(data)) { case SUCCESS: return true; case LEFT: - return left.directedWalk(ds); + return leftBranch.directedWalk(treeWalker); case RIGHT: - return right.directedWalk(ds); + return rightBranch.directedWalk(treeWalker); case FAILURE: return false; default: @@ -144,42 +160,119 @@ public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { } @Override - public boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c) { - switch (tlm) { + public boolean forEach(TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { + switch (linearizationMethod) { case PREORDER: - return preorderTraverse(tlm, c); + return preorderTraverse(linearizationMethod, + traversalPredicate); case INORDER: - return inorderTraverse(tlm, c); + return inorderTraverse(linearizationMethod, + traversalPredicate); case POSTORDER: - return postorderTraverse(tlm, c); + return postorderTraverse(linearizationMethod, + traversalPredicate); default: throw new IllegalArgumentException( - "Passed an incorrect TreeLinearizationMethod."); + "Passed an incorrect TreeLinearizationMethod " + + linearizationMethod + ". WAT"); } } - private boolean inorderTraverse(TreeLinearizationMethod tlm, - Predicate<T> c) { + private boolean inorderTraverse( + TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { + + if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) { + return false; + } + + if (!traverseElement(traversalPredicate)) { + return false; + } + + if (!traverseRightBranch(linearizationMethod, + traversalPredicate)) { + return false; + } - return ((left == null ? true : left.forEach(tlm, c)) - && (deleted ? true : c.test(data)) - && (right == null ? true : right.forEach(tlm, c))); + return true; } - private boolean postorderTraverse(TreeLinearizationMethod tlm, - Predicate<T> c) { + private boolean postorderTraverse( + TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { - return ((left == null ? true : left.forEach(tlm, c)) - && (right == null ? true : right.forEach(tlm, c)) - && (deleted ? true : c.test(data))); + if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) { + return false; + } + + if (!traverseRightBranch(linearizationMethod, + traversalPredicate)) { + return false; + } + + if (!traverseElement(traversalPredicate)) { + return false; + } + + return true; } - private boolean preorderTraverse(TreeLinearizationMethod tlm, - Predicate<T> c) { + private boolean preorderTraverse( + TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { + + if (!traverseElement(traversalPredicate)) { + return false; + } - return ((deleted ? true : c.test(data)) - && (left == null ? true : left.forEach(tlm, c)) - && (right == null ? true : right.forEach(tlm, c))); + if (!traverseLeftBranch(linearizationMethod, traversalPredicate)) { + return false; + } + + if (!traverseRightBranch(linearizationMethod, + traversalPredicate)) { + return false; + } + + return true; + } + + 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) { + boolean leftSuccesfullyTraversed; + if (leftBranch == null) { + leftSuccesfullyTraversed = true; + } else { + leftSuccesfullyTraversed = leftBranch + .forEach(linearizationMethod, traversalPredicate); + } + return leftSuccesfullyTraversed; + } + + private boolean traverseRightBranch( + TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate) { + boolean rightSuccesfullyTraversed; + if (rightBranch == null) { + rightSuccesfullyTraversed = true; + } else { + rightSuccesfullyTraversed = rightBranch + .forEach(linearizationMethod, traversalPredicate); + } + return rightSuccesfullyTraversed; } -} +}
\ No newline at end of file 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 12c87b3..3f12fb6 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 @@ -40,9 +40,9 @@ public interface DirectedWalkFunction<T> { /** * Perform a directed walk on a node of a tree. * - * @param data + * @param element * The data stored in the node currently being visited * @return The way the function wants the walk to go next. */ - public DirectedWalkResult walk(T data); + 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 6ed9fa8..8fa5a3d 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 @@ -41,13 +41,13 @@ public interface ITreePart<T> { /** * Add a element below this tree part somewhere. * - * @param dat + * @param element * The element to add below this tree part - * @param comp + * @param comparator * The thing to use for comparing values to find where to * insert the tree part. */ - public void add(T dat, Comparator<T> comp); + public void add(T element, Comparator<T> comparator); /** * Collapses this tree part into a single value. Does not change the @@ -56,26 +56,27 @@ public interface ITreePart<T> { * @param <E> * The type of the final collapsed value * - * @param f + * @param nodeCollapser * The function to use to transform data into mapped form. - * @param bf + * @param branchCollapser * 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> f, BiFunction<E, E, E> bf); + 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 data + * @param element * The data item to look for. - * @param cmp + * @param comparator * 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. */ - public boolean contains(T data, Comparator<T> cmp); + public boolean contains(T element, Comparator<T> comparator); /** * Get the data associated with this tree part. @@ -87,32 +88,33 @@ public interface ITreePart<T> { /** * Remove the given node from this tree part and any of its children. * - * @param dat + * @param element * The data item to remove. - * @param cmp + * @param comparator * The comparator to use to search for the data item. */ - public void delete(T dat, Comparator<T> cmp); + public void delete(T element, Comparator<T> comparator); /** * Execute a directed walk through the tree. * - * @param ds + * @param treeWalker * The function to use to direct the walk through the tree. * @return Whether the directed walk finished successfully. */ - public boolean directedWalk(DirectedWalkFunction<T> ds); + public boolean directedWalk(DirectedWalkFunction<T> treeWalker); /** * Execute a provided function for each element of tree it succesfully * completes for * - * @param tlm + * @param linearizationMethod * The way to linearize the tree for executing - * @param c + * @param traversalPredicate * The function to apply to each element, where it returning * false terminates traversal early * @return Whether the traversal finished succesfully */ - public boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c); + public boolean forEach(TreeLinearizationMethod linearizationMethod, + Predicate<T> traversalPredicate); } |