package church.util;

import java.util.function.BiFunction;
import java.util.function.Predicate;

import church.lang.ArraySupport;
import church.util.CollectionsSupport.EquivalenceRelation;
import church.util.CollectionsSupport.LeftFold;
import church.util.CollectionsSupport.RightFold;

public abstract class LinkedList<T> {
    public interface Visitor<T, S> {
        S empty();

        S cons(T element, LinkedList<T> rest);
    }

    public abstract <S> S accept(Visitor<T, S> visitor);

    public static <T> LinkedList<T> empty() {
        return new LinkedList<T>() {
            public <S> S accept(Visitor<T, S> visitor) {
                return visitor.empty();
            }
        };
    }

    public static <T> LinkedList<T> cons(T element, LinkedList<T> rest) {
        return new LinkedList<T>() {
            public <S> S accept(Visitor<T, S> visitor) {
                return visitor.cons(element, rest);
            }
        };
    }

    @SuppressWarnings("unchecked")
    public static <T> LinkedList<T> list(T... elements) {
        return ArraySupport.<T>rightFold().reduce(LinkedList::cons, empty(), elements);
    }

    public static <T> int size(LinkedList<T> list) {
        return list.accept(new Visitor<T, Integer>() {
            @Override
            public Integer empty() {
                return 0;
            }

            @Override
            public Integer cons(T element, LinkedList<T> rest) {
                return 1 + rest.accept(this);
            }
        });
    }

    public static <T> T find(LinkedList<T> list, Predicate<T> selector, T defaultValue) {
        return list.accept(new Visitor<T, T>() {
            @Override
            public T empty() {
                return defaultValue;
            }

            @Override
            public T cons(T entry, LinkedList<T> rest) {
                return selector.test(entry) ? entry : rest.accept(this);
            }
        });
    }

    public static <T> boolean contains(EquivalenceRelation<T> equivalence, LinkedList<T> list, T example) {
        return find(list, element -> equivalence.equal(example, element), null) != null;
    }

    public static <T> LeftFold<LinkedList<T>, T> leftFold() {
        return new LeftFold<LinkedList<T>, T>() {
            @Override
            public <R> R reduce(BiFunction<R, T, R> accumulator, R initialValue, LinkedList<T> list) {
                // Pure functional version, allocates O(n) new Visitors.
                /* 
                return new Object() { 
                    private R recurse(LinkedList<T> l, R result) { 
                        return l.accept(new Visitor<T, R>() { 
                            @Override 
                            public R empty() { 
                                return result; 
                            } 
 
                            @Override 
                            public R cons(T entry, LinkedList<T> rest) { 
                                return recurse(rest, accumulator.apply(result, entry)); 
                            } 
                        }); 
                    } 
                }.recurse(list, initialValue); 
                */
//                Iterative version (using assignment).
                return list.accept(new Visitor<T, R>() {
                    private R result = initialValue;

                    @Override
                    public R empty() {
                        return result;
                    }

                    @Override
                    public R cons(T entry, LinkedList<T> rest) {
                        result = accumulator.apply(result, entry);
                        return rest.accept(this);
                    }
                });
            }
        };
    }

    public static <T> RightFold<LinkedList<T>, T> rightFold() {
        return new RightFold<LinkedList<T>, T>() {
            @Override
            public <R> R reduce(BiFunction<T, R, R> accumulator, R initialValue, LinkedList<T> list) {
                return list.accept(new Visitor<T, R>() {
                    @Override
                    public R empty() {
                        return initialValue;
                    }

                    @Override
                    public R cons(T entry, LinkedList<T> rest) {
                        return accumulator.apply(entry, rest.accept(this));
                    }
                });
            }
        };
    }
}