From 9adff31e86603493c2a245e1e803d951675d5e00 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Wed, 13 Apr 2016 23:11:36 -0400 Subject: Implemented new tree abstraction --- .../java/bjc/utils/funcdata/IFunctionalList.java | 92 ++++---- .../java/bjc/utils/funcdata/IFunctionalMap.java | 26 +-- .../src/main/java/bjc/utils/funcdata/ITree.java | 145 +++++++++++++ .../src/main/java/bjc/utils/funcdata/Tree.java | 235 +++++++++++++++++++++ .../bjc/utils/funcdata/bst/BinarySearchTree.java | 1 - .../java/bjc/utils/funcdata/bst/ITreePart.java | 24 --- .../funcdata/bst/TreeLinearizationMethod.java | 25 +++ 7 files changed, 467 insertions(+), 81 deletions(-) create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/ITree.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/Tree.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata') diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalList.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalList.java index 949fc33..4be7277 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalList.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalList.java @@ -19,10 +19,10 @@ import bjc.utils.data.experimental.IPair; * * @author ben * - * @param + * @param * The type in this list */ -public interface IFunctionalList { +public interface IFunctionalList { /** * Add an item to this list @@ -33,7 +33,7 @@ public interface IFunctionalList { * The item to add to this list. * @return Whether the item was added to the list succesfully. */ - boolean add(E item); + boolean add(ContainedType item); /** * Check if all of the elements of this list match the specified @@ -48,7 +48,7 @@ public interface IFunctionalList { * @return Whether all of the elements of the list match the specified * predicate. */ - boolean allMatch(Predicate matchPredicate); + boolean allMatch(Predicate matchPredicate); /** * Check if any of the elements in this list match the specified list. @@ -62,7 +62,7 @@ public interface IFunctionalList { * @return Whether any element in the list matches the provided * predicate. */ - boolean anyMatch(Predicate matchPredicate); + boolean anyMatch(Predicate matchPredicate); /** * Combine this list with another one into a new list and merge the @@ -76,9 +76,9 @@ public interface IFunctionalList { * of this list and the provided one, and c is the running time of the * combiner. * - * @param + * @param * The type of the second list - * @param + * @param * The type of the combined list * * @param rightList @@ -87,8 +87,9 @@ public interface IFunctionalList { * The function to use for combining element pairs. * @return A new list containing the merged pairs of lists. */ - IFunctionalList combineWith(IFunctionalList rightList, - BiFunction itemCombiner); + IFunctionalList combineWith( + IFunctionalList rightList, + BiFunction itemCombiner); /** * Check if the list contains the specified item @@ -99,7 +100,7 @@ public interface IFunctionalList { * The item to see if it is contained * @return Whether or not the specified item is in the list */ - boolean contains(E item); + boolean contains(ContainedType item); /** * Get the first element in the list @@ -108,7 +109,7 @@ public interface IFunctionalList { * * @return The first element in this list. */ - E first(); + ContainedType first(); /** * Apply a function to each member of the list, then flatten the @@ -117,7 +118,7 @@ public interface IFunctionalList { * Takes O(n * m) time, where m is the average number of elements in * the returned list. * - * @param + * @param * The type of the flattened list * * @param elementExpander @@ -125,8 +126,8 @@ public interface IFunctionalList { * @return A new list containing the flattened results of applying the * provided function. */ - IFunctionalList flatMap( - Function> elementExpander); + IFunctionalList flatMap( + Function> elementExpander); /** * Apply a given action for each member of the list @@ -137,7 +138,7 @@ public interface IFunctionalList { * @param action * The action to apply to each member of the list. */ - void forEach(Consumer action); + void forEach(Consumer action); /** * Apply a given function to each element in the list and its index. @@ -149,7 +150,7 @@ public interface IFunctionalList { * The function to apply to each element in the list and its * index. */ - void forEachIndexed(BiConsumer indexedAction); + void forEachIndexed(BiConsumer indexedAction); /** * Retrieve a value in the list by its index. @@ -160,17 +161,19 @@ public interface IFunctionalList { * The index to retrieve a value from. * @return The value at the specified index in the list. */ - E getByIndex(int index); + ContainedType getByIndex(int index); /** * Retrieve a list containing all elements matching a predicate * * Takes O(n) time, where n is the number of elements in the list + * * @param matchPredicate * The predicate to match by * @return A list containing all elements that match the predicate */ - IFunctionalList getMatching(Predicate matchPredicate); + IFunctionalList getMatching( + Predicate matchPredicate); /** * Retrieve the size of the wrapped list @@ -190,19 +193,20 @@ public interface IFunctionalList { * Create a new list by applying the given function to each element in * the list. Does not change the underlying list. * - * @param + * @param * The type of the transformed list * * @param elementTransformer * The function to apply to each element in the list * @return A new list containing the mapped elements of this list. */ - IFunctionalList map(Function elementTransformer); + IFunctionalList map( + Function elementTransformer); /** * Zip two lists into a list of pairs * - * @param + * @param * The type of the second list * * @param rightList @@ -210,8 +214,8 @@ public interface IFunctionalList { * @return A list containing pairs of this element and the specified * list */ - IFunctionalList> pairWith( - IFunctionalList rightList); + IFunctionalList> pairWith( + IFunctionalList rightList); /** * Partition this list into a list of sublists @@ -220,7 +224,8 @@ public interface IFunctionalList { * The size of elements to put into each one of the sublists * @return A list partitioned into partitions of size nPerPart */ - IFunctionalList> partition(int numberPerPartition); + IFunctionalList> partition( + int numberPerPartition); /** * Prepend an item to the list @@ -228,7 +233,7 @@ public interface IFunctionalList { * @param item * The item to prepend to the list */ - void prepend(E item); + void prepend(ContainedType item); /** * Select a random item from this list, using the provided random @@ -238,14 +243,14 @@ public interface IFunctionalList { * The random number generator to use. * @return A random element from this list. */ - E randItem(Function rnd); + ContainedType randItem(Function rnd); /** * Reduce this list to a single value, using a accumulative approach. * - * @param + * @param * The in-between type of the values - * @param + * @param * The final value type * * @param initialValue @@ -259,9 +264,9 @@ public interface IFunctionalList { * @return A single value condensed from this list and transformed into * its final state. */ - F reduceAux(T initialValue, - BiFunction stateAccumulator, - Function resultTransformer); + ReducedType reduceAux(StateType initialValue, + BiFunction stateAccumulator, + Function resultTransformer); /** * Remove all elements that match a given predicate @@ -270,7 +275,7 @@ public interface IFunctionalList { * The predicate to use to determine elements to delete * @return Whether there was anything that satisfied the predicate */ - boolean removeIf(Predicate removePredicate); + boolean removeIf(Predicate removePredicate); /** * Remove all parameters that match a given parameter @@ -278,7 +283,7 @@ public interface IFunctionalList { * @param desiredElement * The object to remove all matching copies of */ - void removeMatching(E desiredElement); + void removeMatching(ContainedType desiredElement); /** * Perform a binary search for the specified key using the provided @@ -292,7 +297,8 @@ public interface IFunctionalList { * use the natural ordering for E * @return The element if it is in this list, or null if it is not. */ - E search(E searchKey, Comparator comparator); + ContainedType search(ContainedType searchKey, + Comparator comparator); /** * Sort the elements of this list using the provided way of comparing @@ -302,14 +308,7 @@ public interface IFunctionalList { * The way to compare elements for sorting. Pass null to use * E's natural ordering */ - void sort(Comparator comparator); - - /** - * Convert the list into a iterable - * - * @return An iterable view onto the list - */ - Iterable toIterable(); + void sort(Comparator comparator); /** * Convert this list into an array @@ -318,5 +317,12 @@ public interface IFunctionalList { * The type of array to return * @return The list, as an array */ - E[] toArray(E[] arrType); + ContainedType[] toArray(ContainedType[] arrType); + + /** + * Convert the list into a iterable + * + * @return An iterable view onto the list + */ + Iterable toIterable(); } \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalMap.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalMap.java index c879229..c5fe559 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalMap.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/IFunctionalMap.java @@ -9,13 +9,13 @@ import java.util.function.Function; * * @author ben * - * @param + * @param * The type of this map's keys - * @param + * @param * The type of this map's values * */ -public interface IFunctionalMap { +public interface IFunctionalMap { /** * Add an entry to the map @@ -32,7 +32,7 @@ public interface IFunctionalMap { * if the map implementation doesn't support modifying the * map */ - V put(K key, V val); + ValueType put(KeyType key, ValueType val); /** * Get the value assigned to the given key @@ -43,7 +43,7 @@ public interface IFunctionalMap { * * */ - V get(K key); + ValueType get(KeyType key); /** * Transform the values returned by this map. @@ -58,7 +58,7 @@ public interface IFunctionalMap { * The function to use to transform values * @return The map where each value will be transformed after lookup */ - IFunctionalMap mapValues(Function transformer); + IFunctionalMap mapValues(Function transformer); /** * Check if this map contains the specified key @@ -67,14 +67,14 @@ public interface IFunctionalMap { * The key to check * @return Whether or not the map contains the key */ - boolean containsKey(K key); + boolean containsKey(KeyType key); /** * Get a list of all the keys in this map * * @return A list of all the keys in this map */ - IFunctionalList keyList(); + IFunctionalList keyList(); /** * Execute an action for each entry in the map @@ -82,7 +82,7 @@ public interface IFunctionalMap { * @param action * the action to execute for each entry in the map */ - void forEach(BiConsumer action); + void forEach(BiConsumer action); /** * Remove the value bound to the key @@ -94,7 +94,7 @@ public interface IFunctionalMap { * null, doesn't mean the map wasn't changed. It may mean that * someone put a null value for that key into the map */ - V remove(K key); + ValueType remove(KeyType key); /** * Get the number of entries in this map @@ -109,7 +109,7 @@ public interface IFunctionalMap { * @param action * The action to perform on each key in the map */ - void forEachKey(Consumer action); + void forEachKey(Consumer action); /** * Perform an action for each value in the map @@ -117,12 +117,12 @@ public interface IFunctionalMap { * @param action * The action to perform on each value in the map */ - void forEachValue(Consumer action); + void forEachValue(Consumer action); /** * Get a list of the values in this map * * @return A list of values in this map */ - IFunctionalList valueList(); + IFunctionalList valueList(); } \ No newline at end of file diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/ITree.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/ITree.java new file mode 100644 index 0000000..624c9d6 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/ITree.java @@ -0,0 +1,145 @@ +package bjc.utils.funcdata; + +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 node in a homogenous tree with a unlimited amount of children + * + * @author ben + * @param + * The type of data contained in the tree nodes + * + */ +public interface ITree { + /** + * Add a child to this node + * + * @param child + * The child to add to this node + */ + public void addChild(ITree child); + + /** + * Transform the value that is the head of this node + * + * @param + * The type of the transformed value + * @param transformer + * The function to use to transform the value + * @return The transformed value + */ + public TransformedType transformHead( + Function transformer); + + /** + * Get a count of the number of direct children this node has + * + * @return The number of direct children this node has + */ + public int getChildrenCount(); + + /** + * Transform one of this nodes children + * + * @param + * The type of the transformed value + * @param childNo + * The number of the child to transform + * @param transformer + * The function to use to transform the value + * @return The transformed value + * + * @throws IllegalArgumentException + * if the childNo is out of bounds (0 <= childNo <= + * childCount()) + */ + public TransformedType transformChild(int childNo, + Function, TransformedType> transformer); + + /** + * Collapse a tree into a single version + * + * @param + * The intermediate type being folded + * @param + * The type that is the end result + * @param leafTransform + * The function to use to convert leaf values + * @param nodeCollapser + * The function to use to convert internal nodes and their + * children + * @param resultTransformer + * The function to use to convert a state to the returned + * version + * @return The final transformed state + */ + public ReturnedType collapse( + Function leafTransform, + Function, NewType>> nodeCollapser, + Function resultTransformer); + + /** + * Expand the nodes of a tree into trees, and then merge the contents + * of those trees into a single tree + * + * @param mapper + * The function to use to map values into trees + * @return A tree, with some nodes expanded into trees + */ + public ITree flatMapTree( + Function> mapper); + + /** + * Transform some of the nodes in this tree + * + * @param nodePicker + * The predicate to use to pick nodes to transform + * @param transformer + * The function to use to transform picked nodes + */ + public void selectiveTransform(Predicate nodePicker, + UnaryOperator transformer); + + /** + * Transform the tree into a tree with a different type of token + * + * @param + * The type of the new tree + * @param transformer + * The function to use to transform tokens + * @return A tree with the token types transformed + */ + public ITree transformTree( + Function transformer); + + /** + * Perform an action on each part of the tree + * + * @param linearizationMethod + * The way to traverse the tree + * @param action + * The action to perform on each tree node + */ + public void traverse(TreeLinearizationMethod linearizationMethod, + Consumer action); + + /** + * Rebuild the tree with the same structure, but different nodes + * + * @param + * The type of the new tree + * @param leafTransformer + * The function to use to transform leaf tokens + * @param operatorTransformer + * The function to use to transform internal tokens + * @return The tree, with the nodes changed + */ + public ITree rebuildTree( + Function leafTransformer, + Function operatorTransformer); +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/Tree.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/Tree.java new file mode 100644 index 0000000..d9938d4 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/Tree.java @@ -0,0 +1,235 @@ +package bjc.utils.funcdata; + +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 node in a homogenous tree. + * + * @author ben + * + * @param + */ +public class Tree implements ITree { + private ContainedType data; + private IFunctionalList> children; + + private boolean hasChildren; + + private int childCount; + + /** + * Create a new leaf node in a tree + * + * @param leafToken + * The data to store as a leaf node + */ + public Tree(ContainedType leafToken) { + data = leafToken; + + hasChildren = false; + } + + /** + * Create a new tree node with the specified children + * + * @param leafToken + * The data to hold in this node + * @param childrn + * A list of children for this node + */ + @SafeVarargs + public Tree(ContainedType leafToken, ITree... childrn) { + data = leafToken; + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for (ITree child : childrn) { + children.add(child); + + childCount++; + } + } + + private Tree(ContainedType leafToken, + IFunctionalList> childrn) { + data = leafToken; + + hasChildren = true; + + childCount = childrn.getSize(); + + children = childrn; + } + + @Override + public void addChild(ITree child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public TransformedType transformHead( + Function transformer) { + return transformer.apply(data); + } + + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public TransformedType transformChild(int childNo, + Function, TransformedType> transformer) { + if (childNo < 0 || childNo > (childCount - 1)) { + throw new IllegalArgumentException( + "Child index #" + childNo + " is invalid"); + } + + return transformer.apply(children.getByIndex(childNo)); + } + + @Override + public ReturnedType collapse( + Function leafTransform, + Function, NewType>> nodeCollapser, + Function resultTransformer) { + + return resultTransformer + .apply(internalCollapse(leafTransform, nodeCollapser)); + } + + protected NewType internalCollapse( + Function leafTransform, + Function, NewType>> nodeCollapser) { + if (hasChildren) { + Function, NewType> nodeTransformer = nodeCollapser + .apply(data); + + IFunctionalList collapsedChildren = children + .map((child) -> { + return child.collapse(leafTransform, nodeCollapser, + (subTreeVal) -> subTreeVal); + }); + + return nodeTransformer.apply(collapsedChildren); + } + + return leafTransform.apply(data); + } + + @Override + public ITree flatMapTree( + Function> mapper) { + if (hasChildren) { + ITree flatMappedData = mapper.apply(data); + + children.map((child) -> child.flatMapTree(mapper)) + .forEach((child) -> flatMappedData.addChild(child)); + + return flatMappedData; + } + + return mapper.apply(data); + } + + @Override + public void selectiveTransform(Predicate nodePicker, + UnaryOperator transformer) { + if (hasChildren) { + children.forEach((child) -> child + .selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public ITree transformTree( + Function transformer) { + if (hasChildren) { + IFunctionalList> transformedChildren = children + .map((child) -> child.transformTree(transformer)); + + return new Tree<>(transformer.apply(data), + transformedChildren); + } + + return new Tree<>(transformer.apply(data)); + } + + @Override + public void traverse(TreeLinearizationMethod linearizationMethod, + Consumer action) { + if (hasChildren) { + switch (linearizationMethod) { + case INORDER: + if (childCount != 2) { + throw new IllegalArgumentException( + "Can only do in-order traversal for binary trees."); + } + + children.getByIndex(0).traverse(linearizationMethod, + action); + + action.accept(data); + + children.getByIndex(1).traverse(linearizationMethod, + action); + break; + case POSTORDER: + children.forEach((child) -> child + .traverse(linearizationMethod, action)); + + action.accept(data); + break; + case PREORDER: + action.accept(data); + + children.forEach((child) -> child + .traverse(linearizationMethod, action)); + break; + default: + break; + + } + } else { + action.accept(data); + } + } + + @Override + public ITree rebuildTree( + Function leafTransformer, + Function operatorTransformer) { + if (hasChildren) { + IFunctionalList> mappedChildren = children + .map((child) -> { + return child.rebuildTree(leafTransformer, + operatorTransformer); + }); + + return new Tree<>(operatorTransformer.apply(data), + mappedChildren); + } + + return new Tree<>(leafTransformer.apply(data)); + } + +} diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java index 67b9985..6e9d14e 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java @@ -7,7 +7,6 @@ import java.util.function.Predicate; import bjc.utils.funcdata.FunctionalList; import bjc.utils.funcdata.IFunctionalList; -import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod; /** * A binary search tree, with some mild support for functional traversal. diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java index 8fa5a3d..cbd7229 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/ITreePart.java @@ -14,30 +14,6 @@ import java.util.function.Predicate; * The data contained in this part of the tree. */ public interface ITreePart { - /** - * 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. * diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java new file mode 100644 index 0000000..6c15284 --- /dev/null +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/TreeLinearizationMethod.java @@ -0,0 +1,25 @@ +package bjc.utils.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 +} \ No newline at end of file -- cgit v1.2.3