Moved around tree stuff.

5 files changed, 0 insertions, 526 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
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 <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
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 <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
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 <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
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 <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
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 <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)));
-	}
-}