import java.util.*;

/**
 * An instance is a set that is implemented using a hash table 
 * with quadratic probing. Null elements are not allowed in the set
 * Matches are based on equals; and method hashCode must be consistently defined.
 */
public class HashSet {
    private static final int DEFAULT_TABLE_SIZE = 101;
    
    private int numberOfRehashes= 0;  // The number of rehashes performed on this instance
    private HashEntry[] b;        // The array in which the hashed elements are placed.
                                  // elements may be null
    private int size= 0;          // The number of entries in the hashtable
    private int occupied= 0;      // The number of array elements that are occupied
                                  // (some array elements are removed from the hashtable
                                  // but remain in the array)

    /**  Constructor: an empty HashSet. */
    public HashSet( ) {
        b= new HashEntry[ DEFAULT_TABLE_SIZE];
        clear( );
    }
        
    /** = the number of items in this collection.
     */
    public int size( ) {
        return size;
    }
    
    /** = the number of rehashes performed on this instance so far */
    public int getRehashes() {
        return numberOfRehashes;
    }
    
    /**  = "x is in the collection". x may not be null. */
    public boolean contains(Object x) {
        return isInSet(b, quadraticProbe(x));
    }
    
    /** = "item in arr[pos] is in the set --it is not null and its isInSet bit is true."
     */
    private static boolean isInSet(HashEntry[] arr, int pos) {
        return arr[pos] != null  &&  arr[pos].isInSet;
    }
    
    /** Add item x to this collection and 
     * return "it was added because it was not yet in"
     * x may not be null.
     */
    public boolean add(Object x) {
        int pos= quadraticProbe(x);
        if(isInSet(b, pos))
            return false;
        
        b[pos]= new HashEntry(x, true);
        size++;
        occupied++;
        
        if(occupied > b.length/2)        
            rehash();
                
        return true;                   
    }
    
    /** Rehash array b */
    private void rehash( ) {
        HashEntry[] oldb= b;  // copy of array
        
        // Create a new, empty array
            b= new HashEntry[nextPrime(4*size())];
            size= 0;
            occupied= 0;
        
        // Copy active elements from oldb to b
            for (int i= 0; i != oldb.length; i= i+1)
                if(isInSet(oldb, i)) 
                    add(oldb[i].element);
        
        numberOfRehashes++;
    }
    
    /** Remove item x from this collection and return the value of
     * "item was removed because it was in the set". x may not be null.
     */
    public boolean remove(Object x) {
        int pos= quadraticProbe(x);
        if(!isInSet(b, pos))
            return false;
        
        b[pos].isInSet= false;
        size--;   
        
        if(size < b.length / 8)
            rehash();
    
        return true;
    }
    
    /** Change the size of this set to zero. */
    public void clear() {
       size= 0;
       occupied= 0;
       for (int i= 0; i != b.length; i= i+1 )
            b[i]= null;
    }
    
    /** = an Iterator for enumerating the collection. */
    public Enumeration enumeration( ) {
        return new HashSetEnumeration();
    }
    
    /** An instance is an Enumeration of this HashSet */
    private class HashSetEnumeration implements Enumeration {
        private int pos= -1;      // all elements in b[0..pos] have been enumerated 
        private int visited= 0;   // number of elements that have been enumerated

        // = "there is another element to enumerate"
        public boolean hasMoreElements() {            
            return visited != size();    
        }
        
        // = the next element to enumerate
        public Object nextElement() {
            if(!hasMoreElements())
                throw new NoSuchElementException( );
            
            pos++;     
            while (pos != b.length && !isInSet(b, pos)) {
                pos++;
            } 
            
            visited= visited+1;      
            return b[pos].element;    
        }
    }
    
    // An instance is an entry that can go in the hash table
    private static class HashEntry {
        public Object  element;   // the element
        public boolean isInSet;  // = "the element has not been deleted"

        // Constructor: an entry that is in the set
        public HashEntry(Object e){
            this(e, true);
        }

        // Constructor: an entry that is in the set iff b
        public HashEntry(Object e, boolean b) {
            element=  e;
            isInSet= b;
        }
    }
    
    /** = the index in array b of x or where x will be put (using quadratic probing).
     *    (see recitation handout). x may not be null.
     */
    private int quadraticProbe(Object x) {
        // Remember: the probes positions H1, H2, ... are defined by H(i)  =  H(i-1) +2i -1.
        int i= 0;
        int k= Math.abs(x.hashCode() % b.length);
        // inv: k = Hi, and x is not one of b[H0], ..., b[Hi-1]
        while(b[k] != null  &&  !x.equals(b[k].element)) {           
            i= i+1;
            k= k + 2*i - 1;     // Store H(i+1) --the next probe position-- in k
            if(k >= b.length)   // Wrap around if necessary
                k= k - b.length;
        }

        return k;
    }

    /** = a prime number at least as large as n, for n > 1 */
    private static int nextPrime( int n ) {
        // Ensure that n is odd
            if (n%2 == 0)
                n++;

        while (!isPrime(n))
            { n= n+2; }

        return n;
    }

    /** = "n is prime" */
    private static boolean isPrime(int n) {
        if (n <= 1)
            return false;
        if (n == 2 || n == 3)
            return true;    
        if (n%2 == 0)
            return false;
        for (int i= 3; i*i <= n; i= i+2)
            if( n%i == 0 )
                return false;
        return true;
    }
    
}