Untitled

import student.TestCase;

/**
 * Extra direct tests for Hash to improve mutation coverage.
 *
 * @author Leguejou Awunganyi
 * @author Ishita Punna
 * @version 2026-02-08
 */
public class HashTest extends TestCase {

    /**
     * Test basic insert/find/remove behavior.
     */
    public void testInsertFindRemoveBasics() {
        Hash hash = new Hash("artist", 10);

        GraphNode a = new GraphNode("A", true, 0);
        Hash.InsertResult result = hash.insert("A", a);

        assertTrue(result.inserted);
        assertFalse(result.duplicate);
        assertFalse(result.resized);
        assertEquals(1, hash.size());
        assertSame(a, (GraphNode)hash.find("A"));

        GraphNode removed = (GraphNode)hash.remove("A");
        assertSame(a, removed);
        assertEquals(0, hash.size());
        assertNull(hash.find("A"));
    }

    /**
     * Test duplicate detection and that original node is preserved.
     */
    public void testDuplicateInsert() {
        Hash hash = new Hash("artist", 10);

        GraphNode first = new GraphNode("A", true, 0);
        GraphNode second = new GraphNode("A-again", true, 1);

        Hash.InsertResult firstResult = hash.insert("A", first);
        Hash.InsertResult secondResult = hash.insert("A", second);

        assertTrue(firstResult.inserted);
        assertFalse(firstResult.duplicate);

        assertFalse(secondResult.inserted);
        assertTrue(secondResult.duplicate);
        assertEquals(1, hash.size());
        assertSame(first, (GraphNode)hash.find("A"));
    }

    /**
     * Test that searching continues past a tombstone and insert reuses tombstone.
     */
    public void testTombstoneSearchAndReuse() {
        Hash hash = new Hash("artist", 10);

        GraphNode a = new GraphNode("A", true, 0);
        GraphNode k = new GraphNode("K", true, 1);
        GraphNode u = new GraphNode("U", true, 2);

        hash.insert("A", a);
        hash.insert("K", k);

        assertSame(a, (GraphNode)hash.find("A"));
        assertSame(k, (GraphNode)hash.find("K"));

        GraphNode removed = (GraphNode)hash.remove("A");
        assertSame(a, removed);
        assertNull(hash.find("A"));

        assertSame(k, (GraphNode)hash.find("K"));

        Hash.InsertResult reuse = hash.insert("U", u);
        assertTrue(reuse.inserted);
        assertFalse(reuse.duplicate);

        assertFuzzyEquals(
            "5: |U|\r\n"
                + "6: |K|\r\n"
                + "total artists: 2\r\n",
            hash.print());

        assertSame(u, (GraphNode)hash.find("U"));
        assertSame(k, (GraphNode)hash.find("K"));
    }

    /**
     * Test resize and rehash preserve active entries.
     */
    public void testResizeRehashPreservesEntries() {
        Hash hash = new Hash("song", 2);

        GraphNode s1 = new GraphNode("Song1", false, 0);
        GraphNode s2 = new GraphNode("Song2", false, 1);
        GraphNode s3 = new GraphNode("Song3", false, 2);

        Hash.InsertResult r1 = hash.insert("Song1", s1);
        Hash.InsertResult r2 = hash.insert("Song2", s2);

        assertFalse(r1.resized);
        assertTrue(r2.resized);
        assertEquals(4, hash.capacity());

        assertSame(s1, (GraphNode)hash.find("Song1"));
        assertSame(s2, (GraphNode)hash.find("Song2"));

        Hash.InsertResult r3 = hash.insert("Song3", s3);
        assertTrue(r3.inserted);
        assertSame(s3, (GraphNode)hash.find("Song3"));
        assertEquals(3, hash.size());
    }

