import java.util.LinkedList;
import java.util.NoSuchElementException;
import org.junit.jupiter.api.Test;

public class HashtableMap<KeyType, ValueType> implements MapADT<KeyType, ValueType> {

    /**
     * Pair inner class that contains key and value mapping
     */
    protected class Pair {
        public KeyType key;
        public ValueType value;

        public Pair(KeyType key, ValueType value) {
            this.key = key;
            this.value = value;
        }
    }

    //array storing chains
    protected LinkedList<Pair>[] table = null;

    //Number of key-value mappings stored
    private int size = 0;

    /**
     * Constructs hashtable with initial capacity
     */
    @SuppressWarnings("unchecked")
    public HashtableMap(int capacity) {
        table = (LinkedList<Pair>[])(new LinkedList[capacity]);
        size = 0;
    }

    /**
     * Constructs hashtable with capacity 8.
     */
    public HashtableMap() {
        this(8);
    }

    /**
     * Finds array index for key
     */
    private int hashIndex(KeyType key) {return Math.abs(key.hashCode()) % table.length;}

    /**
     * Ensures load factor < 0.75 otherwise doubles capacity and rehashes
     */
    private void ensureCapacity() {
        // If >= 0.75 resize to keep collisions low
        double loadFactor = (double)size/table.length;
        if (loadFactor >= 0.75) resize();
    }

    /**
     * Resizes to double capacity and rehashes all pairs
     */
    @SuppressWarnings("unchecked")
    private void resize() {
        LinkedList<Pair>[] oldTable = table;
        // double the old capacity
        table = (LinkedList<Pair>[])(new LinkedList[oldTable.length*2]);
        // size will be recomputed by re -putting all pairs
        size = 0;
        // rehashes entries
        for (LinkedList<Pair> chain : oldTable) {
            if (chain != null) {
                for (Pair p : chain) {
                    put(p.key, p.value);
                }
            }
        }
    }

    /**
     * Adds a new key,value pair/mapping to this collection. It is okay that the value is null.
     * @param key the key of the key,value pair
     * @param value the value that key maps to
     * @throws IllegalArgumentException if key already maps to a value without making any
     *         changes to the table
     * @throws NullPointerException if key is null
     */
    public void put(KeyType key, ValueType value) throws IllegalArgumentException {
        if (key == null) throw new NullPointerException("Key cannot be null.");

        int index = hashIndex(key);

        // create new LinkedList for this chain if index location is empty
        if (table[index] == null) table[index] = new LinkedList<>();

        // Check for duplicate key
        for (Pair p : table[index]) {
            if (p.key.equals(key)) throw new IllegalArgumentException("Duplicate key.");
        }

        // Insert new key and value pair
        table[index].add(new Pair(key, value));
        size++;

        // Check whether resize needed
        ensureCapacity();
    }

    /**
     * Checks whether a key maps to a value in this collection.
     * @param key the key to check
     * @throws NullPointerException if key is null
     * @return true if the key maps to a value, and false is the key doesn't map to a value
     */
    public boolean containsKey(KeyType key) {
        if (key == null) throw new NullPointerException("Key cannot be null.");

        int index = hashIndex(key);
        LinkedList<Pair> chain = table[index];

        // If null key cannot exist
        if (chain == null) return false;

        // find if key exists
        for (Pair p : chain) {
            if (p.key.equals(key)) return true;
        }
        return false;
    }

    /**
     * Retrieves the specific value that a key maps to.
     * @param key the key to look up
     * @return the value that key maps to
     * @throws NoSuchElementException when key is not stored in this collection
     * @throws NullPointerException if key is null
     */
    public ValueType get(KeyType key) throws NoSuchElementException {
        if (key == null) throw new NullPointerException("Key cannot be null.");

        int index = hashIndex(key);
        LinkedList<Pair> chain = table[index];

        // Search through
        if (chain != null) {
            for (Pair p : chain) {
                if (p.key.equals(key)) return p.value;
            }
        }

        throw new NoSuchElementException("Key not found.");
    }

