diff options
Diffstat (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata')
7 files changed, 467 insertions, 81 deletions
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 <E> + * @param <ContainedType> * The type in this list */ -public interface IFunctionalList<E> { +public interface IFunctionalList<ContainedType> { /** * Add an item to this list @@ -33,7 +33,7 @@ public interface IFunctionalList<E> { * 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<E> { * @return Whether all of the elements of the list match the specified * predicate. */ - boolean allMatch(Predicate<E> matchPredicate); + boolean allMatch(Predicate<ContainedType> matchPredicate); /** * Check if any of the elements in this list match the specified list. @@ -62,7 +62,7 @@ public interface IFunctionalList<E> { * @return Whether any element in the list matches the provided * predicate. */ - boolean anyMatch(Predicate<E> matchPredicate); + boolean anyMatch(Predicate<ContainedType> matchPredicate); /** * Combine this list with another one into a new list and merge the @@ -76,9 +76,9 @@ public interface IFunctionalList<E> { * of this list and the provided one, and c is the running time of the * combiner. * - * @param <T> + * @param <OtherType> * The type of the second list - * @param <F> + * @param <CombinedType> * The type of the combined list * * @param rightList @@ -87,8 +87,9 @@ public interface IFunctionalList<E> { * The function to use for combining element pairs. * @return A new list containing the merged pairs of lists. */ - <T, F> IFunctionalList<F> combineWith(IFunctionalList<T> rightList, - BiFunction<E, T, F> itemCombiner); + <OtherType, CombinedType> IFunctionalList<CombinedType> combineWith( + IFunctionalList<OtherType> rightList, + BiFunction<ContainedType, OtherType, CombinedType> itemCombiner); /** * Check if the list contains the specified item @@ -99,7 +100,7 @@ public interface IFunctionalList<E> { * 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<E> { * * @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<E> { * Takes O(n * m) time, where m is the average number of elements in * the returned list. * - * @param <T> + * @param <MappedType> * The type of the flattened list * * @param elementExpander @@ -125,8 +126,8 @@ public interface IFunctionalList<E> { * @return A new list containing the flattened results of applying the * provided function. */ - <T> IFunctionalList<T> flatMap( - Function<E, IFunctionalList<T>> elementExpander); + <MappedType> IFunctionalList<MappedType> flatMap( + Function<ContainedType, IFunctionalList<MappedType>> elementExpander); /** * Apply a given action for each member of the list @@ -137,7 +138,7 @@ public interface IFunctionalList<E> { * @param action * The action to apply to each member of the list. */ - void forEach(Consumer<E> action); + void forEach(Consumer<ContainedType> action); /** * Apply a given function to each element in the list and its index. @@ -149,7 +150,7 @@ public interface IFunctionalList<E> { * The function to apply to each element in the list and its * index. */ - void forEachIndexed(BiConsumer<Integer, E> indexedAction); + void forEachIndexed(BiConsumer<Integer, ContainedType> indexedAction); /** * Retrieve a value in the list by its index. @@ -160,17 +161,19 @@ public interface IFunctionalList<E> { * 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<E> getMatching(Predicate<E> matchPredicate); + IFunctionalList<ContainedType> getMatching( + Predicate<ContainedType> matchPredicate); /** * Retrieve the size of the wrapped list @@ -190,19 +193,20 @@ public interface IFunctionalList<E> { * Create a new list by applying the given function to each element in * the list. Does not change the underlying list. * - * @param <T> + * @param <MappedType> * 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. */ - <T> IFunctionalList<T> map(Function<E, T> elementTransformer); + <MappedType> IFunctionalList<MappedType> map( + Function<ContainedType, MappedType> elementTransformer); /** * Zip two lists into a list of pairs * - * @param <T> + * @param <OtherType> * The type of the second list * * @param rightList @@ -210,8 +214,8 @@ public interface IFunctionalList<E> { * @return A list containing pairs of this element and the specified * list */ - <T> IFunctionalList<IPair<E, T>> pairWith( - IFunctionalList<T> rightList); + <OtherType> IFunctionalList<IPair<ContainedType, OtherType>> pairWith( + IFunctionalList<OtherType> rightList); /** * Partition this list into a list of sublists @@ -220,7 +224,8 @@ public interface IFunctionalList<E> { * The size of elements to put into each one of the sublists * @return A list partitioned into partitions of size nPerPart */ - IFunctionalList<IFunctionalList<E>> partition(int numberPerPartition); + IFunctionalList<IFunctionalList<ContainedType>> partition( + int numberPerPartition); /** * Prepend an item to the list @@ -228,7 +233,7 @@ public interface IFunctionalList<E> { * @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<E> { * The random number generator to use. * @return A random element from this list. */ - E randItem(Function<Integer, Integer> rnd); + ContainedType randItem(Function<Integer, Integer> rnd); /** * Reduce this list to a single value, using a accumulative approach. * - * @param <T> + * @param <StateType> * The in-between type of the values - * @param <F> + * @param <ReducedType> * The final value type * * @param initialValue @@ -259,9 +264,9 @@ public interface IFunctionalList<E> { * @return A single value condensed from this list and transformed into * its final state. */ - <T, F> F reduceAux(T initialValue, - BiFunction<E, T, T> stateAccumulator, - Function<T, F> resultTransformer); + <StateType, ReducedType> ReducedType reduceAux(StateType initialValue, + BiFunction<ContainedType, StateType, StateType> stateAccumulator, + Function<StateType, ReducedType> resultTransformer); /** * Remove all elements that match a given predicate @@ -270,7 +275,7 @@ public interface IFunctionalList<E> { * The predicate to use to determine elements to delete * @return Whether there was anything that satisfied the predicate */ - boolean removeIf(Predicate<E> removePredicate); + boolean removeIf(Predicate<ContainedType> removePredicate); /** * Remove all parameters that match a given parameter @@ -278,7 +283,7 @@ public interface IFunctionalList<E> { * @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<E> { * 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<E> comparator); + ContainedType search(ContainedType searchKey, + Comparator<ContainedType> comparator); /** * Sort the elements of this list using the provided way of comparing @@ -302,14 +308,7 @@ public interface IFunctionalList<E> { * The way to compare elements for sorting. Pass null to use * E's natural ordering */ - void sort(Comparator<E> comparator); - - /** - * Convert the list into a iterable - * - * @return An iterable view onto the list - */ - Iterable<E> toIterable(); + void sort(Comparator<ContainedType> comparator); /** * Convert this list into an array @@ -318,5 +317,12 @@ public interface IFunctionalList<E> { * 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<ContainedType> 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 <K> + * @param <KeyType> * The type of this map's keys - * @param <V> + * @param <ValueType> * The type of this map's values * */ -public interface IFunctionalMap<K, V> { +public interface IFunctionalMap<KeyType, ValueType> { /** * Add an entry to the map @@ -32,7 +32,7 @@ public interface IFunctionalMap<K, V> { * 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<K, V> { * * */ - V get(K key); + ValueType get(KeyType key); /** * Transform the values returned by this map. @@ -58,7 +58,7 @@ public interface IFunctionalMap<K, V> { * The function to use to transform values * @return The map where each value will be transformed after lookup */ - <V2> IFunctionalMap<K, V2> mapValues(Function<V, V2> transformer); + <V2> IFunctionalMap<KeyType, V2> mapValues(Function<ValueType, V2> transformer); /** * Check if this map contains the specified key @@ -67,14 +67,14 @@ public interface IFunctionalMap<K, V> { * 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<K> keyList(); + IFunctionalList<KeyType> keyList(); /** * Execute an action for each entry in the map @@ -82,7 +82,7 @@ public interface IFunctionalMap<K, V> { * @param action * the action to execute for each entry in the map */ - void forEach(BiConsumer<K, V> action); + void forEach(BiConsumer<KeyType, ValueType> action); /** * Remove the value bound to the key @@ -94,7 +94,7 @@ public interface IFunctionalMap<K, V> { * 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<K, V> { * @param action * The action to perform on each key in the map */ - void forEachKey(Consumer<K> action); + void forEachKey(Consumer<KeyType> action); /** * Perform an action for each value in the map @@ -117,12 +117,12 @@ public interface IFunctionalMap<K, V> { * @param action * The action to perform on each value in the map */ - void forEachValue(Consumer<V> action); + void forEachValue(Consumer<ValueType> action); /** * Get a list of the values in this map * * @return A list of values in this map */ - IFunctionalList<V> valueList(); + IFunctionalList<ValueType> 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 <ContainedType> + * The type of data contained in the tree nodes + * + */ +public interface ITree<ContainedType> { + /** + * Add a child to this node + * + * @param child + * The child to add to this node + */ + public void addChild(ITree<ContainedType> child); + + /** + * Transform the value that is the head of this node + * + * @param <TransformedType> + * The type of the transformed value + * @param transformer + * The function to use to transform the value + * @return The transformed value + */ + public <TransformedType> TransformedType transformHead( + Function<ContainedType, TransformedType> 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 <TransformedType> + * 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> TransformedType transformChild(int childNo, + Function<ITree<ContainedType>, TransformedType> transformer); + + /** + * Collapse a tree into a single version + * + * @param <NewType> + * The intermediate type being folded + * @param <ReturnedType> + * 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 <NewType, ReturnedType> ReturnedType collapse( + Function<ContainedType, NewType> leafTransform, + Function<ContainedType, Function<IFunctionalList<NewType>, NewType>> nodeCollapser, + Function<NewType, ReturnedType> 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<ContainedType> flatMapTree( + Function<ContainedType, ITree<ContainedType>> 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<ContainedType> nodePicker, + UnaryOperator<ContainedType> transformer); + + /** + * Transform the tree into a tree with a different type of token + * + * @param <MappedType> + * The type of the new tree + * @param transformer + * The function to use to transform tokens + * @return A tree with the token types transformed + */ + public <MappedType> ITree<MappedType> transformTree( + Function<ContainedType, MappedType> 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<ContainedType> action); + + /** + * Rebuild the tree with the same structure, but different nodes + * + * @param <MappedType> + * 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 <MappedType> ITree<MappedType> rebuildTree( + Function<ContainedType, MappedType> leafTransformer, + Function<ContainedType, MappedType> 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 <ContainedType> + */ +public class Tree<ContainedType> implements ITree<ContainedType> { + private ContainedType data; + private IFunctionalList<ITree<ContainedType>> 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<ContainedType>... childrn) { + data = leafToken; + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for (ITree<ContainedType> child : childrn) { + children.add(child); + + childCount++; + } + } + + private Tree(ContainedType leafToken, + IFunctionalList<ITree<ContainedType>> childrn) { + data = leafToken; + + hasChildren = true; + + childCount = childrn.getSize(); + + children = childrn; + } + + @Override + public void addChild(ITree<ContainedType> child) { + if (hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public <TransformedType> TransformedType transformHead( + Function<ContainedType, TransformedType> transformer) { + return transformer.apply(data); + } + + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public <TransformedType> TransformedType transformChild(int childNo, + Function<ITree<ContainedType>, TransformedType> transformer) { + if (childNo < 0 || childNo > (childCount - 1)) { + throw new IllegalArgumentException( + "Child index #" + childNo + " is invalid"); + } + + return transformer.apply(children.getByIndex(childNo)); + } + + @Override + public <NewType, ReturnedType> ReturnedType collapse( + Function<ContainedType, NewType> leafTransform, + Function<ContainedType, Function<IFunctionalList<NewType>, NewType>> nodeCollapser, + Function<NewType, ReturnedType> resultTransformer) { + + return resultTransformer + .apply(internalCollapse(leafTransform, nodeCollapser)); + } + + protected <NewType> NewType internalCollapse( + Function<ContainedType, NewType> leafTransform, + Function<ContainedType, Function<IFunctionalList<NewType>, NewType>> nodeCollapser) { + if (hasChildren) { + Function<IFunctionalList<NewType>, NewType> nodeTransformer = nodeCollapser + .apply(data); + + IFunctionalList<NewType> collapsedChildren = children + .map((child) -> { + return child.collapse(leafTransform, nodeCollapser, + (subTreeVal) -> subTreeVal); + }); + + return nodeTransformer.apply(collapsedChildren); + } + + return leafTransform.apply(data); + } + + @Override + public ITree<ContainedType> flatMapTree( + Function<ContainedType, ITree<ContainedType>> mapper) { + if (hasChildren) { + ITree<ContainedType> 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<ContainedType> nodePicker, + UnaryOperator<ContainedType> transformer) { + if (hasChildren) { + children.forEach((child) -> child + .selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public <MappedType> ITree<MappedType> transformTree( + Function<ContainedType, MappedType> transformer) { + if (hasChildren) { + IFunctionalList<ITree<MappedType>> 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<ContainedType> 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 <MappedType> ITree<MappedType> rebuildTree( + Function<ContainedType, MappedType> leafTransformer, + Function<ContainedType, MappedType> operatorTransformer) { + if (hasChildren) { + IFunctionalList<ITree<MappedType>> 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 @@ -15,30 +15,6 @@ import java.util.function.Predicate; */ 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 element 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 |