/**
 * A hashtable
 **/
public class ChainingArrayHashTable<Key,Value> implements MyHashTable<Key, Value> {
	final static double MAXLOADFACTOR = 0.8;
	private int size, previous;
	private int elements;
	private Link<Key,Value>[] entries; //= (Link<Key, Value>) new Link[size];

	@SuppressWarnings("unchecked")
	public ChainingArrayHashTable(int size) {
		this.size = size;
		previous = size;
		elements = 0;
		entries = (Link<Key, Value>[]) new Link[size];
	}

	/** default constructor */
	public ChainingArrayHashTable() {
		this(1023);
	}

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

	/**
	 * check whether the hashtable contains a specific key
	 */
	public boolean has(Key key) {
		return entries[Math.abs(key.hashCode() % size)] != 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 = Math.abs(key.hashCode() % size); 
		if (entries[a] == null)
			throw new java.util.NoSuchElementException();
		else {
			Link<Key, Value> entry = entries[a];
			while (entry != null)
				if (entry.key.equals(key))
					return entry.value;
				else
					entry = entry.next;

			throw new java.util.NoSuchElementException();
		}
	}

	/**
	 *  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 = Math.abs(key.hashCode() % size); 
		Link<Key, Value> entry = entries[a], prev = entry;
		if (entry == null)
			return null;
		if (entry.key.equals(key)) {
			entries[a] = entry.next;
			elements--;
			return entry.value;
		}
		while(entry != null) {
			if (entry.key.equals(key)) {
				prev.next = entry.next;
				elements--;
				return entry.value;
			} else {
				prev = entry;
				entry = entry.next;
			}
		}
		throw new java.util.NoSuchElementException();

	}

	/**
	 * Add `key' to the hashtable and associate it with `value'
	 */
	public void put(Key key, Value value) {
		int a = Math.abs(key.hashCode() % size); 
		if (entries[a] == null) {
			//keys[a] = (Link<Key, Value>) new Link(key, value, keys[a]);
			entries[a] = new Link<Key, Value>(key, value, entries[a]);
			elements++;
		}	
		else {
			Link<Key, Value> entry = entries[a];
			while (entry != null) {
				if (entry.key.equals(key)) {
					/* Replace the value of an already present key */
					entry.value = value;
					return;
				} else
					entry = entry.next;
			}
			entries[a] = new Link<Key, Value>(key, value, entries[a]);
			elements++;
			/* check the load factor, resize if necessary */
			if ((double)elements / (double)size > MAXLOADFACTOR)
				resizeArray();
		}
	}


	/**
	 * 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")
	private void resizeArray () {
		int b;
		previous = size;
		/* try to keep the capacity a mersenne prime: */
		size = previous * 2 + 1;
		Link<Key, Value> entry;

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

		/* create the new array */
		entries = new Link[size];

		/* populate the new array using the copy just made */
		for (int a = oldentries.length - 1; a >= 0; a--) {
			entry = oldentries[a];
			while (entry != null) {
				b = Math.abs(entry.key.hashCode() % size);
				Link next = entry.next;
				entry.next = entries[b];
				entries[b] = entry;
				entry = next;
			}
		}
	}

	private class Link<Key,Value> extends Object{
		Key key;
		Value value;
		Link<Key, Value> next;
		public Link(Key key, Value value, Link<Key,Value> next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}
	}
}