// 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.*;
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.*;
/**
* 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){
List<T> l = new ArrayList<>(1);
l.add(t0);
return l;
}
private static <T> List<T> arrayList(
T t0,
T t1){
List<T> l = new ArrayList<>(2);
l.add(t0);
l.add(t1);
return l;
}
static <T> List<T> asList(
T t0,
T t1){
List<T> l = arrayList(
t0,
t1
);
return Collections.unmodifiableList(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
* * <p>Example:
* <pre>{@code
* fold((a,v)->a+v, 0, Arrays.asList(1,2,3,4)) => 10
* }</pre>
*/
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));
};
}
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()));
}
}
