package church.util;

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

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

@SuppressWarnings("unchecked")
public class HashTable<E, K> {
    public interface Factory<E, K> {
        <C> HashTable<E, K> hashTable(Function<E, K> entryToKey, RightFold<C, E> fold, C entries);

        static <E, K> Factory<E, K> hashTable(float loadFactor, EquivalenceRelation<K> equivalenceRelation, HashingFunction<K> hashingFunction) {
            return new Factory<E, K>() {
                @Override
                public <C> HashTable<E, K> hashTable(Function<E, K> entryToKey, RightFold<C, E> fold, C entries) {
                    return new HashTable<>(loadFactor, equivalenceRelation, hashingFunction, entryToKey, fold, entries);
                }
            };
        }

        static <E, K> Factory<E, K> hashTable(EquivalenceRelation<K> equivalenceRelation, HashingFunction<K> hashingFunction) {
            return hashTable(DEFAULT_LOAD_FACTOR, equivalenceRelation, hashingFunction);
        }

        static <E, K> Factory<E, K> hashTable() {
            return hashTable(Object::equals, Object::hashCode);
        }
    }

    // Our load factor is not an upper-bound as it is in java.util.HashMap but, because we are immutable, a
    // fixed percentage. This implementation uses 0.5 with the assumption that the battle-hardened default
    // of 0.75 in java.util.HashMap ends up leaving a HashMap roughly 50% full on average.
    private static final float DEFAULT_LOAD_FACTOR = 0.5f;

    public final  EquivalenceRelation<K> equivalenceRelation;
    @SuppressWarnings("WeakerAccess")
    public final  HashingFunction<K>     hashingFunction;
    private final Function<E, K>         entryToKey;
    private final LinkedList<E>[]        buckets;
    private       int                    size;

    @SuppressWarnings("WeakerAccess")
    protected <C> HashTable(float loadFactor, EquivalenceRelation<K> equivalenceRelation, HashingFunction<K> hashingFunction, Function<E, K> entryToKey, RightFold<C, E> fold, C entries) {
        int inputSize = fold.reduce((l, s) -> 1 + s, 0, entries);
        this.equivalenceRelation = equivalenceRelation;
        this.hashingFunction     = hashingFunction;
        this.entryToKey          = entryToKey;
        //noinspection unchecked
        this.buckets = new LinkedList[(int) (inputSize / loadFactor)];
        Arrays.fill(buckets, LinkedList.empty());
        EquivalenceRelation<E> entryEquivalence = (e1, e2) -> equivalenceRelation.equal(entryToKey.apply(e1), entryToKey.apply(e2));
        BiFunction<E, LinkedList<E>[], LinkedList<E>[]> accumulator = (entry, rest) -> {
            int           bucketIndex = getBucketIndexForEntry(entry);
            LinkedList<E> bucket      = buckets[bucketIndex];
            if (!LinkedList.contains(entryEquivalence, bucket, entry)) {
                size++;
                buckets[bucketIndex] = LinkedList.cons(entry, bucket); // note the sacrilegious modification of state
            }
            return buckets;
        };
        fold.reduce(accumulator, buckets, entries);
    }

    public static <E, K> HashTable<E, K> hashTable(Function<E, K> projection, E[] elements) {
        return Factory.<E, K>hashTable().hashTable(projection, ArraySupport.rightFold(), elements);
    }

    public static <E, K> HashTable<E, K> hashTable4(Function<E, K> projection, EquivalenceRelation<K> equivalenceRelation, HashingFunction<K> hashingFunction, E... elements) {
        return Factory.<E, K>hashTable(equivalenceRelation, hashingFunction).hashTable(projection, ArraySupport.rightFold(), elements);
    }

    public int size() {
        return size;
    }

    private int getBucketIndexForKey(K key) {
        return Integer.remainderUnsigned(hashingFunction.hashCode(key), buckets.length);
    }

    private int getBucketIndexForEntry(E entry) {
        return getBucketIndexForKey(entryToKey.apply(entry));
    }

    public LinkedList<E> getBucketForKey(K key) {
        return buckets[getBucketIndexForKey(key)];
    }

    public LinkedList<E> getBucketForEntry(E entry) {
        return getBucketForKey(entryToKey.apply(entry));
    }

    public boolean contains(K key) {
        LinkedList<E> bucketForKey = getBucketForKey(key);
        Predicate<E>  p            = entry -> equivalenceRelation.equal(entryToKey.apply(entry), key);
        return LinkedList.find(bucketForKey, p, null) != null;
    }

    // Folds

    public static <E, K> LeftFold<HashTable<E, K>, E> leftFold() {
        return CollectionsSupport.compose(ArraySupport.leftFold(), LinkedList.leftFold(), map -> map.buckets);
    }

    public static <E, K> RightFold<HashTable<E, K>, E> rightFold() {
        return CollectionsSupport.compose(ArraySupport.rightFold(), LinkedList.rightFold(), map -> map.buckets);
    }
}