/*
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.query;

import java.io.IOException;
import java.nio.file.Path;
import java.util.*;
import java.util.function.*;
import java.util.stream.Collector;
import java.util.stream.Stream;

import net.ranides.assira.collection.HashFunction;
import net.ranides.assira.collection.iterators.EnumerationUtils;
import net.ranides.assira.collection.iterators.IteratorUtils;
import net.ranides.assira.collection.lists.LazyList;
import net.ranides.assira.collection.lists.NativeArrayList;
import net.ranides.assira.collection.lists.VirtualList;
import net.ranides.assira.collection.query.base.*;
import net.ranides.assira.collection.query.derived.CQTreeBFS;
import net.ranides.assira.collection.query.derived.CQTreeDFS;
import net.ranides.assira.functional.Consumers.EachConsumer;
import net.ranides.assira.functional.Functions.EachFunction;
import net.ranides.assira.functional.Predicates.EachPredicate;
import net.ranides.assira.functional.checked.CheckedFunction;
import net.ranides.assira.functional.checked.CheckedSupplier;
import net.ranides.assira.generic.Ref;
import net.ranides.assira.reflection.*;

/**
 * Query interface is generalization of Streaming API which allows reuse of constructed query.
 *
 * Most important: constructed query can work with MUTABLE source, recomputing result every time.
 *
 * Recomputation can be disabled by "fetch" method.
 *
 * @param <T> T
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 */
@SuppressWarnings("PMD.TooManyDifferentMethods")
public interface CQuery<T> extends Iterable<T> {

    /**
     * Returns empty Query
     *
     * @param <T> T
     * @return query
     */
    static <T> CQuery<T> empty() {
        return from().empty();
    }

    /**
     * Returns empty Query
     *
     * @param <T> T
     * @return query
     */
    static <T> CQuery<T> empty(Supplier<? extends RuntimeException> message) {
        return from().empty(message);
    }

    /**
     * Returns BUILDER which allows construction Query by wrapping provided data source (for example: in memory collection).
     *
     * @param <T> T
     * @return builder
     */
    @SuppressWarnings("unchecked")
    static <T> WrapBuilder<T> from() {
        return WrapBuilder.INSTANCE;
    }

    /**
     * Returns new Query which compute results by using provided collection.
     * Collection can be modified between call.
     * Collection and Query must be synchronized between threads until Collection is thread-safe.
     *
     *
     * @param source source
     * @param <T> T
     * @return query
     */
    static  <T> CQuery<T> from(Collection<T> source) {
        return from().collection(source);
    }

    /**
     * Returns BUILDER which allows construction composite Query from more than one data sources.
     * For example: it allows concatenation of other queries.
     *
     * Please note, that builder tries to infer returned data type.
     *
     * @param <R> R
     * @return builder
     */
    static <R> Builder<R> builder() {
        return new Builder<>();
    }

    /**
     * Returns stream characteristics.
     * CQueryFeatures tells which methods are optimized and should be prefferred.
     * This method is used extensivelly in CQueryAbstract.
     * This method can be used in CQuery subclassess and general algorithms.
     *
     * @return features
     */
    CQueryFeatures features();

    Supplier<? extends RuntimeException> message();

    CQuery<T> message(Supplier<? extends RuntimeException> message);

    /**
     * Turns on/off parallelization.
     * Please note: this method is stateless, but it can return "this".
     *
     * @param enabled enabled
     * @return new stream
     */
    CQuery<T> parallel(boolean enabled);

    /**
     * Turns on parallelization.
     * Please note: this method is stateless, but it can return "this".
     *
     * @return new stream
     */
    CQuery<T> parallel();

    /**
     * Turns on/off parallelization.
     * Please note: this method is stateless, but it can return "this".
     *
     * @param enabled enabled
     * @return new stream
     */
    CQuery<T> sequential(boolean enabled);

    /**
     * Turns off parallelization.
     * Please note: this method is stateless, but it can return "this".
     *
     * @return new stream
     */
    CQuery<T> sequential();

    /**
     * Terminal operation.
     * Creates new stream navigating through computed results.
     * Please note: supports partial evaluation.
     *
     * @return new stream
     */
    Stream<T> stream();

    /**
     * Terminal operation.
     * Creates new iterator navigating through computed results.
     * Please note: supports partial evaluation.
     *
     * @return new iterator
     */
    @Override
    Iterator<T> iterator();

    /**
     * Terminal operation.
     * Creates new spliterator navigating through computed results.
     * Please note: supports partial evaluation.
     *
     * @return new spliterator
     */
    @Override
    Spliterator<T> spliterator();

    /**
     * Terminal operation.
     * Returns number of possibly computed results.
     * Please note: it avoids computation elements if possible.
     * Please note: "features" can inform that this method is optimized.
     *
     * @return int
     */
    int size();

    /**
     * Terminal operation.
     * Inserts all computed results into provided collector.
     * Please note: evaluates all content.
     *
     * @param collector collector
     * @param <A> intermediate accumulation type
     * @param <R> collection
     * @return collection
     */
    <A,R> R collect(Collector<? super T,A,R> collector);

