// java.util.Hashtable -- an implementation of the Java Language Spec sec 21.5
// Written by Charles Briscoe-Smith; refer to the file LEGAL for details.

package java.util;

import java.util.Enumeration;
import java.util.NoSuchElementException;

class HashtableEnumeration implements Enumeration {

	private int elementsLeft=0;
	private Object[] elements;

	HashtableEnumeration(Object[] elems, int count)
	{
		elements=new Object[count];
		int loc=0;
		for (int i=0; i<count; i++) {
			while (elems[loc]==null)
				loc++;
			elements[i]=elems[loc++];
		}
		elementsLeft=count;
	}

	public boolean hasMoreElements()
	{
		return elementsLeft>0;
	}

	public Object nextElement() throws NoSuchElementException
	{
		if (!hasMoreElements())
			throw new NoSuchElementException();
		return elements[--elementsLeft];
	}

}

public class Hashtable extends Dictionary implements Cloneable {

	public Hashtable(int cap, float factor)
	{
		keys=new Object[cap];
		elements=new Object[cap];
		fillfactor=factor;
		size=0;
		maxfill=(int) (cap*fillfactor);
	}

	public Hashtable(int cap)
	{
		this(cap, 0.75f);
	}

	public Hashtable()
	{
		this(16);
	}

	private Hashtable(Hashtable h)
	{
		size=h.size;
		maxfill=h.maxfill;
		fillfactor=h.fillfactor;
		keys=new Object[h.keys.length];
		for (int i=0; i<h.keys.length; i++) {
			keys[i]=h.keys[i];
		}
		elements=new Object[h.elements.length];
		for (int i=0; i<h.elements.length; i++) {
			elements[i]=h.elements[i];
		}
	}

	private Object[] keys;
	private Object[] elements;
	private int size;
	private int maxfill;
	private float fillfactor;

	public synchronized String toString()
	{
		StringBuffer output=new StringBuffer();
		output.append('{');
		int flag=0;
		for (int i=0; i<keys.length; i++) {
			if (keys[i]!=null) {
				if (flag==0) {
					flag=1;
				} else {
					output.append(", ");
				}
				output.append(keys[i]);
				output.append('=');
				output.append(elements[i]);
			}
		}
		output.append('}');
		return output.toString();
	}

	public synchronized Object clone()
	{
		return new Hashtable(this);
	}

	public synchronized int size()
	{
		return size;
	}

	public synchronized boolean isEmpty()
	{
		return size==0;
	}

	private synchronized int getIndex(Object key)
			throws NullPointerException
	{
		int hash=key.hashCode()%keys.length;
		if (hash<0) hash+=keys.length;
		for (int i=hash; i<keys.length; i++) {
			if (keys[i]==null) return -1;
			if (key.equals(keys[i])) return i;
		}
		for (int i=0; i<hash; i++) {
			if (keys[i]==null) return -1;
			if (key.equals(keys[i])) return i;
		}
		return -1;
	}

	public synchronized Object get(Object key)
			throws NullPointerException
	{
		int i=getIndex(key);
		return i==-1 ? null : elements[i];
	}

	private void hashIn(Object key, Object elem)
			throws NullPointerException
	{
		int hash=key.hashCode()%keys.length;
		if (hash<0) hash+=keys.length;
		for (int i=hash; i<keys.length; i++) {
			if (keys[i]==null) {
				keys[i]=key;
				elements[i]=elem;
				return;
			}
		}
		for (int i=0; i<hash; i++) {
			if (keys[i]==null) {
				keys[i]=key;
				elements[i]=elem;
				return;
			}
		}
		throw new InternalError("Can't hash new pair into Hashtable");
	}

	protected synchronized void addElement(Object key, Object elem)
			throws NullPointerException
	{
		size++;
		if (size>maxfill || size>keys.length)
			rehash();
		hashIn(key, elem);
	}

	public synchronized Object put(Object key, Object elem)
			throws NullPointerException
	{
		int i=getIndex(key);
		if (elem==null) throw new NullPointerException();
		Object oldelem=null;
		if (i==-1) {
			addElement(key, elem);
		} else {
			oldelem=elements[i];
			keys[i]=key;
			elements[i]=elem;
		}
		return oldelem;
	}

	public synchronized Object remove(Object key)
			throws NullPointerException
	{
		int start=getIndex(key);
		if (start==-1) return null;
		Object oldelem=elements[start];
		keys[start]=null;
		elements[start]=null;
		for (int i=start+1; i<keys.length; i++) {
			Object shiftkey=keys[i];
			Object shiftelem=keys[i];
			keys[i]=null;
			elements[i]=null;
			if (shiftkey==null) return oldelem;
			hashIn(shiftkey, shiftelem);
		}
		for (int i=0; i<start; i++) {
			Object shiftkey=keys[i];
			Object shiftelem=keys[i];
			keys[i]=null;
			elements[i]=null;
			if (shiftkey==null) return oldelem;
			hashIn(shiftkey, shiftelem);
		}
	}

	public synchronized Enumeration keys()
	{
		return new HashtableEnumeration(keys, size);
	}

	public synchronized Enumeration elements()
	{
		return new HashtableEnumeration(elements, size);
	}

	public synchronized boolean contains(Object elem)
	{
		for (int i=0; i<keys.length; i++) {
			if (elem.equals(elements[i])) {
				return true;
			}
		}
		return false;
	}

	public synchronized boolean containsKey(Object key)
	{
		return getIndex(key)!=-1;
	}

	protected synchronized void rehash()
	{
		Object[] oldkeys=keys;
		Object[] oldelems=elements;
		keys=new Object[oldkeys.length*2];
		elements=new Object[keys.length];
		for (int i=0; i<oldkeys.length; i++) {
			if (oldkeys[i]!=null)
				hashIn(oldkeys[i], oldelems[i]);
		}
		maxfill=(int) (keys.length*fillfactor);
	}

	public synchronized void clear()
	{
		size=0;
		for (int i=0; i<keys.length; i++) {
			keys[i]=null;
			elements[i]=null;
		}
	}

}