diff options
Diffstat (limited to 'src/main/java/bjc')
65 files changed, 9418 insertions, 0 deletions
diff --git a/src/main/java/bjc/data/ArrayIterator.java b/src/main/java/bjc/data/ArrayIterator.java new file mode 100644 index 0000000..7778b81 --- /dev/null +++ b/src/main/java/bjc/data/ArrayIterator.java @@ -0,0 +1,29 @@ +package bjc.data; + +import java.util.Iterator; +/** + * Represents an iterator over an array of values. + * + * @author Ben Culkin + */ +public class ArrayIterator<T> implements Iterator<T> { + private Object[] arr; + private int idx; + + public ArrayIterator(T... elms) { + arr = elms; + idx = 0; + } + + @Override + public boolean hasNext() { + return idx < arr.length; + } + + @Override + public T next() { + if (idx >= arr.length) return null; + + return (T)(arr[idx++]); + } +} diff --git a/src/main/java/bjc/data/BooleanToggle.java b/src/main/java/bjc/data/BooleanToggle.java new file mode 100644 index 0000000..209e97c --- /dev/null +++ b/src/main/java/bjc/data/BooleanToggle.java @@ -0,0 +1,77 @@ +package bjc.data; + +/** + * A simple {@link ValueToggle} that swaps between true and false. + * + * @author EVE + * + */ +public class BooleanToggle implements Toggle<Boolean> { + /* The contained value. */ + private boolean val; + + /** + * Create a new, initially false, flip-flop. + */ + public BooleanToggle() { + this(false); + } + + /** + * Create a flip-flop with the specified initial value. + * + * @param initial + * The initial value of the flip-flop. + */ + public BooleanToggle(final boolean initial) { + val = initial; + } + + @Override + public Boolean get() { + final boolean res = val; + + val = !res; + + return res; + } + + @Override + public Boolean peek() { + return val; + } + + @Override + public void set(final boolean vl) { + val = vl; + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + + result = prime * result + (val ? 1231 : 1237); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof BooleanToggle)) return false; + + final BooleanToggle other = (BooleanToggle) obj; + + if(val != other.val) return false; + + return true; + } + + @Override + public String toString() { + return String.format("BooleanToggle [val=%s]", val); + } +} diff --git a/src/main/java/bjc/data/CircularIterator.java b/src/main/java/bjc/data/CircularIterator.java new file mode 100644 index 0000000..6842b26 --- /dev/null +++ b/src/main/java/bjc/data/CircularIterator.java @@ -0,0 +1,79 @@ +package bjc.data; + +import java.util.Iterator; + +/** + * An iterator that repeats elements from a provided iterable. + * + * @author EVE + * + * @param <E> + * The type of the iterable. + */ +public class CircularIterator<E> implements Iterator<E> { + /* The iterable, and our current iterator into it. */ + private Iterable<E> source; + private Iterator<E> curr; + + /* Our current element. */ + private E curElm; + + /* + * Should we actually get new iterators, or just repeat the last + * element? + */ + private boolean doCircle; + + /** + * Create a new circular iterator. + * + * @param src + * The iterable to iterate from. + * + * @param circ + * Should we actually do circular iteration, or just + * repeat the terminal element? + */ + public CircularIterator(final Iterable<E> src, final boolean circ) { + source = src; + curr = source.iterator(); + + doCircle = circ; + } + + /** + * Create a new circular iterator that does actual circular iteration. + * + * @param src + * The iterable to iterate from. + */ + public CircularIterator(final Iterable<E> src) { + this(src, true); + } + + @Override + public boolean hasNext() { + /* We always have something. */ + return true; + } + + @Override + public E next() { + if (!curr.hasNext()) { + if (!doCircle) { + return curElm; + } + + curr = source.iterator(); + } + + curElm = curr.next(); + + return curElm; + } + + @Override + public void remove() { + curr.remove(); + } +} diff --git a/src/main/java/bjc/data/Either.java b/src/main/java/bjc/data/Either.java new file mode 100644 index 0000000..0588496 --- /dev/null +++ b/src/main/java/bjc/data/Either.java @@ -0,0 +1,191 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Function; + +/** + * Represents a pair where only one side has a value. + * + * @author ben + * + * @param <LeftType> + * The type that could be on the left. + * + * @param <RightType> + * The type that could be on the right. + * + */ +public class Either<LeftType, RightType> implements IPair<LeftType, RightType> { + /** + * Create a new either with the left value occupied. + * + * @param <LeftType> + * The type of the left value. + * + * @param <RightType> + * The type of the empty right value. + * + * @param left + * The value to put on the left. + * + * @return An either with the left side occupied. + */ + public static <LeftType, RightType> Either<LeftType, RightType> left(final LeftType left) { + return new Either<>(left, null); + } + + /** + * Create a new either with the right value occupied. + * + * @param <LeftType> + * The type of the empty left value. + * + * @param <RightType> + * The type of the right value. + * + * @param right + * The value to put on the right. + * + * @return An either with the right side occupied. + */ + public static <LeftType, RightType> Either<LeftType, RightType> right(final RightType right) { + return new Either<>(null, right); + } + + /* The left value of the either. */ + private LeftType leftVal; + /* The right value of the either. */ + private RightType rightVal; + /* Whether the left value is the one filled out. */ + private boolean isLeft; + + /* Create a new either with specifed values. */ + private Either(final LeftType left, final RightType right) { + if(left == null) { + rightVal = right; + } else { + leftVal = left; + + isLeft = true; + } + } + + @Override + public <BoundLeft, BoundRight> IPair<BoundLeft, BoundRight> bind( + final BiFunction<LeftType, RightType, IPair<BoundLeft, BoundRight>> binder) { + if(binder == null) throw new NullPointerException("Binder must not be null"); + + return binder.apply(leftVal, rightVal); + } + + @Override + public <BoundLeft> IPair<BoundLeft, RightType> bindLeft( + final Function<LeftType, IPair<BoundLeft, RightType>> leftBinder) { + if(leftBinder == null) throw new NullPointerException("Left binder must not be null"); + + if(isLeft) return leftBinder.apply(leftVal); + + return new Either<>(null, rightVal); + } + + @Override + public <BoundRight> IPair<LeftType, BoundRight> bindRight( + final Function<RightType, IPair<LeftType, BoundRight>> rightBinder) { + if(rightBinder == null) throw new NullPointerException("Right binder must not be null"); + + if(isLeft) return new Either<>(leftVal, null); + + return rightBinder.apply(rightVal); + } + + @Override + public <OtherLeft, OtherRight, CombinedLeft, CombinedRight> IPair<CombinedLeft, CombinedRight> combine( + final IPair<OtherLeft, OtherRight> otherPair, + final BiFunction<LeftType, OtherLeft, CombinedLeft> leftCombiner, + final BiFunction<RightType, OtherRight, CombinedRight> rightCombiner) { + if(otherPair == null) { + throw new NullPointerException("Other pair must not be null"); + } else if(leftCombiner == null) { + throw new NullPointerException("Left combiner must not be null"); + } else if(rightCombiner == null) { + throw new NullPointerException("Right combiner must not be null"); + } + + if(isLeft) { + return otherPair.bind((otherLeft, otherRight) -> { + CombinedLeft cLeft = leftCombiner.apply(leftVal, otherLeft); + + return new Either<>(cLeft, null); + }); + } + + return otherPair.bind((otherLeft, otherRight) -> { + CombinedRight cRight = rightCombiner.apply(rightVal, otherRight); + + return new Either<>(null, cRight); + }); + } + + @Override + public <NewLeft> IPair<NewLeft, RightType> mapLeft(final Function<LeftType, NewLeft> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + if(isLeft) return new Either<>(mapper.apply(leftVal), null); + + return new Either<>(null, rightVal); + } + + @Override + public <NewRight> IPair<LeftType, NewRight> mapRight(final Function<RightType, NewRight> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + if(isLeft) return new Either<>(leftVal, null); + + return new Either<>(null, mapper.apply(rightVal)); + } + + @Override + public <MergedType> MergedType merge(final BiFunction<LeftType, RightType, MergedType> merger) { + if(merger == null) throw new NullPointerException("Merger must not be null"); + + return merger.apply(leftVal, rightVal); + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + result = prime * result + (isLeft ? 1231 : 1237); + result = prime * result + (leftVal == null ? 0 : leftVal.hashCode()); + result = prime * result + (rightVal == null ? 0 : rightVal.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof Either<?, ?>)) return false; + + final Either<?, ?> other = (Either<?, ?>) obj; + + if(isLeft != other.isLeft) return false; + + if(leftVal == null) { + if(other.leftVal != null) return false; + } else if(!leftVal.equals(other.leftVal)) return false; + + if(rightVal == null) { + if(other.rightVal != null) return false; + } else if(!rightVal.equals(other.rightVal)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("Either [leftVal='%s', rightVal='%s', isLeft=%s]", leftVal, rightVal, isLeft); + } +} diff --git a/src/main/java/bjc/data/GeneratingIterator.java b/src/main/java/bjc/data/GeneratingIterator.java new file mode 100644 index 0000000..9adda6f --- /dev/null +++ b/src/main/java/bjc/data/GeneratingIterator.java @@ -0,0 +1,60 @@ +package bjc.data; + +import java.util.Iterator; +import java.util.function.Predicate; +import java.util.function.UnaryOperator; + +/** + * An iterator that generates a series of elements from a single element. + * + * @author bjculkin + * + * @param <E> + * The type of element generated. + */ +public class GeneratingIterator<E> implements Iterator<E> { + /* Our current state. */ + private E state; + /* The function to use to transition states. */ + private UnaryOperator<E> transtion; + /* The predicate to indicate where to stop. */ + private Predicate<E> stpper; + + /** + * Create a new generative iterator. + * + * @param initial + * The initial state of the generator. + * + * @param transition + * The function to apply to the state. + * + * @param stopper + * The predicate applied to the current state to determine when + * to stop. + */ + public GeneratingIterator(E initial, UnaryOperator<E> transition, Predicate<E> stopper) { + state = initial; + transtion = transition; + stpper = stopper; + } + + @Override + public boolean hasNext() { + return stpper.test(state); + } + + /* + * @NOTE + * + * As this currently is, it only works correctly assuming that next() is + * only called when hasNext() is true. Should we safeguard against + * people who are not doing the right thing? + */ + @Override + public E next() { + state = transtion.apply(state); + + return state; + } +} diff --git a/src/main/java/bjc/data/IHolder.java b/src/main/java/bjc/data/IHolder.java new file mode 100644 index 0000000..e56e23e --- /dev/null +++ b/src/main/java/bjc/data/IHolder.java @@ -0,0 +1,163 @@ +package bjc.data; + +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.UnaryOperator; + +import bjc.data.internals.BoundListHolder; +import bjc.data.internals.WrappedLazy; +import bjc.data.internals.WrappedOption; +import bjc.funcdata.FunctionalList; +import bjc.funcdata.theory.Functor; + +/** + * A holder of a single value. + * + * @author ben + * + * @param <ContainedType> + * The type of value held. + */ +public interface IHolder<ContainedType> extends Functor<ContainedType> { + /** + * Bind a function across the value in this container. + * + * @param <BoundType> + * The type of value in this container. + * + * @param binder + * The function to bind to the value. + * + * @return A holder from binding the value. + */ + public <BoundType> IHolder<BoundType> bind(Function<ContainedType, IHolder<BoundType>> binder); + + /** + * Apply an action to the value. + * + * @param action + * The action to apply to the value. + */ + public default void doWith(final Consumer<? super ContainedType> action) { + transform(value -> { + action.accept(value); + + return value; + }); + } + + @Override + default <ArgType, ReturnType> Function<Functor<ArgType>, Functor<ReturnType>> fmap( + final Function<ArgType, ReturnType> func) { + return argumentFunctor -> { + if(!(argumentFunctor instanceof IHolder<?>)) { + final String msg = "This functor only supports mapping over instances of IHolder"; + + throw new IllegalArgumentException(msg); + } + + final IHolder<ArgType> holder = (IHolder<ArgType>) argumentFunctor; + + return holder.map(func); + }; + } + + @Override + public default ContainedType getValue() { + return unwrap(value -> value); + } + + /** + * Lifts a function to bind over this holder. + * + * @param <NewType> + * The type of the functions return. + * + * @param func + * The function to lift over the holder. + * + * @return The function lifted over the holder. + */ + public <NewType> Function<ContainedType, IHolder<NewType>> lift(Function<ContainedType, NewType> func); + + /** + * Make this holder lazy. + * + * @return A lazy version of this holder. + */ + public default IHolder<ContainedType> makeLazy() { + return new WrappedLazy<>(this); + } + + /** + * Make this holder a list. + * + * @return A list version of this holder. + */ + public default IHolder<ContainedType> makeList() { + return new BoundListHolder<>(new FunctionalList<>(this)); + } + + /** + * Make this holder optional. + * + * @return An optional version of this holder. + */ + public default IHolder<ContainedType> makeOptional() { + return new WrappedOption<>(this); + } + + /** + * Create a new holder with a mapped version of the value in this + * holder. + * + * Does not change the internal state of this holder. + * + * @param <MappedType> + * The type of the mapped value. + * + * @param mapper + * The function to do mapping with. + * + * @return A holder with the mapped value + */ + public <MappedType> IHolder<MappedType> map(Function<ContainedType, MappedType> mapper); + + /** + * Replace the held value with a new one. + * + * @param newValue + * The value to hold instead. + * + * @return The holder itself. + */ + public default IHolder<ContainedType> replace(final ContainedType newValue) { + return transform(oldValue -> { + return newValue; + }); + } + + /** + * Transform the value held in this holder. + * + * @param transformer + * The function to transform the value with. + * + * @return The holder itself, for easy chaining. + */ + public IHolder<ContainedType> transform(UnaryOperator<ContainedType> transformer); + + /** + * Unwrap the value contained in this holder so that it is no longer + * held. + * + * @param <UnwrappedType> + * The type of the unwrapped value. + * + * @param unwrapper + * The function to use to unwrap the value. + * + * @return The unwrapped held value. + */ + public <UnwrappedType> UnwrappedType unwrap(Function<ContainedType, UnwrappedType> unwrapper); +} diff --git a/src/main/java/bjc/data/IPair.java b/src/main/java/bjc/data/IPair.java new file mode 100644 index 0000000..0c63f16 --- /dev/null +++ b/src/main/java/bjc/data/IPair.java @@ -0,0 +1,241 @@ +package bjc.data; + +import java.util.function.BiConsumer; +import java.util.function.BiFunction; +import java.util.function.Function; + +import bjc.funcdata.theory.Bifunctor; + +/** + * Represents a pair of values. + * + * @author ben + * + * @param <LeftType> + * The type of the left side of the pair. + * + * @param <RightType> + * The type of the right side of the pair. + * + */ +public interface IPair<LeftType, RightType> extends Bifunctor<LeftType, RightType> { + /** + * Bind a function across the values in this pair. + * + * @param <BoundLeft> + * The type of the bound left. + * + * @param <BoundRight> + * The type of the bound right. + * + * @param binder + * The function to bind with. + * + * @return The bound pair. + */ + public <BoundLeft, BoundRight> IPair<BoundLeft, BoundRight> bind( + BiFunction<LeftType, RightType, IPair<BoundLeft, BoundRight>> binder); + + /** + * Bind a function to the left value in this pair. + * + * @param <BoundLeft> + * The type of the bound value. + * + * @param leftBinder + * The function to use to bind. + * + * @return A pair with the left type bound. + */ + public <BoundLeft> IPair<BoundLeft, RightType> bindLeft( + Function<LeftType, IPair<BoundLeft, RightType>> leftBinder); + + /** + * Bind a function to the right value in this pair. + * + * @param <BoundRight> + * The type of the bound value. + * + * @param rightBinder + * The function to use to bind. + * + * @return A pair with the right type bound. + */ + public <BoundRight> IPair<LeftType, BoundRight> bindRight( + Function<RightType, IPair<LeftType, BoundRight>> rightBinder); + + /** + * Pairwise combine two pairs together. + * + * @param <OtherLeft> + * The left type of the other pair. + * + * @param <OtherRight> + * The right type of the other pair. + * + * @param otherPair + * The pair to combine with. + * + * @return The pairs, pairwise combined together. + */ + public default <OtherLeft, OtherRight> IPair<IPair<LeftType, OtherLeft>, IPair<RightType, OtherRight>> combine( + final IPair<OtherLeft, OtherRight> otherPair) { + return combine(otherPair, Pair<LeftType, OtherLeft>::new, Pair<RightType, OtherRight>::new); + } + + /** + * Combine the contents of two pairs together. + * + * @param <OtherLeft> + * The type of the left value of the other pair. + * + * @param <OtherRight> + * The type of the right value of the other pair. + * + * @param <CombinedLeft> + * The type of the left value of the combined pair. + * + * @param <CombinedRight> + * The type of the right value of the combined pair. + * + * @param otherPair + * The other pair to combine with. + * + * @param leftCombiner + * The function to combine the left values with. + * + * @param rightCombiner + * The function to combine the right values with. + * + * @return A pair with its values combined. + */ + public <OtherLeft, OtherRight, CombinedLeft, CombinedRight> IPair<CombinedLeft, CombinedRight> combine( + IPair<OtherLeft, OtherRight> otherPair, + BiFunction<LeftType, OtherLeft, CombinedLeft> leftCombiner, + BiFunction<RightType, OtherRight, CombinedRight> rightCombiner); + + /** + * Immediately perfom the specified action with the contents of this + * pair. + * + * @param consumer + * The action to perform on the pair. + */ + public default void doWith(final BiConsumer<LeftType, RightType> consumer) { + merge((leftValue, rightValue) -> { + consumer.accept(leftValue, rightValue); + + return null; + }); + } + + @Override + default <OldLeft, OldRight, NewLeft> LeftBifunctorMap<OldLeft, OldRight, NewLeft> fmapLeft( + final Function<OldLeft, NewLeft> func) { + return argumentPair -> { + if (!(argumentPair instanceof IPair<?, ?>)) { + final String msg = "This function can only be applied to instances of IPair"; + + throw new IllegalArgumentException(msg); + } + + final IPair<OldLeft, OldRight> argPair = (IPair<OldLeft, OldRight>) argumentPair; + + return argPair.mapLeft(func); + }; + } + + @Override + default <OldLeft, OldRight, NewRight> RightBifunctorMap<OldLeft, OldRight, NewRight> fmapRight( + final Function<OldRight, NewRight> func) { + return argumentPair -> { + if (!(argumentPair instanceof IPair<?, ?>)) { + final String msg = "This function can only be applied to instances of IPair"; + + throw new IllegalArgumentException(msg); + } + + final IPair<OldLeft, OldRight> argPair = (IPair<OldLeft, OldRight>) argumentPair; + + return argPair.mapRight(func); + }; + } + + /** + * Get the value on the left side of the pair. + * + * @return The value on the left side of the pair. + */ + @Override + public default LeftType getLeft() { + return merge((leftValue, rightValue) -> leftValue); + } + + /** + * Get the value on the right side of the pair. + * + * @return The value on the right side of the pair. + */ + @Override + public default RightType getRight() { + return merge((leftValue, rightValue) -> rightValue); + } + + /** + * Transform the value on the left side of the pair. + * + * Doesn't modify the pair. + * + * @param <NewLeft> + * The new type of the left part of the pair. + * + * @param mapper + * The function to use to transform the left part of the + * pair. + * + * @return The pair, with its left part transformed. + */ + public <NewLeft> IPair<NewLeft, RightType> mapLeft(Function<LeftType, NewLeft> mapper); + + /** + * Transform the value on the right side of the pair. + * + * Doesn't modify the pair. + * + * @param <NewRight> + * The new type of the right part of the pair. + * + * @param mapper + * The function to use to transform the right part of the + * pair. + * + * @return The pair, with its right part transformed. + */ + public <NewRight> IPair<LeftType, NewRight> mapRight(Function<RightType, NewRight> mapper); + + /** + * Merge the two values in this pair into a single value. + * + * @param <MergedType> + * The type of the single value. + * + * @param merger + * The function to use for merging. + * + * @return The pair, merged into a single value. + */ + public <MergedType> MergedType merge(BiFunction<LeftType, RightType, MergedType> merger); + + /** + * Static pair constructor. + * + * @param left + * The left side of the pair. + * @param right + * The right side of the pair. + * @return A pair, with the specified left/right side. + */ + public static <T1, T2> IPair<T1, T2> pair(T1 left, T2 right) { + return new Pair<>(left, right); + } +} diff --git a/src/main/java/bjc/data/ITree.java b/src/main/java/bjc/data/ITree.java new file mode 100644 index 0000000..4088c10 --- /dev/null +++ b/src/main/java/bjc/data/ITree.java @@ -0,0 +1,278 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.function.UnaryOperator; + +import bjc.funcdata.IList; +import bjc.funcdata.bst.TreeLinearizationMethod; + +/** + * A node in a homogeneous tree with a unlimited amount of children. + * + * @author ben + * + * @param <ContainedType> + * The type of data contained in the tree nodes. + * + */ +public interface ITree<ContainedType> { + /** + * Append a child to this node. + * + * @param child + * The child to append to this node. + */ + void addChild(ITree<ContainedType> child); + + /** + * Append a child to this node. + * + * @param child + * The child to append to this node. + */ + void addChild(ContainedType child); + + /** + * Prepend a child to this node. + * + * @param child + * The child to prepend to this node. + */ + void prependChild(ITree<ContainedType> child); + + /** + * 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. + */ + <NewType, ReturnedType> ReturnedType collapse(Function<ContainedType, NewType> leafTransform, + BiFunction<ContainedType, IList<NewType>, NewType> nodeCollapser, + Function<NewType, ReturnedType> resultTransformer); + + /** + * Execute a given action for each of this tree's children. + * + * @param action + * The action to execute for each child. + */ + void doForChildren(Consumer<ITree<ContainedType>> action); + + /** + * 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. + */ + default ITree<ContainedType> flatMapTree(final Function<ContainedType, ITree<ContainedType>> mapper) { + return topDownTransform(dat -> TopDownTransformResult.PUSHDOWN, node -> { + if(node.getChildrenCount() > 0) { + final ITree<ContainedType> parent = node.transformHead(mapper); + + node.doForChildren(parent::addChild); + + return parent; + } + + return node.transformHead(mapper); + }); + } + + /** + * Get the specified child of this tree. + * + * @param childNo + * The number of the child to get. + * + * @return The specified child of this tree. + */ + default ITree<ContainedType> getChild(final int childNo) { + return transformChild(childNo, child -> child); + } + + /** + * Get a count of the number of direct children this node has. + * + * @return The number of direct children this node has. + */ + int getChildrenCount(); + + /** + * Get a count of the number of direct children this node has. + * + * @return The number of direct children this node has. + */ + default int size() { + return getChildrenCount(); + } + + /** + * Get the data stored in this node. + * + * @return The data stored in this node. + */ + default ContainedType getHead() { + return transformHead(head -> head); + } + + /** + * 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 internalTransformer + * The function to use to transform internal tokens. + * + * @return The tree, with the nodes changed. + */ + <MappedType> ITree<MappedType> rebuildTree(Function<ContainedType, MappedType> leafTransformer, + Function<ContainedType, MappedType> internalTransformer); + + /** + * 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. + */ + void selectiveTransform(Predicate<ContainedType> nodePicker, UnaryOperator<ContainedType> transformer); + + /** + * Do a top-down transform of the tree. + * + * @param transformPicker + * The function to use to pick how to progress. + * + * @param transformer + * The function used to transform picked subtrees. + * + * @return The tree with the transform applied to picked subtrees. + */ + ITree<ContainedType> topDownTransform(Function<ContainedType, TopDownTransformResult> transformPicker, + UnaryOperator<ITree<ContainedType>> transformer); + + /** + * 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()). + */ + <TransformedType> TransformedType transformChild(int childNo, + Function<ITree<ContainedType>, TransformedType> transformer); + + /** + * 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. + */ + <TransformedType> TransformedType transformHead(Function<ContainedType, TransformedType> 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. + */ + default <MappedType> ITree<MappedType> transformTree(final Function<ContainedType, MappedType> transformer) { + return rebuildTree(transformer, 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. + */ + void traverse(TreeLinearizationMethod linearizationMethod, Consumer<ContainedType> action); + + /** + * Find the farthest to right child that satisfies the given predicate. + * + * @param childPred + * The predicate to satisfy. + * + * @return The index of the right-most child that satisfies the + * predicate, or -1 if one doesn't exist. + */ + int revFind(Predicate<ITree<ContainedType>> childPred); + + /** + * Check if this tree contains any nodes that satisfy the predicate. + * + * @param pred + * The predicate to look for. + * + * @return Whether or not any items satisfied the predicate. + */ + default boolean containsMatching(Predicate<ContainedType> pred) { + Toggle<Boolean> tog = new OneWayToggle<>(false, true); + + traverse(TreeLinearizationMethod.POSTORDER, (val) -> { + if(pred.test(val)) tog.get(); + }); + + return tog.get(); + } + + /** + * Set the head of the tree. + * + * @param dat + * The value to set as the head of the tree. + */ + void setHead(ContainedType dat); +} diff --git a/src/main/java/bjc/data/Identity.java b/src/main/java/bjc/data/Identity.java new file mode 100644 index 0000000..8645c4c --- /dev/null +++ b/src/main/java/bjc/data/Identity.java @@ -0,0 +1,112 @@ +package bjc.data; + +import java.util.function.Function; +import java.util.function.UnaryOperator; + +/** + * Simple implementation of IHolder that has no hidden behavior. + * + * @author ben + * + * @param <ContainedType> + * The type contained in the holder. + */ +public class Identity<ContainedType> implements IHolder<ContainedType> { + /* The held value. */ + private ContainedType heldValue; + + /** Create a holder holding null */ + public Identity() { + heldValue = null; + } + + /** + * Create a holder holding the specified value. + * + * @param value + * The value to hold. + */ + public Identity(final ContainedType value) { + heldValue = value; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<ContainedType, IHolder<BoundType>> binder) { + return binder.apply(heldValue); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + (heldValue == null ? 0 : heldValue.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof Identity)) return false; + + final Identity<?> other = (Identity<?>) obj; + + if(heldValue == null) { + if(other.heldValue != null) return false; + } else if(!heldValue.equals(other.heldValue)) return false; + + return true; + } + + @Override + public <NewType> Function<ContainedType, IHolder<NewType>> lift(final Function<ContainedType, NewType> func) { + return (val) -> { + return new Identity<>(func.apply(val)); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<ContainedType, MappedType> mapper) { + return new Identity<>(mapper.apply(heldValue)); + } + + @Override + public String toString() { + return String.format("Identity [heldValue=%s]", heldValue); + } + + @Override + public IHolder<ContainedType> transform(final UnaryOperator<ContainedType> transformer) { + heldValue = transformer.apply(heldValue); + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<ContainedType, UnwrappedType> unwrapper) { + return unwrapper.apply(heldValue); + } + + /** + * Create a new identity container. + * + * @param val + * The contained value. + * + * @return A new identity container. + */ + public static <ContainedType> Identity<ContainedType> id(final ContainedType val) { + return new Identity<>(val); + } + + /** + * Create a new empty identity container. + * + * @return A new empty identity container. + */ + public static <ContainedType> Identity<ContainedType> id() { + return new Identity<>(); + } +} diff --git a/src/main/java/bjc/data/Lazy.java b/src/main/java/bjc/data/Lazy.java new file mode 100644 index 0000000..0702665 --- /dev/null +++ b/src/main/java/bjc/data/Lazy.java @@ -0,0 +1,201 @@ +package bjc.data; + +import java.util.function.Function; +import java.util.function.Supplier; +import java.util.function.UnaryOperator; + +import bjc.data.internals.BoundLazy; +import bjc.funcdata.FunctionalList; +import bjc.funcdata.IList; + +/** + * A holder that holds a means to create a value, but doesn't actually compute + * the value until it's needed. + * + * @author ben + * + * @param <ContainedType> + * The type of the value being held. + */ +public class Lazy<ContainedType> implements IHolder<ContainedType> { + /* The supplier of the type. */ + private Supplier<ContainedType> valueSupplier; + /* The actual type value. */ + private ContainedType heldValue; + /* Whether the value has been created. */ + private boolean valueMaterialized; + + /* The list of pending actions on the value. */ + private IList<UnaryOperator<ContainedType>> actions = new FunctionalList<>(); + + /** + * Create a new lazy value from the specified seed value. + * + * @param value + * The seed value to use. + */ + public Lazy(final ContainedType value) { + heldValue = value; + + valueMaterialized = true; + } + + /** + * Create a new lazy value from the specified value source. + * + * @param supp + * The source of a value to use. + */ + public Lazy(final Supplier<ContainedType> supp) { + valueSupplier = new SingleSupplier<>(supp); + + valueMaterialized = false; + } + + /* Create a new value from a supplier and a list of actions. */ + private Lazy(final Supplier<ContainedType> supp, final IList<UnaryOperator<ContainedType>> pendingActions) { + valueSupplier = supp; + + actions = pendingActions; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<ContainedType, IHolder<BoundType>> binder) { + final IList<UnaryOperator<ContainedType>> pendingActions = new FunctionalList<>(); + + actions.forEach(pendingActions::add); + + final Supplier<ContainedType> supplier = () -> { + if(valueMaterialized) return heldValue; + + return valueSupplier.get(); + }; + + return new BoundLazy<>(() -> { + return new Lazy<>(supplier, pendingActions); + }, binder); + } + + @Override + public <NewType> Function<ContainedType, IHolder<NewType>> lift(final Function<ContainedType, NewType> func) { + return val -> { + return new Lazy<>(func.apply(val)); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<ContainedType, MappedType> mapper) { + final IList<UnaryOperator<ContainedType>> pendingActions = new FunctionalList<>(); + + actions.forEach(pendingActions::add); + + return new Lazy<>(() -> { + ContainedType currVal = heldValue; + + if(!valueMaterialized) { + currVal = valueSupplier.get(); + } + + return pendingActions.reduceAux(currVal, UnaryOperator<ContainedType>::apply, + value -> mapper.apply(value)); + }); + } + + @Override + public String toString() { + if(valueMaterialized) { + if(actions.isEmpty()) { + return String.format("value[v='%s']", heldValue); + } + + return String.format("value[v='%s'] (has pending transforms)", heldValue); + } + + return "(unmaterialized)"; + } + + @Override + public IHolder<ContainedType> transform(final UnaryOperator<ContainedType> transformer) { + actions.add(transformer); + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<ContainedType, UnwrappedType> unwrapper) { + if(!valueMaterialized) { + heldValue = valueSupplier.get(); + + valueMaterialized = true; + } + + actions.forEach(action -> { + heldValue = action.apply(heldValue); + }); + + actions = new FunctionalList<>(); + + return unwrapper.apply(heldValue); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + (actions == null ? 0 : actions.hashCode()); + result = prime * result + (heldValue == null ? 0 : heldValue.hashCode()); + result = prime * result + (valueMaterialized ? 1231 : 1237); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof Lazy<?>)) return false; + + final Lazy<?> other = (Lazy<?>) obj; + + if(valueMaterialized != other.valueMaterialized) return false; + + if(valueMaterialized) { + if(heldValue == null) { + if(other.heldValue != null) return false; + } else if(!heldValue.equals(other.heldValue)) return false; + } else + return false; + + if(actions == null) { + if(other.actions != null) return false; + } else if(actions.getSize() > 0 || other.actions.getSize() > 0) return false; + + return true; + } + + /** + * Create a new lazy container with an already present value. + * + * @param val + * The value for the lazy container. + * + * @return A new lazy container holding that value. + */ + public static <ContainedType> Lazy<ContainedType> lazy(final ContainedType val) { + return new Lazy<>(val); + } + + /** + * Create a new lazy container with a suspended value. + * + * @param supp + * The suspended value for the lazy container. + * + * @return A new lazy container that will un-suspend the value when + * necessary. + */ + public static <ContainedType> Lazy<ContainedType> lazy(final Supplier<ContainedType> supp) { + return new Lazy<>(supp); + } +} diff --git a/src/main/java/bjc/data/LazyPair.java b/src/main/java/bjc/data/LazyPair.java new file mode 100644 index 0000000..1633c65 --- /dev/null +++ b/src/main/java/bjc/data/LazyPair.java @@ -0,0 +1,249 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Supplier; + +import bjc.data.internals.BoundLazyPair; +import bjc.data.internals.HalfBoundLazyPair; + +/** + * A lazy implementation of a pair. + * + * @author ben + * + * @param <LeftType> + * The type on the left side of the pair. + * + * @param <RightType> + * The type on the right side of the pair. + */ +public class LazyPair<LeftType, RightType> implements IPair<LeftType, RightType> { + /* The supplier for the left value. */ + private Supplier<LeftType> leftSupplier; + /* The left value. */ + private LeftType leftValue; + /* Whether the left value has been created. */ + private boolean leftMaterialized; + + /* The supplier for the right value. */ + private Supplier<RightType> rightSupplier; + /* The right value. */ + private RightType rightValue; + /* Whether the right value has been created. */ + private boolean rightMaterialized; + + /** + * Create a new lazy pair, using the set values. + * + * @param leftVal + * The value for the left side of the pair. + * + * @param rightVal + * The value for the right side of the pair. + */ + public LazyPair(final LeftType leftVal, final RightType rightVal) { + leftValue = leftVal; + rightValue = rightVal; + + leftMaterialized = true; + rightMaterialized = true; + } + + /** + * Create a new lazy pair from the given value sources. + * + * @param leftSupp + * The source for a value on the left side of the pair. + * + * @param rightSupp + * The source for a value on the right side of the pair. + */ + public LazyPair(final Supplier<LeftType> leftSupp, final Supplier<RightType> rightSupp) { + /* Use single suppliers to catch double-instantiation bugs. */ + leftSupplier = new SingleSupplier<>(leftSupp); + rightSupplier = new SingleSupplier<>(rightSupp); + + leftMaterialized = false; + rightMaterialized = false; + } + + @Override + public <BoundLeft, BoundRight> IPair<BoundLeft, BoundRight> bind( + final BiFunction<LeftType, RightType, IPair<BoundLeft, BoundRight>> binder) { + return new BoundLazyPair<>(leftSupplier, rightSupplier, binder); + } + + @Override + public <BoundLeft> IPair<BoundLeft, RightType> bindLeft( + final Function<LeftType, IPair<BoundLeft, RightType>> leftBinder) { + final Supplier<LeftType> leftSupp = () -> { + if(leftMaterialized) return leftValue; + + return leftSupplier.get(); + }; + + return new HalfBoundLazyPair<>(leftSupp, leftBinder); + } + + @Override + public <BoundRight> IPair<LeftType, BoundRight> bindRight( + final Function<RightType, IPair<LeftType, BoundRight>> rightBinder) { + final Supplier<RightType> rightSupp = () -> { + if(rightMaterialized) return rightValue; + + return rightSupplier.get(); + }; + + return new HalfBoundLazyPair<>(rightSupp, rightBinder); + } + + @Override + public <OtherLeft, OtherRight, CombinedLeft, CombinedRight> IPair<CombinedLeft, CombinedRight> combine( + final IPair<OtherLeft, OtherRight> otherPair, + final BiFunction<LeftType, OtherLeft, CombinedLeft> leftCombiner, + final BiFunction<RightType, OtherRight, CombinedRight> rightCombiner) { + return otherPair.bind((otherLeft, otherRight) -> { + return bind((leftVal, rightVal) -> { + final CombinedLeft left = leftCombiner.apply(leftVal, otherLeft); + final CombinedRight right = rightCombiner.apply(rightVal, otherRight); + + return new LazyPair<>(left, right); + }); + }); + } + + @Override + public LeftType getLeft() { + if(!leftMaterialized) { + leftValue = leftSupplier.get(); + + leftMaterialized = true; + } + + return leftValue; + } + + @Override + public RightType getRight() { + if(!rightMaterialized) { + rightValue = rightSupplier.get(); + + rightMaterialized = true; + } + + return rightValue; + } + + @Override + public <NewLeft> IPair<NewLeft, RightType> mapLeft(final Function<LeftType, NewLeft> mapper) { + final Supplier<NewLeft> leftSupp = () -> { + if(leftMaterialized) return mapper.apply(leftValue); + + return mapper.apply(leftSupplier.get()); + }; + + final Supplier<RightType> rightSupp = () -> { + if(rightMaterialized) return rightValue; + + return rightSupplier.get(); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public <NewRight> IPair<LeftType, NewRight> mapRight(final Function<RightType, NewRight> mapper) { + final Supplier<LeftType> leftSupp = () -> { + if(leftMaterialized) return leftValue; + + return leftSupplier.get(); + }; + + final Supplier<NewRight> rightSupp = () -> { + if(rightMaterialized) return mapper.apply(rightValue); + + return mapper.apply(rightSupplier.get()); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public <MergedType> MergedType merge(final BiFunction<LeftType, RightType, MergedType> merger) { + if(!leftMaterialized) { + leftValue = leftSupplier.get(); + + leftMaterialized = true; + } + + if(!rightMaterialized) { + rightValue = rightSupplier.get(); + + rightMaterialized = true; + } + + return merger.apply(leftValue, rightValue); + } + + @Override + public String toString() { + String leftVal; + String rightVal; + + if(leftMaterialized) { + leftVal = leftValue.toString(); + } else { + leftVal = "(un-materialized)"; + } + + if(rightMaterialized) { + rightVal = rightValue.toString(); + } else { + rightVal = "(un-materialized)"; + } + + return String.format("pair[l=%s,r=%s]", leftVal, rightVal); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + (leftMaterialized ? 1231 : 1237); + result = prime * result + (leftValue == null ? 0 : leftValue.hashCode()); + result = prime * result + (rightMaterialized ? 1231 : 1237); + result = prime * result + (rightValue == null ? 0 : rightValue.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof LazyPair<?, ?>)) return false; + + final LazyPair<?, ?> other = (LazyPair<?, ?>) obj; + + if(leftMaterialized != other.leftMaterialized) return false; + + if(leftMaterialized) { + if(leftValue == null) { + if(other.leftValue != null) return false; + } else if(!leftValue.equals(other.leftValue)) return false; + } else + return false; + + if(rightMaterialized != other.rightMaterialized) return false; + if(rightMaterialized) { + if(rightValue == null) { + if(other.rightValue != null) return false; + } else if(!rightValue.equals(other.rightValue)) return false; + } else + return false; + + return true; + } +} diff --git a/src/main/java/bjc/data/ListHolder.java b/src/main/java/bjc/data/ListHolder.java new file mode 100644 index 0000000..077c0fb --- /dev/null +++ b/src/main/java/bjc/data/ListHolder.java @@ -0,0 +1,105 @@ +package bjc.data; + +import java.util.function.Function; +import java.util.function.UnaryOperator; + +import bjc.data.internals.BoundListHolder; +import bjc.funcdata.FunctionalList; +import bjc.funcdata.IList; + +/** + * A holder that represents a set of non-deterministic computations. + * + * @author ben + * + * @param <ContainedType> + * The type of contained value. + */ +public class ListHolder<ContainedType> implements IHolder<ContainedType> { + private IList<ContainedType> heldValues; + + /** + * Create a new list holder. + * + * @param values + * The possible values for the computation. + */ + @SafeVarargs + public ListHolder(final ContainedType... values) { + heldValues = new FunctionalList<>(); + + if(values != null) { + for(final ContainedType containedValue : values) { + heldValues.add(containedValue); + } + } + } + + /* Create a new holder with values. */ + private ListHolder(final IList<ContainedType> toHold) { + heldValues = toHold; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<ContainedType, IHolder<BoundType>> binder) { + final IList<IHolder<BoundType>> boundValues = heldValues.map(binder); + + return new BoundListHolder<>(boundValues); + } + + @Override + public <NewType> Function<ContainedType, IHolder<NewType>> lift(final Function<ContainedType, NewType> func) { + return val -> { + return new ListHolder<>(new FunctionalList<>(func.apply(val))); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<ContainedType, MappedType> mapper) { + final IList<MappedType> mappedValues = heldValues.map(mapper); + + return new ListHolder<>(mappedValues); + } + + @Override + public IHolder<ContainedType> transform(final UnaryOperator<ContainedType> transformer) { + heldValues = heldValues.map(transformer); + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<ContainedType, UnwrappedType> unwrapper) { + return unwrapper.apply(heldValues.randItem()); + } + + @Override + public String toString() { + return String.format("ListHolder [heldValues=%s]", heldValues); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + (heldValues == null ? 0 : heldValues.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof ListHolder<?>)) return false; + + final ListHolder<?> other = (ListHolder<?>) obj; + + if(heldValues == null) { + if(other.heldValues != null) return false; + } else if(!heldValues.equals(other.heldValues)) return false; + + return true; + } +} diff --git a/src/main/java/bjc/data/OneWayToggle.java b/src/main/java/bjc/data/OneWayToggle.java new file mode 100644 index 0000000..a4557cd --- /dev/null +++ b/src/main/java/bjc/data/OneWayToggle.java @@ -0,0 +1,53 @@ +package bjc.data; + +/** + * A toggle that will only give the first value once, only yielding the second + * value afterwards. + * + * @author student + * + * @param <E> + * The type of value stored + */ +public class OneWayToggle<E> implements Toggle<E> { + private E first; + private E second; + + private boolean gotFirst; + + /** + * Create a new one-way toggle + * + * @param first + * The value to offer first, and only once + * @param second + * The value to offer second and repeatedly + */ + public OneWayToggle(E first, E second) { + this.first = first; + + this.second = second; + } + + @Override + public E get() { + if (gotFirst) + return second; + + gotFirst = true; + return first; + } + + @Override + public E peek() { + if (gotFirst) + return second; + return first; + } + + @Override + public void set(boolean gotFirst) { + this.gotFirst = gotFirst; + } + +} diff --git a/src/main/java/bjc/data/Option.java b/src/main/java/bjc/data/Option.java new file mode 100644 index 0000000..a180ef9 --- /dev/null +++ b/src/main/java/bjc/data/Option.java @@ -0,0 +1,93 @@ +package bjc.data; + +import java.util.function.Function; +import java.util.function.UnaryOperator; + +/** + * A holder that may or may not contain a value. + * + * @author ben + * + * @param <ContainedType> + * The type of the value that may or may not be held. + */ +public class Option<ContainedType> implements IHolder<ContainedType> { + private ContainedType held; + + /** + * Create a new optional, using the given initial value. + * + * @param seed + * The initial value for the optional. + */ + public Option(final ContainedType seed) { + held = seed; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<ContainedType, IHolder<BoundType>> binder) { + if(held == null) return new Option<>(null); + + return binder.apply(held); + } + + @Override + public <NewType> Function<ContainedType, IHolder<NewType>> lift(final Function<ContainedType, NewType> func) { + return val -> { + return new Option<>(func.apply(val)); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<ContainedType, MappedType> mapper) { + if(held == null) return new Option<>(null); + + return new Option<>(mapper.apply(held)); + } + + @Override + public IHolder<ContainedType> transform(final UnaryOperator<ContainedType> transformer) { + if(held != null) { + held = transformer.apply(held); + } + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<ContainedType, UnwrappedType> unwrapper) { + if(held == null) return null; + + return unwrapper.apply(held); + } + + @Override + public String toString() { + return String.format("Option [held='%s']", held); + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + result = prime * result + (held == null ? 0 : held.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof Option<?>)) return false; + + final Option<?> other = (Option<?>) obj; + + if(held == null) { + if(other.held != null) return false; + } else if(!held.equals(other.held)) return false; + + return true; + } +} diff --git a/src/main/java/bjc/data/Pair.java b/src/main/java/bjc/data/Pair.java new file mode 100644 index 0000000..3c1b7b5 --- /dev/null +++ b/src/main/java/bjc/data/Pair.java @@ -0,0 +1,142 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Function; + +/** + * A pair of values, with nothing special about them. + * + * @author ben + * + * @param <LeftType> + * The type of the left value. + * + * @param <RightType> + * The type of the right value. + */ +public class Pair<LeftType, RightType> implements IPair<LeftType, RightType> { + /* The left value. */ + private LeftType leftValue; + /* The right value. */ + private RightType rightValue; + + /** Create a new pair with both sides set to null. */ + public Pair() { + + } + + /** + * Create a new pair with both sides set to the specified values. + * + * @param left + * The value of the left side. + * + * @param right + * The value of the right side. + */ + public Pair(final LeftType left, final RightType right) { + leftValue = left; + rightValue = right; + } + + @Override + public <BoundLeft, BoundRight> IPair<BoundLeft, BoundRight> bind( + final BiFunction<LeftType, RightType, IPair<BoundLeft, BoundRight>> binder) { + if(binder == null) throw new NullPointerException("Binder must not be null."); + + return binder.apply(leftValue, rightValue); + } + + @Override + public <BoundLeft> IPair<BoundLeft, RightType> bindLeft( + final Function<LeftType, IPair<BoundLeft, RightType>> leftBinder) { + if(leftBinder == null) throw new NullPointerException("Binder must not be null"); + + return leftBinder.apply(leftValue); + } + + @Override + public <BoundRight> IPair<LeftType, BoundRight> bindRight( + final Function<RightType, IPair<LeftType, BoundRight>> rightBinder) { + if(rightBinder == null) throw new NullPointerException("Binder must not be null"); + + return rightBinder.apply(rightValue); + } + + @Override + public <OtherLeft, OtherRight, CombinedLeft, CombinedRight> IPair<CombinedLeft, CombinedRight> combine( + final IPair<OtherLeft, OtherRight> otherPair, + final BiFunction<LeftType, OtherLeft, CombinedLeft> leftCombiner, + final BiFunction<RightType, OtherRight, CombinedRight> rightCombiner) { + return otherPair.bind((otherLeft, otherRight) -> { + final CombinedLeft left = leftCombiner.apply(leftValue, otherLeft); + final CombinedRight right = rightCombiner.apply(rightValue, otherRight); + + return new Pair<>(left, right); + }); + } + + @Override + public <NewLeft> IPair<NewLeft, RightType> mapLeft(final Function<LeftType, NewLeft> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + return new Pair<>(mapper.apply(leftValue), rightValue); + } + + @Override + public <NewRight> IPair<LeftType, NewRight> mapRight(final Function<RightType, NewRight> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + return new Pair<>(leftValue, mapper.apply(rightValue)); + } + + @Override + public <MergedType> MergedType merge(final BiFunction<LeftType, RightType, MergedType> merger) { + if(merger == null) throw new NullPointerException("Merger must not be null"); + + return merger.apply(leftValue, rightValue); + } + + @Override + public String toString() { + return String.format("Pair [leftValue='%s', rightValue='%s']", leftValue, rightValue); + } + + public LeftType getLeft() { + return leftValue; + } + + public RightType getRight() { + return rightValue; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + (leftValue == null ? 0 : leftValue.hashCode()); + result = prime * result + (rightValue == null ? 0 : rightValue.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof Pair<?, ?>)) return false; + + final Pair<?, ?> other = (Pair<?, ?>) obj; + + if(leftValue == null) { + if(other.leftValue != null) return false; + } else if(!leftValue.equals(other.leftValue)) return false; + + if(rightValue == null) { + if(other.rightValue != null) return false; + } else if(!rightValue.equals(other.rightValue)) return false; + + return true; + } +} diff --git a/src/main/java/bjc/data/QueuedIterator.java b/src/main/java/bjc/data/QueuedIterator.java new file mode 100644 index 0000000..8071106 --- /dev/null +++ b/src/main/java/bjc/data/QueuedIterator.java @@ -0,0 +1,228 @@ +package bjc.data; + +import java.util.ArrayDeque; +import java.util.Deque; +import java.util.Iterator; + +/** + * An iterator that supports queuing elements after/before the current iterator; + * + * @author bjculkin + * + * @param <E> + */ +public class QueuedIterator<E> implements Iterator<E> { + private Iterator<E> cur; + + private Deque<Iterator<E>> pending; + + /** + * Static method for constructing iterators. + * + * @return A queued iterator. + */ + public static <E> QueuedIterator<E> queued() { + return new QueuedIterator<>(); + } + + /** + * Static method for constructing iterators. + * + * @param vals + * The values to iterate over. + * + * @return A queued iterator. + */ + public static <E> QueuedIterator<E> queued(E... vals) { + return new QueuedIterator<>(new ArrayIterator<>(vals)); + } + + /** + * Static method for constructing iterators. + * + * @param itrs + * The iterators to use. + * + * @return A queued iterator over the provided iterators. + */ + @SafeVarargs + public static <E> QueuedIterator<E> queued(Iterator<E>... itrs) { + return new QueuedIterator<>(itrs); + } + + /** + * Static method for constructing iterators. + * + * @param itrs + * The iterables to use. + * + * @return A queued iterator over the provided iterables. + */ + @SafeVarargs + public static <E> QueuedIterator<E> queued(Iterable<E>... itrs) { + return new QueuedIterator<>(itrs); + } + + /** + * Create a new queued iterator that starts blank. + */ + public QueuedIterator() { + pending = new ArrayDeque<>(); + } + + /** + * Create a new queued iterator with a set of initial sources. + * + * @param inits + * The set of initial iterators to use. + */ + @SafeVarargs + public QueuedIterator(Iterator<E>... inits) { + this(); + + for (Iterator<E> init : inits) { + pending.add(init); + } + } + + /** + * Create a new queued iterator with a set of initial sources. + * + * @param inits + * The set of initial iterables to use. + */ + @SafeVarargs + public QueuedIterator(Iterable<E>... inits) { + this(); + + for (Iterable<E> init : inits) { + pending.add(init.iterator()); + } + } + + /** + * Create a new queued iterator with a set of initial values. + * + * @param vals + * The set of initial values to use. + */ + @SafeVarargs + public QueuedIterator(E... vals) { + this(new ArrayIterator(vals)); + } + + /** + * Add a new iterator who we will iterate through first. + * + * @param itr + * The iterator to go through first. + */ + public void before(Iterator<E> itr) { + pending.push(cur); + + cur = itr; + } + + /** + * Add a new iterable who we will iterate through first. + * + * @param itr + * The iterable to go through first. + */ + public void before(Iterable<E> itr) { + before(itr.iterator()); + } + + /** + * Add a new set of values who we will iterate through first. + * + * @param vals + * Values to iterate over first. + */ + public void before(E... vals) { + before(new ArrayIterator<>(vals)); + } + + /** + * Add a new iterator who we will iterate through next. + * + * @param itr + * The iterator to go through next. + */ + public void after(Iterator<E> itr) { + pending.push(itr); + } + + /** + * Add a new iterable who we will iterate through next. + * + * @param itr + * The iterable to go through next. + */ + public void after(Iterable<E> itr) { + after(itr.iterator()); + } + + /** + * Add a new set of values who we will iterate through next. + * + * @param vals + * The values to iterate over next. + */ + public void after(E... vals) { + after(new ArrayIterator<>(vals)); + } + + /** + * Add a new iterator who we will iterate through last. + * + * @param itr + * The iterator to go through last. + */ + public void last(Iterator<E> itr) { + pending.add(itr); + } + + /** + * Add a new iterable who we will iterate through last. + * + * @param itr + * The iterable to go through last. + */ + public void last(Iterable<E> itr) { + last(itr.iterator()); + } + + /** + * Add a new set of values who we will iterate through last. + * + * @param itr + * The iterable to go through last. + */ + public void last(E... vals) { + last(new ArrayIterator<>(vals)); + } + + @Override + public boolean hasNext() { + while (cur == null || !cur.hasNext()) { + if (pending.isEmpty()) return false; + + cur = pending.pop(); + } + + return cur.hasNext(); + } + + @Override + public E next() { + while (cur == null || !cur.hasNext()) { + if (pending.isEmpty()) return null; + + cur = pending.pop(); + } + + return cur.next(); + } + +} diff --git a/src/main/java/bjc/data/SingleIterator.java b/src/main/java/bjc/data/SingleIterator.java new file mode 100644 index 0000000..3144447 --- /dev/null +++ b/src/main/java/bjc/data/SingleIterator.java @@ -0,0 +1,42 @@ +package bjc.data; + +import java.util.Iterator; + +/** + * An iterator that will only ever yield one item. + * + * @author EVE + * + * @param <T> + * The type of the item. + */ +public class SingleIterator<T> implements Iterator<T> { + /* The item being held. */ + private final T itm; + /* Whether we've yielded the item yet. */ + private boolean yielded; + + /** + * Create a iterator that yields a single item. + * + * @param item + * The item to yield. + */ + public SingleIterator(final T item) { + itm = item; + + yielded = false; + } + + @Override + public boolean hasNext() { + return !yielded; + } + + @Override + public T next() { + yielded = true; + + return itm; + } +} diff --git a/src/main/java/bjc/data/SingleSupplier.java b/src/main/java/bjc/data/SingleSupplier.java new file mode 100644 index 0000000..bc1fbc4 --- /dev/null +++ b/src/main/java/bjc/data/SingleSupplier.java @@ -0,0 +1,76 @@ +package bjc.data; + +import java.util.function.Supplier; + +/** + * A supplier that can only supply one value. + * + * Attempting to retrieve another value will cause an exception to be thrown. + * + * @author ben + * + * @param <T> + * The supplied type + */ +public class SingleSupplier<T> implements Supplier<T> { + /* The next supplier ID. */ + private static long nextID = 0; + /* The supplier to yield from. */ + private final Supplier<T> source; + /* Whether this value has been retrieved yet. */ + private boolean gotten; + /* The ID of this supplier. */ + private final long id; + + /* + * The place where the supplier was instantiated. + * + * @NOTE This is both slow to create, and generally bad practice to keep + * exceptions around without throwing them. However, it is very useful + * to find where the first instantiation was. + */ + private Exception instSite; + + /** + * Create a new single supplier from an existing value. + * + * @param supp + * The supplier to give a single value from. + */ + public SingleSupplier(final Supplier<T> supp) { + source = supp; + + gotten = false; + + id = nextID++; + } + + @Override + public T get() { + if(gotten == true) { + final String msg = String.format( + "Attempted to retrieve value more than once from single supplier #%d", id); + + final IllegalStateException isex = new IllegalStateException(msg); + + isex.initCause(instSite); + + throw isex; + } + + gotten = true; + + try { + throw new IllegalStateException("Previous instantiation here."); + } catch(final IllegalStateException isex) { + instSite = isex; + } + + return source.get(); + } + + @Override + public String toString() { + return String.format("SingleSupplier [source='%s', gotten=%s, id=%s]", source, gotten, id); + } +} diff --git a/src/main/java/bjc/data/Toggle.java b/src/main/java/bjc/data/Toggle.java new file mode 100644 index 0000000..14c77d3 --- /dev/null +++ b/src/main/java/bjc/data/Toggle.java @@ -0,0 +1,34 @@ +package bjc.data; + +/** + * A stateful holder that swaps between two values of the same type. + * + * @author EVE + * + * @param <E> + * The value stored in the toggle. + */ +public interface Toggle<E> { + /** + * Retrieve the currently-aligned value of this toggle, and swap the + * value to the new one. + * + * @return The previously-aligned value. + */ + E get(); + + /** + * Retrieve the currently-aligned value without altering the alignment. + * + * @return The currently-aligned value. + */ + E peek(); + + /** + * Change the alignment of the toggle. + * + * @param isLeft + * Whether the toggle should be left-aligned or not. + */ + void set(boolean isLeft); +} diff --git a/src/main/java/bjc/data/TopDownTransformIterator.java b/src/main/java/bjc/data/TopDownTransformIterator.java new file mode 100644 index 0000000..5aa2409 --- /dev/null +++ b/src/main/java/bjc/data/TopDownTransformIterator.java @@ -0,0 +1,272 @@ +package bjc.data; + +import static bjc.data.TopDownTransformResult.RTRANSFORM; + +import java.util.Deque; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.NoSuchElementException; +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; + +/* + * @TODO 10/11/17 Ben Culkin :TopDownStep + * + * Figure out what is broken with this, and fix it so that step-wise + * iteration works correctly. + */ + +/** + * An iterative top-down transform of a tree. + * + * @author EVE + * + * @param <ContainedType> + * The type of the nodes in the tree. + */ +public class TopDownTransformIterator<ContainedType> implements Iterator<ITree<ContainedType>> { + /** + * Alias type for a tree transformation. + * + * @author student + * + * @param <ContainedType> + * The type contained in the tree. + */ + public interface TreeTransform<ContainedType> + extends BiFunction<ITree<ContainedType>, Consumer<Iterator<ITree<ContainedType>>>, ITree<ContainedType>> { + + } + + /* + * The function that picks how to transform a given node + */ + private final Function<ContainedType, TopDownTransformResult> picker; + /* + * The transform to apply to a given node. + */ + private final TreeTransform<ContainedType> transform; + + private ITree<ContainedType> preParent; + private ITree<ContainedType> postParent; + + private final Deque<ITree<ContainedType>> preChildren; + private final Deque<ITree<ContainedType>> postChildren; + + private TopDownTransformIterator<ContainedType> curChild; + + private boolean done; + private boolean initial; + + private final Deque<Iterator<ITree<ContainedType>>> toYield; + private Iterator<ITree<ContainedType>> currYield; + + /** + * Create a new tree iterator. + * + * @param pickr + * The function to use to pick how to process nodes. + * @param transfrm + * The transform to apply to the nodes. + * @param tree + * The tree to transform. + */ + public TopDownTransformIterator(final Function<ContainedType, TopDownTransformResult> pickr, + final TreeTransform<ContainedType> transfrm, final ITree<ContainedType> tree) { + preParent = tree; + + preChildren = new LinkedList<>(); + postChildren = new LinkedList<>(); + toYield = new LinkedList<>(); + + picker = pickr; + transform = transfrm; + + done = false; + initial = true; + } + + /** + * Add a set of nodes to yield. + * + * @param src + * The nodes to yield. + */ + public void addYield(final Iterator<ITree<ContainedType>> src) { + if (currYield != null) { + toYield.push(currYield); + } + + currYield = src; + } + + @Override + public boolean hasNext() { + return !done; + } + + /** + * Get the next yielded value. + * + * @param val + * The sentinel value to yield. + * + * @return The next yielded value. + */ + public ITree<ContainedType> flushYields(final ITree<ContainedType> val) { + if (currYield != null) { + /* + * We have non-sentinel values to yield. + */ + + /* + * Add the sentinel to yield later. + */ + toYield.add(new SingleIterator<>(val)); + + if (currYield.hasNext()) { + return currYield.next(); + } + + while (toYield.size() != 0 && !currYield.hasNext()) { + currYield = toYield.pop(); + } + + if (toYield.size() == 0 && !currYield.hasNext()) { + currYield = null; + return val; + } + + return currYield.next(); + } + + return val; + } + + @Override + public ITree<ContainedType> next() { + if (done) + throw new NoSuchElementException(); + + /* + * Flush any values that need to be yielded. + */ + if (currYield != null) { + ITree<ContainedType> yeld = flushYields(null); + + if (yeld != null) + return yeld; + } + + if (initial) { + /* + * Get the way we are transforming. + */ + final TopDownTransformResult res = picker.apply(preParent.getHead()); + + switch (res) { + case PASSTHROUGH: + postParent = new Tree<>(preParent.getHead()); + + if (preParent.getChildrenCount() != 0) { + for (int i = 0; i < preParent.getChildrenCount(); i++) { + preChildren.add(preParent.getChild(i)); + } + + // Return whatever the first child is + break; + } + + done = true; + return flushYields(postParent); + case SKIP: + done = true; + return flushYields(preParent); + case TRANSFORM: + done = true; + return flushYields(transform.apply(preParent, this::addYield)); + case RTRANSFORM: + preParent = transform.apply(preParent, this::addYield); + return flushYields(preParent); + case PUSHDOWN: + if (preParent.getChildrenCount() != 0) { + for (int i = 0; i < preParent.getChildrenCount(); i++) { + preChildren.add(preParent.getChild(i)); + } + + // Return whatever the first child is + break; + } + + done = true; + return flushYields(transform.apply(new Tree<>(preParent.getHead()), this::addYield)); + case PULLUP: + final ITree<ContainedType> intRes = transform.apply(preParent, this::addYield); + + postParent = new Tree<>(intRes.getHead()); + + if (intRes.getChildrenCount() != 0) { + for (int i = 0; i < intRes.getChildrenCount(); i++) { + preChildren.add(intRes.getChild(i)); + } + + // Return whatever the first child is + break; + } + + done = true; + return flushYields(postParent); + default: + throw new IllegalArgumentException("Unknown result type " + res); + } + + if (res != RTRANSFORM) { + initial = false; + } + } + + if (curChild == null || !curChild.hasNext()) { + if (preChildren.size() != 0) { + curChild = new TopDownTransformIterator<>(picker, transform, preChildren.pop()); + + final ITree<ContainedType> res = curChild.next(); + //System.out.println("\t\tTRACE: adding node " + res + " to children"); + postChildren.add(res); + + return flushYields(res); + } + + ITree<ContainedType> res = null; + + if (postParent == null) { + res = new Tree<>(preParent.getHead()); + + //System.out.println("\t\tTRACE: adding nodes " + postChildren + " to " + res); + + for (final ITree<ContainedType> child : postChildren) { + res.addChild(child); + } + + // res = transform.apply(res, + // this::addYield); + } else { + res = postParent; + + //System.out.println("\t\tTRACE: adding nodes " + postChildren + " to " + res); + for (final ITree<ContainedType> child : postChildren) { + res.addChild(child); + } + } + + done = true; + return flushYields(res); + } + + final ITree<ContainedType> res = curChild.next(); + //System.out.println("\t\tTRACE: adding node " + res + " to children"); + postChildren.add(res); + + return flushYields(res); + } +} diff --git a/src/main/java/bjc/data/TopDownTransformResult.java b/src/main/java/bjc/data/TopDownTransformResult.java new file mode 100644 index 0000000..0633cec --- /dev/null +++ b/src/main/java/bjc/data/TopDownTransformResult.java @@ -0,0 +1,22 @@ +package bjc.data; + +/** + * Represents the results for doing a top-down transform of a tree. + * + * @author ben + * + */ +public enum TopDownTransformResult { + /** Do not do anything to this node, and ignore its children. */ + SKIP, + /** Transform this node, and don't touch its children. */ + TRANSFORM, + /** Transform this node, then recursively transform the result. */ + RTRANSFORM, + /** Ignore this node, and traverse its children. */ + PASSTHROUGH, + /** Traverse the nodes of this children, then transform it. */ + PUSHDOWN, + /** Transform this node, then traverse its children. */ + PULLUP; +} diff --git a/src/main/java/bjc/data/TransformIterator.java b/src/main/java/bjc/data/TransformIterator.java new file mode 100644 index 0000000..0fc127a --- /dev/null +++ b/src/main/java/bjc/data/TransformIterator.java @@ -0,0 +1,46 @@ +package bjc.data; + +import java.util.Iterator; +import java.util.function.Function; + +/** + * An iterator that transforms values from one type to another. + * + * @author EVE + * + * @param <S> + * The source iterator type. + * + * @param <D> + * The destination iterator type. + */ +public class TransformIterator<S, D> implements Iterator<D> { + /* Our source of values. */ + private final Iterator<S> source; + /* Transform function. */ + private final Function<S, D> transform; + + /** + * Create a new transform iterator. + * + * @param source + * The source iterator to use. + * + * @param transform + * The transform to apply. + */ + public TransformIterator(final Iterator<S> source, final Function<S, D> transform) { + this.source = source; + this.transform = transform; + } + + @Override + public boolean hasNext() { + return source.hasNext(); + } + + @Override + public D next() { + return transform.apply(source.next()); + } +} diff --git a/src/main/java/bjc/data/Tree.java b/src/main/java/bjc/data/Tree.java new file mode 100644 index 0000000..ad2d677 --- /dev/null +++ b/src/main/java/bjc/data/Tree.java @@ -0,0 +1,432 @@ +package bjc.data; + +import java.util.function.BiFunction; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.function.UnaryOperator; + +import bjc.funcdata.FunctionalList; +import bjc.funcdata.IList; +import bjc.funcdata.bst.TreeLinearizationMethod; + +/** + * A node in a homogeneous tree. + * + * @author ben + * + * @param <ContainedType> + * The type contained in the tree. + */ +public class Tree<ContainedType> implements ITree<ContainedType> { + /* The data/label for this node. */ + private ContainedType data; + + /* The children of this node. */ + private IList<ITree<ContainedType>> children; + + /* Whether this node has children. */ + /* + * @NOTE Why have both this boolean and childCount? Why not just do a + * childCount == 0 whenever you'd check hasChildren? + * - Because hasChildren is set once and not reset, and really what + * it indicates is that children has been allocated. + */ + private boolean hasChildren; + /* The number of children this node has. */ + private int childCount = 0; + + /* The ID of this node. */ + private int ID; + /* The next ID to assign to a node. */ + private static int nextID = 0; + + /** + * Create a new leaf node in a tree. + */ + public Tree() { + this(null); + } + + /** + * Create a new leaf node in a tree. + * + * @param leaf + * The data to store as a leaf node. + */ + public Tree(final ContainedType leaf) { + data = leaf; + + hasChildren = false; + + ID = nextID++; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + public Tree(final ContainedType leaf, final IList<ITree<ContainedType>> childrn) { + this(leaf); + + hasChildren = true; + + childCount = childrn.getSize(); + + children = childrn; + } + + /** + * Create a new tree node with the specified children. + * + * @param leaf + * The data to hold in this node. + * + * @param childrn + * A list of children for this node. + */ + @SafeVarargs + public Tree(final ContainedType leaf, final ITree<ContainedType>... childrn) { + this(leaf); + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for(final ITree<ContainedType> child : childrn) { + children.add(child); + + childCount++; + } + } + + @Override + public void addChild(final ContainedType child) { + addChild(new Tree(child)); + } + + @Override + public void addChild(final ITree<ContainedType> child) { + if(hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public void prependChild(final ITree<ContainedType> child) { + if(hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.prepend(child); + } + + @Override + public void doForChildren(final Consumer<ITree<ContainedType>> action) { + if(childCount > 0) { + children.forEach(action); + } + } + + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public int revFind(final Predicate<ITree<ContainedType>> childPred) { + if(childCount == 0) { + return -1; + } + + for(int i = childCount - 1; i >= 0; i--) { + if(childPred.test(getChild(i))) return i; + } + + return -1; + } + + @Override + public void traverse(final TreeLinearizationMethod linearizationMethod, final Consumer<ContainedType> action) { + if(hasChildren) { + switch(linearizationMethod) { + case INORDER: + if(childCount != 2) { + final String msg = "Can only do in-order traversal for binary trees."; + + throw new IllegalArgumentException(msg); + } + + 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 <NewType, ReturnedType> ReturnedType collapse(final Function<ContainedType, NewType> leafTransform, + final BiFunction<ContainedType, IList<NewType>, NewType> nodeCollapser, + final Function<NewType, ReturnedType> resultTransformer) { + return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override + public ITree<ContainedType> flatMapTree(final Function<ContainedType, ITree<ContainedType>> mapper) { + if(hasChildren) { + final ITree<ContainedType> flatMappedData = mapper.apply(data); + + final IList<ITree<ContainedType>> mappedChildren = children + .map(child -> child.flatMapTree(mapper)); + + mappedChildren.forEach(flatMappedData::addChild); + + return flatMappedData; + } + + return mapper.apply(data); + } + + /* + * Do a collapse of this tree. + * + * @NOTE Why is this protected? I can't see any good reason someone'd + * want to override it. + */ + + protected <NewType> NewType internalCollapse(final Function<ContainedType, NewType> leafTransform, + final BiFunction<ContainedType, IList<NewType>, NewType> nodeCollapser) { + if(hasChildren) { + final IList<NewType> collapsedChildren = children.map(child -> { + final NewType collapsed = child.collapse(leafTransform, nodeCollapser, + subTreeVal -> subTreeVal); + + return collapsed; + }); + + return nodeCollapser.apply(data, collapsedChildren); + } + + return leafTransform.apply(data); + } + + protected void internalToString(final StringBuilder builder, final int indentLevel, final boolean initial) { + if(!initial) { + for(int i = 0; i < indentLevel; i++) { + builder.append(">\t"); + } + } + + builder.append("Node #"); + builder.append(ID); + builder.append(": "); + builder.append(data == null ? "(null)" : data.toString()); + builder.append("\n"); + + if(hasChildren) { + children.forEach(child -> { + if(child instanceof Tree<?>) { + final Tree<ContainedType> kid = (Tree<ContainedType>) child; + + kid.internalToString(builder, indentLevel + 1, false); + } else { + for(int i = 0; i < indentLevel + 1; i++) { + builder.append(">\t"); + } + + builder.append("Unknown node of type "); + builder.append(child.getClass().getName()); + builder.append("\n"); + } + }); + } + } + + @Override + public <MappedType> ITree<MappedType> rebuildTree(final Function<ContainedType, MappedType> leafTransformer, + final Function<ContainedType, MappedType> operatorTransformer) { + if(hasChildren) { + final IList<ITree<MappedType>> mappedChildren = children.map(child -> { + return child.rebuildTree(leafTransformer, operatorTransformer); + }); + + final MappedType mapData = operatorTransformer.apply(data); + return new Tree<>(mapData, mappedChildren); + } + + return new Tree<>(leafTransformer.apply(data)); + } + + @Override + public void selectiveTransform(final Predicate<ContainedType> nodePicker, + final UnaryOperator<ContainedType> transformer) { + if(hasChildren) { + children.forEach(child -> child.selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public ITree<ContainedType> topDownTransform( + final Function<ContainedType, TopDownTransformResult> transformPicker, + final UnaryOperator<ITree<ContainedType>> transformer) { + final TopDownTransformResult transformResult = transformPicker.apply(data); + + switch(transformResult) { + case PASSTHROUGH: + ITree<ContainedType> result = new Tree<>(data); + + if(hasChildren) { + children.forEach(child -> { + final ITree<ContainedType> kid = child.topDownTransform(transformPicker, + transformer); + + result.addChild(kid); + }); + } + + return result; + case SKIP: + return this; + case TRANSFORM: + return transformer.apply(this); + case RTRANSFORM: + return transformer.apply(this).topDownTransform(transformPicker, transformer); + case PUSHDOWN: + result = new Tree<>(data); + + if(hasChildren) { + children.forEach(child -> { + final ITree<ContainedType> kid = child.topDownTransform(transformPicker, + transformer); + + result.addChild(kid); + }); + } + + return transformer.apply(result); + case PULLUP: + final ITree<ContainedType> intermediateResult = transformer.apply(this); + + result = new Tree<>(intermediateResult.getHead()); + + intermediateResult.doForChildren(child -> { + final ITree<ContainedType> kid = child.topDownTransform(transformPicker, transformer); + + result.addChild(kid); + }); + + return result; + default: + final String msg = String.format("Recieved unknown transform result type %s", transformResult); + + throw new IllegalArgumentException(msg); + } + } + + @Override + public <TransformedType> TransformedType transformChild(final int childNo, + final Function<ITree<ContainedType>, TransformedType> transformer) { + if(childNo < 0 || childNo > childCount - 1) { + final String msg = String.format("Child index #%d is invalid", childNo); + + throw new IllegalArgumentException(msg); + } + + final ITree<ContainedType> selectedKid = children.getByIndex(childNo); + + return transformer.apply(selectedKid); + } + + @Override + public <TransformedType> TransformedType transformHead( + final Function<ContainedType, TransformedType> transformer) { + return transformer.apply(data); + } + + @Override + public void setHead(ContainedType dat) { + this.data = dat; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + childCount; + result = prime * result + (children == null ? 0 : children.hashCode()); + result = prime * result + (data == null ? 0 : data.hashCode()); + + return result; + } + + @Override + public String toString() { + final StringBuilder builder = new StringBuilder(); + + internalToString(builder, 1, true); + + /* Delete a trailing nl. */ + builder.deleteCharAt(builder.length() - 1); + + return builder.toString(); + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof Tree<?>)) return false; + + final Tree<?> other = (Tree<?>) obj; + + if(data == null) { + if(other.data != null) return false; + } else if(!data.equals(other.data)) return false; + + if(childCount != other.childCount) return false; + + if(children == null) { + if(other.children != null) return false; + } else if(!children.equals(other.children)) return false; + + return true; + } +} diff --git a/src/main/java/bjc/data/ValueToggle.java b/src/main/java/bjc/data/ValueToggle.java new file mode 100644 index 0000000..e79169f --- /dev/null +++ b/src/main/java/bjc/data/ValueToggle.java @@ -0,0 +1,60 @@ +package bjc.data; + +/** + * A simple implementation of {@link Toggle}. + * + * @author EVE + * + * @param <E> + * The type of value to toggle between. + */ +public class ValueToggle<E> implements Toggle<E> { + /* Our left value. */ + private final E lft; + /* Our right value. */ + private final E rght; + /* Our alignment. */ + private final BooleanToggle alignment; + + /** + * Create a new toggle. + * + * All toggles start right-aligned. + * + * @param left + * The value when the toggle is left-aligned. + * + * @param right + * The value when the toggle is right-aligned. + */ + public ValueToggle(final E left, final E right) { + lft = left; + + rght = right; + + alignment = new BooleanToggle(); + } + + @Override + public E get() { + if(alignment.get()) { + return lft; + } + + return rght; + } + + @Override + public E peek() { + if(alignment.peek()) { + return lft; + } + + return rght; + } + + @Override + public void set(final boolean isLeft) { + alignment.set(isLeft); + } +} diff --git a/src/main/java/bjc/data/internals/BoundLazy.java b/src/main/java/bjc/data/internals/BoundLazy.java new file mode 100644 index 0000000..728af8e --- /dev/null +++ b/src/main/java/bjc/data/internals/BoundLazy.java @@ -0,0 +1,137 @@ +package bjc.data.internals; + +import java.util.function.Function; +import java.util.function.Supplier; +import java.util.function.UnaryOperator; + +import bjc.data.IHolder; +import bjc.data.Lazy; +import bjc.funcdata.FunctionalList; +import bjc.funcdata.IList; + +/** + * Implements a lazy holder that has been bound. + * + * @author Ben Culkin + */ +@SuppressWarnings("javadoc") +public class BoundLazy<OldType, BoundContainedType> implements IHolder<BoundContainedType> { + /* The old value. */ + private final Supplier<IHolder<OldType>> oldSupplier; + + /* The function to use to transform the old value into a new value. */ + private final Function<OldType, IHolder<BoundContainedType>> binder; + + /* The bound value being held. */ + private IHolder<BoundContainedType> boundHolder; + + /* Whether the bound value has been actualized or not. */ + private boolean holderBound; + + /* Transformations currently pending on the bound value. */ + private final IList<UnaryOperator<BoundContainedType>> actions = new FunctionalList<>(); + + /** + * Create a new bound lazy value. + * + * @param supp + * The supplier of the old value. + * + * @param binder + * The function to use to bind the old value to the new one. + */ + public BoundLazy(final Supplier<IHolder<OldType>> supp, + final Function<OldType, IHolder<BoundContainedType>> binder) { + oldSupplier = supp; + this.binder = binder; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<BoundContainedType, IHolder<BoundType>> bindr) { + if(bindr == null) throw new NullPointerException("Binder must not be null"); + + /* Prepare a list of pending actions. */ + final IList<UnaryOperator<BoundContainedType>> pendingActions = new FunctionalList<>(); + actions.forEach(pendingActions::add); + + /* Create the new supplier of a value. */ + final Supplier<IHolder<BoundContainedType>> typeSupplier = () -> { + IHolder<BoundContainedType> oldHolder = boundHolder; + + /* Bind the value if it hasn't been bound before. */ + if(!holderBound) { + oldHolder = oldSupplier.get().unwrap(binder); + } + + /* Apply all the pending actions. */ + return pendingActions.reduceAux(oldHolder, (action, state) -> { + return state.transform(action); + }, (value) -> value); + }; + + return new BoundLazy<>(typeSupplier, bindr); + } + + @Override + public <NewType> Function<BoundContainedType, IHolder<NewType>> lift( + final Function<BoundContainedType, NewType> func) { + if(func == null) throw new NullPointerException("Function to lift must not be null"); + + return (val) -> { + return new Lazy<>(func.apply(val)); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<BoundContainedType, MappedType> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + /* Prepare a list of pending actions. */ + final IList<UnaryOperator<BoundContainedType>> pendingActions = new FunctionalList<>(); + actions.forEach(pendingActions::add); + + /* Prepare the new supplier. */ + final Supplier<MappedType> typeSupplier = () -> { + IHolder<BoundContainedType> oldHolder = boundHolder; + + /* Bound the value if it hasn't been bound. */ + if(!holderBound) { + oldHolder = oldSupplier.get().unwrap(binder); + } + + /* Apply pending actions. */ + return pendingActions.reduceAux(oldHolder.getValue(), (action, state) -> { + return action.apply(state); + }, (value) -> mapper.apply(value)); + }; + + return new Lazy<>(typeSupplier); + } + + @Override + public String toString() { + if(holderBound) return boundHolder.toString(); + + return "(unmaterialized)"; + } + + @Override + public IHolder<BoundContainedType> transform(final UnaryOperator<BoundContainedType> transformer) { + if(transformer == null) throw new NullPointerException("Transformer must not be null"); + + actions.add(transformer); + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<BoundContainedType, UnwrappedType> unwrapper) { + if(unwrapper == null) throw new NullPointerException("Unwrapper must not be null"); + + if(!holderBound) { + boundHolder = oldSupplier.get().unwrap(binder::apply); + } + + return boundHolder.unwrap(unwrapper); + } +} diff --git a/src/main/java/bjc/data/internals/BoundLazyPair.java b/src/main/java/bjc/data/internals/BoundLazyPair.java new file mode 100644 index 0000000..105b410 --- /dev/null +++ b/src/main/java/bjc/data/internals/BoundLazyPair.java @@ -0,0 +1,228 @@ +package bjc.data.internals; + +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Supplier; + +import bjc.data.IHolder; +import bjc.data.IPair; +import bjc.data.Identity; +import bjc.data.LazyPair; + +/** + * Implements a lazy pair that has been bound. + * + * @author Ben Culkin + */ +@SuppressWarnings("javadoc") +public class BoundLazyPair<OldLeft, OldRight, NewLeft, NewRight> implements IPair<NewLeft, NewRight> { + /* The supplier of the left value. */ + private final Supplier<OldLeft> leftSupplier; + /* The supplier of the right value. */ + private final Supplier<OldRight> rightSupplier; + + /* The binder to transform values. */ + private final BiFunction<OldLeft, OldRight, IPair<NewLeft, NewRight>> binder; + + /* The bound pair. */ + private IPair<NewLeft, NewRight> boundPair; + + /* Whether the pair has been bound yet. */ + private boolean pairBound; + + /** + * Create a new bound lazy pair. + * + * @param leftSupp + * The supplier for the left value. + * + * @param rightSupp + * The supplier for the right value. + * + * @param bindr + * The function to use to bind the left and right into a new + * pair. + */ + public BoundLazyPair(final Supplier<OldLeft> leftSupp, final Supplier<OldRight> rightSupp, + final BiFunction<OldLeft, OldRight, IPair<NewLeft, NewRight>> bindr) { + leftSupplier = leftSupp; + rightSupplier = rightSupp; + binder = bindr; + } + + @Override + public <BoundLeft, BoundRight> IPair<BoundLeft, BoundRight> bind( + final BiFunction<NewLeft, NewRight, IPair<BoundLeft, BoundRight>> bindr) { + if(bindr == null) throw new NullPointerException("Binder must not be null"); + + final IHolder<IPair<NewLeft, NewRight>> newPair = new Identity<>(boundPair); + final IHolder<Boolean> newPairMade = new Identity<>(pairBound); + + final Supplier<NewLeft> leftSupp = () -> { + if(!newPairMade.getValue()) { + /* + * If the pair hasn't been bound before, bind + * it. + */ + newPair.replace(binder.apply(leftSupplier.get(), rightSupplier.get())); + + newPairMade.replace(true); + } + + return newPair.unwrap((pair) -> pair.getLeft()); + }; + + final Supplier<NewRight> rightSupp = () -> { + if(!newPairMade.getValue()) { + /* + * If the pair hasn't been bound before, bind + * it. + */ + newPair.replace(binder.apply(leftSupplier.get(), rightSupplier.get())); + + newPairMade.replace(true); + } + + return newPair.unwrap((pair) -> pair.getRight()); + }; + + return new BoundLazyPair<>(leftSupp, rightSupp, bindr); + } + + @Override + public <BoundLeft> IPair<BoundLeft, NewRight> bindLeft( + final Function<NewLeft, IPair<BoundLeft, NewRight>> leftBinder) { + if(leftBinder == null) throw new NullPointerException("Left binder must not be null"); + + final Supplier<NewLeft> leftSupp = () -> { + IPair<NewLeft, NewRight> newPair = boundPair; + + if(!pairBound) { + /* + * If the pair hasn't been bound before, bind + * it. + */ + newPair = binder.apply(leftSupplier.get(), rightSupplier.get()); + } + + return newPair.getLeft(); + }; + + return new HalfBoundLazyPair<>(leftSupp, leftBinder); + } + + @Override + public <BoundRight> IPair<NewLeft, BoundRight> bindRight( + final Function<NewRight, IPair<NewLeft, BoundRight>> rightBinder) { + if(rightBinder == null) throw new NullPointerException("Right binder must not be null"); + + final Supplier<NewRight> rightSupp = () -> { + IPair<NewLeft, NewRight> newPair = boundPair; + + if(!pairBound) { + /* + * If the pair hasn't been bound before, bind + * it. + */ + newPair = binder.apply(leftSupplier.get(), rightSupplier.get()); + } + + return newPair.getRight(); + }; + + return new HalfBoundLazyPair<>(rightSupp, rightBinder); + } + + @Override + public <OtherLeft, OtherRight, CombinedLeft, CombinedRight> IPair<CombinedLeft, CombinedRight> combine( + final IPair<OtherLeft, OtherRight> otherPair, + final BiFunction<NewLeft, OtherLeft, CombinedLeft> leftCombiner, + final BiFunction<NewRight, OtherRight, CombinedRight> rightCombiner) { + if(otherPair == null) { + throw new NullPointerException("Other pair must not be null"); + } else if(leftCombiner == null) { + throw new NullPointerException("Left combiner must not be null"); + } else if(rightCombiner == null) { + throw new NullPointerException("Right combiner must not be null"); + } + + return otherPair.bind((otherLeft, otherRight) -> { + return bind((leftVal, rightVal) -> { + CombinedLeft cLeft = leftCombiner.apply(leftVal, otherLeft); + CombinedRight cRight = rightCombiner.apply(rightVal, otherRight); + + return new LazyPair<>(cLeft, cRight); + }); + }); + } + + @Override + public <NewLeftType> IPair<NewLeftType, NewRight> mapLeft(final Function<NewLeft, NewLeftType> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + final Supplier<NewLeftType> leftSupp = () -> { + if(!pairBound) { + final NewLeft leftVal = binder.apply(leftSupplier.get(), rightSupplier.get()).getLeft(); + + return mapper.apply(leftVal); + } + + return mapper.apply(boundPair.getLeft()); + }; + + final Supplier<NewRight> rightSupp = () -> { + if(!pairBound) return binder.apply(leftSupplier.get(), rightSupplier.get()).getRight(); + + return boundPair.getRight(); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public <NewRightType> IPair<NewLeft, NewRightType> mapRight(final Function<NewRight, NewRightType> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + final Supplier<NewLeft> leftSupp = () -> { + if(!pairBound) return binder.apply(leftSupplier.get(), rightSupplier.get()).getLeft(); + + return boundPair.getLeft(); + }; + + final Supplier<NewRightType> rightSupp = () -> { + if(!pairBound) { + final NewRight rightVal = binder.apply(leftSupplier.get(), rightSupplier.get()) + .getRight(); + + return mapper.apply(rightVal); + } + + return mapper.apply(boundPair.getRight()); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public <MergedType> MergedType merge(final BiFunction<NewLeft, NewRight, MergedType> merger) { + if(merger == null) throw new NullPointerException("Merger must not be null"); + + if(!pairBound) { + /* + * If the pair isn't bound yet, bind it. + */ + boundPair = binder.apply(leftSupplier.get(), rightSupplier.get()); + + pairBound = true; + } + + return boundPair.merge(merger); + } + + @Override + public String toString() { + if(pairBound) return boundPair.toString(); + + return "(un-materialized)"; + } +} diff --git a/src/main/java/bjc/data/internals/BoundListHolder.java b/src/main/java/bjc/data/internals/BoundListHolder.java new file mode 100644 index 0000000..8f8cab4 --- /dev/null +++ b/src/main/java/bjc/data/internals/BoundListHolder.java @@ -0,0 +1,81 @@ +package bjc.data.internals; + +import java.util.function.Function; +import java.util.function.UnaryOperator; + +import bjc.data.IHolder; +import bjc.data.ListHolder; +import bjc.funcdata.IList; + +/** + * Holds a list, converted into a holder. + * + * @author Ben Culkin + */ +@SuppressWarnings("javadoc") +public class BoundListHolder<ContainedType> implements IHolder<ContainedType> { + /* The list of contained holders. */ + private final IList<IHolder<ContainedType>> heldHolders; + + /** + * Create a new list of holders. + * + * @param toHold + * The list of holders to, well, hold. + */ + public BoundListHolder(final IList<IHolder<ContainedType>> toHold) { + heldHolders = toHold; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<ContainedType, IHolder<BoundType>> binder) { + if(binder == null) throw new NullPointerException("Binder must not be null"); + + final IList<IHolder<BoundType>> boundHolders = heldHolders.map((containedHolder) -> { + return containedHolder.bind(binder); + }); + + return new BoundListHolder<>(boundHolders); + } + + @Override + public <NewType> Function<ContainedType, IHolder<NewType>> lift(final Function<ContainedType, NewType> func) { + if(func == null) throw new NullPointerException("Function to lift must not be null"); + + return (val) -> { + return new ListHolder<>(func.apply(val)); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<ContainedType, MappedType> mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + final IList<IHolder<MappedType>> mappedHolders = heldHolders.map((containedHolder) -> { + return containedHolder.map(mapper); + }); + + return new BoundListHolder<>(mappedHolders); + } + + @Override + public IHolder<ContainedType> transform(final UnaryOperator<ContainedType> transformer) { + if(transformer == null) throw new NullPointerException("Transformer must not be null"); + + heldHolders.forEach((containedHolder) -> { + containedHolder.transform(transformer); + }); + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<ContainedType, UnwrappedType> unwrapper) { + if(unwrapper == null) throw new NullPointerException("Unwrapper must not be null"); + + /* + * @NOTE Is there another way we could want to do this? + */ + return heldHolders.randItem().unwrap(unwrapper); + } +} diff --git a/src/main/java/bjc/data/internals/HalfBoundLazyPair.java b/src/main/java/bjc/data/internals/HalfBoundLazyPair.java new file mode 100644 index 0000000..4f28012 --- /dev/null +++ b/src/main/java/bjc/data/internals/HalfBoundLazyPair.java @@ -0,0 +1,177 @@ +package bjc.data.internals; + +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Supplier; + +import bjc.data.IHolder; +import bjc.data.IPair; +import bjc.data.Identity; +import bjc.data.LazyPair; + +/* + * @NOTE + * I am not convinced that this code works correctly. Tests should be + * written to make sure things only ever get instantiated once. + * + * Namely, my main concern is to whether the places that bind the pair + * without setting pairBound are doing the right thing. + */ +/** + * A lazy pair, with only one side bound. + * + * @author Ben Culkin + */ +@SuppressWarnings("javadoc") +public class HalfBoundLazyPair<OldType, NewLeft, NewRight> implements IPair<NewLeft, NewRight> { + /* The supplier of the old value. */ + private final Supplier<OldType> oldSupplier; + + /* The function to transform the old value into a new pair. */ + private final Function<OldType, IPair<NewLeft, NewRight>> binder; + + /* The new bound pair. */ + private IPair<NewLeft, NewRight> boundPair; + /* Has the pair been bound yet or not? */ + private boolean pairBound; + + /** + * Create a new half-bound lazy pair. + * + * @param oldSupp + * The supplier of the old value. + * + * @param bindr + * The function to use to create the pair from the old value. + */ + public HalfBoundLazyPair(final Supplier<OldType> oldSupp, + final Function<OldType, IPair<NewLeft, NewRight>> bindr) { + oldSupplier = oldSupp; + binder = bindr; + } + + @Override + public <BoundLeft, BoundRight> IPair<BoundLeft, BoundRight> bind( + final BiFunction<NewLeft, NewRight, IPair<BoundLeft, BoundRight>> bindr) { + final IHolder<IPair<NewLeft, NewRight>> newPair = new Identity<>(boundPair); + final IHolder<Boolean> newPairMade = new Identity<>(pairBound); + + final Supplier<NewLeft> leftSupp = () -> { + if(!newPairMade.getValue()) { + /* Bind the pair if it hasn't been bound yet. */ + newPair.replace(binder.apply(oldSupplier.get())); + newPairMade.replace(true); + } + + return newPair.unwrap((pair) -> pair.getLeft()); + }; + + final Supplier<NewRight> rightSupp = () -> { + if(!newPairMade.getValue()) { + /* Bind the pair if it hasn't been bound yet. */ + newPair.replace(binder.apply(oldSupplier.get())); + newPairMade.replace(true); + } + + return newPair.unwrap((pair) -> pair.getRight()); + }; + + return new BoundLazyPair<>(leftSupp, rightSupp, bindr); + } + + @Override + public <BoundLeft> IPair<BoundLeft, NewRight> bindLeft( + final Function<NewLeft, IPair<BoundLeft, NewRight>> leftBinder) { + final Supplier<NewLeft> leftSupp = () -> { + IPair<NewLeft, NewRight> newPair = boundPair; + + if(!pairBound) { + newPair = binder.apply(oldSupplier.get()); + } + + return newPair.getLeft(); + }; + + return new HalfBoundLazyPair<>(leftSupp, leftBinder); + } + + @Override + public <BoundRight> IPair<NewLeft, BoundRight> bindRight( + final Function<NewRight, IPair<NewLeft, BoundRight>> rightBinder) { + final Supplier<NewRight> rightSupp = () -> { + IPair<NewLeft, NewRight> newPair = boundPair; + + if(!pairBound) { + newPair = binder.apply(oldSupplier.get()); + } + + return newPair.getRight(); + }; + + return new HalfBoundLazyPair<>(rightSupp, rightBinder); + } + + @Override + public <OtherLeft, OtherRight, CombinedLeft, CombinedRight> IPair<CombinedLeft, CombinedRight> combine( + final IPair<OtherLeft, OtherRight> otherPair, + final BiFunction<NewLeft, OtherLeft, CombinedLeft> leftCombiner, + final BiFunction<NewRight, OtherRight, CombinedRight> rightCombiner) { + return otherPair.bind((otherLeft, otherRight) -> { + return bind((leftVal, rightVal) -> { + CombinedLeft cLeft = leftCombiner.apply(leftVal, otherLeft); + CombinedRight cRight = rightCombiner.apply(rightVal, otherRight); + + return new LazyPair<>(cLeft, cRight); + }); + }); + } + + @Override + public <NewLeftType> IPair<NewLeftType, NewRight> mapLeft(final Function<NewLeft, NewLeftType> mapper) { + final Supplier<NewLeftType> leftSupp = () -> { + if(pairBound) return mapper.apply(boundPair.getLeft()); + + final NewLeft leftVal = binder.apply(oldSupplier.get()).getLeft(); + + return mapper.apply(leftVal); + }; + + final Supplier<NewRight> rightSupp = () -> { + if(pairBound) return boundPair.getRight(); + + return binder.apply(oldSupplier.get()).getRight(); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public <NewRightType> IPair<NewLeft, NewRightType> mapRight(final Function<NewRight, NewRightType> mapper) { + final Supplier<NewLeft> leftSupp = () -> { + if(pairBound) return boundPair.getLeft(); + + return binder.apply(oldSupplier.get()).getLeft(); + }; + + final Supplier<NewRightType> rightSupp = () -> { + if(pairBound) return mapper.apply(boundPair.getRight()); + + final NewRight rightVal = binder.apply(oldSupplier.get()).getRight(); + + return mapper.apply(rightVal); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public <MergedType> MergedType merge(final BiFunction<NewLeft, NewRight, MergedType> merger) { + if(!pairBound) { + boundPair = binder.apply(oldSupplier.get()); + + pairBound = true; + } + + return boundPair.merge(merger); + } +} diff --git a/src/main/java/bjc/data/internals/WrappedLazy.java b/src/main/java/bjc/data/internals/WrappedLazy.java new file mode 100644 index 0000000..17d2309 --- /dev/null +++ b/src/main/java/bjc/data/internals/WrappedLazy.java @@ -0,0 +1,83 @@ +package bjc.data.internals; + +import java.util.function.Function; +import java.util.function.UnaryOperator; + +import bjc.data.IHolder; +import bjc.data.Lazy; + +/** + * A wrapped lazy value. + * + * @author Ben Culkin + * @param <ContainedType> + * The type of the wrapped value. + */ +public class WrappedLazy<ContainedType> implements IHolder<ContainedType> { + /* Held value. */ + private final IHolder<IHolder<ContainedType>> held; + + /** + * Create a new wrapped lazy value. + * + * @param wrappedHolder + * The holder to make lazy. + */ + public WrappedLazy(final IHolder<ContainedType> wrappedHolder) { + held = new Lazy<>(wrappedHolder); + } + + /* + * This has an extra parameter, because otherwise it erases to the same + * as the public one. + * + * This is a case where reified generics would be useful, because then + * the compiler could know which one we meant without the dummy + * parameter. + */ + private WrappedLazy(final IHolder<IHolder<ContainedType>> wrappedHolder, + @SuppressWarnings("unused") final boolean dummy) { + held = wrappedHolder; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<ContainedType, IHolder<BoundType>> binder) { + final IHolder<IHolder<BoundType>> newHolder = held.map((containedHolder) -> { + return containedHolder.bind(binder); + }); + + return new WrappedLazy<>(newHolder, false); + } + + @Override + public <NewType> Function<ContainedType, IHolder<NewType>> lift(final Function<ContainedType, NewType> func) { + return (val) -> { + return new Lazy<>(func.apply(val)); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<ContainedType, MappedType> mapper) { + final IHolder<IHolder<MappedType>> newHolder = held.map((containedHolder) -> { + return containedHolder.map(mapper); + }); + + return new WrappedLazy<>(newHolder, false); + } + + @Override + public IHolder<ContainedType> transform(final UnaryOperator<ContainedType> transformer) { + held.transform((containedHolder) -> { + return containedHolder.transform(transformer); + }); + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<ContainedType, UnwrappedType> unwrapper) { + return held.unwrap((containedHolder) -> { + return containedHolder.unwrap(unwrapper); + }); + } +} diff --git a/src/main/java/bjc/data/internals/WrappedOption.java b/src/main/java/bjc/data/internals/WrappedOption.java new file mode 100644 index 0000000..eb4d120 --- /dev/null +++ b/src/main/java/bjc/data/internals/WrappedOption.java @@ -0,0 +1,96 @@ +package bjc.data.internals; + +import java.util.function.Function; +import java.util.function.UnaryOperator; + +import bjc.data.IHolder; +import bjc.data.Option; + +/** + * A wrapped optional value. + * + * @author Ben Culkin. + * @param <ContainedType> + * The wrapped type. + */ +public class WrappedOption<ContainedType> implements IHolder<ContainedType> { + /* The held value. */ + private final IHolder<IHolder<ContainedType>> held; + + /** + * Create a new wrapped option. + * + * @param seedValue + * The value to wrap. + */ + public WrappedOption(final IHolder<ContainedType> seedValue) { + held = new Option<>(seedValue); + } + + /* + * The dummy parameter is to ensure the compiler can pick the right + * method, because without this method erases to the same type as the + * public one. + */ + private WrappedOption(final IHolder<IHolder<ContainedType>> toHold, + @SuppressWarnings("unused") final boolean dummy) { + held = toHold; + } + + @Override + public <BoundType> IHolder<BoundType> bind(final Function<ContainedType, IHolder<BoundType>> binder) { + final IHolder<IHolder<BoundType>> newHolder = held.map((containedHolder) -> { + return containedHolder.bind((containedValue) -> { + if(containedValue == null) return new Option<>(null); + + return binder.apply(containedValue); + }); + }); + + return new WrappedOption<>(newHolder, false); + } + + @Override + public <NewType> Function<ContainedType, IHolder<NewType>> lift(final Function<ContainedType, NewType> func) { + return (val) -> { + return new Option<>(func.apply(val)); + }; + } + + @Override + public <MappedType> IHolder<MappedType> map(final Function<ContainedType, MappedType> mapper) { + final IHolder<IHolder<MappedType>> newHolder = held.map((containedHolder) -> { + return containedHolder.map((containedValue) -> { + if(containedValue == null) return null; + + return mapper.apply(containedValue); + }); + }); + + return new WrappedOption<>(newHolder, false); + } + + @Override + public IHolder<ContainedType> transform(final UnaryOperator<ContainedType> transformer) { + held.transform((containedHolder) -> { + return containedHolder.transform((containedValue) -> { + if(containedValue == null) return null; + + return transformer.apply(containedValue); + }); + }); + + return this; + } + + @Override + public <UnwrappedType> UnwrappedType unwrap(final Function<ContainedType, UnwrappedType> unwrapper) { + return held.unwrap((containedHolder) -> { + return containedHolder.unwrap((containedValue) -> { + if(containedValue == null) return null; + + return unwrapper.apply(containedValue); + }); + }); + } +} diff --git a/src/main/java/bjc/esodata/AbbrevMap.java b/src/main/java/bjc/esodata/AbbrevMap.java new file mode 100644 index 0000000..048577d --- /dev/null +++ b/src/main/java/bjc/esodata/AbbrevMap.java @@ -0,0 +1,207 @@ +package bjc.esodata; + +import java.util.Arrays; +import java.util.HashSet; +import java.util.Set; + +import bjc.funcdata.FunctionalMap; +import bjc.funcdata.IMap; + +// /** +// * Represents a mapping from a set of strings to a mapping of all unambiguous +// * prefixes of their respective strings. +// * +// * This works the same as Ruby's Abbrev module. +// * +// * @author EVE +// */ +// public class AbbrevMap { +// /* All of the words we have abbreviations for. */ +// private final Set<String> wrds; + +// /* Maps abbreviations to their strings. */ +// private IMap<String, String> abbrevMap; + +// /* Counts how many times we've seen a substring. */ +// private Set<String> seen; + +// /* Maps ambiguous abbreviations to the strings they could be. */ +// private SetMultimap<String, String> ambMap; + +// /** +// * Create a new abbreviation map. +// * +// * @param words +// * The initial set of words to put in the map. +// */ +// public AbbrevMap(final String... words) { +// wrds = new HashSet<>(Arrays.asList(words)); + +// recalculate(); +// } + +// /** +// * Recalculate all the abbreviations in this map. +// * +// * This may be needed after certain operations to ensure that all of the +// * results are correct. +// */ +// public void recalculate() { +// abbrevMap = new FunctionalMap<>(); + +// ambMap = HashMultimap.create(); + +// seen = new HashSet<>(); + +// for(final String word : wrds) { +// intAddWord(word); +// } +// } + +// /** +// * Adds words to the abbreviation map. +// * +// * @param words +// * The words to add to the abbreviation map. +// */ +// public void addWords(final String... words) { +// wrds.addAll(Arrays.asList(words)); + +// for(final String word : words) { +// intAddWord(word); +// } +// } + +// /* Actually add abbreviations of a word. */ +// private void intAddWord(final String word) { +// /* A word always abbreviates to itself. */ +// abbrevMap.put(word, word); + +// /* Skip blank words. */ +// if(word.equals("")) return; + +// /* Handle each possible abbreviation. */ +// for(int i = word.length(); i > 0; i--) { +// final String subword = word.substring(0, i); + +// if(seen.contains(subword)) { +// /* +// * Remove a mapping if its ambiguous and not a +// * whole word. +// */ +// if(abbrevMap.containsKey(subword) && !wrds.contains(subword)) { +// final String oldword = abbrevMap.remove(subword); + +// ambMap.put(subword, oldword); +// ambMap.put(subword, word); +// } else if(!wrds.contains(subword)) { +// ambMap.put(subword, word); +// } +// } else { +// seen.add(subword); + +// abbrevMap.put(subword, word); +// } +// } +// } + +// /** +// * Removes words from the abbreviation map. +// * +// * NOTE: There may be inconsistent behavior after removing a word from +// * the map. Use {@link AbbrevMap#recalculate()} to fix it if it occurs. +// * +// * @param words +// * The words to remove. +// */ +// public void removeWords(final String... words) { +// wrds.removeAll(Arrays.asList(words)); + +// for(final String word : words) { +// intRemoveWord(word); +// } +// } + +// /* Actually remove a word. */ +// private void intRemoveWord(final String word) { +// /* Skip blank words. */ +// if(word.equals("")) return; + +// /* Handle each possible abbreviation. */ +// for(int i = word.length(); i > 0; i--) { +// final String subword = word.substring(0, i); + +// if(abbrevMap.containsKey(subword)) { +// abbrevMap.remove(subword); +// } else { +// ambMap.remove(subword, word); + +// final Set<String> possWords = ambMap.get(subword); + +// if(possWords.size() == 0) { +// seen.remove(subword); +// } else if(possWords.size() == 1) { +// /* +// * An abbreviation went from ambiguous +// * to non-ambiguous. +// */ +// final String newWord = possWords.iterator().next(); + +// abbrevMap.put(subword, newWord); +// ambMap.remove(subword, newWord); +// } +// } +// } +// } + +// /** +// * Convert an abbreviation into all the strings it could abbreviate +// * into. +// * +// * @param abbrev +// * The abbreviation to convert. +// * +// * @return All the expansions for the provided abbreviation. +// */ +// public String[] deabbrev(final String abbrev) { +// if(abbrevMap.containsKey(abbrev)) { +// return new String[] { +// abbrevMap.get(abbrev) +// }; +// } + +// return ambMap.get(abbrev).toArray(new String[0]); +// } + +// @Override +// public int hashCode() { +// final int prime = 31; + +// int result = 1; +// result = prime * result + (wrds == null ? 0 : wrds.hashCode()); + +// return result; +// } + +// @Override +// public boolean equals(final Object obj) { +// if(this == obj) return true; +// if(obj == null) return false; +// if(!(obj instanceof AbbrevMap)) return false; + +// final AbbrevMap other = (AbbrevMap) obj; + +// if(wrds == null) { +// if(other.wrds != null) return false; +// } else if(!wrds.equals(other.wrds)) return false; + +// return true; +// } + +// @Override +// public String toString() { +// final String fmt = "AbbrevMap [wrds=%s, abbrevMap=%s, seen=%s, ambMap=%s]"; + +// return String.format(fmt, wrds, abbrevMap, seen, ambMap); +// } +// } diff --git a/src/main/java/bjc/esodata/DefaultList.java b/src/main/java/bjc/esodata/DefaultList.java new file mode 100644 index 0000000..e4b2806 --- /dev/null +++ b/src/main/java/bjc/esodata/DefaultList.java @@ -0,0 +1,116 @@ +package bjc.esodata; + +import java.util.AbstractList; +import java.util.ArrayList; +import java.util.List; + +/** + * A list that has a default value that out-of-bounds accesses return. + * + * @author Ben Culkin + * @param <ValueType> + * The type of the values contained in the list. + */ +public class DefaultList<ValueType> extends AbstractList<ValueType> { + /* + * @NOTE 9/17/18 + * + * A possible feature to add would be the ability to set a 'default + * index', so that the default value is 'whatever is at that list index' + * + * Of course, this would cause an exception if that index was out of + * bounds, but what are you going to do? + */ + + private ValueType defVal; + + private List<ValueType> backing; + + /** + * Create a new DefaultList. + */ + public DefaultList() { + this(new ArrayList<>(), null); + } + + /** + * Create a new DefaultList, with a set default value. + * + * @param defVal + * The default value for the list. + */ + public DefaultList(ValueType defVal) { + this(new ArrayList<>(), defVal); + } + + /** + * Create a new DefaultList, with a specific backing list. + * + * @param backer + * The backing list to use. + * + */ + public DefaultList(List<ValueType> backer) { + this(backer, null); + } + + /** + * Create a new DefaultList, with a set default value. + * + * @param backer + * The backing list to use. + * + * @param defVal + * The default value for the list. + */ + public DefaultList(List<ValueType> backer, ValueType defVal) { + this.defVal = defVal; + + this.backing = backer; + } + + /** + * Get the default value. + * + * @return The default value. + */ + public ValueType getDefault() { + return defVal; + } + + /** + * Set the default value. + * + * @param defVal The default value. + */ + public void setDefault(ValueType defVal) { + this.defVal = defVal; + } + + @Override + public ValueType get(int idx) { + if (idx < 0 || idx >= backing.size()) return defVal; + + return backing.get(idx); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public ValueType set(int idx, ValueType val) { + return backing.set(idx, val); + } + + @Override + public void add(int idx, ValueType val) { + backing.add(idx, val); + } + + @Override + public ValueType remove(int idx) { + return backing.remove(idx); + } +} diff --git a/src/main/java/bjc/esodata/Directory.java b/src/main/java/bjc/esodata/Directory.java new file mode 100644 index 0000000..4147e17 --- /dev/null +++ b/src/main/java/bjc/esodata/Directory.java @@ -0,0 +1,107 @@ +package bjc.esodata; + +/** + * Represents a hierarchical map. + * + * What's useful about this is that you can hand sub-directories to people and + * be able to ensure that they can't write outside of it. + * + * @param <K> + * The key type of the map. + * @param <V> + * The value type of the map. + */ +public interface Directory<K, V> { + /** + * Retrieves a given sub-directory. + * + * @param key + * The key to retrieve the sub-directory for. + * + * @return The sub-directory under that name. + * + * @throws IllegalArgumentException + * If the given sub-directory doesn't exist. + */ + Directory<K, V> getSubdirectory(K key); + + /** + * Check if a given sub-directory exists. + * + * @param key + * The key to look for the sub-directory under. + * + * @return Whether or not a sub-directory of that name exists. + */ + boolean hasSubdirectory(K key); + + /** + * Insert a sub-directory into the dictionary. + * + * @param key + * The name of the new sub-directory + * @param value + * The sub-directory to insert + * + * @return The old sub-directory attached to this key, or null if such a + * sub-directory didn't exist + */ + Directory<K, V> putSubdirectory(K key, Directory<K, V> value); + + /** + * Create a new sub-directory. + * + * Will fail if a sub-directory of that name already exists. + * + * @param key + * The name of the new sub-directory. + * + * @return The new sub-directory, or null if one by that name already + * exists. + */ + default Directory<K, V> newSubdirectory(final K key) { + if(hasSubdirectory(key)) return null; + + final Directory<K, V> dir = new SimpleDirectory<>(); + + putSubdirectory(key, dir); + + return dir; + } + + /** + * Check if the directory contains a data-item under the given key. + * + * @param key + * The key to check for. + * + * @return Whether or not there is a data item for the given key. + */ + boolean containsKey(K key); + + /** + * Retrieve a given data-item from the directory. + * + * @param key + * The key to retrieve data for. + * + * @return The value for the given key. + * + * @throws IllegalArgumentException + * If no value exists for the given key. + */ + V getKey(K key); + + /** + * Insert a data-item into the directory. + * + * @param key + * The key to insert into. + * + * @param val + * The value to insert. + * + * @return The old value of key, or null if such a value didn't exist. + */ + V putKey(K key, V val); +} diff --git a/src/main/java/bjc/esodata/DoubleSided.java b/src/main/java/bjc/esodata/DoubleSided.java new file mode 100644 index 0000000..6ecbdcf --- /dev/null +++ b/src/main/java/bjc/esodata/DoubleSided.java @@ -0,0 +1,24 @@ +package bjc.esodata; + +/** + * Interface for a double-sided object. + * + * @author bjculkin + * + */ +public interface DoubleSided { + /** + * Flips the object. + * + * The active side becomes inactive, and the inactive side becomes + * active. + */ + void flip(); + + /** + * Check which side of the object is active; + * + * @return True if the front side is active, false otherwise. + */ + boolean currentSide(); +} diff --git a/src/main/java/bjc/esodata/DoubleTape.java b/src/main/java/bjc/esodata/DoubleTape.java new file mode 100644 index 0000000..c36fcff --- /dev/null +++ b/src/main/java/bjc/esodata/DoubleTape.java @@ -0,0 +1,189 @@ +package bjc.esodata; + +/** + * Double-sided tape is essentially two tapes stuck together with a shared + * cursor. + * + * The main way a double-sided tape differs is that it can be flipped, allowing + * access to another set of data. + * + * However, there is only one cursor, and the position of the cursor on one side + * is the inverse of the position on the other side. + * + * When one side is extended, a null will be inserted into the inactive side + * regardless of the auto-extension policy of the tape. The policy will still be + * respected for the active side. + * + * All operations that refer to the tape refer to the currently active side of + * the tape, except for flip. + * + * Flip refers to the entire tape for 'obvious' reasons. + * + * @param <T> + * The element type of the tape. + * + * @author bjculkin + */ +public class DoubleTape<T> implements Tape<T>, DoubleSided { + private boolean frontActive; + + /* The front-side of the tape. */ + private Tape<T> front; + /* The back-side of the tape. */ + private Tape<T> back; + + /** Create a new empty double-sided tape that doesn't autoextend. */ + public DoubleTape() { + this(false); + } + + /** + * Create a new empty double-sided tape that follows the specified + * auto-extension policy. + * + * @param autoExtnd + * Whether or not to auto-extend the tape to the right w/ nulls. + */ + public DoubleTape(final boolean autoExtnd) { + front = new SingleTape<>(autoExtnd); + back = new SingleTape<>(autoExtnd); + + frontActive = true; + } + + @Override + public T item() { + return front.item(); + } + + @Override + public void item(final T itm) { + front.item(itm); + } + + @Override + public int size() { + return front.size(); + } + + @Override + public int position() { + return front.position(); + } + + @Override + public void insertBefore(final T itm) { + front.insertBefore(itm); + back.insertAfter(null); + } + + @Override + public void insertAfter(final T itm) { + front.insertAfter(itm); + back.insertBefore(itm); + } + + @Override + public T remove() { + back.remove(); + + return front.remove(); + } + + @Override + public void first() { + front.first(); + back.last(); + } + + @Override + public void last() { + front.last(); + back.first(); + } + + @Override + public boolean left() { + return left(1); + } + + @Override + public boolean left(final int amt) { + final boolean succ = front.left(amt); + + if(succ) { + back.right(amt); + } + + return succ; + } + + @Override + public boolean right() { + return right(1); + } + + @Override + public boolean right(final int amt) { + final boolean succ = front.right(amt); + + if(succ) { + back.left(amt); + } + + return succ; + } + + public boolean seekTo(int tgtPos) { + return front.seekTo(tgtPos); + } + + @Override + public void flip() { + final Tape<T> tmp = front; + + front = back; + + back = tmp; + + frontActive = !frontActive; + } + + @Override + public boolean currentSide() { + return frontActive; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + (back == null ? 0 : back.hashCode()); + result = prime * result + (front == null ? 0 : front.hashCode()); + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof DoubleTape<?>)) return false; + + final DoubleTape<?> other = (DoubleTape<?>) obj; + + if(back == null) { + if(other.back != null) return false; + } else if(!back.equals(other.back)) return false; + + if(front == null) { + if(other.front != null) return false; + } else if(!front.equals(other.front)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("DoubleTape [front=%s, back=%s]", front, back); + } +} diff --git a/src/main/java/bjc/esodata/MapSet.java b/src/main/java/bjc/esodata/MapSet.java new file mode 100644 index 0000000..cbb5d34 --- /dev/null +++ b/src/main/java/bjc/esodata/MapSet.java @@ -0,0 +1,178 @@ +package bjc.esodata; + +import java.util.AbstractMap; +import java.util.Collection; +import java.util.HashMap; +import java.util.Map; +import java.util.Set; + +/** + * A string-keyed set of maps. + * + * @author bjculkin + * + * @param <KeyType> + * The key type of the maps. + * @param <ValueType> + * The value type of the maps. + */ +public class MapSet<KeyType, ValueType> extends AbstractMap<KeyType, ValueType> { + private Map<String, Map<KeyType, ValueType>> backing; + + private Map<KeyType, ValueType> currentMap = null; + + /** + * Create a new set of maps. + */ + public MapSet() { + backing = new HashMap<>(); + } + + /** + * Create a new set of maps, with the specified set of maps. + * + * @param back + * The set of maps to use. + */ + public MapSet(Map<String, Map<KeyType, ValueType>> back) { + backing = back; + } + + /** + * Add a keyed map. + * + * @param key + * The key for the map. + * @param map + * The map itself. + */ + public void addMap(String key, Map<KeyType, ValueType> map) { + backing.put(key, map); + } + + /** + * Clear out the contents of the set + */ + public void clearMap() { + currentMap = null; + + backing.clear(); + } + + /** + * Check if there is a map attached to the specified key. + * + * @param key + * The key to look for. + * @return Whether or not there is anything attached to the key. + */ + public boolean containsMap(String key) { + return backing.containsKey(key); + } + + /** + * Get the map attached to a specified key. + * + * @param key + * The key to look for. + * @return The map attached to the key. + */ + public Map<KeyType, ValueType> getMap(String key) { + return backing.get(key); + } + + /** + * Get all of the backing entries. + * + * @return The backing entries. + */ + public Set<Map.Entry<String, Map<KeyType, ValueType>>> getMapEntries() { + return backing.entrySet(); + } + + /** + * Get all of the keys. + * + * @return The keys currently in use. + */ + public Set<String> getMapKeys() { + return backing.keySet(); + } + + /** + * Get all of the keyed maps. + * + * @return The keyed maps. + */ + public Collection<Map<KeyType, ValueType>> getMapValues() { + return backing.values(); + } + + /** + * Set the current map. + * + * @param key + * The key to use as the current map. + * @return False if there is no map attached to the key, true otherwise. + */ + public boolean setMap(String key) { + if (!backing.containsKey(key)) return false; + + currentMap = backing.get(key); + + return true; + } + + /** + * Sets the current map, or creates a new one if there isn't one + * attached to that key. + * + * @param key + * The key to use as the current map. + */ + public void setCreateMap(String key) { + if (!backing.containsKey(key)) { + currentMap = new HashMap<>(); + + backing.put(key, currentMap); + + return; + } + + currentMap = backing.get(key); + } + + /** + * Set the current map, or bind a map to it. + * + * @param key + * The key to set or bind. + * @param map + * The map to bind to the key if it isn't present. + */ + public void setPutMap(String key, Map<KeyType, ValueType> map) { + if (!backing.containsKey(key)) { + currentMap = map; + + backing.put(key, map); + + return; + } + + currentMap = backing.get(key); + } + + @Override + public Set<Map.Entry<KeyType, ValueType>> entrySet() { + if (currentMap == null) throw new NullPointerException("Current map is not set"); + + return currentMap.entrySet(); + } + + @Override + public ValueType put(KeyType key, ValueType value) { + if (currentMap == null) throw new NullPointerException("Current map is not set"); + + return currentMap.put(key, value); + } +} diff --git a/src/main/java/bjc/esodata/PushdownMap.java b/src/main/java/bjc/esodata/PushdownMap.java new file mode 100644 index 0000000..5db5f05 --- /dev/null +++ b/src/main/java/bjc/esodata/PushdownMap.java @@ -0,0 +1,158 @@ +package bjc.esodata; + +import java.util.function.BiConsumer; +import java.util.function.Consumer; +import java.util.function.Function; + +import bjc.funcdata.FunctionalMap; +import bjc.funcdata.IList; +import bjc.funcdata.IMap; + +/** + * A variant of a map where inserting a duplicate key shadows the existing value + * instead of replacing it. + * + * This could be useful for things like variable scopes. + * + * @author EVE + * + * @param <KeyType> + * The key of the map. + * + * @param <ValueType> + * The values in the map. + */ +public class PushdownMap<KeyType, ValueType> implements IMap<KeyType, ValueType> { + /* Our backing storage. */ + private final IMap<KeyType, Stack<ValueType>> backing; + + /** Create a new empty stack-based map. */ + public PushdownMap() { + backing = new FunctionalMap<>(); + } + + /** Create a new empty stack-based map using the specified backing. */ + private PushdownMap(final IMap<KeyType, Stack<ValueType>> back) { + backing = back; + } + + @Override + public void clear() { + backing.clear(); + } + + @Override + public boolean containsKey(final KeyType key) { + return backing.containsKey(key); + } + + @Override + public IMap<KeyType, ValueType> extend() { + return new PushdownMap<>(backing.extend()); + } + + @Override + public void forEach(final BiConsumer<KeyType, ValueType> action) { + backing.forEach((key, stk) -> action.accept(key, stk.top())); + } + + @Override + public void forEachKey(final Consumer<KeyType> action) { + backing.forEachKey(action); + } + + @Override + public void forEachValue(final Consumer<ValueType> action) { + backing.forEachValue(stk -> action.accept(stk.top())); + } + + @Override + public ValueType get(final KeyType key) { + return backing.get(key).top(); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public IList<KeyType> keyList() { + return backing.keyList(); + } + + @Override + public <V2> IMap<KeyType, V2> transform(final Function<ValueType, V2> transformer) { + /* + * @NOTE Can and should we support this? More to the point, + * maybe this should be a map sub-type that does what it needs + * to? + */ + throw new UnsupportedOperationException("Cannot transform pushdown maps."); + } + + @Override + public ValueType put(final KeyType key, final ValueType val) { + if(backing.containsKey(key)) { + final Stack<ValueType> stk = backing.get(key); + + final ValueType vl = stk.top(); + + stk.push(val); + + return vl; + } + + final Stack<ValueType> stk = new SimpleStack<>(); + + stk.push(val); + + return null; + } + + @Override + public ValueType remove(final KeyType key) { + final Stack<ValueType> stk = backing.get(key); + + if(stk.size() > 1) { + return stk.pop(); + } + + return backing.remove(key).top(); + } + + @Override + public IList<ValueType> valueList() { + return backing.valueList().map(Stack::top); + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + result = prime * result + (backing == null ? 0 : backing.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof PushdownMap<?, ?>)) return false; + + final PushdownMap<?, ?> other = (PushdownMap<?, ?>) obj; + + if(backing == null) { + if(other.backing != null) return false; + } else if(!backing.equals(other.backing)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("PushdownMap [backing=%s]", backing); + } +} diff --git a/src/main/java/bjc/esodata/QueueStack.java b/src/main/java/bjc/esodata/QueueStack.java new file mode 100644 index 0000000..49476f0 --- /dev/null +++ b/src/main/java/bjc/esodata/QueueStack.java @@ -0,0 +1,89 @@ +package bjc.esodata; + +import java.util.Deque; +import java.util.LinkedList; + +/** + * A FIFO implementation of a stack. + * + * Basically, a stack that actually acts like a queue. + * + * @param <T> + * The datatype stored in the stack. + * + * @author Ben Culkin + */ +public class QueueStack<T> extends Stack<T> { + /* Our backing queue. */ + private final Deque<T> backing; + + /** Create a new empty stack queue. */ + public QueueStack() { + backing = new LinkedList<>(); + } + + @Override + public void push(final T elm) { + backing.add(elm); + } + + @Override + public T pop() { + if(backing.isEmpty()) throw new StackUnderflowException(); + + return backing.remove(); + } + + @Override + public T top() { + if(backing.isEmpty()) throw new StackUnderflowException(); + + return backing.peek(); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public boolean empty() { + return backing.size() == 0; + } + + @SuppressWarnings("unchecked") + @Override + public T[] toArray() { + return (T[]) backing.toArray(); + } + + @Override + public String toString() { + return String.format("QueueStack [backing=%s]", backing); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + + result = prime * result + (backing == null ? 0 : backing.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof QueueStack<?>)) return false; + + final QueueStack<?> other = (QueueStack<?>) obj; + + if(backing == null) { + if(other.backing != null) return false; + } else if(!backing.equals(other.backing)) return false; + + return true; + } +} diff --git a/src/main/java/bjc/esodata/SimpleDirectory.java b/src/main/java/bjc/esodata/SimpleDirectory.java new file mode 100644 index 0000000..8ac19cf --- /dev/null +++ b/src/main/java/bjc/esodata/SimpleDirectory.java @@ -0,0 +1,95 @@ +package bjc.esodata; + +import bjc.funcdata.FunctionalMap; +import bjc.funcdata.IMap; + +/** + * Simple implementation of {@link Directory}. + * + * Has a split namespace for data and children. + * + * @author EVE + * + * @param <K> + * The key type of the directory. + * + * @param <V> + * The value type of the directory. + */ +public class SimpleDirectory<K, V> implements Directory<K, V> { + /* Our sub-directories. */ + private final IMap<K, Directory<K, V>> children; + /* Our data. */ + private final IMap<K, V> data; + + /** Create a new directory. */ + public SimpleDirectory() { + children = new FunctionalMap<>(); + data = new FunctionalMap<>(); + } + + @Override + public Directory<K, V> getSubdirectory(final K key) { + return children.get(key); + } + + @Override + public boolean hasSubdirectory(final K key) { + return children.containsKey(key); + } + + @Override + public Directory<K, V> putSubdirectory(final K key, final Directory<K, V> val) { + return children.put(key, val); + } + + @Override + public boolean containsKey(final K key) { + return data.containsKey(key); + } + + @Override + public V getKey(final K key) { + return data.get(key); + } + + @Override + public V putKey(final K key, final V val) { + return data.put(key, val); + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + result = prime * result + (children == null ? 0 : children.hashCode()); + result = prime * result + (data == null ? 0 : data.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof SimpleDirectory<?, ?>)) return false; + + final SimpleDirectory<?, ?> other = (SimpleDirectory<?, ?>) obj; + + if(children == null) { + if(other.children != null) return false; + } else if(!children.equals(other.children)) return false; + + if(data == null) { + if(other.data != null) return false; + } else if(!data.equals(other.data)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("SimpleDirectory [children=%s, data=%s]", children, data); + } +} diff --git a/src/main/java/bjc/esodata/SimpleStack.java b/src/main/java/bjc/esodata/SimpleStack.java new file mode 100644 index 0000000..41b217d --- /dev/null +++ b/src/main/java/bjc/esodata/SimpleStack.java @@ -0,0 +1,87 @@ +package bjc.esodata; + +import java.util.Deque; +import java.util.LinkedList; + +/** + * Simple implementation of a stack. + * + * @param <T> + * The datatype stored in the stack. + * + * @author Ben Culkin + */ +public class SimpleStack<T> extends Stack<T> { + /* Our backing stack. */ + private final Deque<T> backing; + + /** Create a new empty stack. */ + public SimpleStack() { + backing = new LinkedList<>(); + } + + @Override + public void push(final T elm) { + backing.push(elm); + } + + @Override + public T pop() { + if(backing.isEmpty()) throw new StackUnderflowException(); + + return backing.pop(); + } + + @Override + public T top() { + if(backing.isEmpty()) throw new StackUnderflowException(); + + return backing.peek(); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public boolean empty() { + return backing.size() == 0; + } + + @Override + @SuppressWarnings("unchecked") + public T[] toArray() { + return (T[]) backing.toArray(); + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + result = prime * result + (backing == null ? 0 : backing.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof SimpleStack<?>)) return false; + + final SimpleStack<?> other = (SimpleStack<?>) obj; + + if(backing == null) { + if(other.backing != null) return false; + } else if(!backing.equals(other.backing)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("SimpleStack [backing=%s]", backing); + } +} diff --git a/src/main/java/bjc/esodata/SingleTape.java b/src/main/java/bjc/esodata/SingleTape.java new file mode 100644 index 0000000..28dca2a --- /dev/null +++ b/src/main/java/bjc/esodata/SingleTape.java @@ -0,0 +1,212 @@ +package bjc.esodata; + +import java.util.ArrayList; + +/** + * A tape is a one-dimensional array that can only be accessed in one position + * at a time. + * + * A tape is essentially a 1D array with a cursor attached to it, and you can + * only affect elements at that cursor. The size of the array is theoretically + * unbounded to the right, but in practice bounded by available memory. + * + * You can choose whether or not you want the tape to automatically extend + * itself to the right with null elements by specifying its auto-extension + * policy. + * + * @param <T> + * The element type of the tape. + * + * @author bjculkin + */ +public class SingleTape<T> implements Tape<T> { + /* Our backing store. */ + protected ArrayList<T> backing; + /* Our position in the list. */ + protected int pos; + /* Whether to auto-extend the list on the left with nulls. */ + protected boolean autoExtend; + + /** + * Create a new tape with the specified contents that doesn't + * autoextend. + * + * @param vals + * The values to put on the tape. + */ + @SafeVarargs + public SingleTape(T... vals) { + autoExtend = false; + + backing = new ArrayList<>(vals.length); + + for(T val : vals) { + backing.add(val); + } + } + + /** Create a new empty tape that doesn't autoextend. */ + public SingleTape() { + this(false); + } + + /** + * Create a new tape with values taken from an iterable. + * + * @param itr + * The iterable to get values from. + */ + public SingleTape(Iterable<T> itr) { + this(false); + + for(T itm : itr) { + backing.add(itm); + } + } + + /** + * Create a new empty tape that follows the specified auto-extension + * policy. + * + * @param autoExtnd + * Whether or not to auto-extend the tape to the right w/ nulls. + */ + public SingleTape(final boolean autoExtnd) { + autoExtend = autoExtnd; + + backing = new ArrayList<>(); + } + + @Override + public T item() { + if (pos < 0 || pos >= backing.size()) return null; + + return backing.get(pos); + } + + @Override + public void item(final T itm) { + backing.set(pos, itm); + } + + @Override + public int size() { + return backing.size(); + } + + @Override + public int position() { + return pos; + } + + @Override + public void insertBefore(final T itm) { + backing.add(pos, itm); + } + + @Override + public void insertAfter(final T itm) { + if(pos == backing.size() - 1) { + backing.add(itm); + } else { + backing.add(pos + 1, itm); + } + } + + @Override + public T remove() { + final T res = backing.remove(pos); + if(pos != 0) { + pos -= 1; + } + return res; + } + + @Override + public void first() { + pos = 0; + } + + @Override + public void last() { + pos = backing.size() - 1; + } + + @Override + public boolean left() { + return left(1); + } + + @Override + public boolean left(final int amt) { + if(pos - amt < 0) return false; + + pos -= amt; + return true; + } + + @Override + public boolean right() { + return right(1); + } + + @Override + public boolean right(final int amt) { + if(pos + amt > backing.size()) { + if(autoExtend) { + while(pos + amt >= backing.size() - 1) { + backing.add(null); + } + } else return false; + } + + pos += amt; + return true; + } + + public boolean seekTo(int tgtPos) { + if(tgtPos < 0) + return false; + + if(tgtPos >= backing.size() - 1) + if(autoExtend) + while(tgtPos >= backing.size() - 1) + backing.add(null); + else + return false; + + pos = tgtPos; + + return true; + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + result = prime * result + (backing == null ? 0 : backing.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof SingleTape<?>)) return false; + + final SingleTape<?> other = (SingleTape<?>) obj; + + if(backing == null) { + if(other.backing != null) return false; + } else if(!backing.equals(other.backing)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("SingleTape [backing=%s, pos=%s, autoExtend=%s]", backing, pos, autoExtend); + } +} diff --git a/src/main/java/bjc/esodata/SpaghettiStack.java b/src/main/java/bjc/esodata/SpaghettiStack.java new file mode 100644 index 0000000..9280c28 --- /dev/null +++ b/src/main/java/bjc/esodata/SpaghettiStack.java @@ -0,0 +1,102 @@ +package bjc.esodata; + +import java.util.Arrays; +import java.util.stream.Stream; + +/** + * Implements a spaghetti stack, which is a stack that is branched off of a + * parent stack. + * + * @param <T> + * The datatype stored in the stack. + * + * @author Ben Culkin + */ +class SpaghettiStack<T> extends Stack<T> { + /* Our backing stack. */ + private final Stack<T> backing; + /* The stack we branched off of. */ + private final Stack<T> parent; + + /** + * Create a new empty spaghetti stack, off of the specified parent. + * + * @param par + * The parent stack + */ + public SpaghettiStack(final Stack<T> par) { + backing = new SimpleStack<>(); + + parent = par; + } + + @Override + public void push(final T elm) { + backing.push(elm); + } + + @Override + public T pop() { + if(backing.empty()) return parent.pop(); + + return backing.pop(); + } + + @Override + public T top() { + if(backing.empty()) return parent.top(); + + return backing.top(); + } + + @Override + public int size() { + return parent.size() + backing.size(); + } + + @Override + public boolean empty() { + return backing.empty() && parent.empty(); + } + + @SuppressWarnings("unchecked") + @Override + public T[] toArray() { + return (T[]) Stream.concat(Arrays.stream(parent.toArray()), Arrays.stream(backing.toArray())).toArray(); + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + result = prime * result + (backing == null ? 0 : backing.hashCode()); + result = prime * result + (parent == null ? 0 : parent.hashCode()); + + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof SpaghettiStack<?>)) return false; + + final SpaghettiStack<?> other = (SpaghettiStack<?>) obj; + + if(backing == null) { + if(other.backing != null) return false; + } else if(!backing.equals(other.backing)) return false; + + if(parent == null) { + if(other.parent != null) return false; + } else if(!parent.equals(other.parent)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("SpaghettiStack [backing=%s, parent=%s]", backing, parent); + } +} diff --git a/src/main/java/bjc/esodata/Stack.java b/src/main/java/bjc/esodata/Stack.java new file mode 100644 index 0000000..13480a3 --- /dev/null +++ b/src/main/java/bjc/esodata/Stack.java @@ -0,0 +1,456 @@ +package bjc.esodata; + +import java.util.ArrayList; +import java.util.List; +import java.util.function.Consumer; + +/* + * @TODO 10/11/17 Ben Culkin :StackCombinators + * Implement more combinators for the stack. + */ +/** + * A stack, with support for forth/factor style stack combinators. + * + * <p> + * <h2>Stack underflow</h2> + * <p> + * NOTE: In general, using any operation that attempts to remove more data from + * the stack than exists will cause a {@link StackUnderflowException} to be + * thrown. Check the size of the stack if you want to avoid this. + * <p> + * </p> + * + * @param <T> + * The datatype stored in the stack. + * + * @author Ben Culkin + */ +public abstract class Stack<T> { + /** + * The exception thrown when attempting to access an element from the + * stack that isn't there. + * + * @author EVE + */ + public static class StackUnderflowException extends RuntimeException { + /* The ID of the exception */ + private static final long serialVersionUID = 1423867176204571539L; + } + + /** + * Push an element onto the stack. + * + * @param elm + * The element to insert. + */ + public abstract void push(T elm); + + /** + * Pop an element off of the stack. + * + * @return The element on top of the stack. + */ + public abstract T pop(); + + /** + * Retrieve the top element of this stack without removing it from the + * stack. + * + * @return The top element of this stack. + */ + public abstract T top(); + + /** + * Get the number of elements in the stack. + * + * @return the number of elements in the stack. + */ + public abstract int size(); + + /** + * Check if the stack is empty. + * + * @return Whether or not the stack is empty. + */ + public abstract boolean empty(); + + /** + * Create a spaghetti stack branching off of this one. + * + * @return A spaghetti stack with this stack as a parent. + */ + public Stack<T> spaghettify() { + return new SpaghettiStack<>(this); + } + + /* + * Basic combinators + */ + + /** + * Drop n items from the stack. + * + * @param n + * The number of items to drop. + */ + public void drop(final int n) { + for(int i = 0; i < n; i++) { + pop(); + } + } + + /** Drop one item from the stack. */ + public void drop() { + drop(1); + } + + /** + * Delete n items below the current one. + * + * @param n + * The number of items below the top to delete. + */ + public void nip(final int n) { + final T elm = pop(); + + drop(n); + + push(elm); + } + + /** Delete the second element in the stack. */ + public void nip() { + nip(1); + } + + /** + * Replicate the top n items of the stack m times. + * + * @param n + * The number of items to duplicate. + * + * @param m + * The number of times to duplicate items. + */ + public void multidup(final int n, final int m) { + final List<T> lst = new ArrayList<>(n); + + for(int i = n; i > 0; i--) { + lst.set(i - 1, pop()); + } + + for(int i = 0; i < m; i++) { + for(final T elm : lst) { + push(elm); + } + } + } + + /** + * Duplicate the top n items of the stack. + * + * @param n + * The number of items to duplicate. + */ + public void dup(final int n) { + multidup(n, 2); + } + + /** Duplicate the top item on the stack. */ + public void dup() { + dup(1); + } + + /** + * Replicate the n elements below the top one m times. + * + * @param n + * The number of items to duplicate. + * + * @param m + * The number of times to duplicate items. + */ + public void multiover(final int n, final int m) { + final List<T> lst = new ArrayList<>(n); + + final T elm = pop(); + + for(int i = n; i > 0; i--) { + lst.set(i - 1, pop()); + } + + for(final T nelm : lst) { + push(nelm); + } + push(elm); + + for(int i = 1; i < m; i++) { + for(final T nelm : lst) { + push(nelm); + } + } + } + + /** + * Duplicate the n elements below the top one. + * + * @param n + * The number of items to duplicate. + */ + public void over(final int n) { + multiover(n, 2); + } + + /** Duplicate the second item in the stack. */ + public void over() { + over(1); + } + + /** Duplicate the third item in the stack. */ + public void pick() { + final T z = pop(); + final T y = pop(); + final T x = pop(); + + push(x); + push(y); + push(z); + push(x); + } + + /** Swap the top two items on the stack. */ + public void swap() { + final T y = pop(); + final T x = pop(); + + push(y); + push(x); + } + + /** Duplicate the second item below the first item. */ + public void deepdup() { + final T y = pop(); + final T x = pop(); + + push(x); + push(x); + push(y); + } + + /** Swap the second and third items in the stack. */ + public void deepswap() { + final T z = pop(); + final T y = pop(); + final T x = pop(); + + push(y); + push(x); + push(z); + } + + /** Rotate the top three items on the stack */ + public void rot() { + final T z = pop(); + final T y = pop(); + final T x = pop(); + + push(y); + push(z); + push(x); + } + + /** Inversely rotate the top three items on the stack */ + public void invrot() { + final T z = pop(); + final T y = pop(); + final T x = pop(); + + push(z); + push(x); + push(y); + } + + /* + * :StackCombinators Add a general rotate/roll operator. + */ + + /* + * Dataflow Combinators + */ + + /** + * Hides the top n elements on the stack from an action. + * + * @param n + * The number of elements to hide. + * + * @param action + * The action to hide the elements from + */ + public void dip(final int n, final Consumer<Stack<T>> action) { + final List<T> elms = new ArrayList<>(n); + + for(int i = n; i > 0; i--) { + elms.set(i - 1, pop()); + } + + action.accept(this); + + for(final T elm : elms) { + push(elm); + } + } + + /** + * Hide the top element of the stack from an action. + * + * @param action + * The action to hide the top from + */ + public void dip(final Consumer<Stack<T>> action) { + dip(1, action); + } + + /** + * Copy the top n elements on the stack, replacing them once an action + * is done. + * + * @param n + * The number of elements to copy. + * + * @param action + * The action to execute. + */ + public void keep(final int n, final Consumer<Stack<T>> action) { + /* + * @NOTE Is this correct? + */ + dup(n); + dip(n, action); + } + + /** + * Apply all the actions in a list to the top n elements of the stack. + * + * @param n + * The number of elements to give to cons. + * + * @param actions + * The actions to execute. + */ + public void multicleave(final int n, final List<Consumer<Stack<T>>> actions) { + final List<T> elms = new ArrayList<>(n); + + for(int i = n; i > 0; i--) { + elms.set(i - 1, pop()); + } + + for(final Consumer<Stack<T>> action : actions) { + for(final T elm : elms) { + push(elm); + } + + action.accept(this); + } + } + + /** + * Apply all the actions in a list to the top element of the stack. + * + * @param actions + * The actions to execute. + */ + public void cleave(final List<Consumer<Stack<T>>> actions) { + multicleave(1, actions); + } + + /** + * Apply every action in a list of actions to n arguments. + * + * @param n + * The number of parameters each action takes. + * + * @param actions + * The actions to execute. + */ + public void multispread(final int n, final List<Consumer<Stack<T>>> actions) { + final List<List<T>> nelms = new ArrayList<>(actions.size()); + + for(int i = actions.size(); i > 0; i--) { + final List<T> elms = new ArrayList<>(n); + + for(int j = n; j > 0; j--) { + elms.set(j, pop()); + } + + nelms.set(i, elms); + } + + int i = 0; + for(final List<T> elms : nelms) { + for(final T elm : elms) { + push(elm); + } + + actions.get(i).accept(this); + i += 1; + } + } + + /** + * Apply the actions in a list of actions to corresponding elements from + * the stack. + * + * @param conses + * The actions to execute. + */ + public void spread(final List<Consumer<Stack<T>>> conses) { + multispread(1, conses); + } + + /** + * Apply an action to the first m groups of n arguments. + * + * @param n + * The number of arguments cons takes. + * + * @param m + * The number of time to call cons. + * + * @param action + * The action to execute. + */ + public void multiapply(final int n, final int m, final Consumer<Stack<T>> action) { + final List<Consumer<Stack<T>>> actions = new ArrayList<>(m); + + for(int i = 0; i < m; i++) { + actions.add(action); + } + + multispread(n, actions); + } + + /** + * Apply an action n times to the corresponding elements in the stack. + * + * @param n + * The number of times to execute cons. + * + * @param action + * The action to execute. + */ + public void apply(final int n, final Consumer<Stack<T>> action) { + multiapply(1, n, action); + } + + /* + * Misc. functions + */ + + /** + * Get an array representing this stack. + * + * @return The stack as an array. + */ + public abstract T[] toArray(); +} diff --git a/src/main/java/bjc/esodata/Tape.java b/src/main/java/bjc/esodata/Tape.java new file mode 100644 index 0000000..080e216 --- /dev/null +++ b/src/main/java/bjc/esodata/Tape.java @@ -0,0 +1,135 @@ +package bjc.esodata; + +/** + * Interface for something that acts like a tape. + * + * A tape is essentially a 1D array with a cursor attached to it, and you can + * only affect elements at that cursor. The size of the array is theoretically + * unbounded to the right, but in practice bounded by available memory. + * + * @param <T> + * The element type of the tape. + * + * @author bjculkin + */ +public interface Tape<T> { + /** + * Get the item the tape is currently on. + * + * @return The item the tape is on. + */ + T item(); + + /** + * Set the item the tape is currently on. + * + * @param itm + * The new value for the tape item. + */ + void item(T itm); + + /** + * Get the current number of elements in the tape. + * + * @return The current number of elements in the tape. + */ + int size(); + + /** + * Get the position of the current item. + * + * @return The position of the current item. + */ + int position(); + + /** + * Insert an element before the current item. + * + * @param itm + * The item to add. + */ + void insertBefore(T itm); + + /** + * Insert an element after the current item. + * + * @param itm + * The item to insert. + */ + void insertAfter(T itm); + + /** + * Remove the current element. + * + * Also moves the cursor back one step if possible to maintain relative + * position. + * + * @return The removed item. + */ + T remove(); + + /** Move the cursor to the left-most position. */ + void first(); + + /** Move the cursor to the right-most position. */ + void last(); + + /** + * Move the cursor one space left. + * + * The cursor can't go past zero. + * + * @return True if the cursor was moved left. + */ + boolean left(); + + /** + * Move the cursor the specified amount left. + * + * The cursor can't go past zero. Attempts to move the cursor by amounts + * that would exceed zero don't move the cursor at all. + * + * @param amt + * The amount to attempt to move the cursor left. + * + * @return True if the cursor was moved left. + */ + boolean left(int amt); + + /** + * Move the cursor one space right. + * + * @return Whether the cursor was moved right. + */ + boolean right(); + + /** + * Move the cursor the specified amount right. + * + * @param amt + * The amount to move the cursor right by. + * + * @return Whether the cursor was moved right. + */ + boolean right(int amt); + + /** + * Seek to an absolute position on the tape. + * + * @param pos + * The position to seek to. + * @return Whether or not the tape successfully seeked to that position. + */ + boolean seekTo(int pos); + + /** + * Check if this tape is at its end. + * + * Equivalent to checking if position() == size(). + * + * @return Whether or not the tape is at its end. + */ + default boolean atEnd() { + return position() == size(); + } +} diff --git a/src/main/java/bjc/esodata/ThresholdSet.java b/src/main/java/bjc/esodata/ThresholdSet.java new file mode 100644 index 0000000..b6f677e --- /dev/null +++ b/src/main/java/bjc/esodata/ThresholdSet.java @@ -0,0 +1,238 @@ +package bjc.esodata; + +import java.util.*; + +/** + * Represents a counted set, that overflows to a map. + * + * More specifically, this is a set/map combo type. + * + * Initially, when you add an item, it will go into the set. Attempting to add a duplicate item to + * that set will cause the entry to be removed from the set, and added to the map, which will count + * the number of times that particular item has been added to the set. If you remove enough copies + * of that item to put it back down to 1 copy, that copy will be removed from the map, and readded + * to the set. + * + * The iterator that this type gives by default is an iterator over all of the values in the set, + * not including any of those in the map. + * + * @param KeyType The value being counted. + * + * @author Ben Culkin + */ +public class ThresholdSet<KeyType> { + // View of this class as a java.util.Set + private class SetView extends AbstractSet<KeyType> { + /* + * This is technically not a valid implementation of add, because it does not guarantee that + * the set will contain key after it returns (as a matter of fact, attempting to add the + * component might actually cause it to be removed from the collection). + */ + public boolean add(KeyType key) { + // Qualified-this; allows us to reference the 'this' of our enclosing type. + int ret = ThresholdSet.this.add(key); + + // No change to set contents + if (ret > 2) return false; + + return true; + } + + public boolean remove(Object o) { + // Will throw a ClassCastException if you give us something bad. + KeyType k = (KeyType)o; + + int ret = ThresholdSet.this.remove(k); + + // We removed the element. + if (ret == 0) return true; + + return false; + } + + public boolean contains(Object o) { + // Will throw a ClassCastException if you give us something bad. + KeyType k = (KeyType)o; + + int ret = ThresholdSet.this.remove(k); + + // The object is set-visible + if (ret == 1) return true; + + return false; + } + + public int size() { + return ThresholdSet.this.setSize(); + } + + public Iterator<KeyType> iterator() { + return ThresholdSet.this.setIterator(); + } + } + + private Set<KeyType> keySet; + // @TODO :CountMap Ben Culkin 6/19/2019 + // Replace this with a CountSet or some equivalent concept, whenever that gets written + private Map<KeyType, Integer> keyMap; + + /** + * Create a new empty threshold set. + */ + public ThresholdSet() { + keySet = new HashSet<>(); + keyMap = new HashMap<>(); + } + + /** + * Add multiple keys at once to the map. + * + * @param keys + * The keys to add. + * @return An array containing the results of adding the keys. + */ + public int[] addAll(KeyType... keys) { + int[] ret = new int[keys.length]; + + for (int i = 0; i < keys.length; i++) { + ret[i] = add(keys[i]); + } + + return ret; + } + + /** + * Add a key to the collection. + * + * @param key + * The key to add to the collection. + * @return The number of times that key now exists in the collection. Should always be < 0. + */ + public int add(KeyType key) { + if (keySet.contains(key)) { + // Promote to counted item + keySet.remove(key); + + keyMap.put(key, 2); + + return 2; + } else if (keyMap.containsKey(key)) { + // Increment count + int cnt = keyMap.get(key) + 1; + + keyMap.put(key, cnt); + + return cnt; + } else { + // New key + keySet.add(key); + + return 1; + } + } + + /** + * Remove a bunch of keys from the collection. + * + * @param keys + * The keys to remove from the collection. + * + * @return The results from removing the keys. + */ + public int[] removeAll(KeyType... keys) { + int[] ret = new int[keys.length]; + + for (int i = 0; i < keys.length; i++) { + ret[i] = remove(keys[i]); + } + + return ret; + } + + /** + * Remove a key from the collection. + * + * @param key + * The key to remove from the collection. + * + * @return The number of times that key now exists in the collection. Returns -1 if that key + * wasn't in the collection beforehand. + */ + public int remove(KeyType key) { + if (keySet.contains(key)) { + // No more occurances + keySet.remove(key); + + return 0; + } else if (keyMap.containsKey(key)) { + // Decrement count + int cnt = keyMap.get(key) - 1; + + if (cnt == 1) { + // Move key to set + keyMap.remove(key); + + keySet.add(key); + + return 1; + } else { + keyMap.put(key, cnt); + + return cnt; + } + } else { + // We don't know about that key + return -1; + } + } + + /** + * Get the number of times the set contains a set of given keys. + * + * @param key + * The keys to look for. + * + * @return The containment counts for each key. + */ + public int[] containsAll(KeyType... keys) { + int[] ret = new int[keys.length]; + + for (int i = 0; i < keys.length; i++) { + ret[i] = contains(keys[i]); + } + + return ret; + } + + /** + * Get the number of times the set contains a given key. + * + * @param key + * The key to look for. + * + * @return The number of times the key occurs; -1 if it doesn't occur. + */ + public int contains(KeyType key) { + if (keySet.contains(key)) return 1; + if (!keyMap.containsKey(key)) return -1; + + return keyMap.get(key); + } + + /** + * Get a view of this collection as a java.util.Set. + * + * @return A view of the collection as a set. + */ + public Set<KeyType> setView() { + return new SetView(); + } + + int setSize() { + return keySet.size(); + } + + Iterator<KeyType> setIterator() { + return keySet.iterator(); + } +} diff --git a/src/main/java/bjc/esodata/UnifiedDirectory.java b/src/main/java/bjc/esodata/UnifiedDirectory.java new file mode 100644 index 0000000..dec940f --- /dev/null +++ b/src/main/java/bjc/esodata/UnifiedDirectory.java @@ -0,0 +1,105 @@ +package bjc.esodata; + +import bjc.funcdata.FunctionalMap; +import bjc.funcdata.IMap; + +/** + * Simple implementation of {@link Directory}. + * + * Has a unified namespace for data and children. + * + * @author EVE + * + * @param <K> + * The key type of the directory. + * + * @param <V> + * The value type of the directory. + */ +public class UnifiedDirectory<K, V> implements Directory<K, V> { + /* Our directory children. */ + private final IMap<K, Directory<K, V>> children; + /* Our data children. */ + private final IMap<K, V> data; + + /** Create a new directory. */ + public UnifiedDirectory() { + children = new FunctionalMap<>(); + data = new FunctionalMap<>(); + } + + @Override + public Directory<K, V> getSubdirectory(final K key) { + return children.get(key); + } + + @Override + public boolean hasSubdirectory(final K key) { + return children.containsKey(key); + } + + @Override + public Directory<K, V> putSubdirectory(final K key, final Directory<K, V> val) { + if(data.containsKey(key)) { + final String msg = String.format("Key %s is already used for data", key); + + throw new IllegalArgumentException(msg); + } + + return children.put(key, val); + } + + @Override + public boolean containsKey(final K key) { + return data.containsKey(key); + } + + @Override + public V getKey(final K key) { + return data.get(key); + } + + @Override + public V putKey(final K key, final V val) { + if(children.containsKey(key)) { + final String msg = String.format("Key %s is already used for sub-directories.", key); + + throw new IllegalArgumentException(msg); + } + + return data.put(key, val); + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + (children == null ? 0 : children.hashCode()); + result = prime * result + (data == null ? 0 : data.hashCode()); + return result; + } + + @Override + public boolean equals(final Object obj) { + if(this == obj) return true; + if(obj == null) return false; + if(!(obj instanceof UnifiedDirectory<?, ?>)) return false; + + final UnifiedDirectory<?, ?> other = (UnifiedDirectory<?, ?>) obj; + + if(children == null) { + if(other.children != null) return false; + } else if(!children.equals(other.children)) return false; + + if(data == null) { + if(other.data != null) return false; + } else if(!data.equals(other.data)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("UnifiedDirectory [children=%s, data=%s]", children, data); + } +} diff --git a/src/main/java/bjc/esodata/todos.txt b/src/main/java/bjc/esodata/todos.txt new file mode 100644 index 0000000..28af9b7 --- /dev/null +++ b/src/main/java/bjc/esodata/todos.txt @@ -0,0 +1,3 @@ +@TODO 10/11/17 Ben Culkin :CursorHands + Add cursored list/tree data structures with the ability to pick/put the + current node. 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 <KeyType> + * The type of the keys of the map. + * + * @param <ValueType> + * The type of the values of the map. + */ +class ExtendedMap<KeyType, ValueType> implements IMap<KeyType, ValueType> { + /* The map we delegate lookups to. */ + private final IMap<KeyType, ValueType> delegate; + /* The map we store things in. */ + private final IMap<KeyType, ValueType> 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<KeyType, ValueType> delegate, final IMap<KeyType, ValueType> 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<KeyType, ValueType> extend() { + return new ExtendedMap<>(this, new FunctionalMap<>()); + } + + @Override + public void forEach(final BiConsumer<KeyType, ValueType> action) { + store.forEach(action); + + delegate.forEach(action); + } + + @Override + public void forEachKey(final Consumer<KeyType> action) { + store.forEachKey(action); + + delegate.forEachKey(action); + } + + @Override + public void forEachValue(final Consumer<ValueType> 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<KeyType> keyList() { + IList<KeyType> ilst = new FunctionalList<>(); + + ilst.addAll(store.keyList()); + ilst.addAll(delegate.keyList()); + + return ilst; + } + + @Override + public <MappedValue> IMap<KeyType, MappedValue> transform(final Function<ValueType, MappedValue> 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<ValueType> valueList() { + IList<ValueType> 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 <E> + * The type in this list + */ +public class FunctionalList<E> implements Cloneable, IList<E> { + /* The list used as a backing store */ + private final List<E> 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 <T> IList<T> 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<E> 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<E> 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<E> 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<E> clone() { + final IList<E> cloned = new FunctionalList<>(); + + for(final E element : wrapped) { + cloned.add(element); + } + + return cloned; + } + + @Override + public <T, F> IList<F> combineWith(final IList<T> rightList, final BiFunction<E, T, F> 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<F> returned = new FunctionalList<>(); + + /* Get the iterator for the other list. */ + final Iterator<T> rightIterator = rightList.toIterable().iterator(); + + for(final Iterator<E> 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 <T> IList<T> flatMap(final Function<E, IList<T>> expander) { + if(expander == null) throw new NullPointerException("Expander must not be null"); + + final IList<T> returned = new FunctionalList<>(this.wrapped.size()); + + forEach(element -> { + final IList<T> 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<? super E> action) { + if(action == null) throw new NullPointerException("Action is null"); + + wrapped.forEach(action); + } + + @Override + public void forEachIndexed(final BiConsumer<Integer, E> 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<Integer> 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<E> getInternal() { + return wrapped; + } + + @Override + public IList<E> getMatching(final Predicate<E> predicate) { + if(predicate == null) throw new NullPointerException("Predicate must not be null"); + + final IList<E> 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<IList<E>> currentPartition) { + return currentPartition.unwrap((partition) -> partition.getSize() >= numberPerPartition); + } + + @Override + public <T> IList<T> map(final Function<E, T> elementTransformer) { + if(elementTransformer == null) throw new NullPointerException("Transformer must be not null"); + + final IList<T> returned = new FunctionalList<>(this.wrapped.size()); + + forEach(element -> { + // Add the transformed item to the result + returned.add(elementTransformer.apply(element)); + }); + + return returned; + } + + @Override + public <T> IList<IPair<E, T>> pairWith(final IList<T> rightList) { + return combineWith(rightList, Pair<E, T>::new); + } + + @Override + public IList<IList<E>> 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<IList<E>> returned = new FunctionalList<>(); + + /* The current partition being filled. */ + final IHolder<IList<E>> 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<Integer, Integer> 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 <T, F> F reduceAux(final T initialValue, final BiFunction<E, T, T> stateAccumulator, + final Function<T, F> 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<T> 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<E> 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<E> 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<E> comparator) { + Collections.sort(wrapped, comparator); + } + + @Override + public IList<E> tail() { + return new FunctionalList<>(wrapped.subList(1, getSize())); + } + + @Override + public E[] toArray(final E[] arrType) { + return wrapped.toArray(arrType); + } + + @Override + public Iterable<E> toIterable() { + return wrapped; + } + + @Override + public String toString() { + final int lSize = getSize(); + + if(lSize == 0) return "()"; + + final StringBuilder sb = new StringBuilder("("); + final Iterator<E> 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 <KeyType> + * The type of the map's keys. + * + * @param <ValueType> + * The type of the map's values. + */ +public class FunctionalMap<KeyType, ValueType> implements IMap<KeyType, ValueType> { + /* Our backing store. */ + private Map<KeyType, ValueType> 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<KeyType, ValueType>... entries) { + this(); + + for(final IPair<KeyType, ValueType> 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<KeyType, ValueType> 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<KeyType, ValueType> extend() { + return new ExtendedMap<>(this, new FunctionalMap<>()); + } + + @Override + public void forEach(final BiConsumer<KeyType, ValueType> action) { + wrappedMap.forEach(action); + } + + @Override + public void forEachKey(final Consumer<KeyType> action) { + wrappedMap.keySet().forEach(action); + } + + @Override + public void forEachValue(final Consumer<ValueType> 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<KeyType> keyList() { + final FunctionalList<KeyType> keys = new FunctionalList<>(); + + wrappedMap.keySet().forEach(key -> { + keys.add(key); + }); + + return keys; + } + + @Override + public <MappedValue> IMap<KeyType, MappedValue> transform(final Function<ValueType, MappedValue> 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<ValueType> valueList() { + final FunctionalList<ValueType> 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<String> 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<String> 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 <E> + * 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 <E> IList<E> toList(final Function<String, E> transformer) { + if(transformer == null) throw new NullPointerException("Transformer must not be null"); + + final IList<E> 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 <ContainedType> + * The type in this list + */ +public interface IList<ContainedType> extends Iterable<ContainedType> { + /** + * 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<ContainedType> 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<ContainedType> 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<ContainedType> matcher); + + /** + * Reduce the contents of this list using a collector. + * + * @param <StateType> + * The intermediate accumulation type. + * + * @param <ReducedType> + * The final, reduced type. + * + * @param collector + * The collector to use for reduction. + * + * @return The reduced list. + */ + default <StateType, ReducedType> ReducedType collect( + final Collector<ContainedType, StateType, ReducedType> collector) { + final BiConsumer<StateType, ContainedType> 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 <OtherType> + * The type of the second list. + * + * @param <CombinedType> + * 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. + */ + <OtherType, CombinedType> IList<CombinedType> combineWith(IList<OtherType> list, + BiFunction<ContainedType, OtherType, CombinedType> 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 <MappedType> + * 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. + */ + <MappedType> IList<MappedType> flatMap(Function<ContainedType, IList<MappedType>> 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<? super ContainedType> 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<Integer, ContainedType> 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<ContainedType> getMatching(Predicate<ContainedType> 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 <MappedType> + * 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. + */ + <MappedType> IList<MappedType> map(Function<ContainedType, MappedType> transformer); + + /** + * Zip two lists into a list of pairs. + * + * @param <OtherType> + * 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. + */ + <OtherType> IList<IPair<ContainedType, OtherType>> pairWith(IList<OtherType> 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<IList<ContainedType>> 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<Integer, Integer> rnd); + + /** + * Reduce this list to a single value, using a accumulative approach. + * + * @param <StateType> + * The in-between type of the values + * + * @param <ReducedType> + * 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. + */ + <StateType, ReducedType> ReducedType reduceAux(StateType initial, + BiFunction<ContainedType, StateType, StateType> accumulator, + Function<StateType, ReducedType> transformer); + + /** + * Reduce this list to a single value, using a accumulative approach. + * + * @param <StateType> + * 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> StateType reduceAux(StateType initial, + BiFunction<ContainedType, StateType, StateType> 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<ContainedType> 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<ContainedType> 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<ContainedType> comparator); + + /** + * Get the tail of this list (the list without the first element). + * + * @return The list without the first element. + */ + IList<ContainedType> 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<ContainedType> toIterable(); + + @Override + default Iterator<ContainedType> 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 <KeyType> + * The type of this map's keys. + * + * @param <ValueType> + * The type of this map's values. + */ +public interface IMap<KeyType, ValueType> { + /** + * Execute an action for each entry in the map. + * + * @param action + * The action to execute for each entry in the map. + */ + void forEach(BiConsumer<KeyType, ValueType> 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<KeyType> 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<ValueType> 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 <V2> + * 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 <V2> IMap<KeyType, V2> transform(final Function<ValueType, V2> 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<KeyType, ValueType> 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<KeyType> keyList(); + + /** + * Get a list of the values in this map. + * + * @return A list of values in this map. + */ + default IList<ValueType> valueList() { + final IList<ValueType> 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 <T> + * The type of item in the list. + */ +public class SentryList<T> extends FunctionalList<T> { + /** 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<T> 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 <OldKey> + * The type of the map's keys + * + * @param <OldValue> + * The type of the map's values + * + * @param <NewValue> + * The type of the transformed values + * + */ +final class TransformedValueMap<OldKey, OldValue, NewValue> implements IMap<OldKey, NewValue> { + /* Our backing map. */ + private final IMap<OldKey, OldValue> backing; + /* Our transforming function. */ + private final Function<OldValue, NewValue> 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<OldKey, OldValue> backingMap, + final Function<OldValue, NewValue> 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<OldKey, NewValue> extend() { + return new ExtendedMap<>(this, new FunctionalMap<>()); + } + + @Override + public void forEach(final BiConsumer<OldKey, NewValue> action) { + backing.forEach((key, value) -> { + action.accept(key, transformer.apply(value)); + }); + } + + @Override + public void forEachKey(final Consumer<OldKey> action) { + backing.forEachKey(action); + } + + @Override + public void forEachValue(final Consumer<NewValue> 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<OldKey> keyList() { + return backing.keyList(); + } + + @Override + public <MappedValue> IMap<OldKey, MappedValue> transform(final Function<NewValue, MappedValue> 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<NewValue> 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 <T> + * The data type stored in the node. + */ +public class BinarySearchTree<T> { + /* The comparator for use in ordering items */ + private final Comparator<T> comparator; + + /* The current count of elements in the tree */ + private int elementCount; + + /* The root element of the tree */ + private ITreePart<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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 <T> + * The data stored in the tree. + */ +public class BinarySearchTreeLeaf<T> implements ITreePart<T> { + /** 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<T> comparator) { + throw new IllegalArgumentException("Can't add to a leaf."); + } + + @Override + public <E> E collapse(final Function<T, E> leafTransformer, final BiFunction<E, E, E> 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<T> comparator) { + return this.data.equals(element); + } + + @Override + public T data() { + return data; + } + + @Override + public void delete(final T element, final Comparator<T> comparator) { + if(data.equals(element)) { + isDeleted = true; + } + } + + @Override + public boolean directedWalk(final DirectedWalkFunction<T> 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<T> 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 <T> + * The data type stored in the tree. + */ +public class BinarySearchTreeNode<T> extends BinarySearchTreeLeaf<T> { + /* The left child of this node */ + private ITreePart<T> left; + + /* The right child of this node */ + private ITreePart<T> 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<T> lft, final ITreePart<T> rght) { + super(element); + this.left = lft; + this.right = rght; + } + + @Override + public void add(final T element, final Comparator<T> 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> E collapse(final Function<T, E> nodeCollapser, final BiFunction<E, E, E> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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<T> 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 <T> + * The type of element stored in the walked tree + */ +@FunctionalInterface +public interface DirectedWalkFunction<T> { + /** + * 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 <T> + * The data contained in this part of the tree. + */ +public interface ITreePart<T> { + /** + * 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<T> comparator); + + /** + * Collapses this tree part into a single value. + * + * Does not change the underlying tree. + * + * @param <E> + * 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> E collapse(Function<T, E> nodeCollapser, BiFunction<E, E, E> 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<T> 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<T> 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<T> 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<T> 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 <LeftType> + * The type stored on the 'left' of the pair. + * + * @param <RightType> + * The type stored on the 'right' of the pair. + */ +public interface Bifunctor<LeftType, RightType> { + /** + * Alias for functor mapping. + * + * @author EVE + * + * @param <OldLeft> + * The old left type. + * + * @param <OldRight> + * The old right type. + * + * @param <NewLeft> + * The new left type. + * + * @param <NewRight> + * The new right type. + */ + public interface BifunctorMap<OldLeft, OldRight, NewLeft, NewRight> + extends Function<Bifunctor<OldLeft, OldRight>, Bifunctor<NewLeft, NewRight>> { + /* + * Alias + */ + } + + /** + * Alias for left functor mapping. + * + * @author EVE + * + * @param <OldLeft> + * The old left type. + * + * @param <OldRight> + * The old right type. + * + * @param <NewLeft> + * The new left type. + */ + public interface LeftBifunctorMap<OldLeft, OldRight, NewLeft> + extends BifunctorMap<OldLeft, OldRight, NewLeft, OldRight> { + /* + * Alias + */ + } + + /** + * Alias for right functor mapping. + * + * @author EVE + * + * @param <OldLeft> + * The old left type. + * + * @param <OldRight> + * The old right type. + * + * @param <NewRight> + * The new right type. + */ + public interface RightBifunctorMap<OldLeft, OldRight, NewRight> + extends BifunctorMap<OldLeft, OldRight, OldLeft, NewRight> { + /* + * Alias + */ + } + + /** + * Lift a pair of functions to a single function that maps over both + * parts of a pair. + * + * @param <OldLeft> + * The old left type of the pair. + * + * @param <OldRight> + * The old right type of the pair. + * + * @param <NewLeft> + * The new left type of the pair. + * + * @param <NewRight> + * 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 <OldLeft, OldRight, NewLeft, NewRight> BifunctorMap<OldLeft, OldRight, NewLeft, NewRight> bimap( + final Function<OldLeft, NewLeft> leftFunc, final Function<OldRight, NewRight> rightFunc) { + final BifunctorMap<OldLeft, OldRight, NewLeft, NewRight> bimappedFunc = (argPair) -> { + final LeftBifunctorMap<OldLeft, OldRight, NewLeft> leftMapper = argPair.fmapLeft(leftFunc); + + final Bifunctor<NewLeft, OldRight> leftMappedFunctor = leftMapper.apply(argPair); + final RightBifunctorMap<NewLeft, OldRight, NewRight> rightMapper = leftMappedFunctor + .fmapRight(rightFunc); + + return rightMapper.apply(leftMappedFunctor); + }; + + return bimappedFunc; + } + + /** + * Lift a function to operate over the left part of this pair. + * + * @param <OldLeft> + * The old left type of the pair. + * + * @param <OldRight> + * The old right type of the pair. + * + * @param <NewLeft> + * 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 <OldLeft, OldRight, NewLeft> LeftBifunctorMap<OldLeft, OldRight, NewLeft> fmapLeft( + Function<OldLeft, NewLeft> func); + + /** + * Lift a function to operate over the right part of this pair. + * + * @param <OldLeft> + * The old left type of the pair. + * + * @param <OldRight> + * The old right type of the pair. + * + * @param <NewRight> + * 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 <OldLeft, OldRight, NewRight> RightBifunctorMap<OldLeft, OldRight, NewRight> fmapRight( + Function<OldRight, NewRight> 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 <ContainedType> + * The value inside the functor. + */ +public interface Functor<ContainedType> { + /** + * 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 <ArgType> + * The argument of the function. + * + * @param <ReturnType> + * 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 <ArgType, ReturnType> Function<Functor<ArgType>, Functor<ReturnType>> fmap( + Function<ArgType, ReturnType> func); + + /** + * Retrieve the thing inside this functor. + * + * @return The thing inside this functor. + */ + public ContainedType getValue(); +} diff --git a/src/main/java/bjc/functypes/ID.java b/src/main/java/bjc/functypes/ID.java new file mode 100644 index 0000000..d88858d --- /dev/null +++ b/src/main/java/bjc/functypes/ID.java @@ -0,0 +1,19 @@ +package bjc.functypes; + +import java.util.function.UnaryOperator; + +/** + * Identity function. + * + * @author bjculkin + */ +public class ID { + /** + * Create an identity function. + * + * @return A identity function. + */ + public static <A> UnaryOperator<A> id() { + return (x) -> x; + } +} diff --git a/src/main/java/bjc/functypes/ListFlattener.java b/src/main/java/bjc/functypes/ListFlattener.java new file mode 100644 index 0000000..2f50184 --- /dev/null +++ b/src/main/java/bjc/functypes/ListFlattener.java @@ -0,0 +1,19 @@ +package bjc.functypes; + +import java.util.function.Function; + +import bjc.funcdata.IList; + +/** + * A function that flattens a list. + * + * @author bjculkin + * + * @param <S> + * The type of value in the list. + */ +public interface ListFlattener<S> extends Function<IList<S>, S> { + /* + * Alias + */ +} |