    /**
     * Test print shows tombstone and active entries after removal.
     */
    public void testPrintWithTombstone() {
        Hash hash = new Hash("artist", 10);

        GraphNode a = new GraphNode("A", true, 0);
        GraphNode k = new GraphNode("K", true, 1);

        hash.insert("A", a);
        hash.insert("K", k);
        hash.remove("A");

        assertFuzzyEquals(
            "5: TOMBSTONE\r\n"
                + "6: |K|\r\n"
                + "total artists: 1\r\n",
            hash.print());
    }

    /**
     * Test hash function is deterministic and stays in range.
     */
    public void testHashFunctionDeterministicAndInRange() {
        Hash hash = new Hash("artist", 10);

        int value1 = hash.h("Blind Lemon Jefferson", 10);
        int value2 = hash.h("Blind Lemon Jefferson", 10);

        assertEquals(value1, value2);
        assertTrue(value1 >= 0);
        assertTrue(value1 < 10);
    }
    
    /**
     * Test that resize rehashing handles collisions in placeEntry().
     */
    public void testResizeRehashCollisionPath() {
        Hash hash = new Hash("artist", 4);

        GraphNode a = new GraphNode("A", true, 0);
        GraphNode i = new GraphNode("I", true, 1);
        GraphNode b = new GraphNode("B", true, 2);

        // A and I both hash to 1 mod 4, and also to 1 mod 8.
        // That means when resize happens, placeEntry() must probe
        // while reinserting the old entries.
        Hash.InsertResult r1 = hash.insert("A", a);
        Hash.InsertResult r2 = hash.insert("I", i);

        assertTrue(r1.inserted);
        assertFalse(r1.resized);
        assertTrue(r2.inserted);
        assertFalse(r2.resized);
        assertEquals(2, hash.size());
        assertEquals(4, hash.capacity());

        // Third insert triggers resize from 4 to 8.
        Hash.InsertResult r3 = hash.insert("B", b);
        assertTrue(r3.inserted);
        assertTrue(r3.resized);
        assertEquals(8, hash.capacity());
        assertEquals(3, hash.size());

        // Both old entries must still be present after rehash collision handling.
        assertSame(a, (GraphNode)hash.find("A"));
        assertSame(i, (GraphNode)hash.find("I"));
        assertSame(b, (GraphNode)hash.find("B"));
    }

    /**
     * Test tombstone search across multiple probes after a resize.
     */
    public void testFindPastTombstoneAfterResize() {
        Hash hash = new Hash("artist", 4);

        GraphNode a = new GraphNode("A", true, 0);
        GraphNode i = new GraphNode("I", true, 1);
        GraphNode q = new GraphNode("Q", true, 2);

        hash.insert("A", a);
        hash.insert("I", i);

        // Trigger resize to 8, keeping a collision cluster alive.
        Hash.InsertResult resizeInsert = hash.insert("Q", q);
        assertTrue(resizeInsert.resized);
        assertEquals(8, hash.capacity());

        // Remove the first key in that cluster.
        GraphNode removed = (GraphNode)hash.remove("A");
        assertSame(a, removed);
        assertNull(hash.find("A"));

        // Search must continue past the tombstone and still find the others.
        assertSame(i, (GraphNode)hash.find("I"));
        assertSame(q, (GraphNode)hash.find("Q"));

        assertEquals(2, hash.size());
    }

    /**
     * Tests that insertion reuses the first tombstone in the probe path,
     * not a later tombstone.
     */
    public void testInsertUsesFirstTombstone() {
        Hash hash = new Hash("artist", 7);

        hash.insert("a", "A");
        hash.insert("h", "H");
        hash.insert("o", "O");

        assertEquals("A", hash.remove("a"));
        assertEquals("H", hash.remove("h"));

        hash.insert("v", "V");

        String output = hash.print();

        assertTrue(output.contains("6: |v|"));
        assertTrue(output.contains("0: TOMBSTONE"));
        assertEquals("V", hash.find("v"));
        assertNull(hash.find("a"));
        assertNull(hash.find("h"));
    }


