public class ChainingHashDictionary<K, V> implements IDictionary<K, V> {
    private Supplier<IDictionary<K, V>> chain;
    private int numResize = 0;

    private final int [] primes = {11, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433};
    private IDictionary<K, V>[] data;
    private int size;


    public ChainingHashDictionary(Supplier<IDictionary<K, V>> chain) {
        this.chain = chain;
        this.size = 0;
        this.data = (IDictionary<K, V>[]) new IDictionary[primes[0]];
    }

    /**
     * @param key
     * @return value corresponding to key
     */
    @Override
    public V get(K key) {
        if (this.size == 0){
            return null;
        }

        int index = Math.abs(key.hashCode() % this.data.length);

        if(this.data[index] == null){
            return null;
        }

        return this.data[index].get(key);
    }

    @Override
    public V remove(K key) {
        V val = get(key);

        if(val != null){
            int idx = Math.abs(key.hashCode() % this.data.length);
            this.data[idx].remove(key);
            this.size--;
        }
        return val;
    }

    @Override
    public V put(K key, V value) {
        V ret = get(key);
        if(ret == null){
            this.size++;
        }
        if (((double) this.size / this.data.length) >= 1){
            numResize ++;
            IDictionary<K, V>[] newData = (IDictionary<K, V>[]) new IDictionary[primes[numResize]];

            for(int i = 0; i < this.data.length; i++){
                if(this.data[i] != null){
                    for(K pKeys: this.data[i].keys()){
                        int idx = Math.abs(pKeys.hashCode() % newData.length);
                        if(newData[idx] == null){
                            newData[idx] = this.chain.get();
                        }
                        newData[idx].put(pKeys, get(pKeys));
                    }
                }
            }
            this.data = newData;
            int idx2 = Math.abs(key.hashCode()% this.data.length);
            if(this.data[idx2] == null){
                this.data[idx2] = this.chain.get();
            }
            this.data[idx2].put(key, value);
        }

        else{
            int idx3 = Math.abs(key.hashCode()% this.data.length);
            if(this.data[idx3] == null){
                this.data[idx3] = this.chain.get();
            }
            this.data[idx3].put(key, value);
            }
        return ret;
    }

    @Override
    public boolean containsKey(K key) {
        int idx = Math.abs(key.hashCode() % this.data.length);
        if(this.data[idx] == null){
            return false;
        }
        else {
            for(K d_key : this.data[idx].keys()){
                if(d_key.equals(key)){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * @param value
     * @return true if the HashDictionary contains a key-value pair with
     * this value, and false otherwise
     */
    @Override
    public boolean containsValue(V value) {
        for(int i = 0; i < this.data.length; i++){
            if(this.data[i]!= null){
                for(K key : this.data[i].keys()){
                    if (this.data[i].get(key).equals(value)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * @return number of key-value pairs in the HashDictionary
     */
    @Override
    public int size() {
        return this.size;
    }

    @Override
    public ICollection<K> keys() {
        ICollection<K> ret = new ArrayDeque<>();
        for(int i = 0; i < this.data.length; i++){
            if(this.data[i] != null){
                for(K key : this.data[i].keys()){
                    ret.add(key);
                }
            }
        }
        return ret;
    }


    @Override
    public ICollection<V> values() {
        ICollection<V> ret = new ArrayDeque<>();
        for(int i = 0; i < this.data.length; i++){
            if(this.data[i] != null){
                for(V val : this.data[i].values()){
                    ret.add(val);
                }
            }
        }
        return ret;
    }

    /**
     * @return An iterator for all entries in the HashDictionary
     */
    @Override
    public Iterator<K> iterator() {
        return this.keys().iterator();
    }
}