    /**
     * Terminal operation.
     * Creates array with all computed results.
     * Please note: evaluates all content.
     *
     * @return array
     */
    T[] array();

    /**
     * Terminal operation.
     * Creates array with all computed results.
     * Please note: evaluates all content.
     *
     * @param generator generator
     * @param <A> A
     * @return array
     */
    <A> A[] array(IntFunction<A[]> generator);

    /**
     * Terminal operation.
     * Creates list view with computed results.
     * Please note: in general, evaluates all content.
     *
     * It tries to avoid unecessary copying, returning copy-on-write lists.
     * It tries to avoid unecessary evalution, returning virtual lists.
     *
     * @return list
     */
    List<T> list();

    /**
     * Terminal operation.
     * Creates new set with computed results.
     * Please note: evaluates all content.
     * Please note: it uses hash set which uses natural "hash" and "equals" methods for elements.
     *
     * @return set
     */
    Set<T> set();

    /**
     * Terminal operation.
     * Converts all elements into String and concatenates them.
     * Please note: order in parallel stream are undefined.
     *
     * @return string
     */
    String join();

    /**
     * Terminal operation.
     * Converts all elements into String and concatenates them.
     * Please note: order in parallel stream are undefined.
     *
     * @param joiner joiner
     * @return string
     */
    String join(String joiner);

    /**
     * Precomputes all results and stores as intermediate in memory.
     * All previous operations in chain won't be executed in following queries.
     *
     * @return query
     */
    CQuery<T> fetch();

    /**
     * Schedules "fetch" operation, which will be executed at next terminal operation.
     * Effectively, it is "lazy fetch" operation.
     *
     * @return query
     */
    CQuery<T> prefetch();

    /**
     * Precomputes all results and stores as intermediate in memory.
     * Collected results are serialized into provided file.
     *
     * If file already exists, computation won't be executed, but result will be
     * loaded instantly from file.
     *
     * Effectively, it is persistent "fetch" operation.
     * Usable if we want to preserve results between executions of java application.
     *
     * @param filename filename
     * @return query
     * @throws IOException on error
     */
    CQuery<T> cache(Path filename) throws IOException;

    /**
     * Creates composite query with results merged from both this query and provided one.
     * Please note: we append query by reference, not results computed by provided query.
     *
     * @param next next
     * @return query
     */
    CQuery<T> append(CQuery<T> next);

    /**
     * Terminal operation.
     * Creates Map, which uses provided function to associate every element with key.
     * Generated keys should be unique, "group" does not create MultiMap.
     *
     * @param key key
     * @param <K> K
     * @return map
     */
    <K> Map<K,T> group(Function<? super T, ? extends K> key);

    /**
     * Terminal operation.
     * Creates Map, which uses provided functions to create key-value pair from every element.
     * Generated keys should be unique, "group" does not create MultiMap.
     *
     * @param key key
     * @param value value
     * @param <K> K
     * @param <V> V
     * @return map
     */
    <K,V> Map<K,V> group(Function<? super T, ? extends K> key, Function<? super T, V> value);


    /**
     * Checks if stream is empty.
     * Please note: it avoids computation elements if possible,
     * it evaluates one element at most.
     *
     * @return boolean
     */
    boolean isEmpty();

    /**
     * Returns query which stops traversal if predicate returns "false"
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @return query
     */
    CQuery<T> limit(Predicate<? super T> p);

    /**
     * Returns query which stops traversal after at most "n" elements.
     * Please note: supports partial evaluation.
     *
     * @param n n
     * @return query
     */
    CQuery<T> limit(int n);

    /**
     * Returns query which skips at most "n" elements and returns remaining.
     * Please note: supports partial evaluation.
     *
     * Please note: it avoids computation elements if possible,
     * but it could evaluate even all "skipped" elements.
     *
     * @param n n
     * @return query
     */
    CQuery<T> skip(int n);

    /**
     * Returns query which skips at most "begin" elements and returns remaining until "end".
     * Please note: supports partial evaluation.
     *
     * Please note: it avoids computation elements if possible,
     * but it could evaluate even all elements before "end".
     *
     * @param begin begin
     * @param end end
     * @return query
     */
    CQuery<T> slice(int begin, int end);

    /**
     * Returns query with items accepted by predicate.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @return query
     */
    CQuery<T> filter(Predicate<? super T> p);

    /**
     * Returns query with items accepted by predicate.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @return query
     */
    CQuery<T> filterEach(EachPredicate<? super T> p);

    /**
     * Returns query which returns only elements of specified type.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> filter(Class<R> p);

    /**
     * Returns query which returns only elements of specified type.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> filter(IClass<R> p);

    /**
     * Returns query without items accepted by predicate.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @return query
     */
    CQuery<T> discard(Predicate<? super T> p);

    /**
     * Returns query without items accepted by predicate.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @return query
     */
    CQuery<T> discardEach(EachPredicate<? super T> p);

    /**
     * Returns query which discards elements of specified type.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @return query
     */
    CQuery<T> discard(Class<?> p);

