diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata/bst')
3 files changed, 117 insertions, 61 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 d028293..7bf0007 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 @@ -12,15 +12,28 @@ import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod; * * @author ben * - * @param <T> The data type stored in the node. + * @param <T> + * The data type stored in the node. */ public class BinarySearchTree<T> { + /** + * The comparator for use in ordering items + */ private Comparator<T> comp; + + /** + * The current count of elements in the tree + */ private int nCount; + + /** + * The root element of the tree + */ private ITreePart<T> root; /** * Create a new tree using the specified way to compare elements. + * * @param cmp */ public BinarySearchTree(Comparator<T> cmp) { @@ -30,7 +43,9 @@ public class BinarySearchTree<T> { /** * Add a node to the binary search tree. - * @param dat The data to add to the binary search tree. + * + * @param dat + * The data to add to the binary search tree. */ public void addNode(T dat) { nCount++; @@ -42,49 +57,51 @@ public class BinarySearchTree<T> { } /** - * Balance the tree, and remove soft-deleted nodes for free. - * Takes O(N) time, but also O(N) space. + * 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) { + + 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) { + + if ((piv - adj) >= 0) { root.add(elms.get(piv - adj), comp); - } else if((piv + adj) < elms.size()) { + } 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. + * 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) { @@ -94,7 +111,9 @@ public class BinarySearchTree<T> { /** * Check if a node is in the tree - * @param dat The node to check the presence of for 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) { @@ -103,8 +122,11 @@ public class BinarySearchTree<T> { /** * 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 + * + * @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); diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java index 1928185..e2f204a 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java @@ -7,26 +7,38 @@ import java.util.function.Predicate; /** * A leaf in a tree. + * * @author ben * - * @param <T> The data stored in the tree. + * @param <T> + * The data stored in the tree. */ public class TreeLeaf<T> implements ITreePart<T> { - protected T data; - protected boolean deleted; - + /** + * The data held in this tree leaf + */ + protected T data; + + /** + * Whether this node is soft-deleted or not + */ + protected boolean deleted; + /** * Create a new leaf holding the specified data. - * @param dat The data for the leaf to hold. + * + * @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) + * 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) { @@ -34,9 +46,11 @@ public class TreeLeaf<T> implements ITreePart<T> { } /* - * Just transform our data. - * (non-Javadoc) - * @see bjc.utils.data.bst.ITreePart#collapse(java.util.function.Function, java.util.function.BiFunction) + * 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) { @@ -44,56 +58,62 @@ public class TreeLeaf<T> implements ITreePart<T> { } /* - * Only check our data. - * (non-Javadoc) - * @see bjc.utils.data.bst.ITreePart#contains(java.lang.Object, java.util.Comparator) + * 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) + * 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) + * 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)) { + 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) + * 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)) { + 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) + * 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/funcdata/bst/TreeNode.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java index 65eb546..40cc53f 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 @@ -9,19 +9,32 @@ import java.util.function.Predicate; /** * A binary node in a tree. + * * @author ben * - * @param <T> The data type stored in the tree. + * @param <T> + * The data type stored in the tree. */ public class TreeNode<T> extends TreeLeaf<T> { + /** + * The left child of this node + */ private ITreePart<T> left; + + /** + * The right child of this node + */ 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. + * + * @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); @@ -30,9 +43,10 @@ public class TreeNode<T> extends TreeLeaf<T> { } /* - * 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) + * 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) { @@ -71,7 +85,7 @@ public class TreeNode<T> extends TreeLeaf<T> { return bf.apply(tm, left.collapse(f, bf)); } } else { - if(right != null) { + if (right != null) { return bf.apply(tm, right.collapse(f, bf)); } else { return tm; |