Fixed examples using trees

2 files changed, 23 insertions, 407 deletions

diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/AST.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/AST.java
deleted file mode 100644
index 4625807..0000000
--- a/BJC-Utils2/src/main/java/bjc/utils/parserutils/AST.java
+++ /dev/null
@@ -1,386 +0,0 @@
-package bjc.utils.parserutils;
-
-import java.util.function.BinaryOperator;
-import java.util.function.Consumer;
-import java.util.function.Function;
-import java.util.function.Predicate;
-import java.util.function.UnaryOperator;
-
-import bjc.utils.funcdata.bst.TreeLinearizationMethod;
-
-/**
- * A simple binary tree meant for use as an AST
- * 
- * @author ben
- *
- * @param <T>
- *            The type of token in this AST
- */
-public class AST<T> {
-	/**
-	 * Indent a string n levels
-	 * 
-	 * @param builder
-	 *            The string to indent
-	 * @param levels
-	 *            The number of levels to indent
-	 */
-	protected static void indentNLevels(StringBuilder builder,
-			int levels) {
-		for (int i = 0; i <= levels; i++) {
-			builder.append("\t");
-		}
-	}
-
-	private AST<T>	left;
-	private AST<T>	right;
-
-	private T		token;
-
-	/**
-	 * Create a new leaf AST node
-	 * 
-	 * @param tokn
-	 *            The token in this node
-	 */
-	public AST(T tokn) {
-		token = tokn;
-
-		left = null;
-		right = null;
-	}
-
-	/**
-	 * Create a new AST node with the specified data and children
-	 * 
-	 * @param tokn
-	 *            The token in this node
-	 * @param lft
-	 *            The left child of this AST
-	 * @param rght
-	 *            The right child of this AST
-	 */
-	public AST(T tokn, AST<T> lft, AST<T> rght) {
-		token = tokn;
-
-		left = lft;
-		right = rght;
-	}
-
-	/**
-	 * Apply an action to the head node of this AST
-	 * 
-	 * @param <E>
-	 *            The type of the returned value
-	 * @param headAction
-	 *            The action to apply to the head node
-	 * @return The result of applying the action
-	 */
-	public <E> E applyToHead(Function<T, E> headAction) {
-		if (headAction == null) {
-			throw new NullPointerException("Action must not be null");
-		}
-
-		return headAction.apply(token);
-	}
-
-	/**
-	 * Apply an action to the left side of this AST
-	 * 
-	 * @param <E>
-	 *            The type of the returned value
-	 * @param leftAction
-	 *            The action to apply to the left side
-	 * @return The result of applying the action
-	 */
-	public <E> E applyToLeft(Function<AST<T>, E> leftAction) {
-		if (leftAction == null) {
-			throw new NullPointerException("Action must not be null");
-		}
-
-		return leftAction.apply(left);
-	}
-
-	/**
-	 * Apply an action to the right side of this AST
-	 * 
-	 * @param <E>
-	 *            The type of the returned value
-	 * @param rightAction
-	 *            The action to apply to the right side
-	 * @return The result of applying the action
-	 */
-	public <E> E applyToRight(Function<AST<T>, E> rightAction) {
-		if (rightAction == null) {
-			throw new NullPointerException("Action must not be null");
-		}
-
-		return rightAction.apply(right);
-	}
-
-	/**
-	 * Collapse this tree into a single node
-	 * 
-	 * @param <E>
-	 *            The final value of the collapsed tree
-	 * @param <T2>
-	 * 
-	 * @param tokenTransformer
-	 *            The function to transform nodes into data
-	 * @param nodeTransformer
-	 *            A map of functions for operator collapsing
-	 * @param resultTransformer
-	 *            The function for transforming the result
-	 * @return The collapsed value of the tree
-	 */
-	@SuppressWarnings("unchecked")
-	public <E, T2> E collapse(Function<T, T2> tokenTransformer,
-			Function<T, BinaryOperator<T2>> nodeTransformer,
-			Function<T2, E> resultTransformer) {
-		if (tokenTransformer == null) {
-			throw new NullPointerException(
-					"Token transformer must not be null");
-		} else if (nodeTransformer == null) {
-			throw new NullPointerException(
-					"Node transformer must not be null");
-		}
-
-		if (resultTransformer != null) {
-			return resultTransformer.apply(
-					internalCollapse(tokenTransformer, nodeTransformer));
-		}
-
-		// This is valid because if the user passes null as the last
-		// parameter, E will be inferred as Object, but will actually
-		// be T2
-		return (E) internalCollapse(tokenTransformer, nodeTransformer);
-	}
-
-	private <T2> T2 collapseBranches(Function<T, T2> tokenTransformer,
-			Function<T, BinaryOperator<T2>> nodeTransformer) {
-		T2 leftCollapsed;
-
-		if (left == null) {
-			leftCollapsed = null;
-		} else {
-			leftCollapsed = left.internalCollapse(tokenTransformer,
-					nodeTransformer);
-		}
-
-		T2 rightCollapsed;
-
-		if (right == null) {
-			rightCollapsed = null;
-		} else {
-			rightCollapsed = right.internalCollapse(tokenTransformer,
-					nodeTransformer);
-		}
-
-		return nodeTransformer.apply(token).apply(leftCollapsed,
-				rightCollapsed);
-	}
-
-	/**
-	 * Expand the nodes in an AST
-	 * 
-	 * This is actually equivalent to converting the tree into an ordered
-	 * list, doing a flatMap, and then reconstructing the tree
-	 * 
-	 * @param expander
-	 *            The function to use for expanding nodes
-	 * @return The expanded AST
-	 */
-	public AST<T> flatMapTree(Function<T, AST<T>> expander) {
-		if (expander == null) {
-			throw new NullPointerException("Expander must not be null");
-		}
-
-		return collapse(expander, (operator) -> (leftAST, rightAST) -> {
-			return new AST<>(operator, leftAST, rightAST);
-		}, null);
-	}
-
-	/*
-	 * Internal recursive collapser
-	 */
-	protected <T2> T2 internalCollapse(Function<T, T2> tokenTransformer,
-			Function<T, BinaryOperator<T2>> nodeTransformer) {
-		if (left == null && right == null) {
-			return tokenTransformer.apply(token);
-		}
-
-		return collapseBranches(tokenTransformer, nodeTransformer);
-	}
-
-	/**
-	 * Internal version of toString for proper rendering
-	 * 
-	 * @param builder
-	 *            The string rendering being built
-	 * @param indentLevel
-	 *            The current level to indent the tree
-	 */
-	protected void internalToString(StringBuilder builder,
-			int indentLevel) {
-		indentNLevels(builder, indentLevel);
-
-		if (left == null && right == null) {
-			builder.append("Node: ");
-			builder.append(token.toString());
-			builder.append("\n");
-		} else {
-			builder.append("Node: ");
-			builder.append(token.toString());
-			builder.append("\n");
-
-			if (left != null) {
-				left.internalToString(builder, indentLevel + 2);
-			} else {
-				indentNLevels(builder, indentLevel + 2);
-				builder.append("No left node\n");
-			}
-			if (right != null) {
-				right.internalToString(builder, indentLevel + 2);
-			} else {
-				indentNLevels(builder, indentLevel + 2);
-				builder.append("No right node\n");
-			}
-		}
-	}
-
-	/**
-	 * Execute a transform on selective nodes of the tree
-	 * 
-	 * @param transformerPredicate
-	 *            The predicate to pick nodes to transform
-	 * @param transformer
-	 *            The thing to use to transform the nodes
-	 */
-	public void selectiveTransform(Predicate<T> transformerPredicate,
-			UnaryOperator<T> transformer) {
-		if (transformerPredicate == null) {
-			throw new NullPointerException("Predicate must not be null");
-		} else if (transformer == null) {
-			throw new NullPointerException("Transformer must not be null");
-		}
-
-		if (transformerPredicate.test(token)) {
-			token = transformer.apply(token);
-		}
-
-		if (left != null) {
-			left.selectiveTransform(transformerPredicate, transformer);
-		}
-
-		if (right != null) {
-			right.selectiveTransform(transformerPredicate, transformer);
-		}
-	}
-
-	@Override
-	public String toString() {
-		StringBuilder builder = new StringBuilder();
-
-		internalToString(builder, -1);
-
-		builder.deleteCharAt(builder.length() - 1);
-
-		return builder.toString();
-	}
-
-	/**
-	 * Transmute the tokens in an AST into a different sort of token
-	 * 
-	 * @param <E>
-	 *            The type of the transformed tokens
-	 * 
-	 * @param tokenTransformer
-	 *            The transform to run on the tokens
-	 * @return The AST with transformed tokens
-	 */
-	public <E> AST<E> transmuteAST(Function<T, E> tokenTransformer) {
-		if (tokenTransformer == null) {
-			throw new NullPointerException("Transformer must not be null");
-		}
-
-		AST<E> leftBranch = null;
-		AST<E> rightBranch = null;
-
-		if (left != null) {
-			leftBranch = left.transmuteAST(tokenTransformer);
-		}
-
-		if (right != null) {
-			rightBranch = right.transmuteAST(tokenTransformer);
-		}
-
-		return new AST<>(tokenTransformer.apply(token), leftBranch,
-				rightBranch);
-	}
-
-	/**
-	 * Traverse an AST
-	 * 
-	 * @param linearizationMethod
-	 *            The way to traverse the tree
-	 * @param action
-	 *            The function to call on each traversed element
-	 */
-	public void traverse(TreeLinearizationMethod linearizationMethod,
-			Consumer<T> action) {
-		if (linearizationMethod == null) {
-			throw new NullPointerException(
-					"Linearization method must not be null");
-		} else if (action == null) {
-			throw new NullPointerException("Action must not be null");
-		}
-
-		if (left != null && right != null) {
-			switch (linearizationMethod) {
-				case INORDER:
-					left.traverse(linearizationMethod, action);
-					action.accept(token);
-					right.traverse(linearizationMethod, action);
-					break;
-				case POSTORDER:
-					left.traverse(linearizationMethod, action);
-					right.traverse(linearizationMethod, action);
-					action.accept(token);
-					break;
-				case PREORDER:
-					action.accept(token);
-					left.traverse(linearizationMethod, action);
-					right.traverse(linearizationMethod, action);
-					break;
-				default:
-					throw new IllegalArgumentException(
-							"Got a invalid tree linearizer "
-									+ linearizationMethod + ". WAT");
-			}
-		} else {
-			action.accept(token);
-		}
-	}
-
-	/**
-	 * Change the type of nodes in the tree without changing the structure
-	 * 
-	 * @param <E>
-	 *            The new node type
-	 * @param nodeTransform
-	 *            The transform to apply to leaf nodes
-	 * @param operatorTransform
-	 *            The transform to apply to operator nodes
-	 * @return An AST with the node types transformed
-	 */
-	public <E> AST<E> rebuildTree(Function<T, E> nodeTransform,
-			Function<T, E> operatorTransform) {
-		return collapse((leafNode) -> {
-			E transformedNode = nodeTransform.apply(leafNode);
-			return new AST<>(transformedNode);
-		}, (operator) -> (AST<E> newLeft, AST<E> newRight) -> {
-			return new AST<>(operatorTransform.apply(operator), newLeft,
-					newRight);
-		}, (resultValue) -> resultValue);
-	}
-}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/TreeConstructor.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/TreeConstructor.java
index 088430b..52299bb 100644
--- a/BJC-Utils2/src/main/java/bjc/utils/parserutils/TreeConstructor.java
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/TreeConstructor.java
@@ -12,6 +12,8 @@ import bjc.utils.data.experimental.IPair;
 import bjc.utils.data.experimental.Identity;
 import bjc.utils.data.experimental.Pair;
 import bjc.utils.funcdata.IFunctionalList;
