From 843329de434bb334d90927c4d22345373a388530 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Tue, 2 Jul 2019 18:05:22 -0400 Subject: Rename package root The package root is now bjc, not io.github.bculkin2442. --- src/main/java/bjc/data/ArrayIterator.java | 29 ++ src/main/java/bjc/data/BooleanToggle.java | 77 ++++ src/main/java/bjc/data/CircularIterator.java | 79 ++++ src/main/java/bjc/data/Either.java | 191 +++++++++ src/main/java/bjc/data/GeneratingIterator.java | 60 +++ src/main/java/bjc/data/IHolder.java | 163 ++++++++ src/main/java/bjc/data/IPair.java | 241 ++++++++++++ src/main/java/bjc/data/ITree.java | 278 +++++++++++++ src/main/java/bjc/data/Identity.java | 112 ++++++ src/main/java/bjc/data/Lazy.java | 201 ++++++++++ src/main/java/bjc/data/LazyPair.java | 249 ++++++++++++ src/main/java/bjc/data/ListHolder.java | 105 +++++ src/main/java/bjc/data/OneWayToggle.java | 53 +++ src/main/java/bjc/data/Option.java | 93 +++++ src/main/java/bjc/data/Pair.java | 142 +++++++ src/main/java/bjc/data/QueuedIterator.java | 228 +++++++++++ src/main/java/bjc/data/SingleIterator.java | 42 ++ src/main/java/bjc/data/SingleSupplier.java | 76 ++++ src/main/java/bjc/data/Toggle.java | 34 ++ .../java/bjc/data/TopDownTransformIterator.java | 272 +++++++++++++ src/main/java/bjc/data/TopDownTransformResult.java | 22 ++ src/main/java/bjc/data/TransformIterator.java | 46 +++ src/main/java/bjc/data/Tree.java | 432 +++++++++++++++++++++ src/main/java/bjc/data/ValueToggle.java | 60 +++ src/main/java/bjc/data/internals/BoundLazy.java | 137 +++++++ .../java/bjc/data/internals/BoundLazyPair.java | 228 +++++++++++ .../java/bjc/data/internals/BoundListHolder.java | 81 ++++ .../java/bjc/data/internals/HalfBoundLazyPair.java | 177 +++++++++ src/main/java/bjc/data/internals/WrappedLazy.java | 83 ++++ .../java/bjc/data/internals/WrappedOption.java | 96 +++++ 30 files changed, 4087 insertions(+) create mode 100644 src/main/java/bjc/data/ArrayIterator.java create mode 100644 src/main/java/bjc/data/BooleanToggle.java create mode 100644 src/main/java/bjc/data/CircularIterator.java create mode 100644 src/main/java/bjc/data/Either.java create mode 100644 src/main/java/bjc/data/GeneratingIterator.java create mode 100644 src/main/java/bjc/data/IHolder.java create mode 100644 src/main/java/bjc/data/IPair.java create mode 100644 src/main/java/bjc/data/ITree.java create mode 100644 src/main/java/bjc/data/Identity.java create mode 100644 src/main/java/bjc/data/Lazy.java create mode 100644 src/main/java/bjc/data/LazyPair.java create mode 100644 src/main/java/bjc/data/ListHolder.java create mode 100644 src/main/java/bjc/data/OneWayToggle.java create mode 100644 src/main/java/bjc/data/Option.java create mode 100644 src/main/java/bjc/data/Pair.java create mode 100644 src/main/java/bjc/data/QueuedIterator.java create mode 100644 src/main/java/bjc/data/SingleIterator.java create mode 100644 src/main/java/bjc/data/SingleSupplier.java create mode 100644 src/main/java/bjc/data/Toggle.java create mode 100644 src/main/java/bjc/data/TopDownTransformIterator.java create mode 100644 src/main/java/bjc/data/TopDownTransformResult.java create mode 100644 src/main/java/bjc/data/TransformIterator.java create mode 100644 src/main/java/bjc/data/Tree.java create mode 100644 src/main/java/bjc/data/ValueToggle.java create mode 100644 src/main/java/bjc/data/internals/BoundLazy.java create mode 100644 src/main/java/bjc/data/internals/BoundLazyPair.java create mode 100644 src/main/java/bjc/data/internals/BoundListHolder.java create mode 100644 src/main/java/bjc/data/internals/HalfBoundLazyPair.java create mode 100644 src/main/java/bjc/data/internals/WrappedLazy.java create mode 100644 src/main/java/bjc/data/internals/WrappedOption.java (limited to 'src/main/java/bjc/data') 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 implements Iterator { + 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 { + /* 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 + * The type of the iterable. + */ +public class CircularIterator implements Iterator { + /* The iterable, and our current iterator into it. */ + private Iterable source; + private Iterator 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 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 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 + * The type that could be on the left. + * + * @param + * The type that could be on the right. + * + */ +public class Either implements IPair { + /** + * Create a new either with the left value occupied. + * + * @param + * The type of the left value. + * + * @param + * 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 Either left(final LeftType left) { + return new Either<>(left, null); + } + + /** + * Create a new either with the right value occupied. + * + * @param + * The type of the empty left value. + * + * @param + * 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 Either 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 IPair bind( + final BiFunction> binder) { + if(binder == null) throw new NullPointerException("Binder must not be null"); + + return binder.apply(leftVal, rightVal); + } + + @Override + public IPair bindLeft( + final Function> 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 IPair bindRight( + final Function> 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 IPair combine( + final IPair otherPair, + final BiFunction leftCombiner, + final BiFunction 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 IPair mapLeft(final Function 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 IPair mapRight(final Function 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 merge(final BiFunction 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 + * The type of element generated. + */ +public class GeneratingIterator implements Iterator { + /* Our current state. */ + private E state; + /* The function to use to transition states. */ + private UnaryOperator transtion; + /* The predicate to indicate where to stop. */ + private Predicate 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 transition, Predicate 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 + * The type of value held. + */ +public interface IHolder extends Functor { + /** + * Bind a function across the value in this container. + * + * @param + * The type of value in this container. + * + * @param binder + * The function to bind to the value. + * + * @return A holder from binding the value. + */ + public IHolder bind(Function> binder); + + /** + * Apply an action to the value. + * + * @param action + * The action to apply to the value. + */ + public default void doWith(final Consumer action) { + transform(value -> { + action.accept(value); + + return value; + }); + } + + @Override + default Function, Functor> fmap( + final Function 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 holder = (IHolder) argumentFunctor; + + return holder.map(func); + }; + } + + @Override + public default ContainedType getValue() { + return unwrap(value -> value); + } + + /** + * Lifts a function to bind over this holder. + * + * @param + * The type of the functions return. + * + * @param func + * The function to lift over the holder. + * + * @return The function lifted over the holder. + */ + public Function> lift(Function func); + + /** + * Make this holder lazy. + * + * @return A lazy version of this holder. + */ + public default IHolder makeLazy() { + return new WrappedLazy<>(this); + } + + /** + * Make this holder a list. + * + * @return A list version of this holder. + */ + public default IHolder makeList() { + return new BoundListHolder<>(new FunctionalList<>(this)); + } + + /** + * Make this holder optional. + * + * @return An optional version of this holder. + */ + public default IHolder 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 + * The type of the mapped value. + * + * @param mapper + * The function to do mapping with. + * + * @return A holder with the mapped value + */ + public IHolder map(Function mapper); + + /** + * Replace the held value with a new one. + * + * @param newValue + * The value to hold instead. + * + * @return The holder itself. + */ + public default IHolder 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 transform(UnaryOperator transformer); + + /** + * Unwrap the value contained in this holder so that it is no longer + * held. + * + * @param + * The type of the unwrapped value. + * + * @param unwrapper + * The function to use to unwrap the value. + * + * @return The unwrapped held value. + */ + public UnwrappedType unwrap(Function 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 + * The type of the left side of the pair. + * + * @param + * The type of the right side of the pair. + * + */ +public interface IPair extends Bifunctor { + /** + * Bind a function across the values in this pair. + * + * @param + * The type of the bound left. + * + * @param + * The type of the bound right. + * + * @param binder + * The function to bind with. + * + * @return The bound pair. + */ + public IPair bind( + BiFunction> binder); + + /** + * Bind a function to the left value in this pair. + * + * @param + * The type of the bound value. + * + * @param leftBinder + * The function to use to bind. + * + * @return A pair with the left type bound. + */ + public IPair bindLeft( + Function> leftBinder); + + /** + * Bind a function to the right value in this pair. + * + * @param + * The type of the bound value. + * + * @param rightBinder + * The function to use to bind. + * + * @return A pair with the right type bound. + */ + public IPair bindRight( + Function> rightBinder); + + /** + * Pairwise combine two pairs together. + * + * @param + * The left type of the other pair. + * + * @param + * The right type of the other pair. + * + * @param otherPair + * The pair to combine with. + * + * @return The pairs, pairwise combined together. + */ + public default IPair, IPair> combine( + final IPair otherPair) { + return combine(otherPair, Pair::new, Pair::new); + } + + /** + * Combine the contents of two pairs together. + * + * @param + * The type of the left value of the other pair. + * + * @param + * The type of the right value of the other pair. + * + * @param + * The type of the left value of the combined pair. + * + * @param + * 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 IPair combine( + IPair otherPair, + BiFunction leftCombiner, + BiFunction 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 consumer) { + merge((leftValue, rightValue) -> { + consumer.accept(leftValue, rightValue); + + return null; + }); + } + + @Override + default LeftBifunctorMap fmapLeft( + final Function 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 argPair = (IPair) argumentPair; + + return argPair.mapLeft(func); + }; + } + + @Override + default RightBifunctorMap fmapRight( + final Function 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 argPair = (IPair) 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 + * 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 IPair mapLeft(Function mapper); + + /** + * Transform the value on the right side of the pair. + * + * Doesn't modify the pair. + * + * @param + * 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 IPair mapRight(Function mapper); + + /** + * Merge the two values in this pair into a single value. + * + * @param + * The type of the single value. + * + * @param merger + * The function to use for merging. + * + * @return The pair, merged into a single value. + */ + public MergedType merge(BiFunction 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 IPair 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 + * The type of data contained in the tree nodes. + * + */ +public interface ITree { + /** + * Append a child to this node. + * + * @param child + * The child to append to this node. + */ + void addChild(ITree 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 child); + + /** + * Collapse a tree into a single version. + * + * @param + * The intermediate type being folded. + * + * @param + * The type that is the end result. + * + * @param leafTransform + * The function to use to convert leaf values. + * + * @param nodeCollapser + * The function to use to convert internal nodes and their + * children. + * + * @param resultTransformer + * The function to use to convert a state to the returned + * version. + * + * @return The final transformed state. + */ + ReturnedType collapse(Function leafTransform, + BiFunction, NewType> nodeCollapser, + Function resultTransformer); + + /** + * Execute a given action for each of this tree's children. + * + * @param action + * The action to execute for each child. + */ + void doForChildren(Consumer> 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 flatMapTree(final Function> mapper) { + return topDownTransform(dat -> TopDownTransformResult.PUSHDOWN, node -> { + if(node.getChildrenCount() > 0) { + final ITree 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 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 + * 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. + */ + ITree rebuildTree(Function leafTransformer, + Function 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 nodePicker, UnaryOperator 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 topDownTransform(Function transformPicker, + UnaryOperator> transformer); + + /** + * Transform one of this nodes children. + * + * @param + * The type of the transformed value. + * + * @param childNo + * The number of the child to transform. + * + * @param transformer + * The function to use to transform the value. + * + * @return The transformed value. + * + * @throws IllegalArgumentException + * if the childNo is out of bounds (0 <= childNo <= + * childCount()). + */ + TransformedType transformChild(int childNo, + Function, TransformedType> transformer); + + /** + * Transform the value that is the head of this node. + * + * @param + * The type of the transformed value. + * + * @param transformer + * The function to use to transform the value. + * + * @return The transformed value. + */ + TransformedType transformHead(Function transformer); + + /** + * Transform the tree into a tree with a different type of token. + * + * @param + * The type of the new tree. + * + * @param transformer + * The function to use to transform tokens. + * + * @return A tree with the token types transformed. + */ + default ITree transformTree(final Function 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 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> 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 pred) { + Toggle 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 + * The type contained in the holder. + */ +public class Identity implements IHolder { + /* 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 IHolder bind(final Function> 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 Function> lift(final Function func) { + return (val) -> { + return new Identity<>(func.apply(val)); + }; + } + + @Override + public IHolder map(final Function mapper) { + return new Identity<>(mapper.apply(heldValue)); + } + + @Override + public String toString() { + return String.format("Identity [heldValue=%s]", heldValue); + } + + @Override + public IHolder transform(final UnaryOperator transformer) { + heldValue = transformer.apply(heldValue); + + return this; + } + + @Override + public UnwrappedType unwrap(final Function unwrapper) { + return unwrapper.apply(heldValue); + } + + /** + * Create a new identity container. + * + * @param val + * The contained value. + * + * @return A new identity container. + */ + public static Identity id(final ContainedType val) { + return new Identity<>(val); + } + + /** + * Create a new empty identity container. + * + * @return A new empty identity container. + */ + public static Identity 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 + * The type of the value being held. + */ +public class Lazy implements IHolder { + /* The supplier of the type. */ + private Supplier 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> 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 supp) { + valueSupplier = new SingleSupplier<>(supp); + + valueMaterialized = false; + } + + /* Create a new value from a supplier and a list of actions. */ + private Lazy(final Supplier supp, final IList> pendingActions) { + valueSupplier = supp; + + actions = pendingActions; + } + + @Override + public IHolder bind(final Function> binder) { + final IList> pendingActions = new FunctionalList<>(); + + actions.forEach(pendingActions::add); + + final Supplier supplier = () -> { + if(valueMaterialized) return heldValue; + + return valueSupplier.get(); + }; + + return new BoundLazy<>(() -> { + return new Lazy<>(supplier, pendingActions); + }, binder); + } + + @Override + public Function> lift(final Function func) { + return val -> { + return new Lazy<>(func.apply(val)); + }; + } + + @Override + public IHolder map(final Function mapper) { + final IList> pendingActions = new FunctionalList<>(); + + actions.forEach(pendingActions::add); + + return new Lazy<>(() -> { + ContainedType currVal = heldValue; + + if(!valueMaterialized) { + currVal = valueSupplier.get(); + } + + return pendingActions.reduceAux(currVal, UnaryOperator::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 transform(final UnaryOperator transformer) { + actions.add(transformer); + + return this; + } + + @Override + public UnwrappedType unwrap(final Function 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 Lazy 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 Lazy lazy(final Supplier 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 + * The type on the left side of the pair. + * + * @param + * The type on the right side of the pair. + */ +public class LazyPair implements IPair { + /* The supplier for the left value. */ + private Supplier 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 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 leftSupp, final Supplier rightSupp) { + /* Use single suppliers to catch double-instantiation bugs. */ + leftSupplier = new SingleSupplier<>(leftSupp); + rightSupplier = new SingleSupplier<>(rightSupp); + + leftMaterialized = false; + rightMaterialized = false; + } + + @Override + public IPair bind( + final BiFunction> binder) { + return new BoundLazyPair<>(leftSupplier, rightSupplier, binder); + } + + @Override + public IPair bindLeft( + final Function> leftBinder) { + final Supplier leftSupp = () -> { + if(leftMaterialized) return leftValue; + + return leftSupplier.get(); + }; + + return new HalfBoundLazyPair<>(leftSupp, leftBinder); + } + + @Override + public IPair bindRight( + final Function> rightBinder) { + final Supplier rightSupp = () -> { + if(rightMaterialized) return rightValue; + + return rightSupplier.get(); + }; + + return new HalfBoundLazyPair<>(rightSupp, rightBinder); + } + + @Override + public IPair combine( + final IPair otherPair, + final BiFunction leftCombiner, + final BiFunction 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 IPair mapLeft(final Function mapper) { + final Supplier leftSupp = () -> { + if(leftMaterialized) return mapper.apply(leftValue); + + return mapper.apply(leftSupplier.get()); + }; + + final Supplier rightSupp = () -> { + if(rightMaterialized) return rightValue; + + return rightSupplier.get(); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public IPair mapRight(final Function mapper) { + final Supplier leftSupp = () -> { + if(leftMaterialized) return leftValue; + + return leftSupplier.get(); + }; + + final Supplier rightSupp = () -> { + if(rightMaterialized) return mapper.apply(rightValue); + + return mapper.apply(rightSupplier.get()); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public MergedType merge(final BiFunction 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 + * The type of contained value. + */ +public class ListHolder implements IHolder { + private IList 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 toHold) { + heldValues = toHold; + } + + @Override + public IHolder bind(final Function> binder) { + final IList> boundValues = heldValues.map(binder); + + return new BoundListHolder<>(boundValues); + } + + @Override + public Function> lift(final Function func) { + return val -> { + return new ListHolder<>(new FunctionalList<>(func.apply(val))); + }; + } + + @Override + public IHolder map(final Function mapper) { + final IList mappedValues = heldValues.map(mapper); + + return new ListHolder<>(mappedValues); + } + + @Override + public IHolder transform(final UnaryOperator transformer) { + heldValues = heldValues.map(transformer); + + return this; + } + + @Override + public UnwrappedType unwrap(final Function 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 + * The type of value stored + */ +public class OneWayToggle implements Toggle { + 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 + * The type of the value that may or may not be held. + */ +public class Option implements IHolder { + 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 IHolder bind(final Function> binder) { + if(held == null) return new Option<>(null); + + return binder.apply(held); + } + + @Override + public Function> lift(final Function func) { + return val -> { + return new Option<>(func.apply(val)); + }; + } + + @Override + public IHolder map(final Function mapper) { + if(held == null) return new Option<>(null); + + return new Option<>(mapper.apply(held)); + } + + @Override + public IHolder transform(final UnaryOperator transformer) { + if(held != null) { + held = transformer.apply(held); + } + + return this; + } + + @Override + public UnwrappedType unwrap(final Function 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 + * The type of the left value. + * + * @param + * The type of the right value. + */ +public class Pair implements IPair { + /* 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 IPair bind( + final BiFunction> binder) { + if(binder == null) throw new NullPointerException("Binder must not be null."); + + return binder.apply(leftValue, rightValue); + } + + @Override + public IPair bindLeft( + final Function> leftBinder) { + if(leftBinder == null) throw new NullPointerException("Binder must not be null"); + + return leftBinder.apply(leftValue); + } + + @Override + public IPair bindRight( + final Function> rightBinder) { + if(rightBinder == null) throw new NullPointerException("Binder must not be null"); + + return rightBinder.apply(rightValue); + } + + @Override + public IPair combine( + final IPair otherPair, + final BiFunction leftCombiner, + final BiFunction 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 IPair mapLeft(final Function mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + return new Pair<>(mapper.apply(leftValue), rightValue); + } + + @Override + public IPair mapRight(final Function mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + return new Pair<>(leftValue, mapper.apply(rightValue)); + } + + @Override + public MergedType merge(final BiFunction 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 + */ +public class QueuedIterator implements Iterator { + private Iterator cur; + + private Deque> pending; + + /** + * Static method for constructing iterators. + * + * @return A queued iterator. + */ + public static QueuedIterator queued() { + return new QueuedIterator<>(); + } + + /** + * Static method for constructing iterators. + * + * @param vals + * The values to iterate over. + * + * @return A queued iterator. + */ + public static QueuedIterator 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 QueuedIterator queued(Iterator... 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 QueuedIterator queued(Iterable... 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... inits) { + this(); + + for (Iterator 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... inits) { + this(); + + for (Iterable 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 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 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 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 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 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 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 + * The type of the item. + */ +public class SingleIterator implements Iterator { + /* 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 + * The supplied type + */ +public class SingleSupplier implements Supplier { + /* The next supplier ID. */ + private static long nextID = 0; + /* The supplier to yield from. */ + private final Supplier 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 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 + * The value stored in the toggle. + */ +public interface Toggle { + /** + * 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 + * The type of the nodes in the tree. + */ +public class TopDownTransformIterator implements Iterator> { + /** + * Alias type for a tree transformation. + * + * @author student + * + * @param + * The type contained in the tree. + */ + public interface TreeTransform + extends BiFunction, Consumer>>, ITree> { + + } + + /* + * The function that picks how to transform a given node + */ + private final Function picker; + /* + * The transform to apply to a given node. + */ + private final TreeTransform transform; + + private ITree preParent; + private ITree postParent; + + private final Deque> preChildren; + private final Deque> postChildren; + + private TopDownTransformIterator curChild; + + private boolean done; + private boolean initial; + + private final Deque>> toYield; + private Iterator> 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 pickr, + final TreeTransform transfrm, final ITree 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> 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 flushYields(final ITree 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 next() { + if (done) + throw new NoSuchElementException(); + + /* + * Flush any values that need to be yielded. + */ + if (currYield != null) { + ITree 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 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 res = curChild.next(); + //System.out.println("\t\tTRACE: adding node " + res + " to children"); + postChildren.add(res); + + return flushYields(res); + } + + ITree res = null; + + if (postParent == null) { + res = new Tree<>(preParent.getHead()); + + //System.out.println("\t\tTRACE: adding nodes " + postChildren + " to " + res); + + for (final ITree 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 child : postChildren) { + res.addChild(child); + } + } + + done = true; + return flushYields(res); + } + + final ITree 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 + * The source iterator type. + * + * @param + * The destination iterator type. + */ +public class TransformIterator implements Iterator { + /* Our source of values. */ + private final Iterator source; + /* Transform function. */ + private final Function transform; + + /** + * Create a new transform iterator. + * + * @param source + * The source iterator to use. + * + * @param transform + * The transform to apply. + */ + public TransformIterator(final Iterator source, final Function 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 + * The type contained in the tree. + */ +public class Tree implements ITree { + /* The data/label for this node. */ + private ContainedType data; + + /* The children of this node. */ + private IList> 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> 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... childrn) { + this(leaf); + + hasChildren = true; + + childCount = 0; + + children = new FunctionalList<>(); + + for(final ITree child : childrn) { + children.add(child); + + childCount++; + } + } + + @Override + public void addChild(final ContainedType child) { + addChild(new Tree(child)); + } + + @Override + public void addChild(final ITree child) { + if(hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.add(child); + } + + @Override + public void prependChild(final ITree child) { + if(hasChildren == false) { + hasChildren = true; + + children = new FunctionalList<>(); + } + + childCount++; + + children.prepend(child); + } + + @Override + public void doForChildren(final Consumer> action) { + if(childCount > 0) { + children.forEach(action); + } + } + + @Override + public int getChildrenCount() { + return childCount; + } + + @Override + public int revFind(final Predicate> 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 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 ReturnedType collapse(final Function leafTransform, + final BiFunction, NewType> nodeCollapser, + final Function resultTransformer) { + return resultTransformer.apply(internalCollapse(leafTransform, nodeCollapser)); + } + + @Override + public ITree flatMapTree(final Function> mapper) { + if(hasChildren) { + final ITree flatMappedData = mapper.apply(data); + + final IList> 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 internalCollapse(final Function leafTransform, + final BiFunction, NewType> nodeCollapser) { + if(hasChildren) { + final IList 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 kid = (Tree) 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 ITree rebuildTree(final Function leafTransformer, + final Function operatorTransformer) { + if(hasChildren) { + final IList> 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 nodePicker, + final UnaryOperator transformer) { + if(hasChildren) { + children.forEach(child -> child.selectiveTransform(nodePicker, transformer)); + } else { + data = transformer.apply(data); + } + } + + @Override + public ITree topDownTransform( + final Function transformPicker, + final UnaryOperator> transformer) { + final TopDownTransformResult transformResult = transformPicker.apply(data); + + switch(transformResult) { + case PASSTHROUGH: + ITree result = new Tree<>(data); + + if(hasChildren) { + children.forEach(child -> { + final ITree 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 kid = child.topDownTransform(transformPicker, + transformer); + + result.addChild(kid); + }); + } + + return transformer.apply(result); + case PULLUP: + final ITree intermediateResult = transformer.apply(this); + + result = new Tree<>(intermediateResult.getHead()); + + intermediateResult.doForChildren(child -> { + final ITree 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 transformChild(final int childNo, + final Function, 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 selectedKid = children.getByIndex(childNo); + + return transformer.apply(selectedKid); + } + + @Override + public TransformedType transformHead( + final Function 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 + * The type of value to toggle between. + */ +public class ValueToggle implements Toggle { + /* 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 implements IHolder { + /* The old value. */ + private final Supplier> oldSupplier; + + /* The function to use to transform the old value into a new value. */ + private final Function> binder; + + /* The bound value being held. */ + private IHolder boundHolder; + + /* Whether the bound value has been actualized or not. */ + private boolean holderBound; + + /* Transformations currently pending on the bound value. */ + private final IList> 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> supp, + final Function> binder) { + oldSupplier = supp; + this.binder = binder; + } + + @Override + public IHolder bind(final Function> bindr) { + if(bindr == null) throw new NullPointerException("Binder must not be null"); + + /* Prepare a list of pending actions. */ + final IList> pendingActions = new FunctionalList<>(); + actions.forEach(pendingActions::add); + + /* Create the new supplier of a value. */ + final Supplier> typeSupplier = () -> { + IHolder 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 Function> lift( + final Function func) { + if(func == null) throw new NullPointerException("Function to lift must not be null"); + + return (val) -> { + return new Lazy<>(func.apply(val)); + }; + } + + @Override + public IHolder map(final Function mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + /* Prepare a list of pending actions. */ + final IList> pendingActions = new FunctionalList<>(); + actions.forEach(pendingActions::add); + + /* Prepare the new supplier. */ + final Supplier typeSupplier = () -> { + IHolder 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 transform(final UnaryOperator transformer) { + if(transformer == null) throw new NullPointerException("Transformer must not be null"); + + actions.add(transformer); + + return this; + } + + @Override + public UnwrappedType unwrap(final Function 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 implements IPair { + /* The supplier of the left value. */ + private final Supplier leftSupplier; + /* The supplier of the right value. */ + private final Supplier rightSupplier; + + /* The binder to transform values. */ + private final BiFunction> binder; + + /* The bound pair. */ + private IPair 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 leftSupp, final Supplier rightSupp, + final BiFunction> bindr) { + leftSupplier = leftSupp; + rightSupplier = rightSupp; + binder = bindr; + } + + @Override + public IPair bind( + final BiFunction> bindr) { + if(bindr == null) throw new NullPointerException("Binder must not be null"); + + final IHolder> newPair = new Identity<>(boundPair); + final IHolder newPairMade = new Identity<>(pairBound); + + final Supplier 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 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 IPair bindLeft( + final Function> leftBinder) { + if(leftBinder == null) throw new NullPointerException("Left binder must not be null"); + + final Supplier leftSupp = () -> { + IPair 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 IPair bindRight( + final Function> rightBinder) { + if(rightBinder == null) throw new NullPointerException("Right binder must not be null"); + + final Supplier rightSupp = () -> { + IPair 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 IPair combine( + final IPair otherPair, + final BiFunction leftCombiner, + final BiFunction 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 IPair mapLeft(final Function mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + final Supplier leftSupp = () -> { + if(!pairBound) { + final NewLeft leftVal = binder.apply(leftSupplier.get(), rightSupplier.get()).getLeft(); + + return mapper.apply(leftVal); + } + + return mapper.apply(boundPair.getLeft()); + }; + + final Supplier rightSupp = () -> { + if(!pairBound) return binder.apply(leftSupplier.get(), rightSupplier.get()).getRight(); + + return boundPair.getRight(); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public IPair mapRight(final Function mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + final Supplier leftSupp = () -> { + if(!pairBound) return binder.apply(leftSupplier.get(), rightSupplier.get()).getLeft(); + + return boundPair.getLeft(); + }; + + final Supplier 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 merge(final BiFunction 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 implements IHolder { + /* The list of contained holders. */ + private final IList> heldHolders; + + /** + * Create a new list of holders. + * + * @param toHold + * The list of holders to, well, hold. + */ + public BoundListHolder(final IList> toHold) { + heldHolders = toHold; + } + + @Override + public IHolder bind(final Function> binder) { + if(binder == null) throw new NullPointerException("Binder must not be null"); + + final IList> boundHolders = heldHolders.map((containedHolder) -> { + return containedHolder.bind(binder); + }); + + return new BoundListHolder<>(boundHolders); + } + + @Override + public Function> lift(final Function func) { + if(func == null) throw new NullPointerException("Function to lift must not be null"); + + return (val) -> { + return new ListHolder<>(func.apply(val)); + }; + } + + @Override + public IHolder map(final Function mapper) { + if(mapper == null) throw new NullPointerException("Mapper must not be null"); + + final IList> mappedHolders = heldHolders.map((containedHolder) -> { + return containedHolder.map(mapper); + }); + + return new BoundListHolder<>(mappedHolders); + } + + @Override + public IHolder transform(final UnaryOperator transformer) { + if(transformer == null) throw new NullPointerException("Transformer must not be null"); + + heldHolders.forEach((containedHolder) -> { + containedHolder.transform(transformer); + }); + + return this; + } + + @Override + public UnwrappedType unwrap(final Function 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 implements IPair { + /* The supplier of the old value. */ + private final Supplier oldSupplier; + + /* The function to transform the old value into a new pair. */ + private final Function> binder; + + /* The new bound pair. */ + private IPair 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 oldSupp, + final Function> bindr) { + oldSupplier = oldSupp; + binder = bindr; + } + + @Override + public IPair bind( + final BiFunction> bindr) { + final IHolder> newPair = new Identity<>(boundPair); + final IHolder newPairMade = new Identity<>(pairBound); + + final Supplier 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 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 IPair bindLeft( + final Function> leftBinder) { + final Supplier leftSupp = () -> { + IPair newPair = boundPair; + + if(!pairBound) { + newPair = binder.apply(oldSupplier.get()); + } + + return newPair.getLeft(); + }; + + return new HalfBoundLazyPair<>(leftSupp, leftBinder); + } + + @Override + public IPair bindRight( + final Function> rightBinder) { + final Supplier rightSupp = () -> { + IPair newPair = boundPair; + + if(!pairBound) { + newPair = binder.apply(oldSupplier.get()); + } + + return newPair.getRight(); + }; + + return new HalfBoundLazyPair<>(rightSupp, rightBinder); + } + + @Override + public IPair combine( + final IPair otherPair, + final BiFunction leftCombiner, + final BiFunction 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 IPair mapLeft(final Function mapper) { + final Supplier leftSupp = () -> { + if(pairBound) return mapper.apply(boundPair.getLeft()); + + final NewLeft leftVal = binder.apply(oldSupplier.get()).getLeft(); + + return mapper.apply(leftVal); + }; + + final Supplier rightSupp = () -> { + if(pairBound) return boundPair.getRight(); + + return binder.apply(oldSupplier.get()).getRight(); + }; + + return new LazyPair<>(leftSupp, rightSupp); + } + + @Override + public IPair mapRight(final Function mapper) { + final Supplier leftSupp = () -> { + if(pairBound) return boundPair.getLeft(); + + return binder.apply(oldSupplier.get()).getLeft(); + }; + + final Supplier 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 merge(final BiFunction 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 + * The type of the wrapped value. + */ +public class WrappedLazy implements IHolder { + /* Held value. */ + private final IHolder> held; + + /** + * Create a new wrapped lazy value. + * + * @param wrappedHolder + * The holder to make lazy. + */ + public WrappedLazy(final IHolder 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> wrappedHolder, + @SuppressWarnings("unused") final boolean dummy) { + held = wrappedHolder; + } + + @Override + public IHolder bind(final Function> binder) { + final IHolder> newHolder = held.map((containedHolder) -> { + return containedHolder.bind(binder); + }); + + return new WrappedLazy<>(newHolder, false); + } + + @Override + public Function> lift(final Function func) { + return (val) -> { + return new Lazy<>(func.apply(val)); + }; + } + + @Override + public IHolder map(final Function mapper) { + final IHolder> newHolder = held.map((containedHolder) -> { + return containedHolder.map(mapper); + }); + + return new WrappedLazy<>(newHolder, false); + } + + @Override + public IHolder transform(final UnaryOperator transformer) { + held.transform((containedHolder) -> { + return containedHolder.transform(transformer); + }); + + return this; + } + + @Override + public UnwrappedType unwrap(final Function 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 + * The wrapped type. + */ +public class WrappedOption implements IHolder { + /* The held value. */ + private final IHolder> held; + + /** + * Create a new wrapped option. + * + * @param seedValue + * The value to wrap. + */ + public WrappedOption(final IHolder 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> toHold, + @SuppressWarnings("unused") final boolean dummy) { + held = toHold; + } + + @Override + public IHolder bind(final Function> binder) { + final IHolder> 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 Function> lift(final Function func) { + return (val) -> { + return new Option<>(func.apply(val)); + }; + } + + @Override + public IHolder map(final Function mapper) { + final IHolder> 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 transform(final UnaryOperator transformer) { + held.transform((containedHolder) -> { + return containedHolder.transform((containedValue) -> { + if(containedValue == null) return null; + + return transformer.apply(containedValue); + }); + }); + + return this; + } + + @Override + public UnwrappedType unwrap(final Function unwrapper) { + return held.unwrap((containedHolder) -> { + return containedHolder.unwrap((containedValue) -> { + if(containedValue == null) return null; + + return unwrapper.apply(containedValue); + }); + }); + } +} -- cgit v1.2.3