    /**
     * Returns query which discards elements of specified type.
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @return query
     */
    CQuery<T> discard(IClass<?> p);

    /**
     * Returns query which calculates new value for every item.
     * Please note: supports partial evaluation.
     *
     * @param f f
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> map(Function<? super T,R> f);

    /**
     * Returns query which casts every item to specified class.
     * Please note: supports partial evaluation.
     *
     * @param f f
     * @return query
     * @param <R> R
     */
    <R> CQuery<R> map(Class<R> f);

    /**
     * Returns query which casts every item to specified class.
     * Please note: supports partial evaluation.
     *
     * @param f f
     * @return query
     * @param <R> R
     */
    <R> CQuery<R> map(IClass<R> f);

    /**
     * Returns query which calculates new value for every item.
     * If function returns "empty" then value is discarded.
     * Please note: supports partial evaluation.
     *
     * @param f f
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> mapOptional(Function<? super T, Ref<R>> f);

    /**
     * Returns query which calculates new value for every item.
     * Please note: supports partial evaluation.
     *
     * @param f f
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> mapEach(EachFunction<? super T,R> f);

    /**
     * Expands every item into Query and concatenates generated results into one query.
     * Please note: supports partial evaluation of outer query and inner queries.
     *
     * @param f f
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> flat(Function<? super T, CQuery<R>> f);

    /**
     * Expands every item into Iterator and concatenates generated results into one query.
     * Please note: supports partial evaluation of outer query and inner iterators.
     *
     * @param f f
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> flatIterable(Function<? super T, Iterable<R>> f);

    /**
     * Expands every item into array and concatenates generated results into one query.
     * Please note: supports partial evaluation of outer query.
     *
     * @param f f
     * @param <R> R
     * @return query
     */
    <R> CQuery<R> flatArray(Function<? super T, R[]> f);

    /**
     * Returns query which conditionally calculates new value for every item.
     * It checks if element should be mapped or returned without change.
     *
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> mapIf(Predicate<? super T> p, Function<? super T,T> f);

    /**
     * Returns query which conditionally calculates new value for every item.
     * It checks if element should be mapped or returned without change.
     *
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> mapEachIf(EachPredicate<? super T> p, EachFunction<? super T,T> f);

    /**
     * Returns query which conditionally calculates new value for every item.
     * It checks if element should be mapped or returned without change.
     * If mapping function returns "empty" then value is discarded.
     *
     * Please note: supports partial evaluation.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> mapOptionalIf(Predicate<? super T> p, Function<? super T, Ref<T>> f);

    /**
     * Expands conditionally every item into Query and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query and inner queries.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> flatIf(Predicate<? super T> p, Function<? super T, CQuery<T>> f);

    /**
     * Expands conditionally every item into Iterator and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query and inner iterators.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> flatIterableIf(Predicate<? super T> p, Function<? super T, Iterable<T>> f);

    /**
     * Expands conditionally every item into array and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> flatArrayIf(Predicate<? super T> p, Function<? super T, T[]> f);

    /**
     * Expands conditionally every item into Query and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query and inner queries.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> deepFlatIf(Predicate<? super T> p, Function<? super T, CQuery<T>> f);

    /**
     * Expands conditionally every item into Iterator and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query and inner iterators.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> deepFlatIterableIf(Predicate<? super T> p, Function<? super T, Iterable<T>> f);

    /**
     * Expands conditionally every item into array and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> deepFlatArrayIf(Predicate<? super T> p, Function<? super T, T[]> f);

    /**
     * Expands conditionally every item into Query and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query and inner queries.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> treeFlatIf(Predicate<? super T> p, Function<? super T, CQuery<T>> f);

    /**
     * Expands conditionally every item into Iterator and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query and inner iterators.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> treeFlatIterableIf(Predicate<? super T> p, Function<? super T, Iterable<T>> f);

    /**
     * Expands conditionally every item into array and concatenates generated results into one query.
     * It checks if element should be expanded or returned without change.
     * Please note: supports partial evaluation of outer query.
     *
     * @param p p
     * @param f f
     * @return query
     */
    CQuery<T> treeFlatArrayIf(Predicate<? super T> p, Function<? super T, T[]> f);

    /**
     * Terminal operation.
     * Computes final result by applying accumulator on every item, combining it with
     * intermediate result. First item is combined with "identity" value.
     * Returns "identity" if query is empty.
     *
     * @param identity identity
     * @param accumulator accumulator
     * @return value
     */
    T reduce(T identity, BinaryOperator<T> accumulator);

    /**
     * Terminal operation.
     * Computes final result by applying accumulator on every item, combining it with
     * intermediate result.
     *
     * Returns "null" if query is empty.
     * If query contains only one element, it will be returned.
     * If query contains more elements, first element is assummed to be starting "intermediate"
     *
     * @param accumulator accumulator
     * @return value
     */
    T reduce(BinaryOperator<T> accumulator);

    /**
     * Terminal operation.
     * Returns minimal element from query.
     * It uses provided comparison function to establish order of elements.
     *
     * Returns null if query is empty.
     *
     * @param cmp cmp
     * @return value
     */
    T min(Comparator<? super T> cmp);

