001: // IntHashtable - a Hashtable that uses ints as the keys
002: //
003: // This is 90% based on JavaSoft's java.util.Hashtable.
004: //
005: // Visit the ACME Labs Java page for up-to-date versions of this and other
006: // fine Java utilities: http://www.acme.com/java/
007:
008: package Acme;
009:
010: import org.wings.util.SStringBuilder;
011:
012: import java.util.Dictionary;
013: import java.util.Enumeration;
014: import java.util.NoSuchElementException;
015:
016: /// A Hashtable that uses ints as the keys.
017: // <P>
018: // Use just like java.util.Hashtable, except that the keys must be ints.
019: // This is much faster than creating a new Integer for each access.
020: // <P>
021: // <A HREF="/resources/classes/Acme/IntHashtable.java">Fetch the software.</A><BR>
022: // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
023: // <P>
024: // @see java.util.Hashtable
025:
026: public class IntHashtable extends Dictionary implements Cloneable {
027: /// The hash table data.
028: private IntHashtableEntry table[];
029:
030: /// The total number of entries in the hash table.
031: private int count;
032:
033: /// Rehashes the table when count exceeds this threshold.
034: private int threshold;
035:
036: /// The load factor for the hashtable.
037: private float loadFactor;
038:
039: /// Constructs a new, empty hashtable with the specified initial
040: // capacity and the specified load factor.
041: // @param initialCapacity the initial number of buckets
042: // @param loadFactor a number between 0.0 and 1.0, it defines
043: // the threshold for rehashing the hashtable into
044: // a bigger one.
045: // @exception IllegalArgumentException If the initial capacity
046: // is less than or equal to zero.
047: // @exception IllegalArgumentException If the load factor is
048: // less than or equal to zero.
049: public IntHashtable(int initialCapacity, float loadFactor) {
050: if (initialCapacity <= 0 || loadFactor <= 0.0)
051: throw new IllegalArgumentException();
052: this .loadFactor = loadFactor;
053: table = new IntHashtableEntry[initialCapacity];
054: threshold = (int) (initialCapacity * loadFactor);
055: }
056:
057: /// Constructs a new, empty hashtable with the specified initial
058: // capacity.
059: // @param initialCapacity the initial number of buckets
060: public IntHashtable(int initialCapacity) {
061: this (initialCapacity, 0.75f);
062: }
063:
064: /// Constructs a new, empty hashtable. A default capacity and load factor
065: // is used. Note that the hashtable will automatically grow when it gets
066: // full.
067: public IntHashtable() {
068: this (101, 0.75f);
069: }
070:
071: /// Returns the number of elements contained in the hashtable.
072: public int size() {
073: return count;
074: }
075:
076: /// Returns true if the hashtable contains no elements.
077: public boolean isEmpty() {
078: return count == 0;
079: }
080:
081: /// Returns an enumeration of the hashtable's keys.
082: // @see IntHashtable#elements
083: public synchronized Enumeration keys() {
084: return new IntHashtableEnumerator(table, true);
085: }
086:
087: /// Returns an enumeration of the elements. Use the Enumeration methods
088: // on the returned object to fetch the elements sequentially.
089: // @see IntHashtable#keys
090: public synchronized Enumeration elements() {
091: return new IntHashtableEnumerator(table, false);
092: }
093:
094: /// Returns true if the specified object is an element of the hashtable.
095: // This operation is more expensive than the containsKey() method.
096: // @param value the value that we are looking for
097: // @exception NullPointerException If the value being searched
098: // for is equal to null.
099: // @see IntHashtable#containsKey
100: public synchronized boolean contains(Object value) {
101: if (value == null)
102: throw new NullPointerException();
103: IntHashtableEntry tab[] = table;
104: for (int i = tab.length; i-- > 0;) {
105: for (IntHashtableEntry e = tab[i]; e != null; e = e.next) {
106: if (e.value.equals(value))
107: return true;
108: }
109: }
110: return false;
111: }
112:
113: /// Returns true if the collection contains an element for the key.
114: // @param key the key that we are looking for
115: // @see IntHashtable#contains
116: public synchronized boolean containsKey(int key) {
117: IntHashtableEntry tab[] = table;
118: int hash = key;
119: int index = (hash & 0x7FFFFFFF) % tab.length;
120: for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
121: if (e.hash == hash && e.key == key)
122: return true;
123: }
124: return false;
125: }
126:
127: /// Gets the object associated with the specified key in the
128: // hashtable.
129: // @param key the specified key
130: // @returns the element for the key or null if the key
131: // is not defined in the hash table.
132: // @see IntHashtable#put
133: public synchronized Object get(int key) {
134: IntHashtableEntry tab[] = table;
135: int hash = key;
136: int index = (hash & 0x7FFFFFFF) % tab.length;
137: for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
138: if (e.hash == hash && e.key == key)
139: return e.value;
140: }
141: return null;
142: }
143:
144: /// A get method that takes an Object, for compatibility with
145: // java.util.Dictionary. The Object must be an Integer.
146: public Object get(Object okey) {
147: if (!(okey instanceof Integer))
148: throw new InternalError("key is not an Integer");
149: Integer ikey = (Integer) okey;
150: int key = ikey.intValue();
151: return get(key);
152: }
153:
154: /// Rehashes the content of the table into a bigger table.
155: // This method is called automatically when the hashtable's
156: // size exceeds the threshold.
157: protected void rehash() {
158: int oldCapacity = table.length;
159: IntHashtableEntry oldTable[] = table;
160:
161: int newCapacity = oldCapacity * 2 + 1;
162: IntHashtableEntry newTable[] = new IntHashtableEntry[newCapacity];
163:
164: threshold = (int) (newCapacity * loadFactor);
165: table = newTable;
166:
167: for (int i = oldCapacity; i-- > 0;) {
168: for (IntHashtableEntry old = oldTable[i]; old != null;) {
169: IntHashtableEntry e = old;
170: old = old.next;
171:
172: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
173: e.next = newTable[index];
174: newTable[index] = e;
175: }
176: }
177: }
178:
179: /// Puts the specified element into the hashtable, using the specified
180: // key. The element may be retrieved by doing a get() with the same key.
181: // The key and the element cannot be null.
182: // @param key the specified key in the hashtable
183: // @param value the specified element
184: // @exception NullPointerException If the value of the element
185: // is equal to null.
186: // @see IntHashtable#get
187: // @return the old value of the key, or null if it did not have one.
188: public synchronized Object put(int key, Object value) {
189: // Make sure the value is not null.
190: if (value == null)
191: throw new NullPointerException();
192:
193: // Makes sure the key is not already in the hashtable.
194: IntHashtableEntry tab[] = table;
195: int hash = key;
196: int index = (hash & 0x7FFFFFFF) % tab.length;
197: for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
198: if (e.hash == hash && e.key == key) {
199: Object old = e.value;
200: e.value = value;
201: return old;
202: }
203: }
204:
205: if (count >= threshold) {
206: // Rehash the table if the threshold is exceeded.
207: rehash();
208: return put(key, value);
209: }
210:
211: // Creates the new entry.
212: IntHashtableEntry e = new IntHashtableEntry();
213: e.hash = hash;
214: e.key = key;
215: e.value = value;
216: e.next = tab[index];
217: tab[index] = e;
218: ++count;
219: return null;
220: }
221:
222: /// A put method that takes an Object, for compatibility with
223: // java.util.Dictionary. The Object must be an Integer.
224: public Object put(Object okey, Object value) {
225: if (!(okey instanceof Integer))
226: throw new InternalError("key is not an Integer");
227: Integer ikey = (Integer) okey;
228: int key = ikey.intValue();
229: return put(key, value);
230: }
231:
232: /// Removes the element corresponding to the key. Does nothing if the
233: // key is not present.
234: // @param key the key that needs to be removed
235: // @return the value of key, or null if the key was not found.
236: public synchronized Object remove(int key) {
237: IntHashtableEntry tab[] = table;
238: int hash = key;
239: int index = (hash & 0x7FFFFFFF) % tab.length;
240: for (IntHashtableEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
241: if (e.hash == hash && e.key == key) {
242: if (prev != null)
243: prev.next = e.next;
244: else
245: tab[index] = e.next;
246: --count;
247: return e.value;
248: }
249: }
250: return null;
251: }
252:
253: /// A remove method that takes an Object, for compatibility with
254: // java.util.Dictionary. The Object must be an Integer.
255: public Object remove(Object okey) {
256: if (!(okey instanceof Integer))
257: throw new InternalError("key is not an Integer");
258: Integer ikey = (Integer) okey;
259: int key = ikey.intValue();
260: return remove(key);
261: }
262:
263: /// Clears the hash table so that it has no more elements in it.
264: public synchronized void clear() {
265: IntHashtableEntry tab[] = table;
266: for (int index = tab.length; --index >= 0;)
267: tab[index] = null;
268: count = 0;
269: }
270:
271: /// Creates a clone of the hashtable. A shallow copy is made,
272: // the keys and elements themselves are NOT cloned. This is a
273: // relatively expensive operation.
274: public synchronized Object clone() {
275: try {
276: IntHashtable t = (IntHashtable) super .clone();
277: t.table = new IntHashtableEntry[table.length];
278: for (int i = table.length; i-- > 0;)
279: t.table[i] = (table[i] != null) ? (IntHashtableEntry) table[i]
280: .clone()
281: : null;
282: return t;
283: } catch (CloneNotSupportedException e) {
284: // This shouldn't happen, since we are Cloneable.
285: throw new InternalError();
286: }
287: }
288:
289: /// Converts to a rather lengthy String.
290: public synchronized String toString() {
291: int max = size() - 1;
292: SStringBuilder buf = new SStringBuilder();
293: Enumeration k = keys();
294: Enumeration e = elements();
295: buf.append("{");
296:
297: for (int i = 0; i <= max; ++i) {
298: String s1 = k.nextElement().toString();
299: String s2 = e.nextElement().toString();
300: buf.append(s1 + "=" + s2);
301: if (i < max)
302: buf.append(", ");
303: }
304: buf.append("}");
305: return buf.toString();
306: }
307: }
308:
309: class IntHashtableEntry {
310: int hash;
311: int key;
312: Object value;
313: IntHashtableEntry next;
314:
315: protected Object clone() {
316: IntHashtableEntry entry = new IntHashtableEntry();
317: entry.hash = hash;
318: entry.key = key;
319: entry.value = value;
320: entry.next = (next != null) ? (IntHashtableEntry) next.clone()
321: : null;
322: return entry;
323: }
324: }
325:
326: class IntHashtableEnumerator implements Enumeration {
327: boolean keys;
328: int index;
329: IntHashtableEntry table[];
330: IntHashtableEntry entry;
331:
332: IntHashtableEnumerator(IntHashtableEntry table[], boolean keys) {
333: this .table = table;
334: this .keys = keys;
335: this .index = table.length;
336: }
337:
338: public boolean hasMoreElements() {
339: if (entry != null)
340: return true;
341: while (index-- > 0)
342: if ((entry = table[index]) != null)
343: return true;
344: return false;
345: }
346:
347: public Object nextElement() {
348: if (entry == null)
349: while ((index-- > 0) && ((entry = table[index]) == null))
350: ;
351: if (entry != null) {
352: IntHashtableEntry e = entry;
353: entry = e.next;
354: return keys ? new Integer(e.key) : e.value;
355: }
356: throw new NoSuchElementException("IntHashtableEnumerator");
357: }
358: }
|