    /**
     * Tests that quadratic probing uses home + i * i.
     */
    public void testQuadraticProbeUsesSquareStep() {
        Hash hash = new Hash("artist", 7);

        hash.insert("a", "A");
        hash.insert("h", "H");
        hash.insert("o", "O");

        String output = hash.print();

        assertTrue(output.contains("6: |a|"));
        assertTrue(output.contains("0: |h|"));
        assertTrue(output.contains("3: |o|"));
    }


    /**
     * Tests that resize keeps active entries but does not bring back tombstones.
     */
    public void testResizeDoesNotReinsertTombstones() {
        Hash hash = new Hash("artist", 4);

        hash.insert("a", "A");
        hash.insert("b", "B");

        assertEquals("A", hash.remove("a"));

        hash.insert("c", "C");
        hash.insert("d", "D");

        assertEquals(8, hash.capacity());
        assertEquals(3, hash.size());

        assertNull(hash.find("a"));
        assertEquals("B", hash.find("b"));
        assertEquals("C", hash.find("c"));
        assertEquals("D", hash.find("d"));

        String output = hash.print();
        assertFalse(output.contains("|a|"));
    }


    /**
     * Tests the sfold hash math directly.
     */
    public void testHashSfoldMath() {
        Hash hash = new Hash("artist", 10);

        assertEquals(62, hash.h("abc", 101));
        assertEquals(57, hash.h("abcd", 101));
        assertEquals(57, hash.h("abcde", 101));
    }
   
    /**
     * Tests the case where quadratic probing cycles through only active slots.
     * For capacity 8, keys A, I, Q, and Y all have home slot 1.
     * The probe sequence from slot 1 only reaches 1, 2, and 5, so after
     * A, I, and Q are inserted, Y cannot find a null slot in that probe cycle.
     * This targets the final firstTomb check in insert().
     */
    public void testInsertFailsWhenProbeCycleHasNoTombstone() {
        Hash hash = new Hash("artist", 8);

        assertTrue(hash.insert("A", "A").inserted);
        assertTrue(hash.insert("I", "I").inserted);
        assertTrue(hash.insert("Q", "Q").inserted);

        assertEquals(3, hash.size());
        assertEquals("A", hash.find("A"));
        assertEquals("I", hash.find("I"));
        assertEquals("Q", hash.find("Q"));

        Hash.InsertResult result = hash.insert("Y", "Y");

        assertFalse(result.inserted);
        assertFalse(result.duplicate);
        assertFalse(result.resized);
        assertEquals(3, hash.size());
        assertNull(hash.find("Y"));
    }
    
    /**
     * Tests that several old entries are reinserted during resize.
     * This targets the loop in placeEntry(). If the loop condition is mutated
     * to false, the old records are lost during resize.
     */
    public void testResizePreservesSeveralOldEntries() {
        Hash hash = new Hash("artist", 4);

        GraphNode a = new GraphNode("A", true, 0);
        GraphNode b = new GraphNode("B", true, 1);
        GraphNode c = new GraphNode("C", true, 2);

        assertTrue(hash.insert("A", a).inserted);
        assertTrue(hash.insert("B", b).inserted);

        assertEquals(2, hash.size());
        assertEquals(4, hash.capacity());

        // Third insert triggers resize because count is already half full.
        Hash.InsertResult result = hash.insert("C", c);

        assertTrue(result.resized);
        assertTrue(result.inserted);
        assertEquals(8, hash.capacity());
        assertEquals(3, hash.size());

        // These two assertions are the important mutation killers.
        assertSame(a, hash.find("A"));
        assertSame(b, hash.find("B"));
        assertSame(c, hash.find("C"));

        assertFuzzyEquals(
            "1: |A|\r\n"
                + "2: |B|\r\n"
                + "3: |C|\r\n"
                + "total artists: 3\r\n",
            hash.print());
    }
}