001: /*******************************************************************************
002: * Copyright (c) 2000, 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * Peter Shipton - original hashtable implementation
010: * Nick Edgar - added element comparer support
011: *******************************************************************************/package org.eclipse.jface.viewers;
012:
013: import java.util.Enumeration;
014: import java.util.NoSuchElementException;
015:
016: /**
017: * CustomHashtable associates keys with values. Keys and values cannot be null.
018: * The size of the Hashtable is the number of key/value pairs it contains.
019: * The capacity is the number of key/value pairs the Hashtable can hold.
020: * The load factor is a float value which determines how full the Hashtable
021: * gets before expanding the capacity. If the load factor of the Hashtable
022: * is exceeded, the capacity is doubled.
023: * <p>
024: * CustomHashtable allows a custom comparator and hash code provider.
025: */
026: /* package */final class CustomHashtable {
027:
028: /**
029: * HashMapEntry is an internal class which is used to hold the entries of a Hashtable.
030: */
031: private static class HashMapEntry {
032: Object key, value;
033:
034: HashMapEntry next;
035:
036: HashMapEntry(Object theKey, Object theValue) {
037: key = theKey;
038: value = theValue;
039: }
040: }
041:
042: private static final class EmptyEnumerator implements Enumeration {
043: public boolean hasMoreElements() {
044: return false;
045: }
046:
047: public Object nextElement() {
048: throw new NoSuchElementException();
049: }
050: }
051:
052: private class HashEnumerator implements Enumeration {
053: boolean key;
054:
055: int start;
056:
057: HashMapEntry entry;
058:
059: HashEnumerator(boolean isKey) {
060: key = isKey;
061: start = firstSlot;
062: }
063:
064: public boolean hasMoreElements() {
065: if (entry != null) {
066: return true;
067: }
068: while (start <= lastSlot) {
069: if (elementData[start++] != null) {
070: entry = elementData[start - 1];
071: return true;
072: }
073: }
074: return false;
075: }
076:
077: public Object nextElement() {
078: if (hasMoreElements()) {
079: Object result = key ? entry.key : entry.value;
080: entry = entry.next;
081: return result;
082: } else {
083: throw new NoSuchElementException();
084: }
085: }
086: }
087:
088: transient int elementCount;
089:
090: transient HashMapEntry[] elementData;
091:
092: private float loadFactor;
093:
094: private int threshold;
095:
096: transient int firstSlot = 0;
097:
098: transient int lastSlot = -1;
099:
100: transient private IElementComparer comparer;
101:
102: private static final EmptyEnumerator emptyEnumerator = new EmptyEnumerator();
103:
104: /**
105: * The default capacity used when not specified in the constructor.
106: */
107: public static final int DEFAULT_CAPACITY = 13;
108:
109: /**
110: * Constructs a new Hashtable using the default capacity
111: * and load factor.
112: */
113: public CustomHashtable() {
114: this (13);
115: }
116:
117: /**
118: * Constructs a new Hashtable using the specified capacity
119: * and the default load factor.
120: *
121: * @param capacity the initial capacity
122: */
123: public CustomHashtable(int capacity) {
124: this (capacity, null);
125: }
126:
127: /**
128: * Constructs a new hash table with the default capacity and the given
129: * element comparer.
130: *
131: * @param comparer the element comparer to use to compare keys and obtain
132: * hash codes for keys, or <code>null</code> to use the normal
133: * <code>equals</code> and <code>hashCode</code> methods
134: */
135: public CustomHashtable(IElementComparer comparer) {
136: this (DEFAULT_CAPACITY, comparer);
137: }
138:
139: /**
140: * Constructs a new hash table with the given capacity and the given
141: * element comparer.
142: *
143: * @param capacity the maximum number of elements that can be added without
144: * rehashing
145: * @param comparer the element comparer to use to compare keys and obtain
146: * hash codes for keys, or <code>null</code> to use the normal
147: * <code>equals</code> and <code>hashCode</code> methods
148: */
149: public CustomHashtable(int capacity, IElementComparer comparer) {
150: if (capacity >= 0) {
151: elementCount = 0;
152: elementData = new HashMapEntry[capacity == 0 ? 1 : capacity];
153: firstSlot = elementData.length;
154: loadFactor = 0.75f;
155: computeMaxSize();
156: } else {
157: throw new IllegalArgumentException();
158: }
159: this .comparer = comparer;
160: }
161:
162: /**
163: * Constructs a new hash table with enough capacity to hold all keys in the
164: * given hash table, then adds all key/value pairs in the given hash table
165: * to the new one, using the given element comparer.
166: * @param table the original hash table to copy from
167: *
168: * @param comparer the element comparer to use to compare keys and obtain
169: * hash codes for keys, or <code>null</code> to use the normal
170: * <code>equals</code> and <code>hashCode</code> methods
171: */
172: public CustomHashtable(CustomHashtable table,
173: IElementComparer comparer) {
174: this (table.size() * 2, comparer);
175: for (int i = table.elementData.length; --i >= 0;) {
176: HashMapEntry entry = table.elementData[i];
177: while (entry != null) {
178: put(entry.key, entry.value);
179: entry = entry.next;
180: }
181: }
182: }
183:
184: /**
185: * Returns the element comparer used to compare keys and to obtain
186: * hash codes for keys, or <code>null</code> if no comparer has been
187: * provided.
188: *
189: * @return the element comparer or <code>null</code>
190: *
191: * @since 3.2
192: */
193: public IElementComparer getComparer() {
194: return comparer;
195: }
196:
197: private void computeMaxSize() {
198: threshold = (int) (elementData.length * loadFactor);
199: }
200:
201: /**
202: * Answers if this Hashtable contains the specified object as a key
203: * of one of the key/value pairs.
204: *
205: * @param key the object to look for as a key in this Hashtable
206: * @return true if object is a key in this Hashtable, false otherwise
207: */
208: public boolean containsKey(Object key) {
209: return getEntry(key) != null;
210: }
211:
212: /**
213: * Answers an Enumeration on the values of this Hashtable. The
214: * results of the Enumeration may be affected if the contents
215: * of this Hashtable are modified.
216: *
217: * @return an Enumeration of the values of this Hashtable
218: */
219: public Enumeration elements() {
220: if (elementCount == 0) {
221: return emptyEnumerator;
222: }
223: return new HashEnumerator(false);
224: }
225:
226: /**
227: * Answers the value associated with the specified key in
228: * this Hashtable.
229: *
230: * @param key the key of the value returned
231: * @return the value associated with the specified key, null if the specified key
232: * does not exist
233: */
234: public Object get(Object key) {
235: int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
236: HashMapEntry entry = elementData[index];
237: while (entry != null) {
238: if (keyEquals(key, entry.key)) {
239: return entry.value;
240: }
241: entry = entry.next;
242: }
243: return null;
244: }
245:
246: private HashMapEntry getEntry(Object key) {
247: int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
248: HashMapEntry entry = elementData[index];
249: while (entry != null) {
250: if (keyEquals(key, entry.key)) {
251: return entry;
252: }
253: entry = entry.next;
254: }
255: return null;
256: }
257:
258: /**
259: * Answers the hash code for the given key.
260: */
261: private int hashCode(Object key) {
262: if (comparer == null) {
263: return key.hashCode();
264: } else {
265: return comparer.hashCode(key);
266: }
267: }
268:
269: /**
270: * Compares two keys for equality.
271: */
272: private boolean keyEquals(Object a, Object b) {
273: if (comparer == null) {
274: return a.equals(b);
275: } else {
276: return comparer.equals(a, b);
277: }
278: }
279:
280: /**
281: * Answers an Enumeration on the keys of this Hashtable. The
282: * results of the Enumeration may be affected if the contents
283: * of this Hashtable are modified.
284: *
285: * @return an Enumeration of the keys of this Hashtable
286: */
287: public Enumeration keys() {
288: if (elementCount == 0) {
289: return emptyEnumerator;
290: }
291: return new HashEnumerator(true);
292: }
293:
294: /**
295: * Associate the specified value with the specified key in this Hashtable.
296: * If the key already exists, the old value is replaced. The key and value
297: * cannot be null.
298: *
299: * @param key the key to add
300: * @param value the value to add
301: * @return the old value associated with the specified key, null if the key did
302: * not exist
303: */
304: public Object put(Object key, Object value) {
305: if (key != null && value != null) {
306: int index = (hashCode(key) & 0x7FFFFFFF)
307: % elementData.length;
308: HashMapEntry entry = elementData[index];
309: while (entry != null && !keyEquals(key, entry.key)) {
310: entry = entry.next;
311: }
312: if (entry == null) {
313: if (++elementCount > threshold) {
314: rehash();
315: index = (hashCode(key) & 0x7FFFFFFF)
316: % elementData.length;
317: }
318: if (index < firstSlot) {
319: firstSlot = index;
320: }
321: if (index > lastSlot) {
322: lastSlot = index;
323: }
324: entry = new HashMapEntry(key, value);
325: entry.next = elementData[index];
326: elementData[index] = entry;
327: return null;
328: }
329: Object result = entry.value;
330: entry.key = key; // important to avoid hanging onto keys that are equal but "old" -- see bug 30607
331: entry.value = value;
332: return result;
333: } else {
334: throw new NullPointerException();
335: }
336: }
337:
338: /**
339: * Increases the capacity of this Hashtable. This method is sent when
340: * the size of this Hashtable exceeds the load factor.
341: */
342: private void rehash() {
343: int length = elementData.length << 1;
344: if (length == 0) {
345: length = 1;
346: }
347: firstSlot = length;
348: lastSlot = -1;
349: HashMapEntry[] newData = new HashMapEntry[length];
350: for (int i = elementData.length; --i >= 0;) {
351: HashMapEntry entry = elementData[i];
352: while (entry != null) {
353: int index = (hashCode(entry.key) & 0x7FFFFFFF) % length;
354: if (index < firstSlot) {
355: firstSlot = index;
356: }
357: if (index > lastSlot) {
358: lastSlot = index;
359: }
360: HashMapEntry next = entry.next;
361: entry.next = newData[index];
362: newData[index] = entry;
363: entry = next;
364: }
365: }
366: elementData = newData;
367: computeMaxSize();
368: }
369:
370: /**
371: * Remove the key/value pair with the specified key from this Hashtable.
372: *
373: * @param key the key to remove
374: * @return the value associated with the specified key, null if the specified key
375: * did not exist
376: */
377: public Object remove(Object key) {
378: HashMapEntry last = null;
379: int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
380: HashMapEntry entry = elementData[index];
381: while (entry != null && !keyEquals(key, entry.key)) {
382: last = entry;
383: entry = entry.next;
384: }
385: if (entry != null) {
386: if (last == null) {
387: elementData[index] = entry.next;
388: } else {
389: last.next = entry.next;
390: }
391: elementCount--;
392: return entry.value;
393: }
394: return null;
395: }
396:
397: /**
398: * Answers the number of key/value pairs in this Hashtable.
399: *
400: * @return the number of key/value pairs in this Hashtable
401: */
402: public int size() {
403: return elementCount;
404: }
405:
406: /**
407: * Answers the string representation of this Hashtable.
408: *
409: * @return the string representation of this Hashtable
410: */
411: public String toString() {
412: if (size() == 0) {
413: return "{}"; //$NON-NLS-1$
414: }
415:
416: StringBuffer buffer = new StringBuffer();
417: buffer.append('{');
418: for (int i = elementData.length; --i >= 0;) {
419: HashMapEntry entry = elementData[i];
420: while (entry != null) {
421: buffer.append(entry.key);
422: buffer.append('=');
423: buffer.append(entry.value);
424: buffer.append(", "); //$NON-NLS-1$
425: entry = entry.next;
426: }
427: }
428: // Remove the last ", "
429: if (elementCount > 0) {
430: buffer.setLength(buffer.length() - 2);
431: }
432: buffer.append('}');
433: return buffer.toString();
434: }
435: }
|