/*******************************************************************************
 * Copyright (c) 2000, 2008 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package java.util;

public class HashMap extends AbstractMap {

	int elementCount;
	Entry[] elementData;
	private int limit;
	

private static class Entry implements Map.Entry {
	Object key, value;
	Entry next;
	public boolean equals(Object other) {
		if (this == other) return true;
		if (!(other instanceof Map.Entry)) return false;
		Map.Entry entry = (Map.Entry)other;
		return (getKey() == null ? entry.getKey() == null : getKey().equals(entry.getKey()))  &&
			(getValue() == null ? entry.getValue() == null : getValue().equals(entry.getValue()));
	}
	public Object getKey() {
		return key;
	}
	public Object getValue() {
		return value;
	}
	public int hashCode() {
		return (getKey() == null ? 0 : getKey().hashCode()) ^
			(getValue() == null ? 0 : getValue().hashCode());
	}
	public void setValue(Object value) {
		this.value = value;		
	}
}

public HashMap() {
	this(16, 0.75f);
}

public HashMap(int initialCapacity) {
	this(initialCapacity, 0.75f);
}

public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0) throw new IllegalArgumentException();
	elementData = new Entry[initialCapacity];
	limit = (int)(elementData.length * loadFactor);
}

public HashMap(Map m) {
	this(m.size(), 0.75f);
	putAll(m);
}

public void clear() {
	for (int i = 0; i < elementData.length; i++) {
		elementData[i] = null;
	}
	elementCount = 0;
}

protected Object clone() throws CloneNotSupportedException {
	return super.clone();
}

public boolean containsKey(Object key) {
	if (key == null) throw new NullPointerException();
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % elementData.length;
	Entry entry = elementData[index];
	while (entry != null) {
		if (key.equals(entry.key)) return true;
		entry = entry.next;
	}
	return false;
}

public boolean containsValue(Object value) {
	if (value == null) throw new NullPointerException();
	for (int i = 0; i < elementData.length; i++) {
		Entry entry = elementData[i];
		while (entry != null) {
			if (value.equals(entry.value)) return true;
			entry = entry.next;
		}
	}
	return false;
}

public Set entrySet() {
	return new AbstractSet() {		

		public Iterator iterator() {			
			return new Iterator() {
				int count, pos;
				Entry entry, nextEntry;

				public boolean hasNext() {
					return count < elementCount;
				}

				public Object next() throws NoSuchElementException {
					if (count >= elementCount) throw new NoSuchElementException();
					while (nextEntry == null) nextEntry = elementData[pos++];
					Entry result = nextEntry;
					nextEntry = nextEntry.next;
					count++;
					return entry = result;
				}

				public void remove() throws UnsupportedOperationException, IllegalStateException {
					if (entry == null) throw new IllegalStateException();
					HashMap.this.remove(entry.getKey());
					entry = null;
				}				
			};
		}

		public boolean remove(Object o) {
			return HashMap.this.remove(((Entry)o).getKey()) != null;
		}
		
		public int size() {
			return HashMap.this.size();
		}
		
	};
}

public Object get(Object key) {
	if (key == null) throw new NullPointerException();
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % elementData.length;
	Entry entry = elementData[index];
	while (entry != null) {
		if (key.equals(entry.key)) return entry.value;
		entry = entry.next;
	}
	return null;
}

public boolean isEmpty() {
	return elementCount == 0;
}

public Set keySet() {
	//TODO
	return super.keySet();
}

public Object put(Object key, Object value) {
	if (key == null || value == null) throw new NullPointerException();
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % elementData.length;
	if (elementCount > 0) {
		Entry entry = elementData[index];
		while (entry != null) {
			if (entry.equals(key)) {
				Object result = entry.value;
				entry.value = value;
				return result;				
			}
			entry = entry.next;
		}
	}
	if (elementCount++ >= limit) {
		rehash();
		index = (hash & 0x7FFFFFFF) % elementData.length;
	}
	Entry newEntry = new Entry();
	Entry entry = elementData[index];
	if (entry != null) newEntry.next = entry;
	newEntry.key = key;
	newEntry.value = value;
	elementData[index] = newEntry;
	return null;
}

void rehash() {
	Entry[] newEntries = new Entry[elementData.length * 2 + 1];
	for (int i = 0; i < elementData.length; i++) {
		Entry entry = elementData[i];
		while (entry != null) {
			int hash = entry.key.hashCode();
			int index = (hash & 0x7FFFFFFF) % newEntries.length;
			Entry previous = newEntries[index];
			Entry next = entry.next;
			entry.next = previous != null ? previous : null;
			newEntries[index] = entry;
			entry = next;
		}
	}
	elementData = newEntries;
	limit = elementData.length * 3 / 4;
}

public Object remove(Object key) {
	if (key == null) throw new NullPointerException();
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % elementData.length;
	Entry entry = elementData[index], previous = null;
	while (entry != null) {
		if (key.equals(entry.key)) {
			elementCount--;
			if (previous == null) {
				elementData[index] = entry.next;
			} else {
				previous.next = entry.next;
			}
			return entry.value;
		}
		previous = entry;
		entry = entry.next;
	}
	return null;
}

public int size() {
	return elementCount;
}

public Collection values() {
	// TODO Auto-generated method stub
	return super.values();
}

}