+import bjc.utils.funcdata.ITree;
+import bjc.utils.funcdata.Tree;
 
 /**
  * Creates a parse tree from a postfix expression
@@ -21,8 +23,8 @@ import bjc.utils.funcdata.IFunctionalList;
  */
 public class TreeConstructor {
 	private static final class TokenTransformer<T> implements Consumer<T> {
-		private final class OperatorHandler
-				implements UnaryOperator<IPair<Deque<AST<T>>, AST<T>>> {
+		private final class OperatorHandler implements
+				UnaryOperator<IPair<Deque<ITree<T>>, ITree<T>>> {
 			private T element;
 
 			public OperatorHandler(T element) {
@@ -30,16 +32,16 @@ public class TreeConstructor {
 			}
 
 			@Override
-			public IPair<Deque<AST<T>>, AST<T>> apply(
-					IPair<Deque<AST<T>>, AST<T>> pair) {
+			public IPair<Deque<ITree<T>>, ITree<T>> apply(
+					IPair<Deque<ITree<T>>, ITree<T>> pair) {
 				return pair.bind((queuedASTs, currentAST) -> {
 					return handleOperator(queuedASTs);
 				});
 			}
 
-			private IPair<Deque<AST<T>>, AST<T>> handleOperator(
-					Deque<AST<T>> queuedASTs) {
-				AST<T> newAST;
+			private IPair<Deque<ITree<T>>, ITree<T>> handleOperator(
+					Deque<ITree<T>> queuedASTs) {
+				ITree<T> newAST;
 
 				if (isSpecialOperator.test(element)) {
 					newAST = handleSpecialOperator.apply(queuedASTs);
@@ -52,10 +54,10 @@ public class TreeConstructor {
 										+ queuedASTs.peek());
 					}
 
-					AST<T> rightAST = queuedASTs.pop();
-					AST<T> leftAST = queuedASTs.pop();
+					ITree<T> rightAST = queuedASTs.pop();
+					ITree<T> leftAST = queuedASTs.pop();
 
-					newAST = new AST<>(element, leftAST, rightAST);
+					newAST = new Tree<>(element, leftAST, rightAST);
 				}
 
 				queuedASTs.push(newAST);
@@ -64,16 +66,16 @@ public class TreeConstructor {
 			}
 		}
 
-		private IHolder<IPair<Deque<AST<T>>, AST<T>>>	initialState;
-		private Predicate<T>							operatorPredicate;
-		private Predicate<T>							isSpecialOperator;
-		private Function<Deque<AST<T>>, AST<T>>			handleSpecialOperator;
+		private IHolder<IPair<Deque<ITree<T>>, ITree<T>>>	initialState;
+		private Predicate<T>								operatorPredicate;
+		private Predicate<T>								isSpecialOperator;
+		private Function<Deque<ITree<T>>, ITree<T>>			handleSpecialOperator;
 
 		public TokenTransformer(
-				IHolder<IPair<Deque<AST<T>>, AST<T>>> initialState,
+				IHolder<IPair<Deque<ITree<T>>, ITree<T>>> initialState,
 				Predicate<T> operatorPredicate,
 				Predicate<T> isSpecialOperator,
-				Function<Deque<AST<T>>, AST<T>> handleSpecialOperator) {
+				Function<Deque<ITree<T>>, ITree<T>> handleSpecialOperator) {
 			this.initialState = initialState;
 			this.operatorPredicate = operatorPredicate;
 			this.isSpecialOperator = isSpecialOperator;
@@ -85,7 +87,7 @@ public class TreeConstructor {
 			if (operatorPredicate.test(element)) {
 				initialState.transform(new OperatorHandler(element));
 			} else {
-				AST<T> newAST = new AST<>(element);
+				ITree<T> newAST = new Tree<>(element);
 
 				initialState.doWith((pair) -> {
 					pair.doWith((queue, currentAST) -> {
@@ -116,7 +118,7 @@ public class TreeConstructor {
 	 *            operator
 	 * @return A AST from the expression
 	 */
-	public static <T> AST<T> constructTree(IFunctionalList<T> tokens,
+	public static <T> ITree<T> constructTree(IFunctionalList<T> tokens,
 			Predicate<T> operatorPredicate) {
 		return constructTree(tokens, operatorPredicate, (op) -> false,
 				null);
@@ -146,9 +148,9 @@ public class TreeConstructor {
 	 *         interface. Maybe there's a better way to express how that
 	 *         works
 	 */
-	public static <T> AST<T> constructTree(IFunctionalList<T> tokens,
+	public static <T> ITree<T> constructTree(IFunctionalList<T> tokens,
 			Predicate<T> operatorPredicate, Predicate<T> isSpecialOperator,
-			Function<Deque<AST<T>>, AST<T>> handleSpecialOperator) {
+			Function<Deque<ITree<T>>, ITree<T>> handleSpecialOperator) {
 		if (tokens == null) {
 			throw new NullPointerException("Tokens must not be null");
 		} else if (operatorPredicate == null) {
@@ -159,7 +161,7 @@ public class TreeConstructor {
 					"Special operator determiner must not be null");
 		}
 
-		IHolder<IPair<Deque<AST<T>>, AST<T>>> initialState = new Identity<>(
+		IHolder<IPair<Deque<ITree<T>>, ITree<T>>> initialState = new Identity<>(
 				new Pair<>(new LinkedList<>(), null));
 
 		tokens.forEach(