    /**
     * Terminal operation.
     * Returns maximal element from query.
     * It uses provided comparison function to establish order of elements.
     *
     * Returns null if query is empty.
     *
     * @param cmp cmp
     * @return value
     */
    T max(Comparator<? super T> cmp);

    /**
     * Terminal operation.
     * Returns value only if stream contains exactly one element.
     * If query contains more elements or none, it returns empty.
     *
     * It evaluates at most two elements.
     *
     * @return optional
     */
    Ref<T> single();

    /**
     * Terminal operation.
     * Returns value only if stream contains exactly one element.
     * If query is empty, returns none.
     * If query contains more elements, throws exception.
     *
     * It evaluates at most two elements.
     *
     * @param ambigous ambigous
     * @param <X> X
     * @return optional
     * @throws X if stream contains more than one element
     */
    <X extends Throwable> Ref<T> single(Supplier<X> ambigous) throws X;

    /**
     * Terminal operation.
     * Returns first element or empty.
     *
     * @return optional
     */
    Ref<T> first();

    /**
     * Terminal operation.
     * Returns last element or empty.
     *
     * It evalues only last element, if possible,
     * but it could evaluate even all elements in stream.
     *
     * @return optional
     */
    Ref<T> last();

    /**
     * Terminal operation.
     * Returns element at specified index.
     *
     * It evalues only one element, if possible,
     * but it could evaluate even all elements before "index".
     *
     * @param index index
     * @return optional
     */
    Ref<T> at(int index);

    /**
     * Returns query with distinct values.
     * It uses natural comparator.
     * Detected duplicates are stored internally inside some hash collection (e.g. HashSet).
     *
     * Please note: supports partial evaluation, it discards elements during traversal.
     *
     * @return query
     */
    CQuery<T> distinct();

    /**
     * Returns query with distinct values.
     * It uses provided hash function to detect duplicates.
     * Detected duplicates are stored internally inside some hash collection (e.g. HashSet).
     *
     * Please note: supports partial evaluation, it discards elements during traversal.
     *
     * @param eq eq
     * @return query
     */
    CQuery<T> distinct(HashFunction<T> eq);

    /**
     * Returns query with distinct values.
     * It uses provided comparator to detect duplicates.
     * Detected duplicates are stored internally inside some sorted collection (e.g. tree).
     *
     * Please note: supports partial evaluation, it discards elements during traversal.
     *
     * @param cmp cmp
     * @return query
     */
    CQuery<T> distinct(Comparator<? super T> cmp);

    /**
     * Returns sorted query.
     * It uses natural comparator.
     *
     * Please note: it evalues all elements and stores sorted result in memory.
     *
     * @return query
     */
    CQuery<T> sort();

    /**
     * Returns sorted query.
     * It uses provided comparator.
     *
     * Please note: it evalues all elements and stores sorted result in memory.
     *
     * @param cmp cmp
     * @return query
     */
    CQuery<T> sort(Comparator<? super T> cmp);

    /**
     * Returns query with reversed order of elements.
     *
     * Please note: it converts query into list, possibly evaluating all elements.
     *
     * @return query
     */
    CQuery<T> reverse();

    /**
     * Terminal operation.
     * Iterates over all elements inside stream.
     *
     * @param consumer consumer
     */
    @Override
    void forEach(Consumer<? super T> consumer);

    /**
     * Terminal operation.
     * Iterates over all elements inside stream.
     *
     * @param consumer consumer
     */
    void forEach(EachConsumer<? super T> consumer);

    /**
     * Terminal operation.
     * Iterates over elements inside stream.
     * Stops iteration if consumer returns "false".
     *
     * Returns true if all elements were accepted.
     *
     * @param consumer consumer
     * @return boolean
     */
    boolean whileEach(Predicate<? super T> consumer);

    /**
     * Terminal operation.
     * Iterates over elements inside stream.
     * Stops iteration if consumer returns "false".
     *
     * Returns true if all elements were accepted.
     *
     * @param consumer consumer
     * @return boolean
     */
    boolean whileEach(EachPredicate<? super T> consumer);

    /**
     * Insert into pipeline consumer which will receive every evaluated item
     *
     * @param consumer consumer
     * @return query
     */
    CQuery<T> onEach(Consumer<? super T> consumer);

    /**
     * Insert into pipeline consumer which will receive every evaluated item
     *
     * @param consumer consumer
     * @return query
     */
    CQuery<T> onEach(EachConsumer<? super T> consumer);

    /**
     * Terminal operation.
     * Inserts all computed result into provided collection.
     *
     * @param collection collection
     */
    void into(Collection<? super T> collection);

    /**
     * Terminal operation.
     * Returns true if at least one element matches predicate.
     *
     * It does not evaluate all elements, if possible.
     * That means, it stops on first matched element.
     *
     * @param predicate predicate
     * @return boolean
     */
    boolean matchAny(Predicate<? super T> predicate);

