// IntHashtable - a Hashtable that uses ints as the keys//// This is 90% based on JavaSoft's java.util.Hashtable.//// Visit the ACME Labs Java page for up-to-date versions of this and other// fine Java utilities: http://www.acme.com/java/package Acme;import java.util.*;/// A Hashtable that uses ints as the keys.// <P>// Use just like java.util.Hashtable, except that the keys must be ints.// This is much faster than creating a new Integer for each access.// <P>// <A HREF="/resources/classes/Acme/IntHashtable.java">Fetch the software.</A><BR>// <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>// <P>// @see java.util.Hashtablepublic class IntHashtable extends Dictionary implements Cloneable    {    /// The hash table data.    private IntHashtableEntry table[];    /// The total number of entries in the hash table.    private int count;    /// Rehashes the table when count exceeds this threshold.    private int threshold;    /// The load factor for the hashtable.    private float loadFactor;    /// Constructs a new, empty hashtable with the specified initial     // capacity and the specified load factor.    // @param initialCapacity the initial number of buckets    // @param loadFactor a number between 0.0 and 1.0, it defines    //		the threshold for rehashing the hashtable into    //		a bigger one.    // @exception IllegalArgumentException If the initial capacity    // is less than or equal to zero.    // @exception IllegalArgumentException If the load factor is    // less than or equal to zero.    public IntHashtable( int initialCapacity, float loadFactor )	{	if ( initialCapacity <= 0 || loadFactor <= 0.0 )	    throw new IllegalArgumentException();	this.loadFactor = loadFactor;	table = new IntHashtableEntry[initialCapacity];	threshold = (int) ( initialCapacity * loadFactor );	}    /// Constructs a new, empty hashtable with the specified initial     // capacity.    // @param initialCapacity the initial number of buckets    public IntHashtable( int initialCapacity )	{	this( initialCapacity, 0.75f );	}    /// Constructs a new, empty hashtable. A default capacity and load factor    // is used. Note that the hashtable will automatically grow when it gets    // full.    public IntHashtable()	{	this( 101, 0.75f );	}    /// Returns the number of elements contained in the hashtable.     public int size()	{	return count;	}    /// Returns true if the hashtable contains no elements.    public boolean isEmpty()	{	return count == 0;	}    /// Returns an enumeration of the hashtable's keys.    // @see IntHashtable#elements    public synchronized Enumeration keys()	{	return new IntHashtableEnumerator( table, true );	}    /// Returns an enumeration of the elements. Use the Enumeration methods     // on the returned object to fetch the elements sequentially.    // @see IntHashtable#keys    public synchronized Enumeration elements()	{	return new IntHashtableEnumerator( table, false );	}    /// Returns true if the specified object is an element of the hashtable.    // This operation is more expensive than the containsKey() method.    // @param value the value that we are looking for    // @exception NullPointerException If the value being searched     // for is equal to null.    // @see IntHashtable#containsKey    public synchronized boolean contains( Object value )	{	if ( value == null )	    throw new NullPointerException();	IntHashtableEntry tab[] = table;	for ( int i = tab.length ; i-- > 0 ; )	    {	    for ( IntHashtableEntry e = tab[i] ; e != null ; e = e.next )		{		if ( e.value.equals( value ) )		    return true;		}	    }	return false;	}    /// Returns true if the collection contains an element for the key.    // @param key the key that we are looking for    // @see IntHashtable#contains    public synchronized boolean containsKey( int key )	{	IntHashtableEntry tab[] = table;	int hash = key;	int index = ( hash & 0x7FFFFFFF ) % tab.length;	for ( IntHashtableEntry e = tab[index] ; e != null ; e = e.next )	    {	    if ( e.hash == hash && e.key == key )		return true;	    }	return false;	}    /// Gets the object associated with the specified key in the     // hashtable.    // @param key the specified key    // @returns the element for the key or null if the key    // 		is not defined in the hash table.    // @see IntHashtable#put    public synchronized Object get( int key )	{	IntHashtableEntry tab[] = table;	int hash = key;	int index = ( hash & 0x7FFFFFFF ) % tab.length;	for ( IntHashtableEntry e = tab[index] ; e != null ; e = e.next )	    {	    if ( e.hash == hash && e.key == key )		return e.value;	    }	return null;	}    /// A get method that takes an Object, for compatibility with    // java.util.Dictionary.  The Object must be an Integer.    public Object get( Object okey )	{	if ( ! ( okey instanceof Integer ) )	    throw new InternalError( "key is not an Integer" );	Integer ikey = (Integer) okey;	int key = ikey.intValue();	return get( key );	}    /// Rehashes the content of the table into a bigger table.    // This method is called automatically when the hashtable's    // size exceeds the threshold.    protected void rehash()	{	int oldCapacity = table.length;	IntHashtableEntry oldTable[] = table;	int newCapacity = oldCapacity * 2 + 1;	IntHashtableEntry newTable[] = new IntHashtableEntry[newCapacity];	threshold = (int) ( newCapacity * loadFactor );	table = newTable;	for ( int i = oldCapacity ; i-- > 0 ; )	    {	    for ( IntHashtableEntry old = oldTable[i] ; old != null ; )		{		IntHashtableEntry e = old;		old = old.next;		int index = ( e.hash & 0x7FFFFFFF ) % newCapacity;		e.next = newTable[index];		newTable[index] = e;		}	    }	}    /// Puts the specified element into the hashtable, using the specified    // key.  The element may be retrieved by doing a get() with the same key.    // The key and the element cannot be null.     // @param key the specified key in the hashtable    // @param value the specified element    // @exception NullPointerException If the value of the element     // is equal to null.    // @see IntHashtable#get    // @return the old value of the key, or null if it did not have one.    public synchronized Object put( int key, Object value )	{	// Make sure the value is not null.	if ( value == null )	    throw new NullPointerException();	// Makes sure the key is not already in the hashtable.	IntHashtableEntry tab[] = table;	int hash = key;	int index = ( hash & 0x7FFFFFFF ) % tab.length;	for ( IntHashtableEntry e = tab[index] ; e != null ; e = e.next )	    {	    if ( e.hash == hash && e.key == key )		{		Object old = e.value;		e.value = value;		return old;		}	    }	if ( count >= threshold )	    {	    // Rehash the table if the threshold is exceeded.	    rehash();	    return put( key, value );	    } 	// Creates the new entry.	IntHashtableEntry e = new IntHashtableEntry();	e.hash = hash;	e.key = key;	e.value = value;	e.next = tab[index];	tab[index] = e;	++count;	return null;	}    /// A put method that takes an Object, for compatibility with    // java.util.Dictionary.  The Object must be an Integer.    public Object put( Object okey, Object value )	{	if ( ! ( okey instanceof Integer ) )	    throw new InternalError( "key is not an Integer" );	Integer ikey = (Integer) okey;	int key = ikey.intValue();	return put( key, value );	}    /// Removes the element corresponding to the key. Does nothing if the    // key is not present.    // @param key the key that needs to be removed    // @return the value of key, or null if the key was not found.    public synchronized Object remove( int key )	{	IntHashtableEntry tab[] = table;	int hash = key;	int index = ( hash & 0x7FFFFFFF ) % tab.length;	for ( IntHashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next )	    {	    if ( e.hash == hash && e.key == key )		{		if ( prev != null )		    prev.next = e.next;		else		    tab[index] = e.next;		--count;		return e.value;		}	    }	return null;	}    /// A remove method that takes an Object, for compatibility with    // java.util.Dictionary.  The Object must be an Integer.    public Object remove( Object okey )	{	if ( ! ( okey instanceof Integer ) )	    throw new InternalError( "key is not an Integer" );	Integer ikey = (Integer) okey;	int key = ikey.intValue();	return remove( key );	}    /// Clears the hash table so that it has no more elements in it.    public synchronized void clear()	{	IntHashtableEntry tab[] = table;	for ( int index = tab.length; --index >= 0; )	    tab[index] = null;	count = 0;	}    /// Creates a clone of the hashtable. A shallow copy is made,    // the keys and elements themselves are NOT cloned. This is a    // relatively expensive operation.    public synchronized Object clone()	{	try	    {	    IntHashtable t = (IntHashtable) super.clone();	    t.table = new IntHashtableEntry[table.length];	    for ( int i = table.length ; i-- > 0 ; )		t.table[i] = ( table[i] != null ) ?		    (IntHashtableEntry) table[i].clone() : null;	    return t;	    }	catch ( CloneNotSupportedException e)	    {	    // This shouldn't happen, since we are Cloneable.	    throw new InternalError();	    }	}    /// Converts to a rather lengthy String.    public synchronized String toString()	{	int max = size() - 1;	StringBuffer buf = new StringBuffer();	Enumeration k = keys();	Enumeration e = elements();	buf.append( "{" );	for ( int i = 0; i <= max; ++i )	    {	    String s1 = k.nextElement().toString();	    String s2 = e.nextElement().toString();	    buf.append( s1 + "=" + s2 );	    if ( i < max )		buf.append( ", " );	    }	buf.append( "}" );	return buf.toString();	}    }class IntHashtableEntry    {    int hash;    int key;    Object value;    IntHashtableEntry next;    protected Object clone()	{	IntHashtableEntry entry = new IntHashtableEntry();	entry.hash = hash;	entry.key = key;	entry.value = value;	entry.next = ( next != null ) ? (IntHashtableEntry) next.clone() : null;	return entry;	}    }class IntHashtableEnumerator implements Enumeration    {    boolean keys;    int index;    IntHashtableEntry table[];    IntHashtableEntry entry;    IntHashtableEnumerator( IntHashtableEntry table[], boolean keys )	{	this.table = table;	this.keys = keys;	this.index = table.length;	}	    public boolean hasMoreElements()	{	if ( entry != null )	    return true;	while ( index-- > 0 )	    if ( ( entry = table[index] ) != null )		return true;	return false;	}    public Object nextElement()	{	if ( entry == null )	    while ( ( index-- > 0 ) && ( ( entry = table[index] ) == null ) )		;	if ( entry != null )	    {	    IntHashtableEntry e = entry;	    entry = e.next;	    return keys ? new Integer( e.key ) : e.value;	    }	throw new NoSuchElementException( "IntHashtableEnumerator" );	}    }