// Implements a map of objects using a hash table.
// The hash table uses separate chaining to resolve collisions.
public class HashMap<K, V> {
	private static final double MAX_LOAD_FACTOR = 0.75;
	private HashMapEntry[] elementData;
	private int size;
	
	// Constructs an empty set.
	public HashMap() {
		elementData = new HashMapEntry[10];
		size = 0;
	}
	
	// Removes all elements from the set.
	public void clear() {
		for (int i = 0; i < elementData.length; i++) {
			elementData[i] = null;
		}
		size = 0;
	}
	
	// Returns true if the given key is found in this map.
	public boolean containsKey(K key) {
		return get(key) != null;
	}
	
	// Returns true if the given key is found in this map.
	@SuppressWarnings("unchecked")
	public V get(K key) {
		int bucket = hashFunction(key);
		HashMapEntry current = elementData[bucket];
		while (current != null) {
			if (current.key.equals(key)) {
				return (V) current.value;
			}
			current = current.next;
		}
		return null;
	}
	
	// Returns true if there are no elements in this queue.
	public boolean isEmpty() {
		return size == 0;
	}
	
	// Adds the given key/value pair to this map, if it was not already
	// contained in the map.
	public void put(K key, V value) {
		if (value == null) {
			// special case: value cannot be null
			remove(key);
			return;
		}
		
		int bucket = hashFunction(key);
		HashMapEntry current = elementData[bucket];
		while (current != null) {
			if (current.key.equals(key)) {
				// key already exists; update associated value
				current.value = value;
				return;
			}
			current = current.next;
		}

		// if we get here, the key was not found; add new entry
		if (loadFactor() >= MAX_LOAD_FACTOR) {
			rehash();
			bucket = hashFunction(key);
		}
		// insert new k/v pair at front of list
		elementData[bucket] = new HashMapEntry(key, value, elementData[bucket]);
		size++;
	}
	
	// Removes the given key and its associated value if it is contained in the map.
	// If the map does not contain the key, has no effect.
	public void remove(K key) {
		int bucket = hashFunction(key);
		if (elementData[bucket] != null) {
			// check front of list
			if (elementData[bucket].key.equals(key)) {
				elementData[bucket] = elementData[bucket].next;
				size--;
			} else {
				// check rest of list
				HashMapEntry current = elementData[bucket];
				while (current.next != null && !current.next.key.equals(key)) {
					current = current.next;
				}
				
				// if the key is found, remove it
				if (current.next != null && current.next.key.equals(key)) {
					current.next = current.next.next;
					size--;
				}
			}
		}
	}
	
	// Returns the number of key/value pairs in the map.
	public int size() {
		return size;
	}
	
	// Returns a string representation of this map, such as "{10=a, 20=b, 30=c}";
	// The elements are not guaranteed to be listed in sorted order.
	public String toString() {
		String result = "{";
		boolean first = true;
		if (!isEmpty()) {
			for (int i = 0; i < elementData.length; i++) {
				HashMapEntry current = elementData[i];
				while (current != null) {
					if (!first) {
						result += ", ";
					}
					result += current.key + "=" + current.value;
					first = false;
					current = current.next;
				}
			}
		}
		return result + "}";
	}
	
	
	// Returns the preferred hash bucket index for the given key.
	private int hashFunction(K key) {
		return Math.abs(key.hashCode()) % elementData.length;
	}
	
	private double loadFactor() {
		return (double) size / elementData.length;
	}
	
	// Resizes the hash table to twice its former size.
	@SuppressWarnings("unchecked")
	private void rehash() {
		// replace element data array with a larger empty version
		HashMapEntry[] oldElementData = elementData;
		elementData = new HashMapEntry[2 * oldElementData.length];
		size = 0;

		// re-add all of the old data into the new array
		for (int i = 0; i < oldElementData.length; i++) {
			HashMapEntry current = oldElementData[i];
			while (current != null) {
				put((K) current.key, (V) current.value);
				current = current.next;
			}
		}
	}
	
	// Represents a single value in a chain stored in one hash bucket.
	private static class HashMapEntry {
		public Object key;
		public Object value;
		public HashMapEntry next;

		public HashMapEntry(Object key, Object value) {
			this(key, value, null);
		}

		public HashMapEntry(Object key, Object value, HashMapEntry next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}
	}
}