From 08cf6a8d3fea26dc891783a0d08e30791643135e Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Fri, 18 Mar 2016 09:39:37 -0400 Subject: Reorganized tree packages. This is in preparation for addition of a non-searching binary tree. --- .../main/java/bjc/utils/funcdata/ITreePart.java | 117 +++++++++++++ .../bjc/utils/funcdata/bst/BinarySearchTree.java | 7 +- .../utils/funcdata/bst/BinarySearchTreeLeaf.java | 123 ++++++++++++++ .../utils/funcdata/bst/BinarySearchTreeNode.java | 186 +++++++++++++++++++++ .../java/bjc/utils/funcdata/bst/ITreePart.java | 115 ------------- .../main/java/bjc/utils/funcdata/bst/TreeLeaf.java | 121 -------------- .../main/java/bjc/utils/funcdata/bst/TreeNode.java | 184 -------------------- 7 files changed, 430 insertions(+), 423 deletions(-) create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/ITreePart.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java delete mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java (limited to 'BJC-Utils2/src/main/java/bjc/utils') diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/ITreePart.java new file mode 100644 index 0000000..24e68d4 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/ITreePart.java @@ -0,0 +1,117 @@ +package bjc.utils.funcdata; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +import bjc.utils.funcdata.bst.DirectedWalkFunction; + +/** + * 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. + */ + public 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. + */ + public 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. + */ + public boolean contains(T data, Comparator cmp); + + /** + * Get the data associated with this tree part. + * + * @return The data associated with this tree part. + */ + 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. + */ + public 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. + */ + public 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 + */ + public boolean forEach(TreeLinearizationMethod tlm, Predicate 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 index 7665797..3f65481 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 @@ -6,7 +6,8 @@ import java.util.List; import java.util.function.Predicate; import bjc.utils.funcdata.FunctionalList; -import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod; +import bjc.utils.funcdata.ITreePart; +import bjc.utils.funcdata.ITreePart.TreeLinearizationMethod; /** * A binary search tree, with some mild support for functional traversal. @@ -52,7 +53,7 @@ public class BinarySearchTree { nCount++; if (root == null) { - root = new TreeNode(dat, null, null); + root = new BinarySearchTreeNode(dat, null, null); } else { root.add(dat, comp); } @@ -74,7 +75,7 @@ public class BinarySearchTree { while ((piv - adj) >= 0 && (piv + adj) < elms.getSize()) { if (root == null) { - root = new TreeNode(elms.getByIndex(piv), null, null); + root = new BinarySearchTreeNode(elms.getByIndex(piv), null, null); } else { root.add(elms.getByIndex(piv + adj), comp); root.add(elms.getByIndex(piv - adj), comp); 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 new file mode 100644 index 0000000..02b9c7a --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeLeaf.java @@ -0,0 +1,123 @@ +package bjc.utils.funcdata.bst; + +import java.util.Comparator; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Predicate; + +import bjc.utils.funcdata.ITreePart; + +/** + * A leaf in a tree. + * + * @author ben + * + * @param + * The data stored in the tree. + */ +public class BinarySearchTreeLeaf implements ITreePart { + /** + * 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. + */ + public BinarySearchTreeLeaf(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/BinarySearchTreeNode.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java new file mode 100644 index 0000000..30a9fbd --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTreeNode.java @@ -0,0 +1,186 @@ +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; + +import bjc.utils.funcdata.ITreePart; + +/** + * A binary node in a tree. + * + * @author ben + * + * @param + * The data type stored in the tree. + */ +public class BinarySearchTreeNode extends BinarySearchTreeLeaf { + /** + * The left child of this node + */ + private ITreePart left; + + /** + * The right child of this node + */ + 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 BinarySearchTreeNode(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 BinarySearchTreeNode(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 BinarySearchTreeNode(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(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; + } + }); + } + + @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/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java deleted file mode 100644 index dfcfedd..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java +++ /dev/null @@ -1,115 +0,0 @@ -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. - */ - public 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. - */ - public 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. - */ - public boolean contains(T data, Comparator cmp); - - /** - * Get the data associated with this tree part. - * - * @return The data associated with this tree part. - */ - 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. - */ - public 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. - */ - public 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 - */ - public 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 deleted file mode 100644 index e2f204a..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLeaf.java +++ /dev/null @@ -1,121 +0,0 @@ -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 { - /** - * 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. - */ - 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 deleted file mode 100644 index e8c6c8b..0000000 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeNode.java +++ /dev/null @@ -1,184 +0,0 @@ -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 { - /** - * The left child of this node - */ - private ITreePart left; - - /** - * The right child of this node - */ - 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(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; - } - }); - } - - @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