    /**
     * Terminal operation.
     * Returns true, if all elements match predicate.
     *
     * It does not evaluate all elements, if possible.
     * That means, it stops on first unmatched element.
     *
     * @param predicate predicate
     * @return boolean
     */
    boolean matchAll(Predicate<? super T> predicate);

    /**
     * Terminal operation.
     * Returns true, if no element matches predicate.
     *
     * It does not evaluate all elements, if possible.
     * That means, it stops on first matched element.
     *
     * @param predicate predicate
     * @return boolean
     */
    boolean matchNone(Predicate<? super T> predicate);

    /**
     * Terminal operation.
     *
     * Returns position of first item equals to provided one.
     * Returns negative, it not found.
     *
     * It does not evaluate all elements, if possible.
     * That means, it stops on first matched element.
     *
     * @param value value
     * @return int
     */
    int indexOf(T value);

    /**
     * Terminal operation.
     *
     * Returns position of first item matching predicate.
     * Returns negative, it not found.
     *
     * It does not evaluate all elements, if possible.
     * That means, it stops on first matched element.
     *
     * @param predicate predicate
     * @return int
     */
    int indexOf(Predicate<? super T> predicate);

    /**
     * Terminal operation.
     *
     * Returns position of first item matching predicate.
     * Returns negative, it not found.
     *
     * It does not evaluate all elements, if possible.
     * That means, it stops on first matched element.
     *
     * @param predicate predicate
     * @return int
     */
    int indexOfEach(EachPredicate<? super T> predicate);

    /**
     * Terminal operation.
     *
     * Returns position of first item equals to provided one.
     * Returns negative, it not found.
     *
     * Most of the time, it must evaluate all elements inside query.
     *
     * @param value value
     * @return int
     */
    int lastIndexOf(T value);

    /**
     * Terminal operation.
     *
     * Returns position of first item matching predicate.
     * Returns negative, it not found.
     *
     * Most of the time, it must evaluate all elements inside query.
     *
     * @param predicate predicate
     * @return int
     */
    int lastIndexOf(Predicate<? super T> predicate);

    /**
     * Terminal operation.
     *
     * Returns position of first item matching predicate.
     * Returns negative, it not found.
     *
     * Most of the time, it must evaluate all elements inside query.
     *
     * @param predicate predicate
     * @return int
     */
    int lastIndexOfEach(EachPredicate<? super T> predicate);

    /**
     * Executes provided function passing this stream as an argument.
     * function.apply(stream) is equivalent to stream.apply(function)
     *
     * Designed with CQueryFunction in mind.
     *
     * @param function function
     * @param <R> R
     * @return result
     */
    <R> R apply(Function<? extends CQuery<? super T>, R> function);

    /**
     * Executes provided function passing this stream as an argument.
     * function.apply(stream) is equivalent to stream.apply(function)
     *
     * Designed with CQueryFunction in mind.
     *
     * Should be used, if we want to preserve exact type bound "T"
     *
     * @param function function
     * @param <R> R
     * @return result
     */
    default <R> R applyThis(Function<? extends CQuery<T>, R> function) {
        return apply(function);
    }

    /**
     * Executes provided predicate passing this stream as an argument.
     * predicate.test(stream) is equivalent to stream.test(predicate)
     *
     * Designed with CQueryPredicate in mind.
     *
     * @param predicate predicate
     * @return boolean
     */
    boolean test(Predicate<? extends CQuery<? super T>> predicate);

    /**
     * Executes provided predicate passing this stream as an argument.
     * predicate.apply(stream) is equivalent to stream.apply(predicate)
     *
     * Designed with CQueryPredicate in mind.
     *
     * Should be used, if we want to preserve exact type bound "T"
     *
     * @param predicate predicate
     * @return boolean
     */
    default boolean testThis(Predicate<? extends CQuery<T>> predicate) {
        return test(predicate);
    }

    /**
     * This factory class allows to create new Queries from
     * literal values, collections, iterators etc
     *
     * @param <F> F
     */
    class WrapBuilder<F> {

        @SuppressWarnings({"rawtypes"})
        protected static final WrapBuilder INSTANCE = new WrapBuilder();

        @SuppressWarnings({"rawtypes", "unchecked"})
        protected static final CQuery EMPTY = new CQCollection(Collections.emptyList());

        /**
         * Returns empty query
         * @param <T> T
         * @return query
         */
        @SuppressWarnings("unchecked")
        public final <T extends F> CQuery<T> empty() {
            return EMPTY;
        }

        public final <T extends F> CQuery<T> empty(Supplier<? extends RuntimeException> message) {
            return EMPTY.message(message);
        }

