/*
 * Kyle Smith
 * 04/06/09
 * Computer Science II
 * 22C:021
 * Homework 6
 * 
 */

import java.util.LinkedList;
import java.util.List;
import java.util.*;

// SeparateChaining Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// boolean contains( x )  --> Return true if x is present
// void makeEmpty( )      --> Remove all items

/**
 * Separate chaining table implementation of hash tables.
 * Note that all "matching" is based on the equals method.
 * @author Mark Allen Weiss
 * EDITED BY KYLE ALAN SMITH ON April 6, 2009
 */
public class SeparateChainingHashTable<AnyType>
{
    /**
     * Construct the hash table.
     */
    public SeparateChainingHashTable( )
    {
        this( DEFAULT_TABLE_SIZE );
    }

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

    /**
     * Insert into the hash table. If the item is
     * already present, then do nothing.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
        List<AnyType> whichList = theLists[ myhash( x ) ];
        if( !whichList.contains( x ) )
		{
	        whichList.add( x );

	            // Rehash; see Section 5.5
	        if( ++currentSize > theLists.length )
	            rehash( );
		}
    }

    /**
     * Remove from the hash table.
     * @param x the item to remove.
     */
    public void remove( AnyType x )
    {
        List<AnyType> whichList = theLists[ myhash( x ) ];
        if( whichList.contains( x ) )
		{
	        whichList.remove( x );
			currentSize--;
		}
    }

    /**
     * Find an item in the hash table.
     * @param x the item to search for.
     * @return true if x is not found.
     */
    public boolean contains( AnyType x )
    {
        List<AnyType> whichList = theLists[ myhash( x ) ];
        return whichList.contains( x );
    }

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

    /**
     * A hash routine for String objects.
     * @param key the String to hash.
     * @param tableSize the size of the hash table.
     * @return the hash value.
     */
    public static int hash( String key, int tableSize )
    {
        int hashVal = 0;

        for( int i = 0; i < key.length( ); i++ )
            hashVal = 37 * hashVal + key.charAt( i );

        hashVal %= tableSize;
        if( hashVal < 0 )
            hashVal += tableSize;

        return hashVal;
    }

    private void rehash( )
    {
        List<AnyType> [ ]  oldLists = theLists;

            // Create new double-sized, empty table
        theLists = new List[ nextPrime( 2 * theLists.length ) ];
        for( int j = 0; j < theLists.length; j++ )
            theLists[ j ] = new LinkedList<AnyType>( );

            // Copy table over
        currentSize = 0;
        for( int i = 0; i < oldLists.length; i++ )
            for( AnyType item : oldLists[ i ] )
                insert( item );
    }

    private int myhash( AnyType x )
    {
        int hashVal = x.hashCode( );

        hashVal %= theLists.length;
        if( hashVal < 0 )
            hashVal += theLists.length;

        return hashVal;
    }
	
    private static final int DEFAULT_TABLE_SIZE = 101;

        /** The array of Lists. */
    private List<AnyType> [ ] theLists; 
	private int currentSize;

    /**
     * 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++;

        for( ; !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;
    }
    
    // code for implementation of BinaryHeap delete method - finds a given element in the
    // hash table and returns that element's location value (an integer)
    public int getHeapLocation(AnyType x){
    	if(this.contains(x)){  // only procedes if the element exists
	    	List<AnyType> whichList = theLists[myhash(x)];  // finds linkedlist that contains the element x
	    	if(x instanceof Foo){  // checks to ensure the stored element is a Foo
	    		if(whichList.contains(x)){  // makes sure the element x is in this linkedlist 
	    			ListIterator<AnyType> itr = whichList.listIterator();  // iterator for going through this linked list
	    			while(itr.hasNext()){  // only procedes until the last element of the list
	    				Foo temp = (Foo)itr.next();  // the next item in the list
	    				if(x.equals(temp)){
	    					return temp.location;  // returns location of the heap element
	    				}
	    			}
	    		}
	    	}
    	}
    	return 0;  // x not in 'this' hash table
    }

}