/*
 * Lazy list implementation.
 */

package edu.rice.comp322;

import java.util.NoSuchElementException;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;

/** Interface for a Lazy functional list over generic types. */
public interface LazyList<T> {
    // Data definition: a LazyList is one of two things:
    // - LazyCons: an element of type T, and a LazyList<T> Supplier for the tail
    // - Empty

    static <T> LazyList<T> cons(T head, Supplier<LazyList<T>> tailSupplier) {
        return new LazyCons<>(head, tailSupplier);
    }

    /** Create a new empty list of the given parameter type. */
    @SuppressWarnings("unchecked")
    static <T> LazyList<T> empty() {
        return (LazyList<T>) Empty.SINGLETON;
    }


    /** Returns the value of the first element in the list. */
    T head();

    /**
     * Returns a new Lazy List equal to the old list without its head() element. If the list is empty, this
     * will throw an exception.
     */
    LazyList<T> tail();

    /** Returns a new list with the given value in the front. */
    default LazyList<T> prepend(T val) {
        return new LazyCons<>(val, () -> this);
    }

    /** Returns whether the list is empty or not. */
    boolean isEmpty();

    /**
     *  Make a LazyList of integers starting from i, skipping by step.
     */
    static LazyList<Integer> from(int i, int step) {
        return cons(i,()->from(i + step, step));
    }

    /**
     *  Make a LazyList consisting of all the same elements.
     */
    static <T> LazyList<T> continually(T s) {
        return cons(s,() -> continually(s));
    }

    /** Returns a new list equal to all the elements in the old list satisfying the predicate. */
    LazyList<T> filter(Predicate<T> predicate);

    /** Returns a new list equal to the old list with the function applied to each value. */
    <R> LazyList<R> map(Function<T, R> f);

    /**
     * Returns a value of type U equal to the elements of the list applied in sequence to one another
     * with the given operator. This happens from left-to-right (i.e., from head() to tail()). The
     * zero value is used to the left of the list's head. If the list is empty, the zero value is
     * returned.
     */
    <U> U foldLeft(U zero, BiFunction<U, T, U> operator);

    /**
     * Returns a value of type T equal to the elements of the list applied in sequence to one another
     * with the given operator. This happens from right-to-left (i.e., from tail() to head()). The
     * zero value is used to the right of the list's last non-empty value. If the list is empty, the
     * zero value is returned.
     */
    <U> U foldRight(U zero, BiFunction<T, U, U> operator);

    /**
     * The default implementation of fold is foldLeft.
     */
    default <U> U fold(U zero, BiFunction<U, T, U> operator) {
        return foldLeft(zero, operator);
    }

    /**
     * Returns a new list equal to at most the first n elements of "this" list. If n &gt; length(),
     * then the returned list will be equal to "this" list. If n &lt;= 0, an empty list will be
     * returned.
     */
    LazyList<T> take(int n);


    class LazyCons<T> implements LazyList<T> {
        private final T headVal;
        private final Lazy<LazyList<T>> tail;

        private LazyCons(T value, Supplier<LazyList<T>> tailSupplier) {
            this.headVal = value;
            this.tail = Lazy.of(tailSupplier);
        }

        @Override
        public T head() {
            return headVal;
        }

        @Override
        public LazyList<T> tail() {
            return tail.get();
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        @Override
        public LazyList<T> filter(Predicate<T> predicate) {
            if (predicate.test(headVal)) {
                return cons(headVal, () -> tail.get().filter(predicate));
            } else {
                return tail.get().filter(predicate);
            }
        }

        @Override
        public <R> LazyList<R> map(Function<T, R> f) {
            return cons(f.apply(headVal), ()->tail.get().map(f));
        }

        @Override
        public <U> U foldLeft(U zero, BiFunction<U, T, U> operator) {

            LazyList<T> currentList = this;

            while (!currentList.isEmpty()) {
                zero = operator.apply(zero, currentList.head());
                currentList = currentList.tail();
            }
            return zero;
        }

        @Override
        public <U> U foldRight(U zero, BiFunction<T, U, U> operator) {
            return operator.apply(headVal, tail().foldRight(zero, operator));
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }

            if (!(other instanceof LazyList.LazyCons<?>)) {
                return false;
            }

            var otherList = (LazyCons<?>) other;

            return headVal.equals(otherList.headVal) && tail().equals(otherList.tail());
        }

        @Override
        public int hashCode() {
            return headVal.hashCode() + tail().hashCode() * 31; // a hack, but better than nothing
        }

        @Override
        public LazyList<T> take(int n) {
            if (n < 1) {
                return empty();
            } else {
                return cons(headVal, ()-> tail().take(n - 1));
            }
        }
    }

    class Empty<T> implements LazyList<T> {
        private Empty() {}

        private static final LazyList<?> SINGLETON = new Empty<>();

        @Override
        public T head() {
            throw new NoSuchElementException("can't take head() of an empty list");
        }

        @Override
        public LazyList<T> tail() {
            throw new NoSuchElementException("can't take tail() of an empty list");
        }

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


        @Override
        public LazyList<T> filter(Predicate<T> predicate) {
            return empty();
        }

        @Override
        public LazyList<T> take(int n) {
            return this;
        }

        @Override
        public <R> LazyList<R> map(Function<T, R> f) {
            return empty();
        }

        @Override
        public <U> U foldLeft(U zero, BiFunction<U, T, U> operator) {
            return zero;
        }

        @Override
        public <U> U foldRight(U zero, BiFunction<T, U, U> operator) {
            return zero;
        }

        @Override
        public boolean equals(Object other) {
            return other instanceof Empty<?> ;
        }

        @Override
        public int hashCode() {
            return 1; // a hack, but better than nothing
        }
    }
}