// SeparateChainingHashTable class
//
// CONSTRUCTION: with an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// boolean contains( x )  --> Return item that matches x
// void clear( )          --> Remove all items
// ******************ERRORS********************************
// insert overrides previous value if duplicate; not an error

/**
 * Separate chaining table implementation of hash tables.
 * Note that all "matching" is based on the equals method.
 * @author Mark Allen Weiss
 * @author Dominik Gruntz [changes]
 */
import java.util.LinkedList;

public class SeparateChainingHashTable {
    private static final int DEFAULT_TABLE_SIZE = 101;

    /** The array of Lists. */
    private LinkedList[] list; 

    /**
     * Construct the hash table.
     */
    public SeparateChainingHashTable( ) {
        this( DEFAULT_TABLE_SIZE );
    }

    /**
     * Construct the hash table.
     * @param size approximate table size.
     */
    public SeparateChainingHashTable( int size ) {
        list = new LinkedList[ nextPrime( size ) ];
        for( int i = 0; i < list.length; i++ )
            list[ i ] = new LinkedList( );
    }

    /**
     * Insert into the hash table. If the item is
     * already present, then do nothing.
     * @param x the item to insert.
     */
    public void insert( Object x ) {
        LinkedList whichList = list[ hash( x ) ];
        if(!whichList.contains(x)) whichList.add(0, x);
    }


    /**
     * Remove from the hash table.
     * @param x the item to remove.
     */
    public void remove( Object x ) {
       list[ hash( x ) ].remove( x );
    }

    /**
     * Find an item in the hash table.
     * @param x the item to search for.
     * @return true if found, false otherwise.
     */
    public boolean contains( Object x ) {
        return list[ hash( x )].contains(x);
    }

    /**
     * Make the hash table logically empty.
     */
    public void clear( ) {
        for( int i = 0; i < list.length; i++ ) list[ i ].clear( );
    }

    /**
     * Internal method to compute the hash index.
     * @param x the Objecct to hash.
     * @return the hash value in the range [0, list.length )
     */
    private int hash( Object x ) {
        int hashVal;
        hashVal = x.hashCode() % list.length;
        if( hashVal < 0 )
            hashVal += list.length;

        return hashVal;
    }

    /** 
     * Internal method to find a prime number at least as large as n.
     * @param n the starting number (must be positive).
     * @return a prime number larger than or equal to n.
     */
    private static int nextPrime( int n ) {
        if( n % 2 == 0 ) n++;
        while(!isPrime(n)) n += 2;
        return n;
    }




    /**
     * Internal method to test if a number is prime.
     * Not an efficient algorithm.
     * @param n the number to test.
     * @return the result of the test.
     */
    private static boolean isPrime( int n ) {
        if( n == 2 || n == 3 )
            return true;

        if( n == 1 || n % 2 == 0 )
            return false;

        for( int i = 3; i * i <= n; i += 2 )
            if( n % i == 0 )
                return false;

        return true;
    }
}