summaryrefslogtreecommitdiff
path: root/BJC-Utils2/src/main/java/bjc
diff options
context:
space:
mode:
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc')
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/parserutils/AST.java386
-rw-r--r--BJC-Utils2/src/main/java/bjc/utils/parserutils/TreeConstructor.java44
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(
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-10 22:17:39 +0000