CustomHashtable


1   /*******************************************************************************
2    * Copyright (c) 2000, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     Peter Shipton - original hashtable implementation
10   *     Nick Edgar - added element comparer support
11   *     David Saff (saff@mit.edu) - bug 102632: [JUnit] Support for JUnit 4.
12   *******************************************************************************/
13  
14  package org.eclipse.jdt.internal.junit.runner;
15  
16  import java.util.Enumeration  ;
17  import java.util.NoSuchElementException  ;
18  
19  /**
20   * This is a copy of CustomHashtable from org.eclipse.jface.viewers
21   */
22  /* package */public final class CustomHashtable {
23  
24      /**
25       * HashMapEntry is an internal class which is used to hold the entries of a
26       * Hashtable.
27       */
28      private static class HashMapEntry {
29  
30          Object   key, value;
31  
32          HashMapEntry next;
33  
34          HashMapEntry(Object   theKey, Object   theValue) {
35              key= theKey;
36              value= theValue;
37          }
38          
39          public String   toString() {
40              StringBuffer   buffer= new StringBuffer  ();
41              appendToStringWithCommaNL(buffer);
42              int length= buffer.length();
43              if (length >= 2)
44                  return buffer.substring(0, length - 2);
45              else
46                  return buffer.toString();
47          }
48          
49          private void appendToStringWithCommaNL(StringBuffer   buffer) {
50              CustomHashtable.HashMapEntry hashMapEntry= this;
51              do {
52                  buffer.append(hashMapEntry.key);
53                  buffer.append('=');
54                  buffer.append(hashMapEntry.value);
55                  buffer.append(",\n"); //$NON-NLS-1$
56                  hashMapEntry= hashMapEntry.next;
57              } while (hashMapEntry != null);
58          }
59      }
60  
61      private static final class EmptyEnumerator implements Enumeration   {
62  
63          public boolean hasMoreElements() {
64              return false;
65          }
66  
67          public Object   nextElement() {
68              throw new NoSuchElementException  ();
69          }
70      }
71  
72      private class HashEnumerator implements Enumeration   {
73  
74          boolean key;
75  
76          int start;
77  
78          HashMapEntry entry;
79  
80          HashEnumerator(boolean isKey) {
81              key= isKey;
82              start= firstSlot;
83          }
84  
85          public boolean hasMoreElements() {
86              if (entry != null)
87                  return true;
88              while (start <= lastSlot)
89                  if (elementData[start++] != null) {
90                      entry= elementData[start - 1];
91                      return true;
92                  }
93              return false;
94          }
95  
96          public Object   nextElement() {
97              if (hasMoreElements()) {
98                  Object   result= key ? entry.key : entry.value;
99                  entry= entry.next;
100                 return result;
101             } else
102                 throw new NoSuchElementException  ();
103         }
104     }
105 
106     transient int elementCount;
107 
108     transient HashMapEntry[] elementData;
109 
110     private float loadFactor;
111 
112     private int threshold;
113 
114     transient int firstSlot= 0;
115 
116     transient int lastSlot= - 1;
117 
118     transient private IElementComparer comparer;
119 
120     private static final EmptyEnumerator emptyEnumerator= new EmptyEnumerator();
121 
122     /**
123      * The default capacity used when not specified in the constructor.
124      */
125     public static final int DEFAULT_CAPACITY= 13;
126 
127     /**
128      * Constructs a new Hashtable using the default capacity and load factor.
129      */
130     public CustomHashtable() {
131         this(13);
132     }
133 
134     /**
135      * Constructs a new Hashtable using the specified capacity and the default
136      * load factor.
137      * 
138      * @param capacity the initial capacity
139      */
140     public CustomHashtable(int capacity) {
141         this(capacity, null);
142     }
143 
144     /**
145      * Constructs a new hash table with the default capacity and the given
146      * element comparer.
147      * 
148      * @param comparer the element comparer to use to compare keys and obtain
149      *        hash codes for keys, or <code>null</code> to use the normal
150      *        <code>equals</code> and <code>hashCode</code> methods
151      */
152     public CustomHashtable(IElementComparer comparer) {
153         this(DEFAULT_CAPACITY, comparer);
154     }
155 
156     /**
157      * Constructs a new hash table with the given capacity and the given element
158      * comparer.
159      * 
160      * @param capacity the maximum number of elements that can be added without
161      *        rehashing
162      * @param comparer the element comparer to use to compare keys and obtain
163      *        hash codes for keys, or <code>null</code> to use the normal
164      *        <code>equals</code> and <code>hashCode</code> methods
165      */
166     public CustomHashtable(int capacity, IElementComparer comparer) {
167         if (capacity >= 0) {
168             elementCount= 0;
169             elementData= new HashMapEntry[capacity == 0 ? 1 : capacity];
170             firstSlot= elementData.length;
171             loadFactor= 0.75f;
172             computeMaxSize();
173         } else
174             throw new IllegalArgumentException  ();
175         this.comparer= comparer;
176     }
177 
178     /**
179      * Constructs a new hash table with enough capacity to hold all keys in the
180      * given hash table, then adds all key/value pairs in the given hash table
181      * to the new one, using the given element comparer.
182      * 
183      * @param table the original hash table
184      * @param comparer the element comparer to use to compare keys and obtain
185      *        hash codes for keys, or <code>null</code> to use the normal
186      *        <code>equals</code> and <code>hashCode</code> methods
187      */
188     public CustomHashtable(CustomHashtable table, IElementComparer comparer) {
189         this(table.size() * 2, comparer);
190         for (int i= table.elementData.length; --i >= 0;) {
191             HashMapEntry entry= table.elementData[i];
192             while (entry != null) {
193                 put(entry.key, entry.value);
194                 entry= entry.next;
195             }
196         }
197     }
198 
199     private void computeMaxSize() {
200         threshold= (int) (elementData.length * loadFactor);
201     }
202 
203     /**
204      * Answers if this Hashtable contains the specified object as a key of one
205      * of the key/value pairs.
206      * 
207      * @param key the object to look for as a key in this Hashtable
208      * @return true if object is a key in this Hashtable, false otherwise
209      */
210     public boolean containsKey(Object   key) {
211         return getEntry(key) != null;
212     }
213 
214     /**
215      * Answers an Enumeration on the values of this Hashtable. The results of
216      * the Enumeration may be affected if the contents of this Hashtable are
217      * modified.
218      * 
219      * @return an Enumeration of the values of this Hashtable
220      */
221     public Enumeration   elements() {
222         if (elementCount == 0)
223             return emptyEnumerator;
224         return new HashEnumerator(false);
225     }
226 
227     /**
228      * Answers the value associated with the specified key in this Hashtable.
229      * 
230      * @param key the key of the value returned
231      * @return the value associated with the specified key, null if the
232      *         specified key 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             entry= entry.next;
241         }
242         return null;
243     }
244 
245     /**
246      * Answers the stored key that is equal to the specified key.
247      * 
248      * @param key the key to search
249      * @return the stored key, or null if the specified key does not exist
250      */
251     public Object   getKey(Object   key) {
252         int index= (hashCode(key) & 0x7FFFFFFF) % elementData.length;
253         HashMapEntry entry= elementData[index];
254         while (entry != null) {
255             if (keyEquals(key, entry.key))
256                 return entry.key;
257             entry= entry.next;
258         }
259         return null;
260     }
261 
262     private HashMapEntry getEntry(Object   key) {
263         int index= (hashCode(key) & 0x7FFFFFFF) % elementData.length;
264         HashMapEntry entry= elementData[index];
265         while (entry != null) {
266             if (keyEquals(key, entry.key))
267                 return entry;
268             entry= entry.next;
269         }
270         return null;
271     }
272 
273     /**
274      * Answers the hash code for the given key.
275      */
276     private int hashCode(Object   key) {
277         if (comparer == null)
278             return key.hashCode();
279         else
280             return comparer.hashCode(key);
281     }
282 
283     /**
284      * Compares two keys for equality.
285      */
286     private boolean keyEquals(Object   a, Object   b) {
287         if (comparer == null)
288             return a.equals(b);
289         else
290             return comparer.equals(a, b);
291     }
292 
293     /**
294      * Answers an Enumeration on the keys of this Hashtable. The results of the
295      * Enumeration may be affected if the contents of this Hashtable are
296      * modified.
297      * 
298      * @return an Enumeration of the keys of this Hashtable
299      */
300     public Enumeration   keys() {
301         if (elementCount == 0)
302             return emptyEnumerator;
303         return new HashEnumerator(true);
304     }
305 
306     /**
307      * Associate the specified value with the specified key in this Hashtable.
308      * If the key already exists, the old value is replaced. The key and value
309      * cannot be null.
310      * 
311      * @param key the key to add
312      * @param value the value to add
313      * @return the old value associated with the specified key, null if the key
314      *         did not exist
315      */
316     public Object   put(Object   key, Object   value) {
317         if (key != null && value != null) {
318             int index= (hashCode(key) & 0x7FFFFFFF) % elementData.length;
319             HashMapEntry entry= elementData[index];
320             while (entry != null && ! keyEquals(key, entry.key))
321                 entry= entry.next;
322             if (entry == null) {
323                 if (++elementCount > threshold) {
324                     rehash();
325                     index= (hashCode(key) & 0x7FFFFFFF) % elementData.length;
326                 }
327                 if (index < firstSlot)
328                     firstSlot= index;
329                 if (index > lastSlot)
330                     lastSlot= index;
331                 entry= new HashMapEntry(key, value);
332                 entry.next= elementData[index];
333                 elementData[index]= entry;
334                 return null;
335             }
336             Object   result= entry.value;
337             entry.key= key; // important to avoid hanging onto keys that are
338                             // equal but "old" -- see bug 30607
339             entry.value= value;
340             return result;
341         } else
342             throw new NullPointerException  ();
343     }
344 
345     /**
346      * Increases the capacity of this Hashtable. This method is sent when the
347      * size of this Hashtable exceeds the load factor.
348      */
349     private void rehash() {
350         int length= elementData.length << 1;
351         if (length == 0)
352             length= 1;
353         firstSlot= length;
354         lastSlot= - 1;
355         HashMapEntry[] newData= new HashMapEntry[length];
356         for (int i= elementData.length; --i >= 0;) {
357             HashMapEntry entry= elementData[i];
358             while (entry != null) {
359                 int index= (hashCode(entry.key) & 0x7FFFFFFF) % length;
360                 if (index < firstSlot)
361                     firstSlot= index;
362                 if (index > lastSlot)
363                     lastSlot= index;
364                 HashMapEntry next= entry.next;
365                 entry.next= newData[index];
366                 newData[index]= entry;
367                 entry= next;
368             }
369         }
370         elementData= newData;
371         computeMaxSize();
372     }
373 
374     /**
375      * Remove the key/value pair with the specified key from this Hashtable.
376      * 
377      * @param key the key to remove
378      * @return the value associated with the specified key, null if the
379      *         specified key did not exist
380      */
381     public Object   remove(Object   key) {
382         HashMapEntry last= null;
383         int index= (hashCode(key) & 0x7FFFFFFF) % elementData.length;
384         HashMapEntry entry= elementData[index];
385         while (entry != null && ! keyEquals(key, entry.key)) {
386             last= entry;
387             entry= entry.next;
388         }
389         if (entry != null) {
390             if (last == null)
391                 elementData[index]= entry.next;
392             else
393                 last.next= entry.next;
394             elementCount--;
395             return entry.value;
396         }
397         return null;
398     }
399 
400     /**
401      * Answers the number of key/value pairs in this Hashtable.
402      * 
403      * @return the number of key/value pairs in this Hashtable
404      */
405     public int size() {
406         return elementCount;
407     }
408 
409     /**
410      * Answers the string representation of this Hashtable.
411      * 
412      * @return the string representation of this Hashtable
413      */
414     public String   toString() {
415         if (size() == 0)
416             return "{}"; //$NON-NLS-1$
417 
418         StringBuffer   buffer= new StringBuffer  ();
419         buffer.append('{');
420         for (int i= elementData.length; --i >= 0;) {
421             HashMapEntry entry= elementData[i];
422             if (entry != null)
423                 entry.appendToStringWithCommaNL(buffer);
424         }
425         // Remove the last ", "
426         if (elementCount > 0)
427             buffer.setLength(buffer.length() - 2);
428         buffer.append('}');
429         return buffer.toString();
430     }
431 }
432
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags