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

import java.util.*;
import java.util.function.*;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

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.CompareUtils;
import net.ranides.assira.generic.Ref;
import net.ranides.assira.generic.Wrapper;
import net.ranides.assira.generic.Wrappers;
import net.ranides.assira.trace.ExceptionUtils;

/**
 * Static methods working with Iterator interface.
 *
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 */
public final class IteratorUtils {
    
    private IteratorUtils() {
        /* utility class */
    }

    /**
     * Returns first element for iterator, or none if iterator is empty.
     *
     * @param iterator iterator
     * @param <T> T
     * @return optional
     */
    public static <T> Ref<T> first(Iterator<? extends T> iterator) {
		if(iterator.hasNext()) {
			return Ref.of(iterator.next());
		}
        return Ref.empty();
    }

    /**
     * Returns first element for iterator which satisfies predicate.
     * Returns none if iterator is empty or no element was accepted by predicate.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return optional
     */
    public static <T> Ref<T> first(Iterator<? extends T> iterator, Predicate<? super T> predicate) {
        while(iterator.hasNext()) {
            T v = iterator.next();
            if( predicate.test(v)) {
                return Ref.of(v);
            }
        }
        return Ref.empty();
    }

    /**
     * Returns last element for iterator, or none if iterator is empty.
     * It must traverse whole collection.
     * If you can, lets try ListUtils.
     *
     * @param iterator iterator
     * @param <T> T
     * @return optional
     */
    public static <T> Ref<T> last(Iterator<? extends T> iterator) {
		if(!iterator.hasNext()) {
			return Ref.empty();
		}
        T result = null;
        while(iterator.hasNext()) { 
            result = iterator.next(); 
        }
        return Ref.of(result);
    }

    /**
     * Returns element at specified position or none if iterator contains less elements.
     * It must traverse through all previous elements.
     * If you can, lets try ListUtils.
     *
     * @param iterator iterator
     * @param index index
     * @param <T> T
     * @return optional
     */
    public static <T> Ref<T> at(Iterator<? extends T> iterator, int index) {
        for(int i=0; i<index; i++) {
            if(!iterator.hasNext()) {
                return Ref.empty();
            }
            iterator.next();
        }
        return iterator.hasNext() ? Ref.of(iterator.next()) : Ref.empty();
    }

    /**
     * Returns last element for iterator which satisfies predicate.
     * Returns none if iterator is empty or no element was accepted by predicate.
     * It must traverse whole collection.
     * If you can, lets try ListUtils.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return optional
     */
    public static <T> Ref<T> last(Iterator<? extends T> iterator, Predicate<? super T> predicate) {
        boolean found = false;
		T result = null;
        while(iterator.hasNext()) {
            T v = iterator.next();
            if(predicate.test(v)) {
                result = v;
				found = true;
            }
        }
		if(!found) {
			return Ref.empty();
		}
        return Ref.of(result);
    }

    /**
     * Counts number of elements for specified iterator.
     * It must iterate through all elements, if you can, check collection size directly.
     *
     * @param iterator iterator
     * @return int
     */
    public static int size(Iterator<?> iterator) {
		if(iterator==null) {
			return 0;
		}
        int c = 0;
        while(iterator.hasNext()) {
            c++;
            iterator.next();
        }
        return c;
    }

    /**
     * Returns filtered view of provided Iterator.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return iterator view
     */
    public static <T> Iterator<T> filter(Iterator<? extends T> iterator, Predicate<? super T> predicate) {
        return new FilterIterator<>(iterator, predicate, false);
    }

    /**
     * Returns filtered read-only view of provided Iterator.
     * Returned iterator supports backward iteration, but it does not allow modifications.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return iterator view
     */
    public static <T> ListIterator<T> filter(ListIterator<? extends T> iterator, Predicate<? super T> predicate) {
        return new FilterListIterator<>(iterator, predicate, false);
    }

    /**
     * Returns filtered view of provided Iterator.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return iterator view
     */
    public static <T> Iterator<T> filterEach(Iterator<? extends T> iterator, EachPredicate<? super T> predicate) {
        return new FilterIterator<>(iterator, predicate, false);
    }

    /**
     * Returns filtered read-only view of provided Iterator.
     * Returned iterator supports backward iteration, but it does not allow modifications.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return iterator view
     */
    public static <T> ListIterator<T> filterEach(ListIterator<? extends T> iterator, EachPredicate<? super T> predicate) {
        return new FilterListIterator<>(iterator, predicate, false);
    }

    /**
     * Returns read-only view of provided Iterator.
     * Limited iterator stops at first unmatched element.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return iterator view
     */
    public static <T> Iterator<T> limit(Iterator<? extends T> iterator, Predicate<? super T> predicate) {
        return new FilterIterator<>(iterator, predicate, true);
    }