        /**
         * Returns query with one element for non-null values.
         * If source is "null" returns empty query.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> nullable(T source) {
            return source == null ? empty() : value(source);
        }

        /**
         * Returns query with one element for non-null values.
         * If source is "null" returns empty query.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> optional(Optional<T> source) {
            return source.map(this::value).orElse(empty());
        }

        /**
         * Returns query with one element for non-null values.
         * If source is "null" returns empty query.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> optional(Ref<T> source) {
            return new CQOptional<>(source);
        }

        /**
         * Returns query with one provided value.
         * It accepts null values.
         * Honestly, query with just "null" element inside it is very stupid query.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> value(T source) {
            return new CQSingle<>(null, source);
        }

        /**
         * Returns query with provided values.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        @SafeVarargs
        public final <T extends F> CQuery<T> values(T... source) {
            return new CQArray<>(source);
        }

        /**
         * Returns query which generates values using provided Iterable.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> iterable(Iterable<T> source) {
            return iterator(source::iterator);
        }

        /**
         * Returns query which generates values using provided Supplier.
         * Iterable is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> iterable(CheckedSupplier<Iterable<T>, ?> source) {
            return iterator(() -> source.$get().iterator());
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Iterable is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <T> T
         * @param <P> P
         * @return query
         */
        public final <T extends F,P> CQuery<T> iterable(P param, CheckedFunction<? super P, Iterable<T>, ?> source) {
            return iterator(() -> source.apply(param).iterator());
        }

        /**
         * Returns query which generates values using provided Supplier.
         * Iterator is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> iterator(CheckedSupplier<Iterator<T>, ?> source) {
            return CQIterator.from(source::$get);
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Iterator is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <T> T
         * @param <P> P
         * @return query
         */
        public final <T extends F,P> CQuery<T> iterator(P param, CheckedFunction<? super P, Iterator<T>, ?> source) {
            return iterator(() -> source.apply(param));
        }

        /**
         * Returns query which generates values using provided Supplier.
         * Enumeration is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> enumeration(CheckedSupplier<Enumeration<T>, ?> source) {
            return iterator(() -> EnumerationUtils.iterator(source.$get()));
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Enumeration is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <T> T
         * @param <P> P
         * @return query
         */
        public final <T extends F,P> CQuery<T> enumeration(P param, CheckedFunction<? super P, Enumeration<T>, ?> source) {
            return enumeration(() -> source.apply(param));
        }

        /**
         * Returns query which generates values using provided Supplier.
         * Spliterator is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> spliterator(CheckedSupplier<Spliterator<T>,?> source) {
            return CQSpliterator.from(() -> source.$get());
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Stream is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> stream(CheckedSupplier<Stream<T>,?> source) {
            return CQStream.from(() -> source.$get());
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Stream is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <P> P
         * @param <T> T
         * @return query
         */
        public final <T extends F,P> CQuery<T> stream(P param, CheckedFunction<? super P, Stream<T>,?> source) {
            return CQStream.from(() -> source.$apply(param));
        }

        /**
         * Returns query which uses values stored inside provided collection.
         * Collection is reused by query.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> collection(Collection<T> source) {
            return new CQCollection<>(source);
        }

        /**
         * Returns query which uses values stored inside provided collection.
         * Collection is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> collection(CheckedSupplier<Collection<T>, ?> source) {
            return CQCollectionSupplier.from(source::$get);
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Collection is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <T> T
         * @param <P> P
         * @return query
         */
        public final <T extends F,P> CQuery<T> collection(P param, CheckedFunction<? super P, Collection<T>, ?> source) {
            return collection(() -> source.apply(param));
        }

        /**
         * Returns query which uses values stored inside provided list.
         * List is reused by query.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> list(List<T> source) {
            return new CQList<>(source);
        }

        /**
         * Returns query which uses values stored inside provided list.
         * List is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> list(CheckedSupplier<List<T>, ?> source) {
            return CQListSupplier.from(source::$get);
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * List is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <T> T
         * @param <P> P
         * @return query
         */
        public final <T extends F,P> CQuery<T> list(P param, CheckedFunction<? super P, List<T>, ?> source) {
            return list(() -> source.apply(param));
        }

        /**
         * Returns query which uses values stored inside provided array.
         * Array is reused by query.
         *
         * Please note: this is non-generic version for primitive arrays.
         *
         * @param source source
         * @return query
         */
        public final CQuery<Object> array(Object source) {
            return new CQList<>(NativeArrayList.wrap(source));
        }

        /**
         * Returns query which uses values stored inside provided array.
         * Array is reused by query.
         *
         * Please note: this is generic version for non-primitive arrays.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> array(T[] source) {
            return new CQArray<>(source);
        }

        /**
         * Returns query which uses values stored inside provided array.
         * Array is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> array(CheckedSupplier<T[], ?> source) {
            return CQArraySupplier.from(source::$get);
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Array is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <T> T
         * @param <P> P
         * @return query
         */
        public final <T extends F,P> CQuery<T> array(P param, CheckedFunction<? super P, T[], ?> source) {
            return array(() -> source.apply(param));
        }

        /**
         * Returns query which uses values returned by provided query.
         * Query is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Supplier will be propagated in sneaky way.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> query(CheckedSupplier<CQuery<T>, ?> source) {
            return CQQuerySupplier.from(source::$get);
        }

        /**
         * Returns query which generates values using provided Function called with provided param.
         * Query is recreated inside every terminal operation.
         *
         * Please note, that exception thrown by Function will be propagated in sneaky way.
         *
         * @param param param
         * @param source source
         * @param <T> T
         * @param <P> P
         * @return query
         */
        public final <T extends F,P> CQuery<T> query(P param, CheckedFunction<? super P, CQuery<T>, ?> source) {
            return query(() -> source.apply(param));
        }

