From ba7711b8546e08fa6376a85271d2ca1c34cc902b Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Tue, 29 Sep 2015 16:24:37 -0400 Subject: Moved around tree stuff. --- .../java/bjc/utils/data/bst/BinarySearchTree.java | 128 --------------- .../bjc/utils/data/bst/DirectedWalkFunction.java | 43 ----- .../main/java/bjc/utils/data/bst/ITreePart.java | 81 ---------- .../src/main/java/bjc/utils/data/bst/TreeLeaf.java | 101 ------------ .../src/main/java/bjc/utils/data/bst/TreeNode.java | 173 --------------------- .../bjc/utils/funcdata/bst/BinarySearchTree.java | 128 +++++++++++++++ .../utils/funcdata/bst/DirectedWalkFunction.java | 43 +++++ .../java/bjc/utils/funcdata/bst/ITreePart.java | 81 ++++++++++ .../main/java/bjc/utils/funcdata/bst/TreeLeaf.java | 101 ++++++++++++ .../main/java/bjc/utils/funcdata/bst/TreeNode.java | 173 +++++++++++++++++++++ 10 files changed, 526 insertions(+), 526 deletions(-) delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java (limited to 'BJC-Utils2/src/main/java') 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 deleted file mode 100644 index 509cfcd..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java +++ /dev/null @@ -1,128 +0,0 @@ -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 The data type stored in the node. - */ -public class BinarySearchTree { - private Comparator comp; - private int nCount; - private ITreePart root; - - /** - * Create a new tree using the specified way to compare elements. - * @param cmp - */ - public BinarySearchTree(Comparator 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(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 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(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 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 p) { - root.forEach(tlm, p); - } - - /** - * Remove all soft-deleted nodes from the tree. - */ - public void trim() { - List 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 deleted file mode 100644 index 232f3d4..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/data/bst/DirectedWalkFunction.java +++ /dev/null @@ -1,43 +0,0 @@ -package bjc.utils.data.bst; - -/** - * Represents a function for doing a directed walk of a binary tree. - * @author ben - * - * @param - */ -@FunctionalInterface -public interface DirectedWalkFunction { - /** - * 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 deleted file mode 100644 index 5667ce1..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/data/bst/ITreePart.java +++ /dev/null @@ -1,81 +0,0 @@ -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 The data contained in this part of the tree. - */ -public interface ITreePart { - /** - * 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 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 collapse(Function f, BiFunction 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 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 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 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 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 deleted file mode 100644 index 173afc1..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeLeaf.java +++ /dev/null @@ -1,101 +0,0 @@ -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 The data stored in the tree. - */ -public class TreeLeaf implements ITreePart { - 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 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 collapse(Function f, BiFunction 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 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 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 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 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 deleted file mode 100644 index 660fd03..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/data/bst/TreeNode.java +++ /dev/null @@ -1,173 +0,0 @@ -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 The data type stored in the tree. - */ -public class TreeNode extends TreeLeaf { - private ITreePart left; - private ITreePart 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 left, ITreePart 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 comp) { - switch (comp.compare(data, dat)) { - case -1: - if (left == null) { - left = new TreeNode(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(dat, null, null); - } else { - right.add(dat, comp); - } - } - } - - @Override - public E collapse(Function f, BiFunction 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 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 cmp) { - directedWalk(new DirectedWalkFunction() { - @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 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 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 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 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 c) { - - return ((deleted ? true : c.test(data)) - && (left == null ? true : left.forEach(tlm, c)) - && (right == null ? true : right.forEach(tlm, c))); - } -} 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 new file mode 100644 index 0000000..d028293 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java @@ -0,0 +1,128 @@ +package bjc.utils.funcdata.bst; + +import java.util.ArrayList; +import java.util.Comparator; +import java.util.List; +import java.util.function.Predicate; + +import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod; + +/** + * A binary search tree, with some mild support for functional traversal. + * + * @author ben + * + * @param The data type stored in the node. + */ +public class BinarySearchTree { + private Comparator comp; + private int nCount; + private ITreePart root; + + /** + * Create a new tree using the specified way to compare elements. + * @param cmp + */ + public BinarySearchTree(Comparator 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(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 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(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 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 p) { + root.forEach(tlm, p); + } + + /** + * Remove all soft-deleted nodes from the tree. + */ + public void trim() { + List 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/funcdata/bst/DirectedWalkFunction.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java new file mode 100644 index 0000000..18e80be --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/DirectedWalkFunction.java @@ -0,0 +1,43 @@ +package bjc.utils.funcdata.bst; + +/** + * Represents a function for doing a directed walk of a binary tree. + * @author ben + * + * @param + */ +@FunctionalInterface +public interface DirectedWalkFunction { + /** + * 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/funcdata/bst/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java new file mode 100644 index 0000000..0c8f12e --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java @@ -0,0 +1,81 @@ +package bjc.utils.funcdata.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 The data contained in this part of the tree. + */ +public interface ITreePart { + /** + * 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 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 collapse(Function f, BiFunction 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 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 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 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 c); +} 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 new file mode 100644 index 0000000..1928185 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java @@ -0,0 +1,101 @@ +package bjc.utils.funcdata.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 The data stored in the tree. + */ +public class TreeLeaf implements ITreePart { + 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 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 collapse(Function f, BiFunction 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 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 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 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 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 new file mode 100644 index 0000000..65eb546 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java @@ -0,0 +1,173 @@ +package bjc.utils.funcdata.bst; + +import static bjc.utils.funcdata.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 The data type stored in the tree. + */ +public class TreeNode extends TreeLeaf { + private ITreePart left; + private ITreePart 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 left, ITreePart 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 comp) { + switch (comp.compare(data, dat)) { + case -1: + if (left == null) { + left = new TreeNode(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(dat, null, null); + } else { + right.add(dat, comp); + } + } + } + + @Override + public E collapse(Function f, BiFunction 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 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 cmp) { + directedWalk(new DirectedWalkFunction() { + @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 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 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 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 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 c) { + + return ((deleted ? true : c.test(data)) + && (left == null ? true : left.forEach(tlm, c)) + && (right == null ? true : right.forEach(tlm, c))); + } +} -- cgit v1.2.3