Untitled

/**
 * Implement a hash table for SongDB to use. This is the main indexing for
 * SongDB by storing the string records indirectly through handle.java provided
 * by mem man
 *
 * Data: Strings. Hash function: sfold. Collision resolution: quadratic probing.
 *
 * Adapted here for Project 2 so that strings map to graph nodes.
 *
 * @author Leguejou Awunganyi
 * @author Ishita Punna
 * @version 2026-02-08
 */
public class Hash {

    /**
     * Result returned by an insert attempt.
     */
    public static class InsertResult {

        /**
         * True when the table doubled before insertion.
         */
        public boolean resized;

        /**
         * True when the key was already present.
         */
        public boolean duplicate;

        /**
         * True when the key was inserted.
         */
        public boolean inserted;
    }

    /**
     * Helper class representing one slot in the hash table.
     */
    private static class Entry {

        /**
         * Stored key string.
         */
        private String key;

        /**
         * Graph node associated with the key.
         */
        private GraphNode node;

        /**
         * True if this entry has been logically deleted.
         */
        private boolean tombstone;

        /**
         * Create a new Entry with the given key and graph node.
         *
         * @param itemKey  stored key string
         * @param itemNode node associated with the key
         */
        Entry(String itemKey, GraphNode itemNode) {
            key = itemKey;
            node = itemNode;
            tombstone = false;
        }
    }

    /**
     * String for the table name.
     */
    private String name;

    /**
     * Array of table entries.
     */
    private Entry[] table;

    /**
     * Current capacity of the table.
     */
    private int capacity;

    /**
     * Number of active (non-tombstone) records.
     */
    private int count;

    /**
     * Create a new Hash object.
     *
     * @param n     String for the table name
     * @param isize The initial size (and increment size) for the table
     */
    public Hash(String n, int isize) {
        name = n;
        table = new Entry[isize];
        capacity = isize;
        count = 0;
    }

    /**
     * Get the number of active elements in the table.
     *
     * @return current number of live records
     */
    public int size() {
        return count;
    }

    /**
     * Get the current table capacity.
     *
     * @return current capacity
     */
    public int capacity() {
        return capacity;
    }

    /**
     * Get the graph node associated with a string.
     *
     * @param key string to find
     * @return matching graph node, or null if not found
     */
    public GraphNode find(String key) {
        int slot = findSlot(key);
        if (slot < 0) {
            return null;
        }
        return table[slot].node;
    }

    /**
     * Insert a string and its graph node into the table.
     *
     * @param key  string to insert
     * @param node graph node associated with the string
     * @return insertion result information
     */
    public InsertResult insert(String key, GraphNode node) {
        InsertResult result = new InsertResult();
        if (count >= capacity / 2) {
            resize();
            result.resized = true;
        }

        int home = h(key, capacity);
        int firstTomb = -1;

        for (int i = 0; i < capacity; i++) {
            int pos = probe(home, i);
            Entry entry = table[pos];

            if (entry == null) {
                int insertPos = pos;
                if (firstTomb >= 0) {
                    insertPos = firstTomb;
                }

                table[insertPos] = new Entry(key, node);
                count++;
                result.inserted = true;
                return result;
            }

            if (entry.tombstone) {
                if (firstTomb < 0) {
                    firstTomb = pos;
                }
            } 
            
            else if (entry.key.equals(key)) {
                result.duplicate = true;
                return result;
            }
        }

        if (firstTomb >= 0) {
            table[firstTomb] = new Entry(key, node);
            count++;
            result.inserted = true;
        }
        return result;
    }

    /**
     * Remove a string from the table.
     *
     * @param key string to remove
     * @return removed graph node, or null if not found
     */
    public GraphNode remove(String key) {
        int slot = findSlot(key);
        if (slot < 0) {
            return null;
        }
        table[slot].tombstone = true;
        count--;
        return table[slot].node;
    }

    /**
     * Print the hash table contents.
     *
     * @return formatted table string
     */
    public String print() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < capacity; i++) {
            Entry entry = table[i];
            if (entry != null) {
                builder.append(i).append(": ");
                if (entry.tombstone) {
                    builder.append("TOMBSTONE");
                } 
                
                else {
                    builder.append("|").append(entry.key).append("|");
                }
                builder.append("\r\n");
            }
        }
        String totalMsg = "total " + name.toLowerCase() +
            "s: " + count + "\r\n";
        builder.append(totalMsg);
        return builder.toString();
    }

    /**
     * Find the slot containing the given string.
     *
     * @param key string to find
     * @return slot index, or -1 if not found
     */
    private int findSlot(String key) {
        int home = h(key, capacity);
        for (int i = 0; i < capacity; i++) {
            int pos = probe(home, i);
            Entry entry = table[pos];
            if (entry == null) {
                return -1;
            }
            if (!entry.tombstone && entry.key.equals(key)) {
                return pos;
            }
        }
        return -1;
    }

    /**
     * Quadratic probing function.
     *
     * @param home home slot for the key
     * @param i    probe number
     * @return slot index for this probe/formula
     */
    private int probe(int home, int i) {
        return (home + i * i) % capacity;
    }

    /**
     * Resize the hash table to twice its current capacity and reinsert
     * all active entries.
     */
    private void resize() {
        Entry[] oldTable = table;
        table = new Entry[capacity * 2];
        capacity *= 2;
        count = 0;

        for (Entry entry : oldTable) {
            if (entry != null && !entry.tombstone) {
                placeEntry(entry.key, entry.node);
            }
        }
    }

    /**
     * Place an entry into the current table without resizing.
     *
     * @param key  string to place
     * @param node graph node to store
     */
    private void placeEntry(String key, GraphNode node) {
        int home = h(key, capacity);
        for (int i = 0; i < capacity; i++) {
            int pos = probe(home, i);
            if (table[pos] == null) {
                table[pos] = new Entry(key, node);
                count++;
                return;
            }
        }
    }

    /**
     * Compute the hash function. Uses the "sfold" method from the 
     * OpenDSA module on hash functions.
     *
     * @param s The string that we are hashing
     * @param m The size of the hash table
     * @return The home slot for that string
     */
    public int h(String s, int m) {
        long sum = 0;
        long mult = 1;
        for (int i = 0; i < s.length(); i++) {
            mult = (i % 4 == 0) ? 1 : mult * 256;
            sum += s.charAt(i) * mult;
        }
        return (int) (Math.abs(sum) % m);
    }
}