/**
 * A hashtable
 **/
public class ProbingArrayHashTable implements HashTable {
	private int entries = 0;
	private int size = 100;
	private Object[] keys;
	private Object[] values;

	public ProbingArrayHashTable() {
		keys = new String[size];
		values = new String[size];
	
	}
	/**
 	 * check whether the hashtable is empty
 	 */ 
	public boolean isEmpty() {
		return entries() == 0;
	}

	/**
	 * return the index for `key' by linear probing
	 */
	private int findslot(Object key) {
		int a = key.hashCode() % size;
		do {
			a = (a + 1) % size;
		} while (keys[a] != null && !keys[a].equals(key));
		if (keys[a] == null)
			return a;
		else
			throw new HashTableFullException();
	}
	/**
 	 * check whether the hashtable contains a specific key
 	 */
	public boolean has(Object key) {
		return keys[findslot(key)] != null;
	}
	
	/**
 	 *  get the object associated with a specific key
 	 * @throws java.util.NoSuchElementException
 	 * 	if the specified key is not in the hashtable
 	 */ 
	public Object get(Object key) {
		if (keys[findslot(key)] == null)
			throw new java.util.NoSuchElementException();
		else
			return values[findslot(key)];
	}
	
	/**
 	 *  remove the object associated with a specific key
 	 * @throws java.util.NoSuchElementException
 	 * 	if the specified key is not in the hashtable
 	 */ 
	public Object remove(Object key) {
		Object obj = get(key);
		put(key, null);
		entries--;
		return obj;
	}
	
	/**
 	 * Add `key' to the hashtable and associate it with `value'
 	 */
	public void put(Object key, Object value) {
		int a = findslot(key);
		if (values[a] == null) {
			values[a] = value;
			entries++;
		}
		else {
			// TODO: rebuild
			keys[a] = key;
			values[a] = value;
		}
	}

	
	/**
 	 * Return the number of keys in the hashtable
 	 */ 
	public int entries() {
		return entries;
	}
	
	/**
 	 * Return the keys in the hashtable
 	 */ 
	public Object[] keys() {
		return keys;
	}
}