    /**
     * Returns read-only view of provided Iterator.
     * Limited iterator stops at first unmatched element.
     * Returned iterator supports backward iteration, but it does not allow modifications.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     * @return iterator view
     */
    public static <T> ListIterator<T> limit(ListIterator<? extends T> iterator, Predicate<? super T> predicate) {
        return new FilterListIterator<>(iterator, predicate, true);
    }

    /**
     * Returns read-only view of provided Iterator.
     * Limited iterator returns no more than "limit" elements.
     *
     * @param iterator iterator
     * @param limit limit
     * @param <T> T
     * @return iterator view
     */
    public static <T> Iterator<T> limit(Iterator<T> iterator, int limit) {
        return new LimitIterator<>(iterator, limit);
    }

    /**
     * Returns read-only view of provided Iterator.
     * Limited iterator returns no more than "limit" elements.
     * Returned iterator supports backward iteration, but it does not allow modifications.
     *
     * @param iterator iterator
     * @param limit limit
     * @param <T> T
     * @return iterator view
     */
    public static <T> ListIterator<T> limit(ListIterator<T> iterator, int limit) {
        return new LimitListIterator<>(iterator, limit);
    }

    /**
     * Returns read-only view of provided Iterator.
     * Limited iterator returns elements at most from specified range.
     * It means: it skips first "begin" elements and then stops after reaching "end".
     *
     * @param iterator iterator
     * @param begin begin
     * @param end end
     * @param <T> T
     * @return iterator view
     */
    public static <T> Iterator<T> limit(Iterator<T> iterator, int begin, int end) {
        next(iterator, begin);
        return new LimitIterator<>(iterator, end-begin);
    }

    /**
     * Returns read-only view of provided Iterator.
     * Limited iterator returns elements at most from specified range.
     * It means: it skips first "begin" elements and then stops after reaching "end".
     * Returned iterator supports backward iteration, but it does not allow modifications.
     *
     * @param iterator iterator
     * @param begin begin
     * @param end end
     * @param <T> T
     * @return iterator view
     */
    public static <T> ListIterator<T> limit(ListIterator<T> iterator, int begin, int end) {
        next(iterator, begin);
        return new LimitListIterator<>(iterator, end-begin);
    }

    /**
     * Returns read-only view of iterator which maps every element using provided function.
     *
     * @param iterator iterator
     * @param function function
     * @param <T> T
     * @param <S> S
     * @return iterator view
     */
    public static <S,T> Iterator<T> map(Iterator<? extends S> iterator, EachFunction<? super S,? extends T> function) {
        return new EachAdapter<>(iterator, function);
    }

    /**
     * Returns read-only view of iterator which maps every element using provided function.
     *
     * @param iterator iterator
     * @param function function
     * @param <T> T
     * @param <S> S
     * @return iterator view
     */
    public static <S,T> Iterator<T> map(Iterator<? extends S> iterator, Function<? super S,? extends T> function) {
        return new Adapter<>(iterator, function);
    }

    /**
     * Returns read-only view of iterator which maps every element using provided function.
     * Returned iterator supports backward iteration, but it does not allow modifications.
     *
     * @param iterator iterator
     * @param function function
     * @param <T> T
     * @param <S> S
     * @return iterator view
     */
    public static <S,T> ListIterator<T> map(ListIterator<? extends S> iterator, EachFunction<S,T> function) {
        return new EachListAdapter<>(iterator, function);
    }

    /**
     * Returns read-only view of iterator which maps every element using provided function.
     * Returned iterator supports backward iteration, but it does not allow modifications.
     *
     * @param iterator iterator
     * @param function function
     * @param <T> T
     * @param <S> S
     * @return iterator view
     */
    public static <S,T> ListIterator<T> map(ListIterator<? extends S> iterator, Function<? super S,? extends T> function) {
        return new ListAdapter<>(iterator, function);
    }

    /**
     * Returns view which lazily expands all nested Iterators and merges into one iterator.
     * Flat iterators move forward only as much as necessary (which means one element at time).
     *
     * @param iterator iterator
     * @param <T> T
     * @return iterator view
     */
    public static <T> Iterator<T> flat(Iterator<? extends Iterator<? extends T>> iterator) {
        return new FlatIterator<>(iterator);
    }

    public static <T> Iterator<T> flat(Iterator<? extends T> iterator, Function<? super T, Iterator<T>> splitter) {
        return new FlatMapIterator<>(FlatMode.SHALLOW, iterator, item -> true, splitter);
    }

    public static <T> Iterator<T> flatIf(Iterator<? extends T> iterator, Predicate<? super T> split, Function<? super T, Iterator<T>> splitter) {
        return new FlatMapIterator<>(FlatMode.SHALLOW, iterator, split, splitter);
    }

