// MIT License
//
// Copyright (c) 2017 Stefan von Stein
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
package stonehorse.candy;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;
import static java.util.Collections.emptyIterator;
import static java.util.Objects.requireNonNull;
/**
* Functions of iterables creating lazy iterators. As they are lazy they can be composed without memory exhaustion.
* It's all functions which you easily create new ones of to extend the functionality.
*/
public class Iterables{
/**
* Tail call return value
*/
public static class Continuation<V> {
public final Supplier<Continuation<V>> fun;
public final V value;
public final boolean hasValue;
private Continuation(Supplier<Continuation< V>> fun, V value, boolean hasValue) {
this.fun = fun;
this.value = value;
this.hasValue = hasValue;
}
/**
* return recur to recur withLast f and a
*/
public static < V> Continuation<V> recur(Supplier<Continuation<V>> f) {
return new Continuation<>(f, null, false);
}
private static <V> Continuation<V> nil() {
return new Continuation<>(null, null, false);
}
/** return done to when last value is found */
public static <V> Continuation<V> done(V v) {
return new Continuation<>(null, v, true);
}
/**
* Return stop when done without a value. Null if on trampoline
*/
public static <V> Continuation< V> stop() {
return new Continuation<>(null, null, false);
}
/**
* return seq to yield lazy value v, and continue withLast f a
* f as null is same as done or stop, depending on v
* Will behave like recur on a trampoline
*/
public static < V> Continuation< V> seq(Supplier<Continuation<V>> f, V v) {
return new Continuation<>(f, v, true);
}
}
/**
* Will recur on fun until done(value)
*/
public static <V> V trampoline(Supplier<Continuation<V>> fun) {
boolean value = false;
Continuation< V> ret = Continuation.nil();
while (fun != null && !value) {
ret = fun.get();
fun = ret.fun;
value = ret.hasValue;
}
return ret.value;
}
/**
* Emits a lazy Iterable recuring until stop, done, null or lack of f
*/
public static <V> Iterable<V> lazy(final Supplier<Continuation< V>> fun) {
return ()-> new LazyIterator<>(fun);
}
private static class LazyIterator< V> implements Iterator<V> {
private Supplier<Continuation<V>> fun;
private V next;
private boolean hasNext = false;
public LazyIterator(Supplier<Continuation<V>> fun) {
this.fun = fun;
}
@Override public boolean hasNext() {
if (hasNext)
return true;
if (null == fun)
return false;
while (true) {
Continuation<V> ret = fun.get();
if(null==ret)
return false;
fun = ret.fun;
next = ret.value;
hasNext = ret.hasValue;
if (hasNext)
return true;
if (null == fun)
return false;
}
}
@Override
public V next() {
if (hasNext())
try {
hasNext = false;
return next;
} finally {
next = null;
}
throw new NoSuchElementException();
}
}
private static <T> List<T> arrayList(
T t0,
T t1){
List<T> l = new ArrayList<>(2);
l.add(t0);
l.add(t1);
return l;
}
private Iterables(){}
private static < V> Continuation<V> recur(Supplier<Continuation<V>> f) {
return Continuation.recur(f);
}
private static <V> Continuation<V> done(V v) {
return Continuation.done(v);
}
private static <V> Continuation< V> stop() {
return Continuation.stop();
}
private static < V> Continuation< V> seq(Supplier<Continuation<V>> f, V v) {
return Continuation.seq(f,v);
}
/**
* A new list with elements found in the next iterator of iterable
*/
public static <A> List<A> toList(Iterable<A> iterable) {
requireNonNulls(iterable);
List<A> list = new ArrayList<>();
for (A e : iterable)
list.add(e);
return list;
}
/**
* Combines elements of the first iterator into a single result by repeated application of a combining operation f where the initial result is accumulator
*/
public static <A, V>
A fold(BiFunction<? super A, ? super V, ? extends A> f,
A accumulator,
Iterable<? extends V> elements) {
requireNonNulls(f, elements);
// Accumulate by applying each with the accumulator to the BiFunction
for (V v : elements)
accumulator = f.apply(accumulator, v);
return accumulator;
}
/**
* Iterable of lazy iterators filtering another Iterable using a predicate
* <p>Example:
* <pre>{@code
* toList(filter( e -> 0==e%2, Arrays.asList(1, 2, 3, 4))) => [2, 4]
* }</pre>
*/
public static <T>
Iterable<T> filter(final Predicate<? super T> predicate, // Predicate rather than transformation
Iterable<T> source) {
requireNonNulls(predicate, source);
return () -> {
Iterator<T> sourceIterator = source.iterator();
return sourceIterator.hasNext()
? lazy(filterI(predicate, sourceIterator)).iterator()
: emptyIterator();
};
}
private static <T>
Supplier<Continuation<T>> filterI(Predicate<? super T> predicate,
Iterator<T> elements) {
return () -> {
if (!elements.hasNext())
return stop();
T next = elements.next();
return predicate.test(next)
? Continuation.seq(filterI(predicate, elements), next)
// Recur rather than seq when the element is ommitted
: Continuation.recur(filterI(predicate, elements));
};
}
private static
void requireNonNulls(Object... refs){
for(Object o : refs)
requireNonNull(o);
}
/**
* Iterable of lazy iterators applying a function to all element induced by a Iterable
* <p>Example:
* <pre>{@code
* toList(map( e -> e+1, Arrays.asList(1, 2, 3, 4))) => [2, 3, 4, 5]
* }</pre>
*/
public static <A, V> Iterable<V> map(final Function<? super A, ? extends V> f,
final Iterable<A> data) {
requireNonNulls(data, f);
return () -> {
Supplier<Continuation<V>> supplier = () -> mapIterate(f, data.iterator());
return lazy(supplier).iterator();
};
}
private static <A, V>
Continuation<V> mapIterate(final Function<? super A,? extends V> f,
final Iterator<A> elements) {
return !elements.hasNext()
? stop()
: seq(()->mapIterate(f, elements),
f.apply(elements.next()));
}
/**
* The first value of an Iterable
* <p>Example:
* <pre>{@code
* first(Arrays.asList(1, 2, 3, 4)) => 1
* }</pre>
*/
public static <T>
T first(final Iterable<T> iterable) {
Iterator<T> iterator = iterable.iterator();
return iterator.hasNext()
? iterator.next()
: null;
}
/**
* All values except first
* <p>Example:
* <pre>{@code
* rest(Arrays.asList(1, 2, 3, 4)) => [2, 3, 4]
* }</pre> */
public static <T>
Iterable<T> rest(Iterable<T> iterable) {
requireNonNull(iterable);
return ()->{
Iterator<T> i = iterable.iterator();
if(!i.hasNext())
return emptyIterator();
i.next();
return i.hasNext() ? i : emptyIterator();
};
}
/**
* All values except first, or empty
*/
public static <T>
Iterable<T> next(Iterable<T> iterable) {
requireNonNull(iterable);
Iterator<?> it = iterable.iterator();
if(!it.hasNext())
return null;
it.next();
if(!it.hasNext())
return null;
return ()->{
Iterator<T> i = iterable.iterator();
if(!i.hasNext())
return emptyIterator();
i.next();
if(i.hasNext())
return i;
return emptyIterator();
};
}
/**
* prepend value
* <p>Example:
* <pre>{@code
* with(0,Arrays.asList(1, 2, 3, 4)) => [0, 1, 2, 3, 4]
* }</pre> *
*/
public static <T>
Iterable<T> with(T t,
Iterable<? extends T> iterable) {
requireNonNull(iterable);
return () -> lazy(withI(t, iterable.iterator())).iterator();
}
private static <T>
Supplier<Continuation<T>> withI(T a, Iterator<? extends T> i) {
return () -> i.hasNext()
? seq(withI(i.next(), i), a)
: done(a);
}
/** Append value * <p>Example:
* <pre>{@code
* withLats(,Arrays.asList(1, 2, 3, 4), 5) => [1, 2, 3, 4, 5]
* }</pre> *
*/
public static <T>
Iterable<T> withLast(Iterable<T> iterable, T b){
requireNonNull(iterable);
return ()-> lazy(withLastI( iterable.iterator(), b)).iterator();
}
private static <T> Supplier<Continuation<T>> withLastI(Iterator<T> a, T b){
return ()-> a.hasNext()
? seq(withLastI(a,b), a.next())
: done(b);
}
/**
* Accumulate into value, with explicit accumulator
* <p>Example:
* <pre>{@code
* reduce((a,v)->a+v, Arrays.asList(1,2,3,4)) => 10
* }</pre>
*/
public static <T>
T reduce(BiFunction<? super T, ? super T, ? extends T> f,
Iterable<? extends T> elements) {
return fold(f, first(elements), rest(elements));
}
/**
* Consecutive accumulations with explicit accumulator
* <p>Example:
* <pre>{@code
* reductions((a,v)->a+v, 0, Arrays.asList(1,2,3,4)) => [0, 1, 3, 6, 10]
* }</pre> */
public static <A, V>
Iterable<V> reductions(final BiFunction<? super V, ? super A, ? extends V> f,
final V accumulator,
final Iterable<? extends A> elements) {
requireNonNulls(elements, f);
return () -> with(accumulator,
lazy(reductionsI(f,
accumulator,
elements.iterator()))).iterator();
}
private static <V, A>
Supplier<Continuation<V>> reductionsI(BiFunction<? super V, ? super A, ? extends V> f,
V a,
final Iterator<? extends A> elements) {
return () -> {
if (!elements.hasNext())
return stop();
V acc = f.apply(a, elements.next());
return elements.hasNext()
? seq(reductionsI(f, acc, elements), acc)
: done(acc);
};
}
/** bind of list monad
* Iterable of lazy iterators which concatenate the result of applying map to every element in iterators of data.
* <p>Example:
* <pre>{@code
* flatMap(v -> Arrays.asList(v, v), Arrays.asList(1, 2)) => [1, 1, 2, 2]
* }</pre>
* */
public static <V, A>
Iterable<A> flatMap(Function<? super V, ? extends Iterable<? extends A>> f,
Iterable<? extends V> data) {
requireNonNulls(data, f);
return lazy(flatMapI(f, null, data.iterator()));
}
private static <V, A> Supplier<Continuation<A>> flatMapI(Function<? super V, ? extends Iterable<? extends A>> f,
Iterator<? extends A> current,
Iterator<? extends V> data) {
return () -> {
if (current != null && current.hasNext()) {
return seq(flatMapI(f, current, data), current.next());
}
while (data.hasNext()) {
Iterable<? extends A> nextChunk = f.apply(data.next());
if (nextChunk != null) {
Iterator<? extends A> nextIter = nextChunk.iterator();
if (nextIter.hasNext()) {
return recur(flatMapI(f, nextIter, data));
}
}
}
return stop();
};
}
/**
* Iterable of lazy infinite iterators iterating over function with initial value. That is x, f(x), f(f(x)) and so on
* <p>Example:
* <pre>{@code
* iterate (x -> x + 1, 0) -> [0,1,2,3,4.....
* }</pre>*/
public static <T>
Iterable<T> iterate(Function<? super T, ? extends T> f,
T x) {
requireNonNull(f);
return () -> with(x, lazy(iterateI(f, x))).iterator();
}
private static <T>
Supplier<Continuation<T>> iterateI(Function<? super T, ? extends T> f,
T x) {
return () -> {
T n = f.apply(x);
return seq(iterateI(f,n), n);
};
}
/**
* Iterable of lazy iterators having num first values of iterable
* <p>Example:
* <pre>{@code
* take(2, Arrays.asList(1, 2, 3, 4)) => [1, 2]
* }</pre>
*/
public static <T>
Iterable<T> take(final int num,
final Iterable<T> iterable) {
requireNonNull(iterable);
return () -> num < 1
? emptyIterator()
: lazy(takeI(num, iterable.iterator())).iterator();
}
private static <T>
Supplier<Continuation<T>> takeI(int num, Iterator<? extends T> iterator) {
return () -> iterator.hasNext() && num > 0
? seq(takeI(num - 1, iterator), iterator.next())
: stop();
}
/**
* Iterable of lazy iterators having the first elements matching predicate
* <p>Example:
* <pre>{@code
* takeWhile(x -> x<3, Arrays.asList(1, 2, 3, 4)) => [1, 2]
* }</pre>
*/
public static <T>
Iterable<T> takeWhile(Predicate<? super T> pred,
Iterable<T> iterable) {
requireNonNulls(pred,iterable);
return () -> lazy(takeWhileI(pred,
iterable.iterator())).iterator();
}
private static <T> Supplier<Continuation<T>> takeWhileI(Predicate<? super T> pred, Iterator<? extends T> iterator) {
return () -> {
if (!iterator.hasNext())
return stop();
T t = iterator.next();
return pred.test(t)
? seq(takeWhileI(pred, iterator), t)
: stop();
};
}
/** Flattens Iterable<Iterable <T>> into Iterable<T> */
public static <T>
Iterable<T> join(Iterable<? extends Iterable<? extends T>> nested) {
requireNonNull(nested);
return flatMap(Function.identity(), nested);
}
/** creates a singleton list of a value, lifting the value into List context */
public static <T>
Iterable<T> unit(T value) {
return Collections.singletonList(value);
}
/** Iterable of lazy iterators partitioning elements by application to function
* <p>Example:
* <pre>{@code
* partitionBy( v -> v%2, asList(1, 3, 4, 5, 7, 6)) => [[1, 3], [4], [5, 7], [6]]
* }</pre>
*/
public static <T>
Iterable<List<T>> partitionBy(Function<? super T, Object> function,
Iterable<T> iterable) {
requireNonNulls(function, iterable);
return () -> lazy(partitionByI(function,
new Group<>(null, null),
iterable.iterator())).iterator();
}
static private
class Group<T> {
final Object key;
final List<T> values;
Group(Object key, List<T> values) {
this.key = key;
this.values = values;
}
}
private static <T>
Supplier<Continuation<List<T>>> partitionByI(Function<? super T, Object> function,
Group<T> acc,
Iterator<T> it) {
return () -> {
if (it.hasNext()) {
T value = it.next();
Object key = function.apply(value);
if (Objects.equals(acc.key, key)) {
List<T> current = acc.values != null ? acc.values : new ArrayList<>();
current.add(value);
return recur(partitionByI(function, new Group<>(key, current), it));
}
if (acc.values != null) {
List<T> newGroup = new ArrayList<>();
newGroup.add(value);
return seq(partitionByI(function, new Group<>(key, newGroup), it),
new ArrayList<>(acc.values)); // ← concrete copy
}
List<T> firstGroup = new ArrayList<>();
firstGroup.add(value);
return recur(partitionByI(function, new Group<>(key, firstGroup), it));
}
return acc.values == null
? stop()
: done(new ArrayList<>(acc.values)); // ← also concrete
};
}
/**
* Iterable of lazy iterators but the num first elements of iterable
*/
public static <T> Iterable<T> drop(int num, Iterable<T> iterable) {
requireNonNull( iterable);
return () ->
(num < 1)
? iterable.iterator()
: lazy(dropI(num, iterable.iterator())).iterator();
}
private static <T> Supplier<Continuation<T>> dropI(int num, Iterator<? extends T> i) {
return () -> {
if (0 < num) {
if (i.hasNext()) {
i.next();
return recur(dropI(num - 1, i));
}
return stop();
}
if (i.hasNext()) {
T v = i.next();
return seq(dropI(0, i), v);
}
return stop();
};
}
/** Iterable of lazy iterators emitting all elements but except the first matching predicate*/
public static <T> Iterable<T> dropWhile(Predicate<? super T> predicate, Iterable<T> iterable) {
requireNonNulls( iterable, predicate);
return () -> lazy(dropWhileI(predicate, true, iterable.iterator())).iterator();
}
private static <T> Supplier<Continuation<T>> dropWhileI(Predicate<? super T> predicate, boolean dropping, Iterator<T> i){
return ()->{
if(i.hasNext()){
T v=i.next();
return (dropping && predicate.test(v))
? recur(dropWhileI(predicate, true, i))
: seq(dropWhileI(predicate, false, i), v);
}
return stop();
};
}
}
