/**
 * A hashtable
 **/
public class ProbingArrayHashTable<Key,Value> implements MyHashTable<Key, Value> {
	final static double MAXLOADFACTOR = 0.5;
	private int elements = 0, size, previous;
	private Node<Key,Value>[] entries;

	/** constructor, size specified */
	@SuppressWarnings("unchecked")  /* necessary for generic array creation. */
	public ProbingArrayHashTable(int size) {
		this.size = size;
		previous = size;
		entries = (Node<Key,Value>[]) new Node[size];
	}

	/** default constructor */
	public ProbingArrayHashTable() {
		this(11);
	}

	/**
	 * return the index for `key' by linear probing
	 */
	private int findslot(Key key) {
		int a = Math.abs(key.hashCode()) % size;
		int begin = a;

		/* feeling lucky */
		if (entries[a] == null || entries[a].key.equals(key))
			return a;

		/* look further */
		do
			a = (a + 1) % size;
		while (entries[a] != null && !entries[a].key.equals(key) && a != begin);

		/* if we are back were we started, 
		 * then something is wrong */
		if (a == begin)
			return -1;
		/* we either found an empty slot, or the location of 'key' */ 
		else
			return a;
	}
	/**
	 * check whether the hashtable contains a specific key
	 */
	public boolean has(Key key) {
		int a = findslot(key);
		return (a != -1 && entries[a].key != null);
	}

	/**
	 *  get the object associated with a specific key
	 * @throws java.util.NoSuchElementException
	 * 	if the specified key is not in the hashtable
	 */ 
	public Value get(Key key) {
		int a = findslot(key);
		if (a == -1)
			throw new java.util.NoSuchElementException("-1");
		else if (entries[a] == null)
			throw new java.util.NoSuchElementException(key + "/" + elements + "[" + a + "/" + entries.length + "] -> ");
		else
			return entries[a].value;
	}

	/**
	 *  remove the object associated with a specific key
	 * @throws java.util.NoSuchElementException
	 * 	if the specified key is not in the hashtable
	 */ 
	public Value remove(Key key) {
		int a = findslot(key);
		if (a == -1) 
			throw new java.util.NoSuchElementException(key + " " + a + " ");
		if (entries[a] == null)
			return null;
		//throw new java.util.NoSuchElementException(key + "/" + elements + "[" + a + "/" + entries.length + "] -> ");
		int b = a, c;
		Value v = entries[a].value;

		/* now make sure that all entries with the same hash
		 * are clustered together */
		while (true) {
			b = (b + 1) % size;
			if (entries[b] == null)
				break;
			c = Math.abs(entries[b].key.hashCode()) % size;
			if ((b > a && (c <= a || c > b)) ||
				(b < a && (c <= a && c > b))) {
				entries[a].key = entries[b].key;
				entries[a].value = entries[b].value;
				a = b;
			}	
		}
		entries[a] = null;
		elements--;
		return v;
	}

	/**
	 * Add `key' to the hashtable and associate it with `value'
	 */
	public void put(Key key, Value value) {
		int a = findslot(key);
		/* resize the array if it was not possible to find a vacant slot 
		 * (perhaps because of a not so uniform hash function) */
		while (a == -1) {
			resizeArray();
			a = findslot(key);
		}
		if (entries[a] == null) {
			/* add the new element */
			entries[a] = new Node<Key, Value>(key, value);
			elements++;
			/* resize the array if the load factor is too high */
			if ((double)elements / (double)size > MAXLOADFACTOR)
				resizeArray();
		} else {
			/* replace existing element */
			entries[a].value = value;
		}
		//System.out.printf("%d = %d\n", a, key);
	}

	/**
	 * check whether the hashtable is empty
	 */ 
	public boolean isEmpty() {
		return elements == 0;
	}

	/**
	 * Return the number of keys in the hashtable
	 */ 
	public int elements() {
		return elements;
	}

	/**
	 * Resize array quadratically by creating a new array, with double the
	 * size of the original
	 */ 
	@SuppressWarnings("unchecked") /* necessary for generic array creation. */
	private void resizeArray () {
		int b;
		previous = size;
		/* try to keep the capacity a mersenne prime: */
		size = previous * 2 + 1;

		/* preserve the old keys and values */	
		Node<Key, Value>[] oldentries = entries;

		/* create the new arrays */
		entries = (Node<Key, Value>[]) new Node[size];

		/* populate the new arrays using the copy just made */
		for (int a = 0; a < previous; a++) {
			if (oldentries[a] != null) {
				b = findslot(oldentries[a].key);
				entries[b] = oldentries[a];
			}
		}
	}

	private class Node<Key, Value> {
		Key key;
		Value value;
		public Node(Key key, Value value) {
			this.key = key;
			this.value = value;
		}
	}
}