        /**
         * Creates query with infinite number of elements. Each item is created by subsequent calls to generator.
         *
         * Please note, that means generator should be statefull.
         * Please note, that it is impossible to "rewind" generator, which means generated infinite stream probably
         * will return different results on every call.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> infinite(CheckedSupplier<T, ?> source) {
            return iterable(() -> IteratorUtils.infinite(source));
        }

        /**
         * Creates query with infinite number of elements. Each item is created by subsequent calls to generator.
         *
         * Please note, that generator does not need to be statefull.
         * Generates receives "previously" computed result (or identity at start) and can make computation using it.
         * For example, it can create all natural numbers by simple incrementation.
         *
         * @param identity starting value passed to generator
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> infinite(T identity, CheckedFunction<T, T, ?> source) {
            return iterable(() -> IteratorUtils.infinite(identity, source));
        }

        /**
         * Creates query with finite number of elements. Each item is created by subsequent calls to generator.
         *
         * Please note, that means generator should be statefull.
         * Please note, that it is impossible to "rewind" generator, which means generated infinite stream probably
         * will return different results on every call.
         *
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> finite(CheckedSupplier<Ref<T>, ?> source) {
            return iterable(() -> IteratorUtils.finite(source));
        }

        /**
         * Creates query with finite number of elements. Each item is created by subsequent calls to generator.
         *
         * Please note, that generator does not need to be statefull.
         * Generates receives "previously" computed result (or identity at start) and can make computation using it.
         * For example, it can create all natural numbers by simple incrementation.
         *
         * @param identity starting value passed to generator
         * @param source source
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> finite(T identity, CheckedFunction<T, Ref<T>, ?> source) {
            return iterable(() -> IteratorUtils.finite(identity, source));
        }

        /**
         * Creates query with virtual list made of generated elements
         * Element as each index is computed by "function" at every access.
         * Size of the list provided as first argument
         *
         * @param size size
         * @param function function
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> finite(int size, IntFunction<? extends T> function) {
            return CQuery.from().list(VirtualList.of(size, function));
        }

        /**
         * Creates query with virtual list made of generated elements
         * Element as each index is computed by "function" at every access.
         * Size of the list computed by supplier provided as first argument.
         *
         * @param size size
         * @param function function
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> finite(IntSupplier size, IntFunction<? extends T> function) {
            return CQuery.from().list(VirtualList.of(size, function));
        }

        /**
         * Creates query with lazy virtual list made of generated elements
         * Element as each index is computed by "function" at every access.
         * Size of the list provided as first argument
         *
         * @param size size
         * @param function function
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> lazy(int size, IntFunction<? extends T> function) {
            return CQuery.from().list(LazyList.of(size, function));
        }

        /**
         * Creates query with lazy virtual list made of generated elements
         * Element as each index is computed by "function" at every access.
         * Size of the list computed by supplier provided as first argument.
         *
         * @param size size
         * @param function function
         * @param <T> T
         * @return query
         */
        public final <T extends F> CQuery<T> lazy(IntSupplier size, IntFunction<? extends T> function) {
            return CQuery.from().list(LazyList.of(size, function));
        }

        /**
         * Creates stream with natural numbers from specified range.
         *
         * @param begin begin
         * @param end end
         * @return query
         */
        public CQuery<Integer> range(int begin, int end) {
            return from(VirtualList.of(Math.max(0, end-begin), v -> begin+v));
        }

        /**
         * Creates stream with natural numbers from specified range.
         *
         * @param begin begin
         * @param end end
         * @return query
         */
        public CQuery<Long> range(long begin, long end) {
            return from(VirtualList.of((int)Math.max(0, end-begin), v -> begin+v));
        }

        /**
         * Creates stream traversing provided tree nodes.
         *
         * @param <T> T
         * @return builder
         */
        @SuppressWarnings("unchecked")
        public <T> TreeBuilder<T> tree() {
            return TreeBuilder.INSTANCE;
        }

    }

    /**
     * This factory class allows to create new Queries from tree
     *
     * @param <F> F
     */
    class TreeBuilder<F> {

        @SuppressWarnings({"rawtypes"})
        protected static final TreeBuilder INSTANCE = new TreeBuilder();

        /**
         * Creates stream traversing provided tree nodes.
         *
         *
         * @param <T> T
         * @param root root
         * @param children children
         * @param isTerm isTerm
         * @return query
         */
        public <T> CQuery<T> dfs(Supplier<T> root, Function<T, CQuery<T>> children, Predicate<T> isTerm) {
            return new CQTreeDFS<>(root, children, isTerm, null);
        }

        /**
         * Creates stream traversing provided tree nodes.
         *
         * @param root root
         * @param children children
         * @return query
         * @param <T> T
         */
        public <T> CQuery<T> dfs(Supplier<T> root, Function<T, CQuery<T>> children) {
            return new CQTreeDFS<>(root, children, node -> false, null);
        }

