diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/data/bst')
5 files changed, 526 insertions, 0 deletions
diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java new file mode 100644 index 0000000..509cfcd --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java @@ -0,0 +1,128 @@ +package bjc.utils.data.bst; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.function.Predicate; + +import bjc.utils.data.bst.ITreePart.TreeLinearizationMethod; + +/** + * A binary search tree, with some mild support for functional traversal. + * + * @author ben + * + * @param <T> The data type stored in the node. + */ +public class BinarySearchTree<T> { + private Comparator<T> comp; + private int nCount; + private ITreePart<T> root; + + /** + * Create a new tree using the specified way to compare elements. + * @param cmp + */ + public BinarySearchTree(Comparator<T> cmp) { + nCount = 0; + comp = cmp; + } + + /** + * Add a node to the binary search tree. + * @param dat The data to add to the binary search tree. + */ + public void addNode(T dat) { + nCount++; + if (root == null) { + root = new TreeNode<T>(dat, null, null); + } else { + root.add(dat, comp); + } + } + + /** + * Balance the tree, and remove soft-deleted nodes for free. + * Takes O(N) time, but also O(N) space. + */ + public void balance() { + ArrayList<T> elms = new ArrayList<>(nCount); + + root.forEach(TreeLinearizationMethod.INORDER, e -> elms.add(e)); + + root = null; + + int piv = elms.size() / 2; + int adj = 0; + + while((piv - adj) >= 0 && (piv + adj) < elms.size()) { + if(root == null) { + root = new TreeNode<T>(elms.get(piv), null, null); + } else { + root.add(elms.get(piv + adj), comp); + root.add(elms.get(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); + } + } + + /** + * 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. + * @param dat + */ + public void deleteNode(T dat) { + nCount--; + root.delete(dat, comp); + } + + /** + * Check if a node is in the tree + * @param dat 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); + } + + /** + * Traverse the tree in a specified way until the function fails + * @param tlm The way to linearize the tree for traversal + * @param p The function to use until it fails + */ + public void traverse(TreeLinearizationMethod tlm, Predicate<T> p) { + root.forEach(tlm, p); + } + + /** + * Remove all soft-deleted nodes from the tree. + */ + public void trim() { + List<T> nds = new ArrayList<>(nCount); + + traverse(TreeLinearizationMethod.PREORDER, d -> { + nds.add(d); + return true; + }); + + root = null; + + nds.forEach(d -> addNode(d)); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java new file mode 100644 index 0000000..232f3d4 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java @@ -0,0 +1,43 @@ +package bjc.utils.data.bst; + +/** + * Represents a function for doing a directed walk of a binary tree. + * @author ben + * + * @param <T> + */ +@FunctionalInterface +public interface DirectedWalkFunction<T> { + /** + * Represents the results used to direct a walk in a binary tree. + * + * @author ben + * + */ + 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, + /** + * Specifies that the function wants to move right in the tree next. + */ + RIGHT + } + + /** + * Perform a directed walk on a node of a tree. + * @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/data/bst/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java new file mode 100644 index 0000000..5667ce1 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java @@ -0,0 +1,81 @@ +package bjc.utils.data.bst; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +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. + */ +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. + */ + INORDER, + /** + * Visit the left side of this tree part, the right side, and then the tree part itself. + */ + POSTORDER, + /** + * 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. + */ + 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. + * @return A single value from collapsing the tree. + */ + <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. + */ + 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(); + /** + * 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. + */ + 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. + * @return Whether the directed walk finished successfully. + */ + 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 + * @return Whether the traversal finished succesfully + */ + boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c); +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java new file mode 100644 index 0000000..173afc1 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java @@ -0,0 +1,101 @@ +package bjc.utils.data.bst; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A leaf in a tree. + * @author ben + * + * @param <T> The data stored in the tree. + */ +public class TreeLeaf<T> implements ITreePart<T> { + protected T data; + protected boolean deleted; + + /** + * Create a new leaf holding the specified data. + * @param dat The data for the leaf to hold. + */ + public TreeLeaf(T dat) { + data = dat; + } + + /* + * Can't add things to a leaf. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#add(java.lang.Object, java.util.Comparator) + */ + @Override + public void add(T dat, Comparator<T> comp) { + throw new IllegalArgumentException("Can't add to a leaf."); + } + + /* + * Just transform our data. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#collapse(java.util.function.Function, java.util.function.BiFunction) + */ + @Override + public <E> E collapse(Function<T, E> f, BiFunction<E, E, E> bf) { + return f.apply(data); + } + + /* + * Only check our data. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#contains(java.lang.Object, java.util.Comparator) + */ + @Override + public boolean contains(T data, Comparator<T> cmp) { + return this.data.equals(data); + } + + /* + * Just get the data + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#data() + */ + @Override + public T data() { + return data; + } + + /* + * Just mark ourselves as "not here" + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#delete(java.lang.Object, java.util.Comparator) + */ + @Override + public void delete(T dat, Comparator<T> cmp) { + if(data.equals(dat)) { + deleted = true; + } + } + + /* + * Just walk our data and only succede if the walk does, because there's nowhere left to go. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#directedWalk(bjc.utils.data.bst.DirectedWalkFunction) + */ + @Override + public boolean directedWalk(DirectedWalkFunction<T> ds) { + switch(ds.walk(data)) { + case SUCCESS: + return true; + default: + return false; + } + } + + /* + * Just check our data. + * (non-Javadoc) + * @see bjc.utils.data.bst.ITreePart#forEach(bjc.utils.data.bst.ITreePart.TreeLinearizationMethod, java.util.function.Predicate) + */ + public boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c) { + return c.test(data); + } +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java new file mode 100644 index 0000000..660fd03 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java @@ -0,0 +1,173 @@ +package bjc.utils.data.bst; + +import static bjc.utils.data.bst.DirectedWalkFunction.DirectedWalkResult.*; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +/** + * A binary node in a tree. + * @author ben + * + * @param <T> The data type stored in the tree. + */ +public class TreeNode<T> extends TreeLeaf<T> { + private ITreePart<T> left; + private ITreePart<T> right; + + /** + * Create a new node with the specified data and children. + * @param data The data to store in this node. + * @param left The left child of this node. + * @param right The right child of this node. + */ + public TreeNode(T data, ITreePart<T> left, ITreePart<T> right) { + super(data); + this.left = left; + this.right = right; + } + + /* + * Either adds it to the left/right, or undeletes itself. + * (non-Javadoc) + * @see bjc.utils.data.bst.TreeLeaf#add(java.lang.Object, java.util.Comparator) + */ + @Override + public void add(T dat, Comparator<T> comp) { + switch (comp.compare(data, dat)) { + case -1: + if (left == null) { + left = new TreeNode<T>(dat, null, null); + } else { + left.add(dat, comp); + } + case 0: + if (deleted) { + deleted = false; + } else { + throw new IllegalArgumentException( + "Can't add duplicate values"); + } + case 1: + if (right == null) { + right = new TreeNode<T>(dat, null, null); + } else { + right.add(dat, comp); + } + } + } + + @Override + public <E> E collapse(Function<T, E> f, BiFunction<E, E, E> bf) { + E tm = f.apply(data); + + if (left != null) { + if (right != null) { + return bf.apply(tm, bf.apply(left.collapse(f, bf), + right.collapse(f, bf))); + } else { + return bf.apply(tm, left.collapse(f, bf)); + } + } else { + if(right != null) { + return bf.apply(tm, right.collapse(f, bf)); + } else { + return tm; + } + } + } + + @Override + public boolean contains(T data, Comparator<T> cmp) { + return directedWalk(ds -> { + switch (cmp.compare(data, ds)) { + case -1: + return LEFT; + case 0: + return deleted ? FAILURE : SUCCESS; + case 1: + return RIGHT; + default: + return FAILURE; + } + }); + } + + @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; + } + } + }); + } + + @Override + public boolean directedWalk(DirectedWalkFunction<T> ds) { + switch (ds.walk(data)) { + case SUCCESS: + return true; + case LEFT: + return left.directedWalk(ds); + case RIGHT: + return right.directedWalk(ds); + case FAILURE: + return false; + default: + return false; + } + } + + @Override + public boolean forEach(TreeLinearizationMethod tlm, Predicate<T> c) { + switch (tlm) { + case PREORDER: + return preorderTraverse(tlm, c); + case INORDER: + return inorderTraverse(tlm, c); + case POSTORDER: + return postorderTraverse(tlm, c); + default: + throw new IllegalArgumentException( + "Passed an incorrect TreeLinearizationMethod."); + } + } + + private boolean inorderTraverse(TreeLinearizationMethod tlm, + Predicate<T> c) { + + return ((left == null ? true : left.forEach(tlm, c)) + && (deleted ? true : c.test(data)) + && (right == null ? true : right.forEach(tlm, c))); + } + + private boolean postorderTraverse(TreeLinearizationMethod tlm, + Predicate<T> c) { + + return ((left == null ? true : left.forEach(tlm, c)) + && (right == null ? true : right.forEach(tlm, c)) + && (deleted ? true : c.test(data))); + + } + + private boolean preorderTraverse(TreeLinearizationMethod tlm, + Predicate<T> c) { + + return ((deleted ? true : c.test(data)) + && (left == null ? true : left.forEach(tlm, c)) + && (right == null ? true : right.forEach(tlm, c))); + } +} |