///////////////////////////////////////////
///
/// File: HashtableMap.java
/// Author: Evan Gaul
/// Email: eagaul@wisc.edu
/// Date: 12/3/25
/// Assignment: P213.Hashtable
/// Course: CS400 Lec004 Fall 2025
/// Professor: Ashley Samuelson
///
///////////////////////////////////////////
///
/// Assistance: None
///
///////////////////////////////////////////

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

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

    /**
     * Pair class to group a key and its value.
     */
    protected class Pair {
        public KeyType key;
        public ValueType value;

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

    protected LinkedList<Pair>[] table = null; // The table array storing LinkedLists of Pair objects.
    private int size = 0;
    private static final double LOADFACTOR = 0.75;
    private static final int DEFAULT_CAPACITY = 8;

    /**
     * Makes a hashtable with an initial capacity.
     *
     * @param capacity initial capacity, must be greater or equal to 1
     */
    @SuppressWarnings("unchecked")
    public HashtableMap(int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException("Capacity must be at >= 1");
        }
        // Create array and cast to generic type
        table = (LinkedList<Pair>[]) new LinkedList[capacity];
        size = 0;
    }

    /**
     * Makes a hashtable with default capacity
     */
    public HashtableMap() {
        this(DEFAULT_CAPACITY);
    }

    // Helper Methods

    /** helper
     * Compute the table index for a key
     */
    private int indexForKey(KeyType key) {
        return key.hashCode() % getCapacity();
    }

    /** helper
     * Find a Pair in a chain that has a matching key and return it
     * return null if not found
     */
    private Pair findPairInChain(LinkedList<Pair> chain, KeyType key) {
        if (chain == null) return null;
        for (Pair p : chain) {
            if (p.key.equals(key)) {
                return p;
            }
        }
        return null;
    }

    /** helper
     * Resize the table by doubling capacity and rehashing all pairs
     */
    @SuppressWarnings("unchecked")
    private void resizeAndRehash() {
        int oldCapacity = getCapacity();
        int newCapacity = oldCapacity * 2;
        LinkedList<Pair>[] oldTable = table;

        LinkedList<Pair>[] newTable = (LinkedList<Pair>[]) new LinkedList[newCapacity]; // create new table

        // rehash all pairs into newTable
        for (int i = 0; i < oldCapacity; i++) {
            LinkedList<Pair> chain = oldTable[i];
            if (chain != null) {
                for (Pair p : chain) {
                    int newIndex = p.key.hashCode() % newCapacity;

                    if (newTable[newIndex] == null) {
                        newTable[newIndex] = new LinkedList<>();
                    }
                    newTable[newIndex].add(new Pair(p.key, p.value));
                }
            }
        }

        // replace table reference
        table = newTable;
    }

    /** helper
     * Check if adding one more key would make load factor >= threshold
     * I used this to decide if to resize before insertion
     */
    private boolean wouldExceedLoadFactorOnInsert() {
        int capacity = getCapacity();
        double newLoad = ((double) (size + 1)) / (double) capacity; // check with one more than size
        return newLoad >= LOADFACTOR;
    }

    /**
     * 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
     */
    @Override
    public void put(KeyType key, ValueType value) throws IllegalArgumentException {
        if (key == null) {
            throw new NullPointerException("Key can't be null!");
        }

        // If the key already exists, throw IllegalArgumentException
        int idx = indexForKey(key);
        LinkedList<Pair> chain = table[idx];
        if (chain != null) {
            Pair existing = findPairInChain(chain, key);
            if (existing != null) {
                throw new IllegalArgumentException("Key already exists in table");
            }
        }

        // Resize if insertion would make load factor >= threshold
        if (wouldExceedLoadFactorOnInsert()) {
            resizeAndRehash();
            // get index again after rehash
            idx = indexForKey(key);
            chain = table[idx];
        }

        // Make sure that chain exists
        if (chain == null) {
            chain = new LinkedList<>();
            table[idx] = chain;
        }

        // insert new pair
        chain.add(new Pair(key, value));
        size++;
    }

    /**
     * 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
     */
    @Override
    public boolean containsKey(KeyType key) {
        if (key == null) {
            throw new NullPointerException("Key can't be null!");
        }
        int idx = indexForKey(key);
        LinkedList<Pair> chain = table[idx];
        Pair found = findPairInChain(chain, key);
        return found != null;
    }


    /**
     * 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
     */
    @Override
    public ValueType get(KeyType key) throws NoSuchElementException {
        if (key == null) {
            throw new NullPointerException("Key can't be null!");
        }
        int idx = indexForKey(key);
        LinkedList<Pair> chain = table[idx];
        Pair found = findPairInChain(chain, key);
        if (found == null) { // key not in collection
            throw new NoSuchElementException("Key not found");
        }
        return found.value;
    }

    /**
     * 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
     */
    @Override
    public ValueType remove(KeyType key) throws NoSuchElementException {
        if (key == null) {
            throw new NullPointerException("Key can't be null");
        }
        int idx = indexForKey(key);
        LinkedList<Pair> chain = table[idx];
        if (chain == null) {
            throw new NoSuchElementException("Key not found");
        }

        Pair toRemove = null;
        for (Pair p : chain) {
            if (p.key.equals(key)) {
                toRemove = p;
                break;
            }
        }
        if (toRemove == null) {
            throw new NoSuchElementException("Key not found");
        }

        chain.remove(toRemove);
        size--;
        return toRemove.value;
    }

    /**
     * Removes all key,value pairs from this collection without changing the
     * capacity of the underlying array.
     */
    @Override
    public void clear() {
        // Keep the same capacity but remove all chains
        for (int i = 0; i < getCapacity(); i++) {
            table[i] = null;
        }
        size = 0;
    }

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

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

    // TESTS!

    /**
     * Tests insertion and getting of key-value pairs.
     */
    @Test
    public void testPutAndGet() {
        // Create small map and insert pairs
        HashtableMap<String, Integer> map = new HashtableMap<>(4);
        map.put("a", 1);
        map.put("b", 2);

        // Get and check values
        assertEquals(1, map.get("a"));
        assertEquals(2, map.get("b"));
        // Check size
        assertEquals(2, map.getSize());
    }

    /**
     * Tests that a resize is triggered if load factor >= 0.75.
     */
    @Test
    public void testResizeTrigger() {
        // Capacity 4,so resize when size reaches 3
        HashtableMap<Integer, Integer> map = new HashtableMap<>(4);
        map.put(1, 10);
        map.put(2, 20);
        map.put(3, 30); // Should trigger resize

        // Capacity should double to 8
        assertEquals(8, map.getCapacity());
    }

    /**
     * Tests that pairs are correctly rehashed and preserved after resize.
     */
    @Test
    public void testRehashCorrectness() {
        HashtableMap<Integer, String> map = new HashtableMap<>(4);

        map.put(10, "ten");
        map.put(20, "twenty");
        map.put(30, "thirty");
        map.put(40, "forty"); // resize here

        // Make sure you can still get them
        assertEquals("ten", map.get(10));
        assertEquals("twenty", map.get(20));
        assertEquals("thirty", map.get(30));
        assertEquals("forty", map.get(40));

        // Check size also
        assertEquals(4, map.getSize());
    }

    /**
     * Tests containsKey() and remove() for removal lookup.
     */
    @Test
    public void testContainsAndRemove() {
        HashtableMap<String, Integer> map = new HashtableMap<>(4);
        map.put("x", 100);
        map.put("y", 200);

        // containsKey should work
        assertTrue(map.containsKey("x"));
        assertFalse(map.containsKey("z"));

        // remove should return value and delete key
        assertEquals(100, map.remove("x"));
        assertFalse(map.containsKey("x"));

        // check that it throws exception for removing a key that isn't in it
        assertThrows(NoSuchElementException.class, () -> map.remove("CS400IsSooMuchFUN!:)"));
    }

    /**
     * Tests clear(), getSize(), and NoSuchElementException for get().
     */
    @Test
    public void testClearAndExceptions() {
        HashtableMap<Integer, Integer> map = new HashtableMap<>(4);
        map.put(5, 50);
        map.put(6, 60);
        map.clear(); // clear everything

        // Size should be zero
        assertEquals(0, map.getSize());

        // Getting any key should now fail
        assertThrows(NoSuchElementException.class, () -> map.get(5));
    }

}