import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;

public class OpenHashTable<T> extends AbstractSet<T> {
    private ArrayList<LinkedList<T>> buckets;
    private int size;
    
    public OpenHashTable(int capacity) {
        buckets = new ArrayList<LinkedList<T>>(capacity);
        for( int i = 0; i < capacity; i++ ) {
            buckets.add(new LinkedList<T>());
        }// end for
        size = 0;
    }// end constructor 
    
    public OpenHashTable() {
        this(13);
    }// end constructor
    
    public boolean add(T x) {
        if( this.contains(x) ) {
            return false;
        } else {
            if( size >= buckets.size() ) rehash();
            int hashAddress = Math.abs(x.hashCode())%buckets.size();
            size++;
            return buckets.get(hashAddress).add(x);
        } // end if
    } // end add 
    
    public boolean contains(Object x) {
        int hashAddress = Math.abs(x.hashCode())%buckets.size();
        return buckets.get(hashAddress).contains(x);
    } // end contains 
    
    public boolean remove(Object x) {
        int hashAddress = Math.abs(x.hashCode())%buckets.size();
        if( !this.contains(x) ) {
            return false;
        } else {
            size--;
            return buckets.get(hashAddress).remove(x);
        } // end if
    } // end remove
    
    public int size() {
        return size;
    }// end size
    
    public Iterator<T> iterator() {
        return new HashIterator(buckets);
    }// end iterator 
    
    public String toString() {
        String out = "";
        for( LinkedList<T> list : buckets ) {
            for( T x : list ) out += x + " ";
        } // end for
        return out + "\n";
    } // end toString 
    
    public Object[] toArray() {
        Object[] array = new Object[this.size];
        int k = 0;
        for( LinkedList<T> list : buckets ) {
            for( T x : list ) {
                array[k] = x;
                k++;
            } // end for
        } // end for
        return array;
    }// end toArray
    
    public String numberInEachBucket() {
        String out = "";
        int i = 0;
        for( LinkedList<T> list : buckets ) {
            int num = list.size();
            out += "    Bucket #"+ i +" has " + num + (num==0?" element":" ELEMENT") + (num==1?"":"s")+".\n";
            i++;
        } // end for
        return out;
    }// end umberInEachBucket 
    
    private void rehash() {
        ArrayList<LinkedList<T>> save = buckets;
        int oldCapacity = buckets.size();
        int newCapacity = oldCapacity * 2 + 1;
        buckets = new ArrayList<LinkedList<T>>(newCapacity);
        for( int i = 0; i < newCapacity; i++ ) {
            buckets.add(new LinkedList<T>());
        } // end for
        size = 0;
        for( LinkedList<T> list : save ) {
            for( T x : list ) add(x);
        } // end for
    } // end rehash
    
    private class HashIterator implements Iterator<T> {
        private ArrayList<LinkedList<T>> buckets;
        ArrayList<T> theElements;
        int next; 
        
        HashIterator(ArrayList<LinkedList<T>> buckets) {
            this.buckets = buckets;
            theElements = new ArrayList<T>();
            for( List<T> list : buckets ) {
                for( T x : list ) theElements.add(x);
            }// end for
            next = -1;
        }// end constructor 
        
        public boolean hasNext() {
            return next < theElements.size()-1;
        }// end hasNext 
        
        
        public T next() {
            return theElements.get(++next);
        }// end next        
        public void remove() {
            throw new UnsupportedOperationException();
        }// end remove 
        
    } // end HashIterator
}// end OpenHashTable