    /**
     * Remove the mapping for a key from this collection.
     * @param key the key whose mapping to remove
     * @return the value that the removed key mapped to
     * @throws NoSuchElementException when key is not stored in this collection
     * @throws NullPointerException if key is null
     */
    public ValueType remove(KeyType key) throws NoSuchElementException {
        if (key == null) throw new NullPointerException("Key cannot be null.");

        int index = hashIndex(key);
        LinkedList<Pair> chain = table[index];

        if (chain != null) {
            // Go by index, can remove by position
            for (int i = 0; i < chain.size(); i++) {
                if (chain.get(i).key.equals(key)) {
                    ValueType val = chain.get(i).value;
                    // remove pair
                    chain.remove(i);
                    //update size
                    size--;
                    return val;
                }
            }
        }

        throw new NoSuchElementException("Key not found.");
    }

    /**
     * Removes all key,value pairs from this collection without changing the
     * capacity of the underlying array.
     */
    public void clear() {
        // clear all chains and maintain capacity
        for (int i = 0; i < table.length; i++) {
            table[i] = null;
        }

        size = 0;
    }

    /**
     * Retrieves the number of keys stored in this collection.
     * @return the number of keys stored in this collection
     */
    public int getSize() {return size;}

    /**
     * Retrieves this collection's capacity.
     * @return the size of the underlying array for this collection
     */
    public int getCapacity() {return table.length;}

    /**
     * getKeys() method for P214
     */
    public LinkedList<KeyType> getKeys() {
	LinkedList<KeyType> keys = new LinkedList<>();
	for (LinkedList<Pair> chain : table) {
	    if (chain != null) {
                for (Pair p : chain) {
                    keys.add(p.key);
                }
            }
         }
	return keys;
    }


    /**
     * Test number 1: Tests put() and get()
     */
    @Test
    public void testPutAndGet() {
        // create map
        HashtableMap<String, Integer> map = new HashtableMap<>();

        // insert a key and value pair
        map.put("balls", 10);

        // assert correct value
        assert(map.get("balls") == 10);

        // assert size increments
        assert(map.getSize() == 1);
    }

    /**
     * Test number 2: Tests containsKey()
     */
    @Test
    public void testContainsKey() {
        // create map
        HashtableMap<Integer, String> map = new HashtableMap<>();

        // insert pairs
        map.put(1, "uno");
        map.put(2, "dos");

        // assert correct and incorrectness
        assert(map.containsKey(1));
        assert(!map.containsKey(3));
    }

    /**
     * Test number 3: Tests remove()
     */
    @Test
    public void testRemove() {
        // create map
        HashtableMap<String, String> map = new HashtableMap<>();

        // insert pairs
        map.put("A", "a");
        map.put("B", "b");

        // remove "A" key
        String removed = map.remove("A");

        // assertions
        assert(removed.equals("a"));
        assert(!map.containsKey("A"));
        assert(map.getSize() == 1);
    }

    /**
     * Test number 4: Tests map triggers resizes at threshold
     */
    @Test
    public void testResizeTrigger() {
        // create map with initial capacity 8
        HashtableMap<Integer, Integer> map = new HashtableMap<>();

        // resize after 6th insertion
        for (int i = 0; i < 6; i++) {
            map.put(i, i*i);
        }

        // check size before resize
        assert(map.getSize() == 6);

        // one more element to force resize
        map.put(6, 36);

        // assertions
        // old
        assert(map.get(5) == 25);
        // new
        assert(map.get(6) == 36);
    }

    /**
     * Test number 5: Tests rehashing redistributes elements after resize()
     */
    @Test
    public void testRehashCorrectness() {
        // create map
        HashtableMap<Integer, String> map = new HashtableMap<>();

        // insert data to force resize
        for (int i = 0; i < 20; i++) {
            map.put(i, "num" + i);
        }

        // assert size
        assert(map.getSize() == 20);

        // assert All values still exist
        for (int i = 0; i < 20; i++) {
            assert(map.get(i).equals("num" + i));
        }

        // test clear() after a resize
        map.clear();
        assert(map.getSize() == 0);
        assert(!map.containsKey(0));
    }

}