import java.util.HashSet;



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


/**
 * Cuckoo hash table implementation of hash tables.
 * @author Mark Allen Weiss
 */
public class CuckooHashTableClassic<AnyType>
{
    /**
     * Construct the hash table.
     */
    public CuckooHashTableClassic( HashFamily<? super AnyType> hf )
    {
        this( hf, DEFAULT_TABLE_SIZE );
    }

    /**
     * Construct the hash table.
     * @param size the approximate initial size.
     */
    public CuckooHashTableClassic( HashFamily<? super AnyType> hf, int size )
    {
        hashFunctions = hf;
        numHashFunctions = hf.getNumberOfFunctions( );
        subTableSize = nextPrime( size / numHashFunctions );
        subTableStarts = new int[ numHashFunctions ];
        for( int i = 0; i < numHashFunctions; i++ )
            subTableStarts[ i ] = i * subTableSize;
        
        allocateArray( subTableSize * numHashFunctions );
        doClear( );
    }

    
    private static final double MAX_LOAD = 0.49;
    private static final int ALLOWED_REHASHES = 100;
    
    private int rehashes = 0;
    
    /**
     * Insert into the hash table. If the item is
     * already present, return false.
     * @param x the item to insert.
     */
    public boolean insert( AnyType x )
    {         
        final int COUNT_LIMIT = 100;
        
        if( contains( x ) )
            return false;
        
        if( currentSize >= array.length * MAX_LOAD )
            expand( );

        for( int i = 0, which = 0; i < COUNT_LIMIT; i++, which++ )
        {
            if( which == numHashFunctions )
                which = 0;
            
            int pos = myhash( x, which );

            if( array[ pos ] == null )
            {
                array[ pos ] = x;
                currentSize++;
                return true;
            }

            AnyType tmp = array[ pos ];
            array[ pos ] = x;
            x = tmp;
        }
            
        if( rehashes++ >= ALLOWED_REHASHES )
        {
            expand( );
            rehashes = 0;
        }
        else
            rehash( );
        
        return insert( x );
    }

    protected int myhash( AnyType x, int which )
    {
        int hashVal = hashFunctions.hash( x, which );
        
        hashVal %= subTableSize;
        if( hashVal < 0 )
            hashVal += subTableSize;
        
        return hashVal + subTableStarts[ which ];
    }
    
    private void expand( )
    {
        rehash( numHashFunctions * nextPrime( (int) ( array.length / MAX_LOAD  / numHashFunctions ) ) );
    }
    
    private void rehash( )
    {
        //System.out.println( "NEW HASH FUNCTIONS " + array.length );
        hashFunctions.generateNewFunctions( );
        rehash( array.length );
    }
    
    private void rehash( int newLength )
    {
     //   System.out.println( "REHASH: " + array.length + " " + newLength + " " + currentSize );
        
        AnyType [ ] oldArray = array;    // Create a new double-sized, empty table
        
        if( newLength != array.length )
        {
            subTableSize = newLength / numHashFunctions;
            for( int i = 0; i < numHashFunctions; i++ )
                subTableStarts[ i ] = i * subTableSize;
        }
            
        allocateArray( newLength );
        
        currentSize = 0;
        
            // Copy table over
        for( AnyType str : oldArray )
            if( str != null )
                insert( str );
    }
    
    /**
     * Gets the size of the table.
     * @return number of items in the hash table.
     */
    public int size( )
    {
        return currentSize;
    }
    
    /**
     * Gets the length (potential capacity) of the table.
     * @return length of the internal array in the hash table.
     */
    public int capacity( )
    {
        return array.length;
    }
    
    /**
     * Method that searches two places.
     * @param x the item to search for.
     * @return the position where the search terminates, or -1 if not found.
     */
    private int findPos( AnyType x )
    {
        for( int i = 0; i < numHashFunctions; i++ )
        {
            int pos = myhash( x, i );
            if( array[ pos ] != null && array[ pos ].equals( x ) )
                return pos;
        }
        
        return -1;
    }

    /**
     * Remove from the hash table.
     * @param x the item to remove.
     * @return true if item was found and removed
     */
    public boolean remove( AnyType x )
    {
        int pos = findPos( x );
        
        if( pos != -1 )
        {
            array[ pos ] = null;
            currentSize--;
        }
        
        return pos != -1;
    }

    /**
     * Find an item in the hash table.
     * @param x the item to search for.
     * @return the matching item.
     */
    public boolean contains( AnyType x )
    {
        return findPos( x ) != -1;
    }
    
    /**
     * Make the hash table logically empty.
     */
    public void makeEmpty( )
    {
        doClear( );
    }

    private void doClear( )
    {
        currentSize = 0;
        for( int i = 0; i < array.length; i++ )
            array[ i ] = null;
    }
    

    
    private static final int DEFAULT_TABLE_SIZE = 101;

    private final HashFamily<? super AnyType> hashFunctions;
    private final int numHashFunctions;
    private AnyType [ ] array; // The array of elements
    private int currentSize; 
    private int subTableSize;
    private int [ ] subTableStarts;

    /**
     * Internal method to allocate array.
     * @param arraySize the size of the array.
     */
    private void allocateArray( int arraySize )
    {
        array = (AnyType[]) new Object[ arraySize ];
    }

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


    // Simple main
    public static void main( String [ ] args )
    {
        CuckooHashTableClassic<String> H = new CuckooHashTableClassic<>( new StringHashFamily( 2 ) );

        java.util.Random r = new java.util.Random( );
        HashSet<String> t = new HashSet<>( );
         
        System.out.println( "Checking... (no more output means success)" );


        long startTime = System.currentTimeMillis( );
        
        final int NUMS = 2000000;
        final int GAP  =   37;
        
        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            H.insert( ""+i );
        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            if( H.insert( ""+i ) )
                System.out.println( "OOPS!!! " + i );
        for( int i = 1; i < NUMS; i+= 2 )
            H.remove( ""+i );

        for( int i = 2; i < NUMS; i+=2 )
            if( !H.contains( ""+i ) )
                System.out.println( "Find fails " + i );

        for( int i = 1; i < NUMS; i+=2 )
        {
            if( H.contains( ""+i ) )
                System.out.println( "OOPS!!! " +  i  );
        }

             
        long endTime = System.currentTimeMillis( );
        
        System.out.println( "Elapsed time: " + (endTime - startTime) );
        
        System.out.println( "H size is: " + H.size( ) );
        System.out.println( "Array size is: " + H.capacity( ) );
       
          
        
        /*
        Scanner scan = null;
        Set<String> words = new HashSet<>( );
        
        try
        {
             scan = new Scanner( new FileReader( "dict.txt" ) );
             String oneLine = null;
             while( scan.hasNextLine( ) )
             {
                 words.add( oneLine = scan.nextLine( ) );
                 H.insert( oneLine );
             }
             
             if( words.size( ) != H.size( ) )
                 System.out.println( "OOPS!!! SIZE MISMATCH " +
                         words.size( ) + " " + H.size( ) );
             
             for( String s : words )
                 if( !H.contains( s ) )
                     System.out.println( "OOPS!! COULDN'T FIND " + s );
             
             System.out.println( "H size is: " + H.size( ) );
             System.out.println( "Array size is: " + H.capacity( ) );
        }
        catch( IOException e )
        {
        }
        finally
        {
            if( scan != null )
                scan.close( );
        }
        */
    }

}
