import java.util.AbstractSet;
import java.util.Iterator;

public class ClosedHashTable extends AbstractSet {
	private final int DEFAULT_CAPACITY = 13;
	private final UsedBucket USED = new UsedBucket(); 
	private int capacity;
	private Object[] buckets;
	private int size;
	
	public ClosedHashTable() {
		capacity = DEFAULT_CAPACITY;
		buckets = new Object[capacity];
		size = 0;
	}
	
	public boolean add(Object x) {
		if( 2*size >= capacity ) rehash();
		int hashAddress = Math.abs(x.hashCode()) % capacity;
		int i = hashAddress;
		int save = -1;
		int j = 1;
		while( buckets[i] != null && !buckets[i].equals(x) ) {
			if( save == -1 && buckets[i].equals(USED) ) save = i;
			// quadratic resolution of collisions
			i = (i + 2*j -1) % capacity;
			j++;
		} // end while
		if( buckets[i] != null ) return false;
		size++;
		if( save == -1 ) {
			buckets[i] = x;
		} else {
			buckets[save] = x;
		} // end if
		return true;
	} // end add
	
	public boolean contains(Object x) {
		int hashAddress = Math.abs(x.hashCode())%capacity;
		int i = hashAddress;
		int j = 1;
		while( buckets[i] != null && !buckets[i].equals(x) ) {
			// quadratic resolution of collisions
			i = (i + 2*j - 1) % capacity;
			j++;
		} // end while
		return buckets[i] != null;
	} // end contains
		
	public boolean remove(Object x) {
		int hashAddress = Math.abs(x.hashCode())%capacity;
		int i = hashAddress;
		int j = 1;
		while( buckets[i] != null && !buckets[i].equals(x) ) {
			// quadratic resolution of collisions
			i = (i + 2*j -1) % capacity;
			j++;
		} // end while
		if( buckets[i] == null ) return false;
		size--;
		buckets[i] = USED;
		return true;
	} // end remove
	
/*	
	//The following uses linear resolution of collisions

	public boolean add(Object x) {
		if( 2*size >= capacity ) rehash();
		int hashAddress = Math.abs(x.hashCode()) % capacity;
		int i = hashAddress;
		int save = -1;
		while( buckets[i] != null && !buckets[i].equals(x) ) {
			if( save == -1 && buckets[i].equals(USED) ) save = i;
			// linear resolution of collisions
			i = (i + 1) % capacity;
		} // end while
		if( buckets[i] != null ) return false;
		size++;
		if( save == -1 ) {
			buckets[i] = x;
		} else {
			buckets[save] = x;
		} // end if
		return true;
	} // end add

	public boolean contains(Object x) {
		int hashAddress = Math.abs(x.hashCode())%capacity;
		int i = hashAddress;
		while( buckets[i] != null && !buckets[i].equals(x) ) {
			// linear resolution of collisions
			i = (i + 1) % capacity;
		} // end while
		return buckets[i] != null;
	} // end contains

	public boolean remove(Object x) {
		int hashAddress = Math.abs(x.hashCode())%capacity;
		int i = hashAddress;
		while( buckets[i] != null && !buckets[i].equals(x) ) {
			// linear resolution of collisions
			i = (i + 1) % capacity;
		} // end while
		if( buckets[i] == null ) return false;
		size--;
		buckets[i] = USED;
		return true;
	} // end remove
	
*/	
	public int size() {
		return size;
	}
	
	public Iterator iterator() {
		return new HashIterator(this);
	}
	
	public String toString() {
		String out = "";
		for( int i = 0; i < capacity; i++ ) {
			if( buckets[i] != null && !buckets[i].equals(USED) ) {
				out += buckets[i] + " ";
			} // end if
		} // end for
		return out + "\n";
	} // end toString
	
	public Object[] toArray() {
		Object[] A = new Object[this.size];
		int k = 0;
		for( int i = 0; i < capacity; i++ ) {
			if( buckets[i] != null && !buckets[i].equals(USED) ) {
				A[k] = buckets[i];
				k++;
			} // end if
		} // end for
		return A;
	}
	
	public String buckets() {
		String out = "";
		for( int i = 0; i < capacity; i++ ) {
			if( buckets[i] != null && !buckets[i].equals(USED) ) {
				out += "Bucket #" + i + " is OCCUPIED.\n";
			} else {
				out += "Bucket #" + i + " is unoccupied.\n";
			}// end if
		} // end for
		return out + "\n";
	}

				
	private void rehash() {
		Object[] save = buckets;
		int oldCapacity = capacity;
		capacity = nextPrime(capacity * 2);
		buckets = new Object[capacity];
		size = 0;
		for( int i = 0; i < oldCapacity; i++ ) {
			if( save[i] != null && !save[i].equals(USED) ) {
				Object x = save[i];
				add(x);
			} // end if
		} // end for
	} // end rehash
	
	private class UsedBucket {}
	
	/**
	  * Internal method to return a prime number at least as large as n.
	  */
	private final int nextPrime(int n) {
		if( n % 2 == 0 ) n++;
		while( !isPrime(n) ) n += 2;
		return n;
	}
	
	private boolean isPrime(long n) {
		for( long i = 3; i*i <=n ; i += 2 ) {
			if( n % i == 0 ) return false;
		} // end for
		return true;
	}
	
	private class HashIterator implements Iterator {
		ClosedHashTable theHashTable;
		Object[] theElements;
		int next;
		
		HashIterator(ClosedHashTable H) {
			theHashTable = H;
			theElements = H.toArray();
			next = -1;
		}
		
		public boolean hasNext() {
			return next < theElements.length-1;
		}
		
		public Object next() {
			return theElements[++next];
		}
		
		public void remove() {
			throw new UnsupportedOperationException();
		};
		
	} // end HashIterator

		
} // end ClosedHashTable