Rename package root

The package root is now bjc, not io.github.bculkin2442.

6 files changed, 806 insertions, 0 deletions

diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTree.java b/src/main/java/bjc/funcdata/bst/BinarySearchTree.java
new file mode 100644
index 0000000..d0319e4
--- /dev/null
+++ b/src/main/java/bjc/funcdata/bst/BinarySearchTree.java
@@ -0,0 +1,224 @@
+package bjc.funcdata.bst;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Predicate;
+
+import bjc.funcdata.FunctionalList;
+import bjc.funcdata.IList;
+
+/**
+ * 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> {
+	/* The comparator for use in ordering items */
+	private final Comparator<T> comparator;
+
+	/* The current count of elements in the tree */
+	private int elementCount;
+
+	/* The root element of the tree */
+	private ITreePart<T> root;
+
+	/**
+	 * Create a new tree using the specified way to compare elements.
+	 *
+	 * @param cmp
+	 *        The thing to use for comparing elements
+	 */
+	public BinarySearchTree(final Comparator<T> cmp) {
+		if(cmp == null) throw new NullPointerException("Comparator must not be null");
+
+		elementCount = 0;
+		comparator = cmp;
+	}
+
+	/**
+	 * Add a node to the binary search tree.
+	 *
+	 * @param element
+	 *        The data to add to the binary search tree.
+	 */
+	public void addNode(final T element) {
+		elementCount++;
+
+		if(root == null) {
+			root = new BinarySearchTreeNode<>(element, null, null);
+		} else {
+			root.add(element, comparator);
+		}
+	}
+
+	/**
+	 * Check if an adjusted pivot falls with the bounds of a list.
+	 *
+	 * @param elements
+	 *        The list to get bounds from.
+	 *
+	 * @param pivot
+	 *        The pivot.
+	 *
+	 * @param pivotAdjustment
+	 *        The distance from the pivot.
+	 *
+	 * @return Whether the adjusted pivot is with the list.
+	 */
+	private boolean adjustedPivotInBounds(final IList<T> elements, final int pivot, final int pivotAdjustment) {
+		return ((pivot - pivotAdjustment) >= 0) && ((pivot + pivotAdjustment) < elements.getSize());
+	}
+
+	/**
+	 * Balance the tree, and remove soft-deleted nodes for free.
+	 *
+	 * Takes O(N) time, but also O(N) space.
+	 */
+	public void balance() {
+		final IList<T> elements = new FunctionalList<>();
+
+		/* Add each element to the list in sorted order. */
+		root.forEach(TreeLinearizationMethod.INORDER, element -> elements.add(element));
+
+		/* Clear the tree. */
+		root = null;
+
+		/* Set up the pivot and adjustment for readding elements. */
+		final int pivot = elements.getSize() / 2;
+		int pivotAdjustment = 0;
+
+		/* Add elements until there aren't any left. */
+		while(adjustedPivotInBounds(elements, pivot, pivotAdjustment)) {
+			if(root == null) {
+				/* Create a new root element. */
+				root = new BinarySearchTreeNode<>(elements.getByIndex(pivot), null, null);
+			} else {
+				/*
+				 * Add the left and right elements in a balanced
+				 * manner.
+				 */
+				root.add(elements.getByIndex(pivot + pivotAdjustment), comparator);
+				root.add(elements.getByIndex(pivot - pivotAdjustment), comparator);
+			}
+
+			/* Increase the distance from the pivot. */
+			pivotAdjustment++;
+		}
+
+		/* Add any trailing unbalanced elements. */
+		if(pivot - pivotAdjustment >= 0) {
+			root.add(elements.getByIndex(pivot - pivotAdjustment), comparator);
+		} else if(pivot + pivotAdjustment < elements.getSize()) {
+			root.add(elements.getByIndex(pivot + pivotAdjustment), comparator);
+		}
+	}
+
+	/**
+	 * 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 element
+	 *        The node to delete
+	 */
+	public void deleteNode(final T element) {
+		elementCount--;
+
+		root.delete(element, comparator);
+	}
+
+	/**
+	 * Get the root of the tree.
+	 *
+	 * @return The root of the tree.
+	 */
+	public ITreePart<T> getRoot() {
+		return root;
+	}
+
+	/**
+	 * Check if a node is in the tree.
+	 *
+	 * @param element
+	 *        The node to check the presence of for the tree..
+	 *
+	 * @return Whether or not the node is in the tree.
+	 */
+	public boolean isInTree(final T element) {
+		return root.contains(element, comparator);
+	}
+
+	/**
+	 * Traverse the tree in a specified way until the function fails.
+	 *
+	 * @param linearizationMethod
+	 *        The way to linearize the tree for traversal.
+	 *
+	 * @param traversalPredicate
+	 *        The function to use until it fails.
+	 */
+	public void traverse(final TreeLinearizationMethod linearizationMethod, final Predicate<T> traversalPredicate) {
+		if(linearizationMethod == null) {
+			throw new NullPointerException("Linearization method must not be null");
+		} else if(traversalPredicate == null) {
+			throw new NullPointerException("Predicate must not be nulls");
+		}
+
+		root.forEach(linearizationMethod, traversalPredicate);
+	}
+
+	/** Remove all soft-deleted nodes from the tree. */
+	public void trim() {
+		final List<T> nodes = new ArrayList<>(elementCount);
+
+		/*
+		 * Add all non-soft deleted nodes to the tree in insertion
+		 * order.
+		 */
+		traverse(TreeLinearizationMethod.PREORDER, node -> {
+			nodes.add(node);
+			return true;
+		});
+
+		/* Clear the tree. */
+		root = null;
+
+		/* Add the nodes to the tree in the order they were inserted. */
+		nodes.forEach(node -> addNode(node));
+	}
+
+	@Override
+	public String toString() {
+		return String.format("BinarySearchTree [elementCount=%s, root='%s']", elementCount, root);
+	}
+
+	@Override
+	public int hashCode() {
+		final int prime = 31;
+		int result = 1;
+		result = prime * result + elementCount;
+		result = prime * result + (root == null ? 0 : root.hashCode());
+		return result;
+	}
+
+	@Override
+	public boolean equals(final Object obj) {
+		if(this == obj) return true;
+		if(obj == null) return false;
+		if(!(obj instanceof BinarySearchTree<?>)) return false;
+
+		final BinarySearchTree<?> other = (BinarySearchTree<?>) obj;
+
+		if(elementCount != other.elementCount) return false;
+		if(root == null) {
+			if(other.root != null) return false;
+		} else if(!root.equals(other.root)) return false;
+
+		return true;
+	}
+}
diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java b/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java
new file mode 100644
index 0000000..dfad3d9
--- /dev/null
+++ b/src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java
@@ -0,0 +1,115 @@
+package bjc.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 <T>
+ *        The data stored in the tree.
+ */
+public class BinarySearchTreeLeaf<T> implements ITreePart<T> {
+	/** The data held in this tree leaf */
+	protected T data;
+
+	/** Whether this node is soft-deleted or not */
+	protected boolean isDeleted;
+
+	/**
+	 * Create a new leaf holding the specified data.
+	 *
+	 * @param element
+	 *        The data for the leaf to hold.
+	 */
+	public BinarySearchTreeLeaf(final T element) {
+		data = element;
+	}
+
+	@Override
+	public void add(final T element, final Comparator<T> comparator) {
+		throw new IllegalArgumentException("Can't add to a leaf.");
+	}
+
+	@Override
+	public <E> E collapse(final Function<T, E> leafTransformer, final BiFunction<E, E, E> branchCollapser) {
+		if(leafTransformer == null) throw new NullPointerException("Transformer must not be null");
+
+		return leafTransformer.apply(data);
+	}
+
+	@Override
+	public boolean contains(final T element, final Comparator<T> comparator) {
+		return this.data.equals(element);
+	}
+
+	@Override
+	public T data() {
+		return data;
+	}
+
+	@Override
+	public void delete(final T element, final Comparator<T> comparator) {
+		if(data.equals(element)) {
+			isDeleted = true;
+		}
+	}
+
+	@Override
+	public boolean directedWalk(final DirectedWalkFunction<T> treeWalker) {
+		if(treeWalker == null) throw new NullPointerException("Tree walker must not be null");
+
+		switch(treeWalker.walk(data)) {
+		case SUCCESS:
+			return true;
+		/* We don't have any children to care about. */
+		case FAILURE:
+		case LEFT:
+		case RIGHT:
+		default:
+			return false;
+		}
+	}
+
+	@Override
+	public boolean forEach(final TreeLinearizationMethod linearizationMethod,
+			final Predicate<T> traversalPredicate) {
+		if(traversalPredicate == null) throw new NullPointerException("Predicate must not be null");
+
+		return traversalPredicate.test(data);
+	}
+
+	@Override
+	public String toString() {
+		return String.format("BinarySearchTreeLeaf [data='%s', isDeleted=%s]", data, isDeleted);
+	}
+
+	@Override
+	public int hashCode() {
+		final int prime = 31;
+		int result = 1;
+		result = prime * result + (data == null ? 0 : data.hashCode());
+		result = prime * result + (isDeleted ? 1231 : 1237);
+		return result;
+	}
+
+	@Override
+	public boolean equals(final Object obj) {
+		if(this == obj) return true;
+		if(obj == null) return false;
+		if(!(obj instanceof BinarySearchTreeLeaf<?>)) return false;
+
+		final BinarySearchTreeLeaf<?> other = (BinarySearchTreeLeaf<?>) obj;
+
+		if(data == null) {
+			if(other.data != null) return false;
+		} else if(!data.equals(other.data)) return false;
+		if(isDeleted != other.isDeleted) return false;
+
+		return true;
+	}
+}
diff --git a/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java
new file mode 100644
index 0000000..0453f80
--- /dev/null
+++ b/src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java
@@ -0,0 +1,295 @@
+package bjc.funcdata.bst;
+
+import static bjc.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.FAILURE;
+import static bjc.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.LEFT;
+import static bjc.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.RIGHT;
+import static bjc.funcdata.bst.DirectedWalkFunction.DirectedWalkResult.SUCCESS;
+
+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 BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<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 element
+	 *        The data to store in this node.
+	 *
+	 * @param lft
+	 *        The left child of this node.
+	 *
+	 * @param rght
+	 *        The right child of this node.
+	 */
+	public BinarySearchTreeNode(final T element, final ITreePart<T> lft, final ITreePart<T> rght) {
+		super(element);
+		this.left = lft;
+		this.right = rght;
+	}
+
+	@Override
+	public void add(final T element, final Comparator<T> comparator) {
+		if(comparator == null) throw new NullPointerException("Comparator must not be null");
+
+		switch(comparator.compare(data, element)) {
+		case -1:
+			if(left == null) {
+				left = new BinarySearchTreeNode<>(element, null, null);
+			} else {
+				left.add(element, comparator);
+			}
+			break;
+		case 0:
+			if(isDeleted) {
+				isDeleted = false;
+			} else
+				throw new IllegalArgumentException("Can't add duplicate values");
+			break;
+		case 1:
+			if(right == null) {
+				right = new BinarySearchTreeNode<>(element, null, null);
+			} else {
+				right.add(element, comparator);
+			}
+			break;
+		default:
+			throw new IllegalStateException("Error: Comparator yielded invalid value");
+		}
+	}
+
+	@Override
+	public <E> E collapse(final Function<T, E> nodeCollapser, final BiFunction<E, E, E> branchCollapser) {
+		if(nodeCollapser == null || branchCollapser == null)
+			throw new NullPointerException("Collapser must not be null");
+
+		final E collapsedNode = nodeCollapser.apply(data);
+
+		if(left != null) {
+			final E collapsedLeftBranch = left.collapse(nodeCollapser, branchCollapser);
+
+			if(right != null) {
+				final E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser);
+
+				final E collapsedBranches = branchCollapser.apply(collapsedLeftBranch,
+						collapsedRightBranch);
+
+				return branchCollapser.apply(collapsedNode, collapsedBranches);
+			}
+
+			return branchCollapser.apply(collapsedNode, collapsedLeftBranch);
+		}
+
+		if(right != null) {
+			final E collapsedRightBranch = right.collapse(nodeCollapser, branchCollapser);
+
+			return branchCollapser.apply(collapsedNode, collapsedRightBranch);
+		}
+
+		return collapsedNode;
+	}
+
+	@Override
+	public boolean contains(final T element, final Comparator<T> comparator) {
+		if(comparator == null) throw new NullPointerException("Comparator must not be null");
+
+		return directedWalk(currentElement -> {
+			switch(comparator.compare(element, currentElement)) {
+			case -1:
+				return LEFT;
+			case 0:
+				return isDeleted ? FAILURE : SUCCESS;
+			case 1:
+				return RIGHT;
+			default:
+				return FAILURE;
+			}
+		});
+	}
+
+	@Override
+	public void delete(final T element, final Comparator<T> comparator) {
+		if(comparator == null) throw new NullPointerException("Comparator must not be null");
+
+		directedWalk(currentElement -> {
+			switch(comparator.compare(data, element)) {
+			case -1:
+				return left == null ? FAILURE : LEFT;
+			case 0:
+				isDeleted = true;
+				return FAILURE;
+			case 1:
+				return right == null ? FAILURE : RIGHT;
+			default:
+				return FAILURE;
+			}
+		});
+	}
+
+	@Override
+	public boolean directedWalk(final DirectedWalkFunction<T> treeWalker) {
+		if(treeWalker == null) throw new NullPointerException("Walker must not be null");
+
+		switch(treeWalker.walk(data)) {
+		case SUCCESS:
+			return true;
+		case LEFT:
+			return left.directedWalk(treeWalker);
+		case RIGHT:
+			return right.directedWalk(treeWalker);
+		case FAILURE:
+		default:
+			return false;
+		}
+	}
+
+	@Override
+	public boolean forEach(final TreeLinearizationMethod linearizationMethod,
+			final Predicate<T> traversalPredicate) {
+		if(linearizationMethod == null) {
+			throw new NullPointerException("Linearization method must not be null");
+		} else if(traversalPredicate == null) {
+			throw new NullPointerException("Predicate must not be null");
+		}
+
+		switch(linearizationMethod) {
+		case PREORDER:
+			return preorderTraverse(linearizationMethod, traversalPredicate);
+		case INORDER:
+			return inorderTraverse(linearizationMethod, traversalPredicate);
+		case POSTORDER:
+			return postorderTraverse(linearizationMethod, traversalPredicate);
+		default:
+			String msg = String.format("Passed an incorrect TreeLinearizationMethod %s. WAT",
+					linearizationMethod);
+
+			throw new IllegalArgumentException(msg);
+		}
+	}
+
+	/* Do an in-order traversal. */
+	private boolean inorderTraverse(final TreeLinearizationMethod linearizationMethod,
+			final Predicate<T> traversalPredicate) {
+		if(!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false;
+
+		if(!traverseElement(traversalPredicate)) return false;
+
+		if(!traverseRightBranch(linearizationMethod, traversalPredicate)) return false;
+
+		return true;
+	}
+
+	/* Do a post-order traversal. */
+	private boolean postorderTraverse(final TreeLinearizationMethod linearizationMethod,
+			final Predicate<T> traversalPredicate) {
+		if(!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false;
+
+		if(!traverseRightBranch(linearizationMethod, traversalPredicate)) return false;
+
+		if(!traverseElement(traversalPredicate)) return false;
+
+		return true;
+
+	}
+
+	/* Do a pre-order traversal. */
+	private boolean preorderTraverse(final TreeLinearizationMethod linearizationMethod,
+			final Predicate<T> traversalPredicate) {
+		if(!traverseElement(traversalPredicate)) return false;
+
+		if(!traverseLeftBranch(linearizationMethod, traversalPredicate)) return false;
+
+		if(!traverseRightBranch(linearizationMethod, traversalPredicate)) return false;
+
+		return true;
+	}
+
+	/* Traverse an element. */
+	private boolean traverseElement(final Predicate<T> traversalPredicate) {
+		boolean nodeSuccesfullyTraversed;
+
+		if(isDeleted) {
+			nodeSuccesfullyTraversed = true;
+		} else {
+			nodeSuccesfullyTraversed = traversalPredicate.test(data);
+		}
+
+		return nodeSuccesfullyTraversed;
+	}
+
+	/* Traverse the left branch of a tree. */
+	private boolean traverseLeftBranch(final TreeLinearizationMethod linearizationMethod,
+			final Predicate<T> traversalPredicate) {
+		boolean leftSuccesfullyTraversed;
+
+		if(left == null) {
+			leftSuccesfullyTraversed = true;
+		} else {
+			leftSuccesfullyTraversed = left.forEach(linearizationMethod, traversalPredicate);
+		}
+
+		return leftSuccesfullyTraversed;
+	}
+
+	/* Traverse the right branch of a tree. */
+	private boolean traverseRightBranch(final TreeLinearizationMethod linearizationMethod,
+			final Predicate<T> traversalPredicate) {
+		boolean rightSuccesfullyTraversed;
+
+		if(right == null) {
+			rightSuccesfullyTraversed = true;
+		} else {
+			rightSuccesfullyTraversed = right.forEach(linearizationMethod, traversalPredicate);
+		}
+
+		return rightSuccesfullyTraversed;
+	}
+
+	@Override
+	public String toString() {
+		return String.format("BinarySearchTreeNode [left='%s', right='%s']", left, right);
+	}
+
+	@Override
+	public int hashCode() {
+		final int prime = 31;
+		int result = super.hashCode();
+		result = prime * result + (left == null ? 0 : left.hashCode());
+		result = prime * result + (right == null ? 0 : right.hashCode());
+		return result;
+	}
+
+	@Override
+	public boolean equals(final Object obj) {
+		if(this == obj) return true;
+		if(!super.equals(obj)) return false;
+		if(!(obj instanceof BinarySearchTreeNode<?>)) return false;
+
+		final BinarySearchTreeNode<?> other = (BinarySearchTreeNode<?>) obj;
+
+		if(left == null) {
+			if(other.left != null) return false;
+		} else if(!left.equals(other.left)) return false;
+
+		if(right == null) {
+			if(other.right != null) return false;
+		} else if(!right.equals(other.right)) return false;
+
+		return true;
+	}
+}
diff --git a/src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java b/src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java
new file mode 100644
index 0000000..ac2b918
--- /dev/null
+++ b/src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java
@@ -0,0 +1,44 @@
+package bjc.funcdata.bst;
+
+/**
+ * Represents a function for doing a directed walk of a binary tree.
+ *
+ * @author ben
+ *
+ * @param <T>
+ *        The type of element stored in the walked tree
+ */
+@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 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,
+		/** Specifies that the function has succesfully completed */
+		SUCCESS
+	}
+
+	/**
+	 * Perform a directed walk on a node of a tree.
+	 *
+	 * @param element
+	 *        The data stored in the node currently being visited.
+	 *
+	 * @return The way the function wants the walk to go next.
+	 */
+	public DirectedWalkResult walk(T element);
+}
diff --git a/src/main/java/bjc/funcdata/bst/ITreePart.java b/src/main/java/bjc/funcdata/bst/ITreePart.java
new file mode 100644
index 0000000..903965f
--- /dev/null
+++ b/src/main/java/bjc/funcdata/bst/ITreePart.java
@@ -0,0 +1,104 @@
+package bjc.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 <T>
+ *        The data contained in this part of the tree.
+ */
+public interface ITreePart<T> {
+	/**
+	 * Add a element below this tree part somewhere.
+	 *
+	 * @param element
+	 *        The element to add below this tree part
+	 *
+	 * @param comparator
+	 *        The thing to use for comparing values to find where to insert
+	 *        the tree part.
+	 */
+	public void add(T element, Comparator<T> comparator);
+
+	/**
+	 * Collapses this tree part into a single value.
+	 *
+	 * Does not change the underlying tree.
+	 *
+	 * @param <E>
+	 *        The type of the final collapsed value
+	 *
+	 * @param nodeCollapser
+	 *        The function to use to transform data into mapped form.
+	 *
+	 * @param branchCollapser
+	 *        The function to use to collapse data in mapped form into a
+	 *        single value.
+	 *
+	 * @return A single value from collapsing the tree.
+	 */
+	public <E> E collapse(Function<T, E> nodeCollapser, BiFunction<E, E, E> branchCollapser);
+
+	/**
+	 * Check if this tre part or below it contains the specified data item.
+	 *
+	 * @param element
+	 *        The data item to look for.
+	 *
+	 * @param comparator
+	 *        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 element, Comparator<T> comparator);
+
+	/**
+	 * 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 element
+	 *        The data item to remove.
+	 *
+	 * @param comparator
+	 *        The comparator to use to search for the data item.
+	 */
+	public void delete(T element, Comparator<T> comparator);
+
+	/**
+	 * Execute a directed walk through the tree.
+	 *
+	 * @param walker
+	 *        The function to use to direct the walk through the tree.
+	 *
+	 * @return Whether the directed walk finished successfully.
+	 */
+	public boolean directedWalk(DirectedWalkFunction<T> walker);
+
+	/**
+	 * Execute a provided function for each element of tree it succesfully
+	 * completes for.
+	 *
+	 * @param linearizationMethod
+	 *        The way to linearize the tree for executing.
+	 *
+	 * @param predicate
+	 *        The predicate to apply to each element, where it returning
+	 *        false terminates traversal early.
+	 *
+	 * @return Whether the traversal finished succesfully.
+	 */
+	public boolean forEach(TreeLinearizationMethod linearizationMethod, Predicate<T> predicate);
+}
diff --git a/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java b/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java
new file mode 100644
index 0000000..35b116b
--- /dev/null
+++ b/src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java
@@ -0,0 +1,24 @@
+package bjc.funcdata.bst;
+
+/**
+ * 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
+}