From 843329de434bb334d90927c4d22345373a388530 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Tue, 2 Jul 2019 18:05:22 -0400 Subject: Rename package root The package root is now bjc, not io.github.bculkin2442. --- src/main/java/bjc/funcdata/ExtendedMap.java | 157 +++++++ src/main/java/bjc/funcdata/FunctionalList.java | 465 +++++++++++++++++++++ src/main/java/bjc/funcdata/FunctionalMap.java | 175 ++++++++ .../bjc/funcdata/FunctionalStringTokenizer.java | 162 +++++++ src/main/java/bjc/funcdata/IList.java | 463 ++++++++++++++++++++ src/main/java/bjc/funcdata/IMap.java | 190 +++++++++ src/main/java/bjc/funcdata/SentryList.java | 39 ++ .../java/bjc/funcdata/TransformedValueMap.java | 116 +++++ .../java/bjc/funcdata/bst/BinarySearchTree.java | 224 ++++++++++ .../bjc/funcdata/bst/BinarySearchTreeLeaf.java | 115 +++++ .../bjc/funcdata/bst/BinarySearchTreeNode.java | 295 +++++++++++++ .../bjc/funcdata/bst/DirectedWalkFunction.java | 44 ++ src/main/java/bjc/funcdata/bst/ITreePart.java | 104 +++++ .../bjc/funcdata/bst/TreeLinearizationMethod.java | 24 ++ src/main/java/bjc/funcdata/theory/Bifunctor.java | 176 ++++++++ src/main/java/bjc/funcdata/theory/Functor.java | 43 ++ 16 files changed, 2792 insertions(+) create mode 100644 src/main/java/bjc/funcdata/ExtendedMap.java create mode 100644 src/main/java/bjc/funcdata/FunctionalList.java create mode 100644 src/main/java/bjc/funcdata/FunctionalMap.java create mode 100644 src/main/java/bjc/funcdata/FunctionalStringTokenizer.java create mode 100644 src/main/java/bjc/funcdata/IList.java create mode 100644 src/main/java/bjc/funcdata/IMap.java create mode 100644 src/main/java/bjc/funcdata/SentryList.java create mode 100644 src/main/java/bjc/funcdata/TransformedValueMap.java create mode 100644 src/main/java/bjc/funcdata/bst/BinarySearchTree.java create mode 100644 src/main/java/bjc/funcdata/bst/BinarySearchTreeLeaf.java create mode 100644 src/main/java/bjc/funcdata/bst/BinarySearchTreeNode.java create mode 100644 src/main/java/bjc/funcdata/bst/DirectedWalkFunction.java create mode 100644 src/main/java/bjc/funcdata/bst/ITreePart.java create mode 100644 src/main/java/bjc/funcdata/bst/TreeLinearizationMethod.java create mode 100644 src/main/java/bjc/funcdata/theory/Bifunctor.java create mode 100644 src/main/java/bjc/funcdata/theory/Functor.java (limited to 'src/main/java/bjc/funcdata') diff --git a/src/main/java/bjc/funcdata/ExtendedMap.java b/src/main/java/bjc/funcdata/ExtendedMap.java new file mode 100644 index 0000000..76fac01 --- /dev/null +++ b/src/main/java/bjc/funcdata/ExtendedMap.java @@ -0,0 +1,157 @@ +package bjc.funcdata; + +import java.util.function.BiConsumer; +import java.util.function.Consumer; +import java.util.function.Function; + +/** + * An extended version of a map, that stores values into a map, but can look + * into a different one for others. + * + * @author Ben Culkin + * + * @param + * The type of the keys of the map. + * + * @param + * The type of the values of the map. + */ +class ExtendedMap implements IMap { + /* The map we delegate lookups to. */ + private final IMap delegate; + /* The map we store things in. */ + private final IMap store; + + /** + * Create a new extended map. + * + * @param delegate + * The map to lookup things in. + * + * @param store + * The map to store things in. + */ + public ExtendedMap(final IMap delegate, final IMap store) { + this.delegate = delegate; + this.store = store; + } + + @Override + public void clear() { + store.clear(); + } + + @Override + public boolean containsKey(final KeyType key) { + if(store.containsKey(key)) return true; + + return delegate.containsKey(key); + } + + @Override + public IMap extend() { + return new ExtendedMap<>(this, new FunctionalMap<>()); + } + + @Override + public void forEach(final BiConsumer action) { + store.forEach(action); + + delegate.forEach(action); + } + + @Override + public void forEachKey(final Consumer action) { + store.forEachKey(action); + + delegate.forEachKey(action); + } + + @Override + public void forEachValue(final Consumer action) { + store.forEachValue(action); + + delegate.forEachValue(action); + } + + @Override + public ValueType get(final KeyType key) { + if(store.containsKey(key)) return store.get(key); + + return delegate.get(key); + } + + @Override + public int size() { + return store.size() + delegate.size(); + } + + @Override + public IList keyList() { + IList ilst = new FunctionalList<>(); + + ilst.addAll(store.keyList()); + ilst.addAll(delegate.keyList()); + + return ilst; + } + + @Override + public IMap transform(final Function transformer) { + return new TransformedValueMap<>(this, transformer); + } + + @Override + public ValueType put(final KeyType key, final ValueType val) { + return store.put(key, val); + } + + @Override + public ValueType remove(final KeyType key) { + if(!store.containsKey(key)) return delegate.remove(key); + + return store.remove(key); + } + + @Override + public IList valueList() { + IList ilst = new FunctionalList<>(); + + ilst.addAll(store.valueList()); + ilst.addAll(delegate.valueList()); + + return ilst; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + (delegate == null ? 0 : delegate.hashCode()); + result = prime * result + (store == null ? 0 : store.hashCode()); + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof ExtendedMap)) return false; + + final ExtendedMap other = (ExtendedMap) obj; + + if(delegate == null) { + if(other.delegate != null) return false; + } else if(!delegate.equals(other.delegate)) return false; + if(store == null) { + if(other.store != null) return false; + } else if(!store.equals(other.store)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("ExtendedMap [delegate=%s, store=%s]", delegate, store); + } +} diff --git a/src/main/java/bjc/funcdata/FunctionalList.java b/src/main/java/bjc/funcdata/FunctionalList.java new file mode 100644 index 0000000..99b36fe --- /dev/null +++ b/src/main/java/bjc/funcdata/FunctionalList.java @@ -0,0 +1,465 @@ +package bjc.funcdata; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.function.BiConsumer; +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; + +import bjc.data.IHolder; +import bjc.data.IPair; +import bjc.data.Identity; +import bjc.data.Pair; + +/** + * A wrapper over another list that provides eager functional operations over + * it. + * + * Differs from a stream in every way except for the fact that they both provide + * functional operations. + * + * @author ben + * + * @param + * The type in this list + */ +public class FunctionalList implements Cloneable, IList { + /* The list used as a backing store */ + private final List wrapped; + + /** Create a new empty functional list. */ + public FunctionalList() { + wrapped = new ArrayList<>(); + } + + /** + * Create a new functional list containing the specified items. + * + * Takes O(n) time, where n is the number of items specified + * + * @param items + * The items to put into this functional list. + */ + @SafeVarargs + public FunctionalList(final E... items) { + wrapped = new ArrayList<>(items.length); + + for(final E item : items) { + wrapped.add(item); + } + } + + /** + * Create a new functional list containing the specified items. + * + * Takes O(n) time, where n is the number of items specified + * + * @param items + * The items to put into this functional list. + * @return The returned list. + */ + @SafeVarargs + public static IList listOf(final T... items) { + return new FunctionalList<>(items); + } + /** + * Create a new functional list with the specified size. + * + * @param size + * The size of the backing list . + */ + private FunctionalList(final int size) { + wrapped = new ArrayList<>(size); + } + + /** + * Create a new functional list as a wrapper of a existing list. + * + * Takes O(1) time, since it doesn't copy the list. + * + * @param backing + * The list to use as a backing list. + */ + public FunctionalList(final List backing) { + if(backing == null) throw new NullPointerException("Backing list must be non-null"); + + wrapped = backing; + } + + @Override + public boolean add(final E item) { + return wrapped.add(item); + } + + @Override + public boolean allMatch(final Predicate predicate) { + if(predicate == null) throw new NullPointerException("Predicate must be non-null"); + + for(final E item : wrapped) { + if(!predicate.test(item)) + /* We've found a non-matching item. */ + return false; + } + + /* All of the items matched. */ + return true; + } + + @Override + public boolean anyMatch(final Predicate predicate) { + if(predicate == null) throw new NullPointerException("Predicate must be not null"); + + for(final E item : wrapped) { + if(predicate.test(item)) + /* We've found a matching item. */ + return true; + } + + /* We didn't find a matching item. */ + return false; + } + + /** + * Clone this list into a new one, and clone the backing list as well. + * + * Takes O(n) time, where n is the number of elements in the list. + * + * @return A copy of the list. + */ + @Override + public IList clone() { + final IList cloned = new FunctionalList<>(); + + for(final E element : wrapped) { + cloned.add(element); + } + + return cloned; + } + + @Override + public IList combineWith(final IList rightList, final BiFunction itemCombiner) { + if(rightList == null) { + throw new NullPointerException("Target combine list must not be null"); + } else if(itemCombiner == null) { + throw new NullPointerException("Combiner must not be null"); + } + + final IList returned = new FunctionalList<>(); + + /* Get the iterator for the other list. */ + final Iterator rightIterator = rightList.toIterable().iterator(); + + for(final Iterator leftIterator = wrapped.iterator(); leftIterator.hasNext() + && rightIterator.hasNext();) { + /* Add the transformed items to the result list. */ + final E leftVal = leftIterator.next(); + final T rightVal = rightIterator.next(); + + returned.add(itemCombiner.apply(leftVal, rightVal)); + } + + return returned; + } + + @Override + public boolean contains(final E item) { + /* Check if any items in the list match the provided item. */ + return this.anyMatch(item::equals); + } + + @Override + public E first() { + if(wrapped.size() < 1) throw new NoSuchElementException("Attempted to get first element of empty list"); + + return wrapped.get(0); + } + + @Override + public E last() { + if(wrapped.size() < 1) throw new NoSuchElementException("Attempted to get last element of empty list"); + + return wrapped.get(wrapped.size() - 1); + } + + @Override + public E popFirst() { + if(wrapped.size() < 1) throw new NoSuchElementException("Attempted to pop first element of empty list"); + + E head = first(); + wrapped.remove(0); + + return head; + } + + @Override + public E popLast() { + if(wrapped.size() < 1) throw new NoSuchElementException("Attempted to pop last element of empty list"); + + E tail = last(); + wrapped.remove(wrapped.size() - 1); + + return tail; + } + + @Override + public IList flatMap(final Function> expander) { + if(expander == null) throw new NullPointerException("Expander must not be null"); + + final IList returned = new FunctionalList<>(this.wrapped.size()); + + forEach(element -> { + final IList expandedElement = expander.apply(element); + + if(expandedElement == null) throw new NullPointerException("Expander returned null list"); + + /* Add each element to the returned list. */ + expandedElement.forEach(returned::add); + }); + + return returned; + } + + @Override + public void forEach(final Consumer action) { + if(action == null) throw new NullPointerException("Action is null"); + + wrapped.forEach(action); + } + + @Override + public void forEachIndexed(final BiConsumer indexedAction) { + if(indexedAction == null) throw new NullPointerException("Action must not be null"); + + /* + * This is held b/c ref'd variables must be final/effectively + * final. + */ + final IHolder currentIndex = new Identity<>(0); + + wrapped.forEach((element) -> { + /* Call the action with the index and the value. */ + indexedAction.accept(currentIndex.unwrap(index -> index), element); + + /* Increment the value. */ + currentIndex.transform((index) -> index + 1); + }); + } + + @Override + public E getByIndex(final int index) { + return wrapped.get(index); + } + + /** + * Get the internal backing list. + * + * @return The backing list this list is based off of. + */ + public List getInternal() { + return wrapped; + } + + @Override + public IList getMatching(final Predicate predicate) { + if(predicate == null) throw new NullPointerException("Predicate must not be null"); + + final IList returned = new FunctionalList<>(); + + wrapped.forEach((element) -> { + if(predicate.test(element)) { + /* + * The item matches, so add it to the returned + * list. + */ + returned.add(element); + } + }); + + return returned; + } + + @Override + public int getSize() { + return wrapped.size(); + } + + @Override + public boolean isEmpty() { + return wrapped.isEmpty(); + } + + /* Check if a partition has room for another item. */ + private Boolean isPartitionFull(final int numberPerPartition, final IHolder> currentPartition) { + return currentPartition.unwrap((partition) -> partition.getSize() >= numberPerPartition); + } + + @Override + public IList map(final Function elementTransformer) { + if(elementTransformer == null) throw new NullPointerException("Transformer must be not null"); + + final IList returned = new FunctionalList<>(this.wrapped.size()); + + forEach(element -> { + // Add the transformed item to the result + returned.add(elementTransformer.apply(element)); + }); + + return returned; + } + + @Override + public IList> pairWith(final IList rightList) { + return combineWith(rightList, Pair::new); + } + + @Override + public IList> partition(final int numberPerPartition) { + if(numberPerPartition < 1 || numberPerPartition > wrapped.size()) { + final String fmt = "%s is an invalid partition size. Must be between 1 and %d"; + final String msg = String.format(fmt, numberPerPartition, wrapped.size()); + + throw new IllegalArgumentException(msg); + } + + final IList> returned = new FunctionalList<>(); + + /* The current partition being filled. */ + final IHolder> currentPartition = new Identity<>(new FunctionalList<>()); + + this.forEach(element -> { + if(isPartitionFull(numberPerPartition, currentPartition)) { + /* Add the partition to the list. */ + returned.add(currentPartition.unwrap(partition -> partition)); + + /* Start a new partition. */ + currentPartition.transform(partition -> new FunctionalList<>()); + } else { + /* Add the element to the current partition. */ + currentPartition.unwrap(partition -> partition.add(element)); + } + }); + + return returned; + } + + @Override + public void prepend(final E item) { + wrapped.add(0, item); + } + + @Override + public E randItem(final Function rnd) { + if(rnd == null) throw new NullPointerException("Random source must not be null"); + + final int randomIndex = rnd.apply(wrapped.size()); + + return wrapped.get(randomIndex); + } + + @Override + public F reduceAux(final T initialValue, final BiFunction stateAccumulator, + final Function resultTransformer) { + if(stateAccumulator == null) { + throw new NullPointerException("Accumulator must not be null"); + } else if(resultTransformer == null) { + throw new NullPointerException("Transformer must not be null"); + } + + /* The current collapsed list. */ + final IHolder currentState = new Identity<>(initialValue); + + wrapped.forEach(element -> { + /* Accumulate a new value into the state. */ + currentState.transform(state -> stateAccumulator.apply(element, state)); + }); + + /* Convert the state to its final value. */ + return currentState.unwrap(resultTransformer); + } + + @Override + public boolean removeIf(final Predicate removePredicate) { + if(removePredicate == null) throw new NullPointerException("Predicate must be non-null"); + + return wrapped.removeIf(removePredicate); + } + + @Override + public void removeMatching(final E desiredElement) { + removeIf(element -> element.equals(desiredElement)); + } + + @Override + public void reverse() { + Collections.reverse(wrapped); + } + + @Override + public E search(final E searchKey, final Comparator comparator) { + /* Search our internal list. */ + final int foundIndex = Collections.binarySearch(wrapped, searchKey, comparator); + + if(foundIndex >= 0) { + /* We found a matching element. */ + return wrapped.get(foundIndex); + } + + /* We didn't find an element. */ + return null; + } + + @Override + public void sort(final Comparator comparator) { + Collections.sort(wrapped, comparator); + } + + @Override + public IList tail() { + return new FunctionalList<>(wrapped.subList(1, getSize())); + } + + @Override + public E[] toArray(final E[] arrType) { + return wrapped.toArray(arrType); + } + + @Override + public Iterable toIterable() { + return wrapped; + } + + @Override + public String toString() { + final int lSize = getSize(); + + if(lSize == 0) return "()"; + + final StringBuilder sb = new StringBuilder("("); + final Iterator itr = toIterable().iterator(); + final E itm = itr.next(); + int i = 0; + + if(lSize == 1) return "(" + itm + ")"; + + for(final E item : toIterable()) { + sb.append(item.toString()); + + if(i < lSize - 1) { + sb.append(", "); + } + + i += 1; + } + + sb.append(")"); + + return sb.toString(); + } +} diff --git a/src/main/java/bjc/funcdata/FunctionalMap.java b/src/main/java/bjc/funcdata/FunctionalMap.java new file mode 100644 index 0000000..fc53829 --- /dev/null +++ b/src/main/java/bjc/funcdata/FunctionalMap.java @@ -0,0 +1,175 @@ +package bjc.funcdata; + +import java.util.HashMap; +import java.util.Map; +import java.util.function.BiConsumer; +import java.util.function.Consumer; +import java.util.function.Function; + +import bjc.data.IPair; + +/** + * Basic implementation of {@link IMap} + * + * @author ben + * + * @param + * The type of the map's keys. + * + * @param + * The type of the map's values. + */ +public class FunctionalMap implements IMap { + /* Our backing store. */ + private Map wrappedMap; + + /** Create a new blank functional map */ + public FunctionalMap() { + wrappedMap = new HashMap<>(); + } + + /** + * Create a new functional map with the specified entries. + * + * @param entries + * The entries to put into the map. + */ + @SafeVarargs + public FunctionalMap(final IPair... entries) { + this(); + + for(final IPair entry : entries) { + entry.doWith((key, val) -> { + wrappedMap.put(key, val); + }); + } + } + + /** + * Create a new functional map wrapping the specified map. + * + * @param wrap + * The map to wrap. + */ + public FunctionalMap(final Map wrap) { + if(wrap == null) throw new NullPointerException("Map to wrap must not be null"); + + wrappedMap = wrap; + } + + @Override + public void clear() { + wrappedMap.clear(); + } + + @Override + public boolean containsKey(final KeyType key) { + return wrappedMap.containsKey(key); + } + + @Override + public IMap extend() { + return new ExtendedMap<>(this, new FunctionalMap<>()); + } + + @Override + public void forEach(final BiConsumer action) { + wrappedMap.forEach(action); + } + + @Override + public void forEachKey(final Consumer action) { + wrappedMap.keySet().forEach(action); + } + + @Override + public void forEachValue(final Consumer action) { + wrappedMap.values().forEach(action); + } + + @Override + public ValueType get(final KeyType key) { + if(key == null) throw new NullPointerException("Key must not be null"); + + if(!wrappedMap.containsKey(key)) { + final String msg = String.format("Key %s is not present in the map", key); + + throw new IllegalArgumentException(msg); + } + + return wrappedMap.get(key); + } + + @Override + public int size() { + return wrappedMap.size(); + } + + @Override + public IList keyList() { + final FunctionalList keys = new FunctionalList<>(); + + wrappedMap.keySet().forEach(key -> { + keys.add(key); + }); + + return keys; + } + + @Override + public IMap transform(final Function transformer) { + if(transformer == null) throw new NullPointerException("Transformer must not be null"); + + return new TransformedValueMap<>(this, transformer); + } + + @Override + public ValueType put(final KeyType key, final ValueType val) { + if(key == null) throw new NullPointerException("Key must not be null"); + + return wrappedMap.put(key, val); + } + + @Override + public ValueType remove(final KeyType key) { + return wrappedMap.remove(key); + } + + @Override + public String toString() { + return wrappedMap.toString(); + } + + @Override + public IList valueList() { + final FunctionalList values = new FunctionalList<>(); + + wrappedMap.values().forEach(value -> { + values.add(value); + }); + + return values; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + (wrappedMap == null ? 0 : wrappedMap.hashCode()); + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof FunctionalMap)) return false; + + final FunctionalMap other = (FunctionalMap) obj; + + if(wrappedMap == null) { + if(other.wrappedMap != null) return false; + } else if(!wrappedMap.equals(other.wrappedMap)) return false; + return true; + } +} diff --git a/src/main/java/bjc/funcdata/FunctionalStringTokenizer.java b/src/main/java/bjc/funcdata/FunctionalStringTokenizer.java new file mode 100644 index 0000000..7b7c2f2 --- /dev/null +++ b/src/main/java/bjc/funcdata/FunctionalStringTokenizer.java @@ -0,0 +1,162 @@ +package bjc.funcdata; + +import java.util.StringTokenizer; +import java.util.function.Consumer; +import java.util.function.Function; + +/** + * A string tokenizer that exposes a functional interface. + * + * @author ben + */ +public class FunctionalStringTokenizer { + /** + * Create a new tokenizer from the specified string. + * + * @param strang + * The string to create a tokenizer from. + * + * @return A new tokenizer that splits the provided string on spaces. + */ + public static FunctionalStringTokenizer fromString(final String strang) { + if(strang == null) throw new NullPointerException("String to tokenize must be non-null"); + + return new FunctionalStringTokenizer(new StringTokenizer(strang, " ")); + } + + /* The string tokenizer being driven */ + private final StringTokenizer input; + + /** + * Create a functional string tokenizer from a given string. + * + * @param inp + * The string to tokenize. + */ + public FunctionalStringTokenizer(final String inp) { + if(inp == null) throw new NullPointerException("String to tokenize must be non-null"); + + this.input = new StringTokenizer(inp); + } + + /** + * Create a functional string tokenizer from a given string and set of + * separators. + * + * @param input + * The string to tokenize. + * + * @param seperators + * The set of separating tokens to use for splitting. + */ + public FunctionalStringTokenizer(final String input, final String seperators) { + if(input == null) { + throw new NullPointerException("String to tokenize must not be null"); + } else if(seperators == null) { + throw new NullPointerException("Tokens to split on must not be null"); + } + + this.input = new StringTokenizer(input, seperators); + } + + /** + * Create a functional string tokenizer from a non-functional one. + * + * @param toWrap + * The non-functional string tokenizer to wrap. + */ + public FunctionalStringTokenizer(final StringTokenizer toWrap) { + if(toWrap == null) throw new NullPointerException("Wrapped tokenizer must not be null"); + + this.input = toWrap; + } + + /** + * Execute a provided action for each of the remaining tokens. + * + * @param action + * The action to execute for each token. + */ + public void forEachToken(final Consumer action) { + if(action == null) throw new NullPointerException("Action must not be null"); + + while(input.hasMoreTokens()) { + action.accept(input.nextToken()); + } + } + + /** + * Get the string tokenizer encapsulated by this tokenizer. + * + * @return The encapsulated tokenizer. + */ + public StringTokenizer getInternal() { + return input; + } + + /** + * Check if this tokenizer has more tokens. + * + * @return Whether or not this tokenizer has more tokens. + */ + public boolean hasMoreTokens() { + return input.hasMoreTokens(); + } + + /** + * Return the next token from the tokenizer. + * + * @return The next token from the tokenizer, or null if no more tokens + * are available. + */ + public String nextToken() { + if(input.hasMoreTokens()) { + /* Return the next available token. */ + return input.nextToken(); + } + + /* Return no token. */ + return null; + } + + /** + * Convert this tokenizer into a list of strings. + * + * @return This tokenizer, converted into a list of strings. + */ + public IList toList() { + return toList((final String element) -> element); + } + + /** + * Convert the contents of this tokenizer into a list. Consumes all of + * the input from this tokenizer. + * + * @param + * The type of the converted tokens. + * + * @param transformer + * The function to use to convert tokens. + * + * @return A list containing all of the converted tokens. + */ + public IList toList(final Function transformer) { + if(transformer == null) throw new NullPointerException("Transformer must not be null"); + + final IList returned = new FunctionalList<>(); + + /* Add each token to the list after transforming it. */ + forEachToken(token -> { + final E transformedToken = transformer.apply(token); + + returned.add(transformedToken); + }); + + return returned; + } + + @Override + public String toString() { + return String.format("FunctionalStringTokenizer [input=%s]", input); + } +} diff --git a/src/main/java/bjc/funcdata/IList.java b/src/main/java/bjc/funcdata/IList.java new file mode 100644 index 0000000..38356e2 --- /dev/null +++ b/src/main/java/bjc/funcdata/IList.java @@ -0,0 +1,463 @@ +package bjc.funcdata; + +import java.util.Comparator; +import java.util.Iterator; +import java.util.function.BiConsumer; +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.stream.Collector; + +import bjc.data.IPair; +import bjc.functypes.ID; + +/** + * A wrapper over another list that provides functional operations over it. + * + * @author ben + * + * @param + * The type in this list + */ +public interface IList extends Iterable { + /** + * Add an item to this list. + * + * @param item + * The item to add to this list. + * + * @return Whether the item was added to the list successfully.. + */ + boolean add(ContainedType item); + + /** + * Add all of the elements in the provided list to this list. + * + * @param items + * The list of items to add. + * + * @return True if every item was successfully added to the list, false + * otherwise. + */ + default boolean addAll(final IList items) { + return items.map(this::add).anyMatch(bl -> bl == false); + } + + /** + * Add all of the elements in the provided array to this list. + * + * @param items + * The array of items to add. + * + * @return True if every item was successfully added to the list, false + * otherwise. + */ + @SuppressWarnings("unchecked") + default boolean addAll(final ContainedType... items) { + boolean succ = true; + + for (final ContainedType item : items) { + final boolean addSucc = add(item); + + succ = succ ? addSucc : false; + } + + return succ; + } + + /** + * Check if all of the elements of this list match the specified + * predicate. + * + * @param matcher + * The predicate to use for checking. + * + * @return Whether all of the elements of the list match the specified + * predicate. + */ + boolean allMatch(Predicate matcher); + + /** + * Check if any of the elements in this list match the specified list. + * + * @param matcher + * The predicate to use for checking. + * + * @return Whether any element in the list matches the provided + * predicate. + */ + boolean anyMatch(Predicate matcher); + + /** + * Reduce the contents of this list using a collector. + * + * @param + * The intermediate accumulation type. + * + * @param + * The final, reduced type. + * + * @param collector + * The collector to use for reduction. + * + * @return The reduced list. + */ + default ReducedType collect( + final Collector collector) { + final BiConsumer accumulator = collector.accumulator(); + + final StateType initial = collector.supplier().get(); + return reduceAux(initial, (value, state) -> { + accumulator.accept(state, value); + + return state; + }, collector.finisher()); + } + + /** + * Combine this list with another one into a new list and merge the + * results. + * + * Works sort of like a combined zip/map over resulting pairs. Does not + * change the underlying list. + * + * NOTE: The returned list will have the length of the shorter of this + * list and the combined one. + * + * @param + * The type of the second list. + * + * @param + * The type of the combined list. + * + * @param list + * The list to combine with. + * + * @param combiner + * The function to use for combining element pairs. + * + * @return A new list containing the merged pairs of lists. + */ + IList combineWith(IList list, + BiFunction combiner); + + /** + * Check if the list contains the specified item. + * + * @param item + * The item to see if it is contained. + * + * @return Whether or not the specified item is in the list. + */ + boolean contains(ContainedType item); + + /** + * Get the first element in the list. + * + * @return The first element in this list. + */ + ContainedType first(); + + /** + * Get the last element in the list. + * + * @return The last element in this list. + */ + ContainedType last(); + + /** + * Remove and return the first element from the list. + * + * @return The first element from the list. + */ + ContainedType popFirst(); + + /** + * Remove and return the last element from the list. + * + * @return The last element from the list. + */ + ContainedType popLast(); + + /** + * Apply a function to each member of the list, then flatten the + * results. + * + * Does not change the underlying list. + * + * @param + * The type of the flattened list. + * + * @param expander + * The function to apply to each member of the list. + * + * @return A new list containing the flattened results of applying the + * provided function. + */ + IList flatMap(Function> expander); + + /** + * Apply a given action for each member of the list. + * + * @param action + * The action to apply to each member of the list. + */ + @Override + void forEach(Consumer action); + + /** + * Apply a given function to each element in the list and its index. + * + * @param action + * The function to apply to each element in the list and + * its index. + */ + void forEachIndexed(BiConsumer action); + + /** + * Retrieve a value in the list by its index. + * + * @param index + * The index to retrieve a value from. + * + * @return The value at the specified index in the list. + */ + ContainedType getByIndex(int index); + + /** + * Retrieve a list containing all elements matching a predicate. + * + * @param predicate + * The predicate to match by. + * + * @return A list containing all elements that match the predicate. + */ + IList getMatching(Predicate predicate); + + /** + * Retrieve the size of the wrapped list. + * + * @return The size of the wrapped list. + */ + int getSize(); + + /** + * Check if this list is empty. + * + * @return Whether or not this list is empty. + */ + boolean isEmpty(); + + /** + * Create a new list by applying the given function to each element in + * the list. + * + * Does not change the underlying list. + * + * @param + * The type of the transformed list. + * + * @param transformer + * The function to apply to each element in the list. + * + * @return A new list containing the mapped elements of this list. + */ + IList map(Function transformer); + + /** + * Zip two lists into a list of pairs. + * + * @param + * The type of the second list. + * + * @param list + * The list to use as the left side of the pair. + * + * @return A list containing pairs of this element and the specified + * list. + */ + IList> pairWith(IList list); + + /** + * Partition this list into a list of sublists. + * + * @param partitionSize + * The size of elements to put into each one of the + * sublists. + * + * @return A list partitioned into partitions of size partitionSize. The + * last partition may not be completely full if the size of the + * list is not a multiple of partitionSize. + */ + IList> partition(int partitionSize); + + /** + * Prepend an item to the list. + * + * @param item + * The item to prepend to the list. + */ + void prepend(ContainedType item); + + /** + * Prepend an array of items to the list. + * + * @param items + * The items to prepend to the list. + */ + @SuppressWarnings("unchecked") + default void prependAll(final ContainedType... items) { + for (final ContainedType item : items) { + prepend(item); + } + } + + /** + * Select a random item from the list, using a default random number + * generator. + * + * @return A random item from the list + */ + default ContainedType randItem() { + return randItem(num -> (int) (Math.random() * num)); + } + + /** + * Select a random item from this list, using the provided random number + * generator. + * + * @param rnd + * The random number generator to use. + * + * @return A random element from this list. + */ + ContainedType randItem(Function rnd); + + /** + * Reduce this list to a single value, using a accumulative approach. + * + * @param + * The in-between type of the values + * + * @param + * The final value type + * + * @param initial + * The initial value of the accumulative state. + * + * @param accumulator + * The function to use to combine a list element with the + * accumulative state. + * + * @param transformer + * The function to use to convert the accumulative state + * into a final result. + * + * @return A single value condensed from this list and transformed into + * its final state. + */ + ReducedType reduceAux(StateType initial, + BiFunction accumulator, + Function transformer); + + /** + * Reduce this list to a single value, using a accumulative approach. + * + * @param + * The in-between type of the values. + * + * @param initial + * The initial value of the accumulative state. + * + * @param accumulator + * The function to use to combine a list element with the + * accumulative state. + * + * @return A single value condensed from this list. + */ + default StateType reduceAux(StateType initial, + BiFunction accumulator) { + return reduceAux(initial, accumulator, ID.id()); + } + + /** + * Remove all elements that match a given predicate. + * + * @param predicate + * The predicate to use to determine elements to delete. + * + * @return Whether there was anything that satisfied the predicate. + */ + boolean removeIf(Predicate predicate); + + /** + * Remove all parameters that match a given parameter. + * + * @param element + * The object to remove all matching copies of. + */ + void removeMatching(ContainedType element); + + /** Reverse the contents of this list in place. */ + void reverse(); + + /** + * Perform a binary search for the specified key using the provided + * means of comparing elements. + * + * Since this IS a binary search, the list must have been sorted before + * hand. + * + * @param key + * The key to search for. + * + * @param comparator + * The way to compare elements for searching. Pass null + * to use the natural ordering for E. + * + * @return The element if it is in this list, or null if it is not. + */ + ContainedType search(ContainedType key, Comparator comparator); + + /** + * Sort the elements of this list using the provided way of comparing + * elements. + * + * Does change the underlying list. + * + * @param comparator + * The way to compare elements for sorting. Pass null to + * use E's natural ordering + */ + void sort(Comparator comparator); + + /** + * Get the tail of this list (the list without the first element). + * + * @return The list without the first element. + */ + IList tail(); + + /** + * Convert this list into an array. + * + * @param type + * The type of array to return. + * + * @return The list, as an array. + */ + ContainedType[] toArray(ContainedType[] type); + + /** + * Convert the list into a Iterable. + * + * @return An iterable view onto the list. + */ + Iterable toIterable(); + + @Override + default Iterator iterator() { + return toIterable().iterator(); + } +} diff --git a/src/main/java/bjc/funcdata/IMap.java b/src/main/java/bjc/funcdata/IMap.java new file mode 100644 index 0000000..ba56578 --- /dev/null +++ b/src/main/java/bjc/funcdata/IMap.java @@ -0,0 +1,190 @@ +package bjc.funcdata; + +import java.util.function.BiConsumer; +import java.util.function.Consumer; +import java.util.function.Function; + +/** + * Functional wrapper over map providing some useful things. + * + * @author ben + * + * @param + * The type of this map's keys. + * + * @param + * The type of this map's values. + */ +public interface IMap { + /** + * Execute an action for each entry in the map. + * + * @param action + * The action to execute for each entry in the map. + */ + void forEach(BiConsumer action); + + /** + * Perform an action for each key in the map. + * + * @param action + * The action to perform on each key in the map. + */ + default void forEachKey(final Consumer action) { + forEach((key, val) -> action.accept(key)); + } + + /** + * Perform an action for each value in the map. + * + * @param action + * The action to perform on each value in the map. + */ + default void forEachValue(final Consumer action) { + forEach((key, val) -> action.accept(val)); + } + + /** + * Check if this map contains the specified key. + * + * @param key + * The key to check. + * + * @return Whether or not the map contains the key. + */ + boolean containsKey(KeyType key); + + /** + * Get the value assigned to the given key. + * + * @param key + * The key to look for a value under. + * + * @return The value of the key. + */ + ValueType get(KeyType key); + + /** + * Get a value from the map, and return a default value if the key + * doesn't exist. + * + * @param key + * The key to attempt to retrieve. + * + * @param defaultValue + * The value to return if the key doesn't exist. + * + * @return The value associated with the key, or the default value if + * the key doesn't exist. + */ + default ValueType getOrDefault(final KeyType key, final ValueType defaultValue) { + try { + return get(key); + } catch(final IllegalArgumentException iaex) { + /* + * We don't care about this, because it indicates a key + * is missing. + */ + return defaultValue; + } + } + + /** + * Add an entry to the map. + * + * @param key + * The key to put the value under. + * + * @param val + * The value to add. + * + * @return The previous value of the key in the map, or null if the key + * wasn't in the map. However, note that it may also return null + * if the key was set to null. + * + * @throws UnsupportedOperationException + * If the map implementation doesn't support modifying the map. + */ + ValueType put(KeyType key, ValueType val); + + /** Delete all the values in the map. */ + default void clear() { + keyList().forEach(key -> remove(key)); + } + + /** + * Get the number of entries in this map. + * + * @return The number of entries in this map. + */ + default int size() { + return keyList().getSize(); + } + + /* + * @NOTE Do we want this to be the semantics for transform, or do we + * want to go to semantics using something like Isomorphism, or doing a + * one-time bulk conversion of the values? + */ + /** + * Transform the values returned by this map. + * + * NOTE: This transform is applied once for each lookup of a value, so + * the transform passed should be a proper function, or things will + * likely not work as expected. + * + * @param + * The new type of returned values. + * + * @param transformer + * The function to use to transform values. + * + * @return The map where each value will be transformed after lookup. + */ + default IMap transform(final Function transformer) { + return new TransformedValueMap<>(this, transformer); + } + + /** + * Extends this map, creating a new map that will delegate queries to + * the map, but store any added values itself. + * + * @return An extended map. + */ + IMap extend(); + + /** + * Remove the value bound to the key. + * + * @param key + * The key to remove from the map. + * + * @return The previous value for the key in the map, or null if the key + * wasn't in the class. NOTE: Just because you received null, + * doesn't mean the map wasn't changed. It may mean that someone + * put a null value for that key into the map. + */ + ValueType remove(KeyType key); + + /** + * Get a list of all the keys in this map. + * + * @return A list of all the keys in this map. + */ + IList keyList(); + + /** + * Get a list of the values in this map. + * + * @return A list of values in this map. + */ + default IList valueList() { + final IList returns = new FunctionalList<>(); + + for(final KeyType key : keyList()) { + returns.add(get(key)); + } + + return returns; + } +} diff --git a/src/main/java/bjc/funcdata/SentryList.java b/src/main/java/bjc/funcdata/SentryList.java new file mode 100644 index 0000000..8a56675 --- /dev/null +++ b/src/main/java/bjc/funcdata/SentryList.java @@ -0,0 +1,39 @@ +package bjc.funcdata; + +import java.util.List; + +/** + * A list that logs when items are inserted into it. + * + * @author bjculkin + * + * @param + * The type of item in the list. + */ +public class SentryList extends FunctionalList { + /** Create a new sentry list. */ + public SentryList() { + super(); + } + + /** + * Create a new sentry list backed by an existing list. + * + * @param backing + * The backing list. + */ + public SentryList(final List backing) { + super(backing); + } + + @Override + public boolean add(final T item) { + final boolean val = super.add(item); + + if(val) { + System.out.println("Added item (" + item + ") to list"); + } + + return val; + } +} diff --git a/src/main/java/bjc/funcdata/TransformedValueMap.java b/src/main/java/bjc/funcdata/TransformedValueMap.java new file mode 100644 index 0000000..0f0b3b5 --- /dev/null +++ b/src/main/java/bjc/funcdata/TransformedValueMap.java @@ -0,0 +1,116 @@ +package bjc.funcdata; + +import java.util.function.BiConsumer; +import java.util.function.Consumer; +import java.util.function.Function; + +/** + * A map that transforms values from one type to another + * + * @author ben + * + * @param + * The type of the map's keys + * + * @param + * The type of the map's values + * + * @param + * The type of the transformed values + * + */ +final class TransformedValueMap implements IMap { + /* Our backing map. */ + private final IMap backing; + /* Our transforming function. */ + private final Function transformer; + + /** + * Create a new transformed-value loop. + * + * @param backingMap + * The map to use as backing. + * + * @param transform + * The function to use for the transform. + */ + public TransformedValueMap(final IMap backingMap, + final Function transform) { + backing = backingMap; + transformer = transform; + } + + @Override + public void clear() { + backing.clear(); + } + + @Override + public boolean containsKey(final OldKey key) { + return backing.containsKey(key); + } + + @Override + public IMap extend() { + return new ExtendedMap<>(this, new FunctionalMap<>()); + } + + @Override + public void forEach(final BiConsumer action) { + backing.forEach((key, value) -> { + action.accept(key, transformer.apply(value)); + }); + } + + @Override + public void forEachKey(final Consumer action) { + backing.forEachKey(action); + } + + @Override + public void forEachValue(final Consumer action) { + backing.forEachValue(value -> { + action.accept(transformer.apply(value)); + }); + } + + @Override + public NewValue get(final OldKey key) { + return transformer.apply(backing.get(key)); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public IList keyList() { + return backing.keyList(); + } + + @Override + public IMap transform(final Function transform) { + return new TransformedValueMap<>(this, transform); + } + + @Override + public NewValue put(final OldKey key, final NewValue value) { + throw new UnsupportedOperationException("Can't add items to transformed map"); + } + + @Override + public NewValue remove(final OldKey key) { + return transformer.apply(backing.remove(key)); + } + + @Override + public String toString() { + return backing.toString(); + } + + @Override + public IList valueList() { + return backing.valueList().map(transformer); + } +} 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 + * The data type stored in the node. + */ +public class BinarySearchTree { + /* The comparator for use in ordering items */ + private final Comparator comparator; + + /* The current count of elements in the tree */ + private int elementCount; + + /* The root element of the tree */ + private ITreePart 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 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 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 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 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 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 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 + * The data stored in the tree. + */ +public class BinarySearchTreeLeaf implements ITreePart { + /** 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 comparator) { + throw new IllegalArgumentException("Can't add to a leaf."); + } + + @Override + public E collapse(final Function leafTransformer, final BiFunction 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 comparator) { + return this.data.equals(element); + } + + @Override + public T data() { + return data; + } + + @Override + public void delete(final T element, final Comparator comparator) { + if(data.equals(element)) { + isDeleted = true; + } + } + + @Override + public boolean directedWalk(final DirectedWalkFunction 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 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 + * The data type stored in the tree. + */ +public class BinarySearchTreeNode extends BinarySearchTreeLeaf { + /* The left child of this node */ + private ITreePart left; + + /* The right child of this node */ + private ITreePart 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 lft, final ITreePart rght) { + super(element); + this.left = lft; + this.right = rght; + } + + @Override + public void add(final T element, final Comparator 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 collapse(final Function nodeCollapser, final BiFunction 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 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 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 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 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 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 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 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 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 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 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 + * The type of element stored in the walked tree + */ +@FunctionalInterface +public interface DirectedWalkFunction { + /** + * 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 + * The data contained in this part of the tree. + */ +public interface ITreePart { + /** + * 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 comparator); + + /** + * Collapses this tree part into a single value. + * + * Does not change the underlying tree. + * + * @param + * 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 collapse(Function nodeCollapser, BiFunction 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 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 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 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 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 +} diff --git a/src/main/java/bjc/funcdata/theory/Bifunctor.java b/src/main/java/bjc/funcdata/theory/Bifunctor.java new file mode 100644 index 0000000..b576a2b --- /dev/null +++ b/src/main/java/bjc/funcdata/theory/Bifunctor.java @@ -0,0 +1,176 @@ +package bjc.funcdata.theory; + +import java.util.function.Function; + +/** + * A functor over a pair of heterogeneous types. + * + * @author ben + * + * @param + * The type stored on the 'left' of the pair. + * + * @param + * The type stored on the 'right' of the pair. + */ +public interface Bifunctor { + /** + * Alias for functor mapping. + * + * @author EVE + * + * @param + * The old left type. + * + * @param + * The old right type. + * + * @param + * The new left type. + * + * @param + * The new right type. + */ + public interface BifunctorMap + extends Function, Bifunctor> { + /* + * Alias + */ + } + + /** + * Alias for left functor mapping. + * + * @author EVE + * + * @param + * The old left type. + * + * @param + * The old right type. + * + * @param + * The new left type. + */ + public interface LeftBifunctorMap + extends BifunctorMap { + /* + * Alias + */ + } + + /** + * Alias for right functor mapping. + * + * @author EVE + * + * @param + * The old left type. + * + * @param + * The old right type. + * + * @param + * The new right type. + */ + public interface RightBifunctorMap + extends BifunctorMap { + /* + * Alias + */ + } + + /** + * Lift a pair of functions to a single function that maps over both + * parts of a pair. + * + * @param + * The old left type of the pair. + * + * @param + * The old right type of the pair. + * + * @param + * The new left type of the pair. + * + * @param + * The new right type of the pair. + * + * @param leftFunc + * The function that maps over the left of the pair. + * + * @param rightFunc + * The function that maps over the right of the pair. + * + * @return A function that maps over both parts of the pair. + */ + public default BifunctorMap bimap( + final Function leftFunc, final Function rightFunc) { + final BifunctorMap bimappedFunc = (argPair) -> { + final LeftBifunctorMap leftMapper = argPair.fmapLeft(leftFunc); + + final Bifunctor leftMappedFunctor = leftMapper.apply(argPair); + final RightBifunctorMap rightMapper = leftMappedFunctor + .fmapRight(rightFunc); + + return rightMapper.apply(leftMappedFunctor); + }; + + return bimappedFunc; + } + + /** + * Lift a function to operate over the left part of this pair. + * + * @param + * The old left type of the pair. + * + * @param + * The old right type of the pair. + * + * @param + * The new left type of the pair. + * + * @param func + * The function to lift to work over the left side of the pair. + * + * @return The function lifted to work over the left side of bifunctors. + */ + public LeftBifunctorMap fmapLeft( + Function func); + + /** + * Lift a function to operate over the right part of this pair. + * + * @param + * The old left type of the pair. + * + * @param + * The old right type of the pair. + * + * @param + * The new right type of the pair. + * + * @param func + * The function to lift to work over the right side of the pair. + * + * @return The function lifted to work over the right side of + * bifunctors. + */ + public RightBifunctorMap fmapRight( + Function func); + + /** + * Get the value contained on the left of this bifunctor. + * + * @return The value on the left side of this bifunctor. + */ + public LeftType getLeft(); + + /** + * Get the value contained on the right of this bifunctor. + * + * @return The value on the right of this bifunctor. + */ + public RightType getRight(); +} diff --git a/src/main/java/bjc/funcdata/theory/Functor.java b/src/main/java/bjc/funcdata/theory/Functor.java new file mode 100644 index 0000000..4192bf4 --- /dev/null +++ b/src/main/java/bjc/funcdata/theory/Functor.java @@ -0,0 +1,43 @@ +package bjc.funcdata.theory; + +import java.util.function.Function; + +/** + * Represents a container or context some sort usually, but the precise + * definition is that it represents exactly what it is defined as. + * + * @author ben + * + * @param + * The value inside the functor. + */ +public interface Functor { + /** + * Converts a normal function to operate over values in a functor.. + * + * N.B: Even though the type signature implies that you can apply the + * resulting function to any type of functor, it is only safe to call it + * on instances of the type of functor you called fmap on.. + * + * @param + * The argument of the function. + * + * @param + * The return type of the function. + * + * @param func + * The function to convert. + * + * @return The passed in function converted to work over a particular + * type of functors. + */ + public Function, Functor> fmap( + Function func); + + /** + * Retrieve the thing inside this functor. + * + * @return The thing inside this functor. + */ + public ContainedType getValue(); +} -- cgit v1.2.3