    public static <T> Iterator<T> deepFlatIf(Iterator<? extends T> iterator, Predicate<? super T> split, Function<? super T, Iterator<T>> splitter) {
        return new FlatMapIterator<>(FlatMode.DEEP, iterator, split, splitter);
    }

    public static <T> Iterator<T> treeFlatIf(Iterator<? extends T> iterator, Predicate<? super T> split, Function<? super T, Iterator<T>> splitter) {
        return new FlatMapIterator<>(FlatMode.TREE, iterator, split, splitter);
    }

    /**
     * Returns view which lazily expands all provided Iterators and merges into one iterator.
     * Flat iterators move forward only as much as necessary (which means one element at time).
     *
     * @param iterators iterators
     * @param <T> T
     * @return iterator
     * @see #flat
     */
    @SafeVarargs
    public static <T> Iterator<T> concat(Iterator<? extends T>... iterators) {
        return flat(Arrays.asList(iterators).iterator());
    }

    /**
     * Creates new sequential Stream from provided iterator.
     *
     * @param iterator iterator
     * @param <T> T
     * @return stream
     */
    public static <T> Stream<T> stream(Iterator<? extends T> iterator) {
		return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, 0), false);
	}

    /**
     * Inserts all elements returned by iterator into provided collection.
     *
     * @param iterator iterator
     * @param target target
     * @param <T> T
     * @param <C> C
     * @return target
     */
    public static <T, C extends Collection<? super T>> C collect(Iterator<? extends T> iterator, C target) {
        while(iterator.hasNext()) {
            target.add(iterator.next());
        }
        return target;
	}

    /**
     * Creates mutable iterator which runs in reversed order.
     * It supports removing elements.
     *
     * Please note, that input iterator must be correctly rewinded before use.
     *
     * @param iterator iterator
     * @param <T> T
     * @return iterator view
     */
	public static <T> Iterator<T> reverse(ListIterator<? extends T> iterator) {
		return new ReverseIterator<>(iterator);
	}

    /**
     * It creates read-only iterator which offers limited backward iteration.
     * It buffers last "max" results and allows to read back them.
     *
     * It does not support any modifications, including "remove".
     *
     * @param iterator iterator
     * @param max max
     * @param <T> T
     * @return iterator
     */
	public static <T> ListIterator<T> buffered(Iterator<? extends T> iterator, int max) {
        return new BufferedIterator<>(iterator, max);
    }

    /**
     * Tries to skip "count" elements.
     * Returns number of successfully skipped elements.
     *
     * @param iterator iterator
     * @param count count
     * @param <T> T
     * @return int
     */
    public static <T> int next(Iterator<? extends T> iterator, int count) {
		int i=0;
		for(; i<count && iterator.hasNext(); i++) {
			iterator.next();
		}
		return i;
	}

    /**
     * Checks if provided iterators contain equal elements.
     * Order of elements is important.
     *
     * @param a a
     * @param b b
     * @param <T> T
     * @return bool
     */
    public static <T> boolean equals(Iterator<? extends T> a, Iterator<? extends T> b) {
        return equals(a, b, CompareUtils::equals);
    }

    /**
     * Checks if provided iterators contain equal elements using provided comparison function.
     * Order of elements is important.
     *
     * @param a a
     * @param b b
     * @param predicate predicate
     * @param <T> T
     * @return bool
     */
    public static <T> boolean equals(Iterator<? extends T> a, Iterator<? extends T> b, BiPredicate<? super T,? super T> predicate) {
        while(a.hasNext() && b.hasNext()) {
            if( !predicate.test(a.next(), b.next())) {
                return false;
            }
        }
        return !a.hasNext() && !b.hasNext();
    }

    /**
     * Checks if provided iterators contain equal elements.
     * Order of elements is important.
     * It is three-value version, which returns +1, 0, -1
     *
     * @param a a
     * @param b b
     * @param <T> T
     * @return int
     */
    public static <T> int compare(Iterator<? extends T> a, Iterator<? extends T> b) {
        return compare(a, b, CompareUtils.comparator());
    }

    /**
     * Checks if provided iterators contain equal elements using provided comparison function.
     * Order of elements is important.
     * It is three-value version, which returns +1, 0, -1
     *
     * @param a a
     * @param b b
     * @param cmp cmp
     * @param <T> T
     * @return int
     */
    public static <T> int compare(Iterator<? extends T> a, Iterator<? extends T> b, Comparator<? super T> cmp) {
        while(a.hasNext() && b.hasNext()) {
            int icmp = cmp.compare(a.next(), b.next());
            if(icmp !=0) {
                return icmp;
            }
        }
        return a.hasNext() ? +1 : b.hasNext() ? -1 : 0;
    }

    /**
     * Iterates through all values and removes every element which is matched by predicate.
     *
     * @param iterator iterator
     * @param predicate predicate
     * @param <T> T
     */
    public static <T> void remove(Iterator<? extends T> iterator, Predicate<? super T> predicate) {
        while(iterator.hasNext()) {
            T v = iterator.next();
            if(predicate.test(v)) {
                iterator.remove();
            }
        }
    }

    /**
     * Creates new infinite iterator which returns values generated by provided supplier.
     * Rethrows all unchecked exceptions from generator.
     * Wraps by RuntimeException all checked exceptions from generator.
     *
     * Probably supplier must be statefull.
     *
     * @param generator generator
     * @param <T> T
     * @return iterator
     */
    public static <T> Iterator<T> infinite(CheckedSupplier<T, ?> generator) {
        return new Iterator<T>() {
            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public T next() {
                try {
                    return generator.get();
                } catch (RuntimeException cause) {
                    throw cause;
                } catch (Exception cause) {
                    throw new RuntimeException(cause);
                }
            }
        };
    }

    /**
     * Creates new infinite iterator which returns values generated by provided generator.
     * Rethrows all unchecked exceptions from generator.
     * Wraps by RuntimeException all checked exceptions from generator.
     *
     * Generator can be stateless, because it received previously generated value and could use it in computations.
     * For example, it could simply increment it.
     *
     * @param identity identity
     * @param generator generator
     * @param <T> T
     * @return iterator
     */
    public static <T> Iterator<T> infinite(T identity, CheckedFunction<T, T, ?> generator) {
        return new Iterator<T>() {

            private T previous = null;

            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public T next() {
                try {
                    if(previous == null) {
                        return previous = identity;
                    } else {
                        return (previous = generator.apply(previous));
                    }
                } catch (RuntimeException cause) {
                    throw cause;
                } catch (Exception cause) {
                    throw new RuntimeException(cause);
                }
            }
        };
    }


    /**
     * Creates new finite iterator which returns values generated by provided function.
     * Iterator stops when function returns "optional.empty"
     *
     * Rethrows all unchecked exceptions from generator.
     * Wraps by RuntimeException all checked exceptions from generator.
     *
     * Generator can be stateless, it transforms previous value.
     *
     * @param generator generator
     * @param <T> T
     * @return iterator
     */
    public static <T> Iterator<T> finite(T identity, CheckedFunction<T, Ref<T>, ?> generator) {
        return new Iterator<T>() {

            private Ref<T> last = Ref.of(identity);
            private boolean generated = true;

            @Override
            public boolean hasNext() {
                if(generated) {
                    return last.isPresent();
                }
                try {
                    if(last.isPresent()) {
                        last = generator.apply(last.get());
                        generated = true;
                    }
                    return last.isPresent();
                } catch (RuntimeException cause) {
                    last = Ref.empty();
                    generated = true;
                    throw cause;
                } catch (Exception cause) {
                    last = Ref.empty();
                    generated = true;
                    throw new RuntimeException(cause);
                }
            }

            @Override
            public T next() {
                try {
                    if(!generated) {
                        last = generator.apply(last.orElseThrow(NoSuchElementException::new));
                    }
                } catch (RuntimeException cause) {
                    last = Ref.empty();
                    throw cause;
                } catch (Exception cause) {
                    last = Ref.empty();
                    throw new RuntimeException(cause);
                } finally {
                    generated = false;
                }
                return last.orElseThrow(NoSuchElementException::new);
            }
        };
    }

    /**
     * Creates new finite iterator which returns values generated by provided supplier.
     * Iterator stops when generator returns "optional.empty"
     *
     * Rethrows all unchecked exceptions from generator.
     * Wraps by RuntimeException all checked exceptions from generator.
     *
     * Probably supplier must be statefull.
     *
     * @param generator generator
     * @param <T> T
     * @return iterator
     */
    public static <T> Iterator<T> finite(CheckedSupplier<Ref<T>, ?> generator) {
	    return new Iterator<T>() {

	        private Ref<T> last = Ref.empty();
            private boolean generated = false;

            @Override
            public boolean hasNext() {
                if(generated) {
                    return last.isPresent();
                }
                try {
                    last = generator.get();
                    generated = true;
                    return last.isPresent();
                } catch (RuntimeException cause) {
                    last = Ref.empty();
                    generated = true;
                    throw cause;
                } catch (Exception cause) {
                    last = Ref.empty();
                    generated = true;
                    throw new RuntimeException(cause);
                }
            }

            @Override
            public T next() {
                try {
                    if(!generated) {
                        last = generator.get();
                    }
                } catch (RuntimeException cause) {
                    last = Ref.empty();
                    throw cause;
                } catch (Exception cause) {
                    last = Ref.empty();
                    throw new RuntimeException(cause);
                } finally {
                    generated = false;
                }
                return last.orElseThrow(NoSuchElementException::new);
            }
        };
    }

    /**
     * Creates safe iterator which will never throw any exception except NoSuchElementException.
     * All exceptions are silently ignored.
     * Behaviour of iterator methods in such case:
     *  - "hasNext" returns false
     *  - "next" throws NoSuchElementException
     *  - "remove" does nothing
     *
     * @param iterator iterator
     * @param <T> T
     * @return iterator
     */
    public static <T> Iterator<T> safe(Iterator<T> iterator) {
        return safe(iterator, Exception.class, e -> {});
    }

    /**
     * Creates safe iterator which will never throw exception of specified "type".
     * Exceptions of "type" are silently ignored.
     * Behaviour of iterator methods in such case:
     *   - "hasNext" returns false
     *   - "next" throws NoSuchElementException
     *   - "remove" does nothing
     *
     * Please note, that other exceptions still will be propagated without change.
     *
     * Please note, that NoSuchElementException will be thrown as usuall.
     *
     * @param iterator iterator
     * @param type exception to ignore
     * @param <T> T
     * @param <E> E
     * @return iterator
     */
    public static <T, E extends Throwable> Iterator<T> safe(Iterator<T> iterator, Class<E> type) {
        return safe(iterator, type, e -> {});
    }

    /**
     * Creates safe iterator which will never throw exception of specified "type".
     * Exceptions of "type" are sent to handler.
     *
     * Behaviour of iterator methods in such case:
     *   - "hasNext" returns false
     *   - "next" throws NoSuchElementException
     *   - "remove" does nothing
     *
     * Please note, that other exceptions still will be propagated without change.
     *
     * Please note, that NoSuchElementException will be thrown as usuall.
     *
     * @param iterator iterator
     * @param type exception to ignore
     * @param handler handler
     * @param <T> T
     * @param <E> E
     * @return iterator
     */
    public static <T, E extends Throwable> Iterator<T> safe(Iterator<T> iterator, Class<E> type, Consumer<E> handler) {
        return new SafeIterator<>(iterator, type, handler);
    }

    /**
     * Creates iterator with single provided value
     *
     * @param value value
     * @param <T> T
     * @return iterator
     */
    public static <T> Iterator<T> singletonIterator(T value) {
	    return new SingleIterator<>(value);
    }

    public static <T> Iterator<T> withCause(Iterator<T> iterator, Supplier<? extends Throwable> cause) {
        if(cause == null) {
            return iterator;
        } else {
            return new CustomIterator<T>(cause, iterator);
        }
    }

    public static <T> ListIterator<T> withCause(ListIterator<T> iterator, Supplier<? extends Throwable> cause) {
        if(cause == null) {
            return iterator;
        } else {
            return new CustomListIterator<T>(cause, iterator);
        }
    }

    private static final class Adapter<S, T> implements Iterator<T> {
    
        protected final Iterator<S> delegate;
        
        protected final Function<? super S,? extends T> function;

        protected <E> Adapter(Iterator<S> delegate, Function<? super S,? extends T> function) {
            this.delegate = delegate;
            this.function = function;
        }

        @Override
        public boolean hasNext() {
            return delegate.hasNext();
        }

        @Override
        public T next() {
            return function.apply(delegate.next());
        }

        @Override
        public void remove() {
            delegate.remove();
        }
        
    }    
    
    private static final class EachAdapter<S, T> implements Iterator<T> {
    
        protected final Iterator<S> delegate;
        
        protected final EachFunction<? super S,? extends T> function;
        
        protected int index;

        protected <E> EachAdapter(Iterator<S> delegate, EachFunction<? super S,? extends T> function) {
            this.delegate = delegate;
            this.function = function;
            this.index = 0;
        }

        @Override
        public boolean hasNext() {
            return delegate.hasNext();
        }

        @Override
        public T next() {
            return function.apply(index++, delegate.next());
        }

        @Override
        public void remove() {
            delegate.remove();
        }
        
    } 
    
    private static final class ListAdapter<S, T> implements ListIterator<T> {
    
        protected final ListIterator<S> delegate;
        
        protected final Function<? super S,? extends T> function;

        protected <E> ListAdapter(ListIterator<S> delegate, Function<? super S,? extends T> function) {
            this.delegate = delegate;
            this.function = function;
        }
        
        @Override
        public T next() {
            return function.apply(delegate.next());
        }
        
        @Override
        public T previous() {
            return function.apply(delegate.previous());
        }

        @Override
        public boolean hasNext() {
            return delegate.hasNext();
        }

        @Override
        public boolean hasPrevious() {
            return delegate.hasPrevious();
        }

        @Override
        public int nextIndex() {
            return delegate.nextIndex();
        }

        @Override
        public int previousIndex() {
            return delegate.previousIndex();
        }

        @Override
        public void remove() {
            delegate.remove();
        }

        @Override
        public void set(T value) {
            throw new UnsupportedOperationException("");
        }

        @Override
        public void add(T value) {
            throw new UnsupportedOperationException("");
        }
        
    }
    
    private static final class EachListAdapter<S, T> implements ListIterator<T> {
    
        protected final ListIterator<S> delegate;
        
        protected final EachFunction<? super S,? extends T> function;

        protected <E> EachListAdapter(ListIterator<S> delegate, EachFunction<? super S,? extends T> function) {
            this.delegate = delegate;
            this.function = function;
        }
        
        @Override
        public T next() {
            
            return function.apply(delegate.nextIndex(), delegate.next());
        }
        
        @Override
        public T previous() {
            return function.apply(delegate.previousIndex(), delegate.previous());
        }

        @Override
        public boolean hasNext() {
            return delegate.hasNext();
        }

        @Override
        public boolean hasPrevious() {
            return delegate.hasPrevious();
        }

        @Override
        public int nextIndex() {
            return delegate.nextIndex();
        }

        @Override
        public int previousIndex() {
            return delegate.previousIndex();
        }

        @Override
        public void remove() {
            delegate.remove();
        }

        @Override
        public void set(T value) {
            throw new UnsupportedOperationException("");
        }

        @Override
        public void add(T value) {
            throw new UnsupportedOperationException("");
        }
        
    }
    
    private static class FilterIterator<T> implements Iterator<T> {

        private final Iterator<? extends T> iterator;
        private final EachPredicate<? super T> predicate;
        private final boolean limit;
        private T next;
        private boolean hasNext;
        private boolean isTerminated;
        private int index;

        public FilterIterator(Iterator<? extends T> iterator, Predicate<? super T> predicate, boolean limit) {
            this(iterator, (i,v) -> predicate.test(v), limit);
        }

        public FilterIterator(Iterator<? extends T> iterator, EachPredicate<? super T> predicate, boolean limit) {
            this.iterator = iterator;
			this.predicate = predicate;
            this.limit = limit;
            this.index = -1;
            this.hasNext = false;
            this.isTerminated = false;
        }

        @Override
        public boolean hasNext() {
            if(hasNext) {
                return true;
            }
            if(isTerminated) {
                return false;
            }

            while (iterator.hasNext()) {
                T value = iterator.next();
                index++;
                if (predicate.test(index, value)) {
                    hasNext = true;
                    this.next = value;
                    return true;
                } else if(limit) {
                    break;
                }
            }
            isTerminated = true;
            return false;
        }

        @Override
        public T next() {
            if(!hasNext()) {
                throw new NoSuchElementException();
            }
//            index++;
            hasNext = false;
            return next;
        }

        @Override
        public void remove() {
            iterator.remove();
        }

    }
	
	private static class FilterListIterator<T> implements ListIterator<T> {

        private final ListIterator<? extends T> iterator;
        private final EachPredicate<? super T> predicate;
        private final boolean limit;
        private int index;
		private T next;
        private boolean hasNext;

        public FilterListIterator(ListIterator<? extends T> iterator, Predicate<? super T> predicate, boolean limit) {
            this(iterator, (i,v) -> predicate.test(v), limit);
        }

        public FilterListIterator(ListIterator<? extends T> iterator, EachPredicate<? super T> predicate, boolean limit) {
            this.iterator = iterator;
			this.predicate = predicate;
            this.limit = limit;
            nextMatch();
        }
        
        @Override
        public boolean hasNext() {
            return hasNext;
        }
		
		@Override
        public boolean hasPrevious() {
            return index>0;
        }

        @Override
        public T next() {
            if (!hasNext) {
                throw new NoSuchElementException();
            }
			index++;
            return nextMatch();
        }
		
		@Override
        public T previous() {
            if (index<=0) {
                throw new NoSuchElementException();
            }
			index--;
            return prevMatch();
        }

        private T nextMatch() {
            T ilast = next;
			
            while (iterator.hasNext()) {
                T value = iterator.next();
                if (predicate.test(index, value)) {
                    hasNext = true;
                    next = value;
                    return ilast;
                } else if(limit) {
                    break;
                }
            }

            hasNext = false;
            return ilast;
        }
		
		private T prevMatch() {
            while (iterator.hasPrevious()) {
                T value = iterator.previous();
                if (predicate.test(index, value)) {
                    hasNext = true;
                    next = value;
                    return next;
                }
            }
            throw new AssertionError("unreachable code");
        }

		
		@Override
		public int nextIndex() {
			return index;
		}
		
		@Override
		public int previousIndex() {
			return index-1;
		}

		@Override
		public void remove() {
			// impossible to implement both "hasNext" & "mutable methods" reliably
            throw new UnsupportedOperationException();
		}

		@Override
		public void set(T e) {
			// impossible to implement both "hasNext" & "mutable methods" reliably
            throw new UnsupportedOperationException();
		}

		@Override
		public void add(T e) {
			// impossible to implement both "hasNext" & "mutable methods" reliably
            throw new UnsupportedOperationException();
		}

    }

    private static final class LimitIterator<T> implements Iterator<T> {

        private final Iterator<T> src;
        private final int limit;
        private int index;

        public LimitIterator(Iterator<T> src, int limit) {
            this.src = src;
            this.limit = limit;
        }

        @Override
        public boolean hasNext() {
            return index <limit && src.hasNext();
        }

        @Override
        public T next() {
            if(index >=limit) {
                throw new NoSuchElementException();
            }
            index++;
            return src.next();
        }

    }

    private static final class LimitListIterator<T> implements ListIterator<T> {

        private final ListIterator<T> src;
        private final int limit;
        private int index;

        public LimitListIterator(ListIterator<T> src, int limit) {
            this.src = src;
            this.limit = limit;
        }

        @Override
        public boolean hasNext() {
            return index <limit && src.hasNext();
        }

        @Override
        public T next() {
            if(index>=limit) {
                throw new NoSuchElementException();
            }
            index++;
            return src.next();
        }

        @Override
        public boolean hasPrevious() {
            return index >0 && src.hasPrevious();
        }

        @Override
        public T previous() {
            if(index<=0) {
                throw new NoSuchElementException();
            }
            index--;
            return src.previous();
        }

        @Override
        public int nextIndex() {
            return index;
        }

        @Override
        public int previousIndex() {
            return index - 1;
        }

        @Override
        public void remove() {
            src.remove();
        }

        @Override
        public void set(T value) {
            src.set(value);
        }

        @Override
        public void add(T value) {
            src.add(value);
        }

    }

    /**
     * We implement only Iterator, because it is impossible to create correct reversed ListIterator.
     * Indexing will be invalid and #add operation will insert into wrong place.
     * Eventually we can implement #set operation, but it is not enough to return interface which is 90% not implemented.
     * @param <T>
     */
	private static class ReverseIterator<T> implements Iterator<T> {
		
		private final ListIterator<? extends T> iterator;

		public ReverseIterator(ListIterator<? extends T> iterator) {
			this.iterator = iterator;
		}

		@Override
		public void remove() {
			iterator.remove();
		}

		@Override
		public boolean hasNext() {
			return iterator.hasPrevious();
		}

		@Override
		public T next() {
			return iterator.previous();
		}

	}

    private static class BufferedIterator<T> implements ListIterator<T> {

        private final int max;

        private final Iterator<? extends T> iterator;

        private final Deque<T> prev = new LinkedList<>();

        private final Deque<T> next = new LinkedList<>();

        private int index;

        public BufferedIterator(Iterator<? extends T> iterator, int max) {
            this.max = max;
            this.index = 0;
            this.iterator = iterator;
        }

        @Override
        public boolean hasNext() {
            return !next.isEmpty() || iterator.hasNext();
        }

        @Override
        public T next() {
            index++;
            T out = !next.isEmpty() ? next.removeLast() : iterator.next();
            prev.addLast(out);
            if(prev.size() > max) {
                prev.removeFirst();
            }
            return out;
        }

        @Override
        public boolean hasPrevious() {
            return !prev.isEmpty();
        }

        @Override
        public T previous() {
            index--;
            T out = prev.removeLast();
            next.addLast(out);
            if(next.size() > max) {
                next.removeFirst();
            }
            return out;
        }

        @Override
        public int nextIndex() {
            return index;
        }

        @Override
        public int previousIndex() {
            return index-1;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public void set(T t) {
            throw new UnsupportedOperationException();
        }

        @Override
        public void add(T t) {
            throw new UnsupportedOperationException();
        }

    }

    private static final class FlatIterator<T> implements Iterator<T> {

        private final Iterator<? extends Iterator<? extends T>> li;
        private Iterator<? extends T> ci;

        public FlatIterator(Iterator<? extends Iterator<? extends T>> data) {
            li = data;
            ci = Collections.emptyListIterator();
        }

        @Override
        public boolean hasNext() {
            if(ci.hasNext()) {
                return true;
            }
            while(li.hasNext()) {
                ci = li.next();
                if(ci.hasNext()) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public T next() {
            if(!hasNext()) {
                throw new NoSuchElementException();
            }
            return ci.next();
        }

        @Override
        public void remove() {
            ci.remove();
        }

    }

    private enum FlatMode {
        SHALLOW,
        DEEP,
        TREE
    }

    private static class FlatMapIterator<T> extends ForwardIterator<T> {

        private final Deque<Iterator<? extends T>> stack = new ArrayDeque<>(1);

        private final FlatMode mode;
        private final Predicate<? super T> split;
        private final Function<? super T, Iterator<T>> splitter;

        public FlatMapIterator(FlatMode mode, Iterator<? extends T> iterator, Predicate<? super T> split, Function<? super T, Iterator<T>> splitter) {
            this.mode = mode;
            this.split = split;
            this.splitter = splitter;
            this.stack.push(iterator);
        }

        @Override
        protected boolean next(Consumer<? super T> action) {
            if(stack.isEmpty()) {
                return false;
            }

            if(!stack.peek().hasNext()) {
                stack.pop();
                return next(action);
            }

            T item = stack.peek().next();
            if((stack.size() == 1 || mode != FlatMode.SHALLOW) && split.test(item)) {
                stack.push(splitter.apply(item));
                if(mode == FlatMode.TREE)  {
                    action.accept(item);
                    return true;
                } else {
                    return next(action);
                }
            } else {
                action.accept(item);
                return true;
            }
        }

    }

    private static class SingleIterator<T> implements Iterator<T> {

        private final T value;

        private boolean hasNext = true;

        public SingleIterator(T value) {
            this.value = value;
        }

        public boolean hasNext() {
            return hasNext;
        }

        @Override
        public T next() {
            if (hasNext()) {
                hasNext = false;
                return value;
            }
            throw new NoSuchElementException();
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public void forEachRemaining(Consumer<? super T> action) {
            Objects.requireNonNull(action);
            if (hasNext()) {
                action.accept(value);
                hasNext = false;
            }
        }
    }

    private static class SafeIterator<T, E extends Throwable> implements Iterator<T> {

        private final Iterator<? extends T> iterator;
        private final Class<E> type;
        private final Consumer<E> handler;
        private final Wrapper <T> last;

        public SafeIterator(Iterator<? extends T> iterator, Class<E> type, Consumer<E> handler) {
            this.iterator = iterator;
            this.type = type;
            this.handler = handler;
            this.last = Wrappers.mutable(null);
        }

        @Override
        public boolean hasNext() {
            if (last.isPresent()) {
                return true;
            }
            if (!iterator.hasNext()) {
                return false;
            }
            while(last.isEmpty() && iterator.hasNext()) {
                try {
                    last.set(iterator.next());
                    return true;
                } catch (Throwable e) {
                    if (type.isInstance(e)) {
                        e.printStackTrace();
                        handler.accept(type.cast(e));
                    } else {
                        throw ExceptionUtils.rethrow(e);
                    }
                }
            }
            return false;
        }

        @Override
        public T next() {
            if (last.isPresent()) {
                return last.replace(null);
            } else {
                throw new NoSuchElementException();
            }
        }

        @Override
        public void remove() {
            try {
                iterator.remove();
            } catch (Throwable e) {
                if(type.isInstance(e)) {
                    handler.accept(type.cast(e));
                } else {
                    throw ExceptionUtils.rethrow(e);
                }
            }
        }

    }

    private static class CustomIterator<V> implements Iterator<V> {

        private final Supplier<? extends Throwable> cause;

        private Iterator<V> iterator;

        public CustomIterator(Supplier<? extends Throwable> cause, Iterator<V> iterator) {
            this.cause = cause;
            this.iterator = iterator;
        }

        public boolean hasNext() {
            return iterator.hasNext();
        }

        @Override
        public void remove() {
            iterator.remove();
        }

        @Override
        public V next() {
            if(iterator.hasNext()) {
                return iterator.next();
            } else {
                Throwable throwable = cause.get();
                NoSuchElementException exception = new NoSuchElementException(throwable.getMessage());
                exception.initCause(throwable);
                throw exception;
            }
        }
    }

    private static class CustomListIterator<V> implements ListIterator<V> {

        private final Supplier<? extends Throwable> cause;

        private ListIterator<V> iterator;

        public CustomListIterator(Supplier<? extends Throwable> cause, ListIterator<V> iterator) {
            this.cause = cause;
            this.iterator = iterator;
        }

        public boolean hasNext() {
            return iterator.hasNext();
        }

        @Override
        public boolean hasPrevious() {
            return iterator.hasPrevious();
        }

        @Override
        public int nextIndex() {
            return iterator.nextIndex();
        }

        @Override
        public int previousIndex() {
            return iterator.previousIndex();
        }

        @Override
        public void remove() {
            iterator.remove();
        }

        @Override
        public void set(V v) {
            iterator.set(v);
        }

        @Override
        public void add(V v) {
            iterator.add(v);
        }

        @Override
        public V previous() {
            if(iterator.hasPrevious()) {
                return iterator.previous();
            } else {
                Throwable throwable = cause.get();
                NoSuchElementException exception = new NoSuchElementException(throwable.getMessage());
                exception.initCause(throwable);
                throw exception;
            }
        }

        @Override
        public V next() {
            if(iterator.hasNext()) {
                return iterator.next();
            } else {
                Throwable throwable = cause.get();
                NoSuchElementException exception = new NoSuchElementException(throwable.getMessage());
                exception.initCause(throwable);
                throw exception;
            }
        }

    }
}
