/** 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.Hashtable */ public 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, or 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. * @return */ public int size() { return count; } /** Returns true if the hashtable contains no elements. * @return */ public boolean isEmpty() { return count == 0; } /** Returns an enumeration of the hashtable's keys. * @see IntHashtable#elements * @return */ 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 * @return */ 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. * @see IntHashtable#contains * @param key the key that we are looking for * @return */ 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" ); } }
# | Change | User | Description | Committed | |
---|---|---|---|---|---|
#2 | 2735 | andrei_loskutov | sources are now included to binary distribution at http://andrei.gmxhome.de/perforce/index.html | ||
#1 | 2222 | andrei_loskutov |
#13.10.2002 22:16 Revision 1.2.1 1) Documentation task is finished... Yes!!! 2) New feature: copy P4 depot path 3) Some small fixes to menu shortkeys belongs ctrl + c and ctrl + d 4) Clipboard fix because of JDK 1.2 - 1.3 bug 5) Smallest refactoring on some methods. 6) Html help updated |