More data structure work.

Yet more imports from previous version.

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)));
+	}
+}