import java.io.Serializable;
import java.util.Iterator;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;

/**
 * HashSet implementation.
 * Matches are based on equals; and hashCode must be consistently defined.
 *
 * @author Mark Allen Weiss
 * @author Jerod Weinman
 * @author YOUR NAME HERE
 */
public class HashSet<AnyType> implements Iterable<AnyType>
{
    /**
     * Construct an empty HashSet with the default capacity, load
     * factor, and probe method.
     */
    public HashSet( )
    {
      this( DEFAULT_CAPACITY );
    }

    /**
     * Constructs an empty HashSet with the specified initial capacity
     * and default load factor and probe method.
     */
    public HashSet( int initialCapacity ) 
    {
      this( initialCapacity, DEFAULT_LOAD_FACTOR );
    }


    /**
     * Constructs an empty HashSet with the specified initial capacity
     * and load factor and default probe method.
     */
    public HashSet( int initialCapacity, float loadFactor ) 
    {
      this( initialCapacity, loadFactor, USE_LINEAR_PROBE_DEFAULT );
    }


    public HashSet( int initialCapacity, float loadFactor, boolean useLinearProbe ) 
    {
      allocateArray( (int)(initialCapacity / loadFactor) );
      clear();
      this.useLinearProbe = useLinearProbe;
    }

    /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size( )
    {
        return currentSize;
    }


    /**
     * Returns the number of probes made since the last reset.
     * @return the number of probes
     */
    public long getNumProbes( )
    {
        return numProbes;
    }
 
    /**
     * Resets the number of probes to zero.
     */
    public void resetNumProbes( )
    {
        numProbes = 0;
    }

    
    /**
     * This method is not part of standard Java.
     * Like contains, it checks if x is in the set.
     * If it is, it returns the reference to the matching
     * object; otherwise it returns null.
     * @param x the object to search for.
     * @return if contains(x) is false, the return value is null;
     * otherwise, the return value is the object that causes
     * contains(x) to return true.
     */
    public AnyType getMatch( AnyType x )
    {
        int currentPos = findPos( x );

        if( isActive( array, currentPos ) )
            return (AnyType) array[ currentPos ].element;
        return null;
    }
    
    /**
     * Tests if some item is in this collection.
     * @param x any object.
     * @return true if this collection contains an item equal to x.
     */
    public boolean contains( Object x )
    {
        return isActive( array, findPos( x ) );
    }
    
    /**
     * Tests if item in pos is active.
     * @param pos a position in the hash table.
     * @param arr the HashEntry array (can be oldArray during rehash).
     * @return true if this position is active.
     */
    private static boolean isActive( HashEntry [ ] arr, int pos )
    {
        return pos>0 && arr[ pos ] != null && arr[ pos ].isActive;
    }
    
    /**
     * Adds an item to this collection.
     * @param x any object.
     * @return true if this item was added to the collection.
     */
    public boolean add( AnyType x )
    {
        int currentPos = findPos( x );
        if( isActive( array, currentPos ) )
            return false;
        
        array[ currentPos ] = new HashEntry( x, true );
        currentSize++;
        occupied++;
        modCount++;
        
         if( occupied > array.length / 2 )        
           rehash( );
                
        return true;                   
    }
    
    /**
     * Private routine to perform rehashing.
     * Can be called by both add and remove.
     */
    private void rehash( )
    {
        HashEntry [ ] oldArray = array;
        
            // Create a new, empty table
        allocateArray( nextPrime( 4 * size( ) ) );
        currentSize = 0;
        occupied = 0;
        
            // Copy table over
        for( int i = 0; i < oldArray.length; i++ )
            if( isActive( oldArray, i ) ) 
                add( (AnyType) oldArray[ i ].element );
    }
    
    /**
     * Removes an item from this collection.
     * @param x any object.
     * @return true if this item was removed from the collection.
     */
    public boolean remove( Object x )
    {
        int currentPos = findPos( x );
        if( !isActive( array, currentPos ) )
            return false;
        
        array[ currentPos ].isActive = false;
        currentSize--;
        modCount++;    
        
        if( currentSize < array.length / 8 )
            rehash( );
    
        return true;
    }
    
    /**
     * Change the size of this collection to zero.
     */
    public void clear( )
    {
        currentSize = occupied = 0;
        modCount++;
        for( int i = 0; i < array.length; i++ )
            array[ i ] = null;
    }
    
    /**
     * Obtains an Iterator object used to traverse the collection.
     * @return an iterator positioned prior to the first element.
     */
    public Iterator<AnyType> iterator( )
    {
        return new HashSetIterator( );
    }
    
    /**
     * This is the implementation of the HashSetIterator.
     * It maintains a notion of a current position and of
     * course the implicit reference to the HashSet.
     */
    private class HashSetIterator implements Iterator<AnyType>
    {
        private int expectedModCount = modCount;
        private int currentPos = -1;
        private int visited = 0;       
        
        public boolean hasNext( )
        {
            if( expectedModCount != modCount )
                throw new ConcurrentModificationException( );
            
            return visited != size( );    
        }
        
        public AnyType next( )
        {
            if( !hasNext( ) )
                throw new NoSuchElementException( );
                          
            do
            {
                currentPos++;
            } while( currentPos < array.length && !isActive( array, currentPos ) );
                            
            visited++;
            return (AnyType) array[ currentPos ].element;    
        }
        
        public void remove( )
        {
            if( expectedModCount != modCount )
                throw new ConcurrentModificationException( );              
            if( currentPos == -1 || !isActive( array, currentPos ) )
                throw new IllegalStateException( );
    
            array[ currentPos ].isActive = false;
            currentSize--;
            visited--;
            modCount++;
            expectedModCount++;
        }
    }
    
    private static class HashEntry implements Serializable
    {
        public Object  element;   // the element
        public boolean isActive;  // false if marked deleted

        public HashEntry( Object e )
        {
            this( e, true );
        }

        public HashEntry( Object e, boolean i )
        {
            element  = e;
            isActive = i;
        }
    }
    
    
    /**
     * Method that performs linear or quadratic probing resolution.
     * @param x the item to search for.
     * @return the position where the search terminates.
     */
    private int findPos( Object x )
    {
        int hashPos = ( x == null ) ? 
          0 : 
          Math.abs( x.hashCode( ) % array.length );

        int offset = 1;
        int currentPos = hashPos;

        // Increment for the probe about to be done in the while test
        numProbes++;

        while( array[ currentPos ] != null )
        {
            if( x == null )
            {
                if( array[ currentPos ].element == null )
                    break;
            }
            else if( x.equals( array[ currentPos ].element ) )   
                break; 
            
            currentPos += offset;                  // Compute ith probe

            offset += 2;

            if( currentPos >= array.length )       // Implement the mod
                currentPos -= array.length;
            
            if (currentPos == hashPos)
              return -1;

            // Increment for the probe about to be done in the while test
            numProbes++;
        }

        return currentPos;
    }
    
    
    /**
     * Internal method to allocate array.
     * @param arraySize the size of the array.
     */
    private void allocateArray( int arraySize )
    {
        array = new HashEntry[ nextPrime( 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;
    }
    
    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private static final boolean USE_LINEAR_PROBE_DEFAULT = false;

    private int currentSize = 0;
    private int occupied = 0;
    private int modCount = 0;
    private HashEntry [ ] array;
    private boolean useLinearProbe = false;
    private long numProbes = 0;
    private long maxNumProbes = 0;

}