package weiss.util;

import java.io.Serializable;

/**
 * HashSet implementation.
 * Matches are based on equals; and hashCode must be consistently defined.
 */
public class HashSet<AnyType> extends AbstractCollection<AnyType> implements Set<AnyType>
{
    /**
     * Construct an empty HashSet.
     */
    public HashSet( )
    {
        allocateArray( DEFAULT_TABLE_SIZE );
        clear( );
    }
    
    /**
     * Construct a HashSet from any collection.
     */
    public HashSet( Collection<? extends AnyType> other )
    {
        allocateArray( nextPrime( other.size( ) * 2 ) );
        clear( );
        
        for( AnyType val : other )
            add( val );    
    }
    
    /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size( )
    {
        return currentSize;
    }
    
    
    /**
     * 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 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;
       
        if( array[ currentPos ] == null ) 
            occupied++;
        array[ currentPos ] = new HashEntry( x, true );
        currentSize++;
        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 quadratic probing resolution.
     * Assumes table is at least half-empty.
     * @param x the item to search for.
     * @return the position where the search terminates.
     */
    private int findPos( Object x )
    {
        int offset = 1;
        int currentPos = ( x == null ) ? 0 : Math.abs( x.hashCode( ) % array.length );

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

        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_TABLE_SIZE = 101;
    
    private int currentSize = 0;
    private int occupied = 0;
    private int modCount = 0;
    private HashEntry [ ] array;
}