diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata')
5 files changed, 131 insertions, 86 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 3fd05da..d2f0988 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/FunctionalList.java @@ -129,6 +129,7 @@ public class FunctionalList<E> implements Cloneable { return true; } } + return false; } @@ -203,11 +204,7 @@ public class FunctionalList<E> implements Cloneable { public <T> FunctionalList<T> flatMap(Function<E, List<T>> f) { FunctionalList<T> fl = new FunctionalList<>(this.wrap.size()); - forEach(e -> { - f.apply(e).forEach(e2 -> { - fl.add(e2); - }); - }); + forEach(e -> f.apply(e).forEach(fl::add)); return fl; } @@ -230,11 +227,13 @@ public class FunctionalList<E> implements Cloneable { * index. */ public void forEachIndexed(BiConsumer<Integer, E> c) { - int i = 0; + GenHolder<Integer> i = new GenHolder<>(0); - for (E e : wrap) { - c.accept(i++, e); - } + wrap.forEach((val) -> { + c.accept(i.unwrap(vl -> vl), val); + + i.transform((vl) -> vl + 1); + }); } /** @@ -267,7 +266,7 @@ public class FunctionalList<E> implements Cloneable { public FunctionalList<E> getMatching(Predicate<E> matchPred) { FunctionalList<E> fl = new FunctionalList<>(); - this.forEach((elem) -> { + wrap.forEach((elem) -> { if (matchPred.test(elem)) { fl.add(elem); } @@ -369,6 +368,10 @@ public class FunctionalList<E> implements Cloneable { return wrap.removeIf(remPred); } + public void removeMatching(E obj) { + removeIf((ele) -> ele.equals(obj)); + } + /** * Perform a binary search for the specified key using the provided * means of comparing elements. Since this IS a binary search, the list @@ -423,9 +426,12 @@ public class FunctionalList<E> implements Cloneable { return sb.toString(); } - public void removeMatching(E obj) { - removeIf((ele) -> { - return ele.equals(obj); - }); + /** + * Retrieve the size of the wrapped list + * + * @return The size of the wrapped list + */ + public int getSize() { + return wrap.size(); } } 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 7bf0007..7665797 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 @@ -5,6 +5,7 @@ import java.util.Comparator; import java.util.List; import java.util.function.Predicate; +import bjc.utils.funcdata.FunctionalList; import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod; /** @@ -49,6 +50,7 @@ public class BinarySearchTree<T> { */ public void addNode(T dat) { nCount++; + if (root == null) { root = new TreeNode<T>(dat, null, null); } else { @@ -61,43 +63,34 @@ public class BinarySearchTree<T> { * time, but also O(N) space. */ public void balance() { - ArrayList<T> elms = new ArrayList<>(nCount); + FunctionalList<T> elms = new FunctionalList<>(); root.forEach(TreeLinearizationMethod.INORDER, e -> elms.add(e)); root = null; - int piv = elms.size() / 2; + int piv = elms.getSize() / 2; int adj = 0; - while ((piv - adj) >= 0 && (piv + adj) < elms.size()) { + while ((piv - adj) >= 0 && (piv + adj) < elms.getSize()) { if (root == null) { - root = new TreeNode<T>(elms.get(piv), null, null); + root = new TreeNode<T>(elms.getByIndex(piv), null, null); } else { - root.add(elms.get(piv + adj), comp); - root.add(elms.get(piv - adj), comp); + root.add(elms.getByIndex(piv + adj), comp); + root.add(elms.getByIndex(piv - adj), comp); } adj++; } if ((piv - adj) >= 0) { - root.add(elms.get(piv - adj), comp); - } else if ((piv + adj) < elms.size()) { - root.add(elms.get(piv + adj), comp); + root.add(elms.getByIndex(piv - adj), comp); + } else if ((piv + adj) < elms.getSize()) { + root.add(elms.getByIndex(piv + adj), comp); } } /** - * Get the root of the tree. - * - * @return The root of the tree. - */ - public ITreePart<T> getRoot() { - return root; - } - - /** * 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. @@ -106,10 +99,20 @@ public class BinarySearchTree<T> { */ public void deleteNode(T dat) { nCount--; + root.delete(dat, comp); } /** + * Get the root of the tree. + * + * @return The root of the tree. + */ + public ITreePart<T> getRoot() { + return root; + } + + /** * Check if a node is in the tree * * @param dat 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 18e80be..12c87b3 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,9 +2,11 @@ package bjc.utils.funcdata.bst; /** * Represents a function for doing a directed walk of a binary tree. + * * @author ben * * @param <T> + * The type of element stored in the walked tree */ @FunctionalInterface public interface DirectedWalkFunction<T> { @@ -16,27 +18,30 @@ public interface DirectedWalkFunction<T> { */ public enum DirectedWalkResult { /** - * Specifies that the function has succesfully completed - * - */ - SUCCESS, - /** * Specifies that the function has failed. */ FAILURE, - /** + /** * Specifies that the function wants to move left in the tree next. */ - LEFT, + LEFT, /** - * Specifies that the function wants to move right in the tree next. + * Specifies that the function wants to move right in the tree + * next. */ - RIGHT + RIGHT, + /** + * Specifies that the function has succesfully completed + * + */ + SUCCESS } /** * Perform a directed walk on a node of a tree. - * @param data The data stored in the node currently being visited + * + * @param data + * 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); 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 0c8f12e..dfcfedd 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,75 +7,109 @@ import java.util.function.Predicate; /** * A interface for the fundamental things that want to be part of a tree. + * * @author ben * - * @param <T> The data contained in this part of the tree. + * @param <T> + * The data contained in this part of the tree. */ public interface ITreePart<T> { /** * Represents the ways to linearize a tree for traversal. + * * @author ben * */ 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, + INORDER, /** - * Visit the left side of this tree part, the right side, and then the tree part itself. + * Visit the left side of this tree part, the right side, and then + * the tree part itself. */ - POSTORDER, + 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 } - + /** * Add a element below this tree part somewhere. - * @param dat The element to add below this tree part - * @param comp The thing to use for comparing values to find where to insert the tree part. + * + * @param dat + * The element to add below this tree part + * @param comp + * The thing to use for comparing values to find where to + * insert the tree part. */ - void add(T dat, Comparator<T> comp); + public void add(T dat, Comparator<T> comp); + /** - * Collapses this tree part into a single value. - * Does not change the underlying tree. - * @param f The function to use to transform data into mapped form. - * @param bf The function to use to collapse data in mapped form into a single value. + * Collapses this tree part into a single value. Does not change the + * underlying tree. + * + * @param f + * The function to use to transform data into mapped form. + * @param bf + * The function to use to collapse data in mapped form into + * a single value. * @return A single value from collapsing the tree. */ - <E> E collapse(Function<T, E> f, BiFunction<E, E, E> bf); + public <E> E collapse(Function<T, E> f, BiFunction<E, E, E> bf); + /** * Check if this tre part or below it contains the specified data item - * @param data The data item to look for. - * @param cmp 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. + * + * @param data + * The data item to look for. + * @param cmp + * 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. */ - boolean contains(T data, Comparator<T> cmp); + public boolean contains(T data, Comparator<T> cmp); + /** * Get the data associated with this tree part. + * * @return The data associated with this tree part. */ - T data(); + public T data(); + /** * Remove the given node from this tree part and any of its children. - * @param dat The data item to remove. - * @param cmp The comparator to use to search for the data item. + * + * @param dat + * The data item to remove. + * @param cmp + * The comparator to use to search for the data item. */ - void delete(T dat, Comparator<T> cmp); + public void delete(T dat, Comparator<T> cmp); + /** * Execute a directed walk through the tree. - * @param ds The function to use to direct the walk through the tree. + * + * @param ds + * The function to use to direct the walk through the tree. * @return Whether the directed walk finished successfully. */ - boolean directedWalk(DirectedWalkFunction<T> ds); + public boolean directedWalk(DirectedWalkFunction<T> ds); + /** - * Execute a provided function for each element of tree it succesfully completes for - * @param tlm The way to linearize the tree for executing - * @param c The function to apply to each element, where it returning false - * terminates traversal early + * Execute a provided function for each element of tree it succesfully + * completes for + * + * @param tlm + * The way to linearize the tree for executing + * @param c + * The function to apply to each element, where it returning + * false terminates traversal early * @return Whether the traversal finished succesfully */ - boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c); + public boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c); } diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java index 40cc53f..e8c6c8b 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java @@ -111,20 +111,17 @@ public class TreeNode<T> extends TreeLeaf<T> { @Override public void delete(T dat, Comparator<T> cmp) { - directedWalk(new DirectedWalkFunction<T>() { - @Override - public DirectedWalkResult walk(T ds) { - switch (cmp.compare(data, dat)) { - case -1: - return left == null ? FAILURE : LEFT; - case 0: - deleted = true; - return FAILURE; - case 1: - return right == null ? FAILURE : RIGHT; - default: - return DirectedWalkResult.FAILURE; - } + directedWalk(ds -> { + switch (cmp.compare(data, dat)) { + case -1: + return left == null ? FAILURE : LEFT; + case 0: + deleted = true; + return FAILURE; + case 1: + return right == null ? FAILURE : RIGHT; + default: + return FAILURE; } }); } |