        /**
         * Creates stream traversing provided tree nodes.
         *
         *
         * @param <T> T
         * @param root root
         * @param children children
         * @param isTerm isTerm
         * @return query
         */
        public <T> CQuery<T> bfs(Supplier<T> root, Function<T, CQuery<T>> children, Predicate<T> isTerm) {
            return new CQTreeBFS<>(root, children, isTerm, null);
        }

        /**
         * Creates stream traversing provided tree nodes.
         *
         * @param root root
         * @param children children
         * @return query
         * @param <T> T
         */
        public <T> CQuery<T> bfs(Supplier<T> root, Function<T, CQuery<T>> children) {
            return new CQTreeBFS<>(root, children, node -> false, null);
        }

    }

    /**
     * This builder is factory creating composite queries, which use more than one data source under the hood.
     *
     * @author Ranides Atterwim {@literal <ranides@gmail.com>}
     */
    final class Builder<F> {

        private final List<CQuery<? extends F>> list = new ArrayList<>();

        protected Builder() {
            // do nothing
        }

        @SuppressWarnings("unchecked")
        private <T> Builder<T> self() {
            return (Builder<T>)this;
        }

        /**
         * Appends literal values.
         *
         * @param items items
         * @param <T> T
         * @return builder
         */
        @SafeVarargs
        public final <T extends F> Builder<T> with(T... items) {
            list.add(from().values(items));
            return self();
        }

        /**
         * Appends query.
         * Query will be evaluated later, by terminal operations.
         *
         * @param item item
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withQuery(CQuery<T> item) {
            list.add(item);
            return self();
        }

        /**
         * Appends query.
         * Query will be created and evaluated later, by terminal operations.
         *
         * @param item item
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withQuery(CheckedSupplier<CQuery<T>,?> item) {
            list.add(from().query(item));
            return self();
        }

        /**
         * Appends query.
         * Query will be created and evaluated later, by terminal operations.
         *
         * @param param param
         * @param item item
         * @param <T> T
         * @param <P> P
         * @return builder
         */
        public <T extends F, P> Builder<T> withQuery(P param, CheckedFunction<? super P, CQuery<T>, ?> item) {
            list.add(from().query(param,item));
            return self();
        }

        /**
         * Appends iterable.
         * Iterable will be evaluated later, by terminal operations.
         *
         * @param f f
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withIterable(Iterable<T> f) {
            return withQuery(from().iterable(f));
        }

        /**
         * Appends iterable.
         * Iterable will be created and evaluated later, by terminal operations.
         *
         * @param f f
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withIterable(CheckedSupplier<Iterable<T>, ?> f) {
            return withQuery(from().iterable(f));
        }

        /**
         * Appends iterable.
         * Iterable will be created and evaluated later, by terminal operations.
         *
         * @param param param
         * @param f f
         * @param <T> T
         * @param <P> P
         * @return builder
         */
        public <T extends F, P> Builder<T> withIterable(P param, CheckedFunction<? super P,Iterable<T>, ?> f) {
            return withQuery(from().iterable(param, f));
        }

        /**
         * Appends collection.
         * Collection will be evaluated later, by terminal operations.
         *
         * @param f f
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withCollection(Collection<T> f) {
            return withQuery(from().collection(f));
        }

        /**
         * Appends collection.
         * Collection will be created and evaluated later, by terminal operations.
         *
         * @param f f
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withCollection(CheckedSupplier<Collection<T>, ?> f) {
            return withQuery(from().collection(f));
        }

        /**
         * Appends collection.
         * Collection will be created and evaluated later, by terminal operations.
         *
         * @param param param
         * @param f f
         * @param <T> T
         * @param <P> P
         * @return builder
         */
        public <T extends F, P> Builder<T> withCollection(P param, CheckedFunction<? super P, Collection<T>, ?> f) {
            return withQuery(from().collection(param, f));
        }

        /**
         * Appends array.
         * Array will be evaluated later, by terminal operations.
         *
         * @param f f
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withArray(T[] f) {
            return withQuery(from().array(f));
        }

        /**
         * Appends array.
         * Array will be created and evaluated later, by terminal operations.
         *
         * @param f f
         * @param <T> T
         * @return builder
         */
        public <T extends F> Builder<T> withArray(CheckedSupplier<T[], ?> f) {
            return withQuery(from().array(f));
        }

        /**
         * Appends array.
         * Array will be created and evaluated later, by terminal operations.
         *
         * @param param param
         * @param f f
         * @param <T> T
         * @param <P> P
         * @return builder
         */
        public <T extends F, P> Builder<T> withArray(P param, CheckedFunction<? super P, T[], ?> f) {
            return withQuery(from().array(param, f));
        }

        /**
         * Creates new Query with contect configured by this builder.
         *
         * @return query
         */
        @SuppressWarnings("unchecked")
        public CQuery<F> build() {
            return (CQuery<F>) from().collection(list).flat(v -> v);
        }
    }

}
