KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > osgi > framework > util > KeyedHashSet


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  * IBM Corporation - initial API and implementation
10  *******************************************************************************/

11 package org.eclipse.osgi.framework.util;
12
13 import java.util.Iterator JavaDoc;
14 import java.util.NoSuchElementException JavaDoc;
15
16 /**
17  * A set data structure which only accepts {@link KeyedElement} objects as elements of the set.
18  * Unlike typical set implementations this set requires each element to provide its own key. This helps
19  * reduce the overhead of storing the keys of each individual element<p>
20  * This class in not thread safe, clients must ensure synchronization when modifying an object of this type.
21  * @since 3.2
22  */

23 // This class was moved from /org.eclipse.osgi/core/framework/org/eclipse/osgi/framework/internal/core/KeyedHashSet.java
24
public class KeyedHashSet {
25     public static final int MINIMUM_SIZE = 7;
26     int elementCount = 0;
27     KeyedElement[] elements;
28     private boolean replace;
29     private int capacity;
30
31     /**
32      * Constructs an KeyedHashSet which allows elements to be replaced and with the minimum initial capacity.
33      */

34     public KeyedHashSet() {
35         this(MINIMUM_SIZE, true);
36     }
37
38     /**
39      * Constructs an KeyedHashSet with the minimum initial capacity.
40      * @param replace true if this set allows elements to be replaced
41      */

42     public KeyedHashSet(boolean replace) {
43         this(MINIMUM_SIZE, replace);
44     }
45
46     /**
47      * Constructs an KeyedHashSet which allows elements to be replaced.
48      * @param capacity the initial capacity of this set
49      */

50     public KeyedHashSet(int capacity) {
51         this(capacity, true);
52     }
53
54     /**
55      * Constructs an KeyedHashSet
56      * @param capacity the initial capacity of this set
57      * @param replace true if this set allows elements to be replaced
58      */

59     public KeyedHashSet(int capacity, boolean replace) {
60         elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
61         this.replace = replace;
62         this.capacity = capacity;
63     }
64
65     /**
66      * Constructs a new KeyedHashSet and copies to specified KeyedHashSet's contents to the new KeyedHashSet.
67      * @param original the KeyedHashSet to copy
68      */

69     public KeyedHashSet(KeyedHashSet original) {
70         elements = new KeyedElement[original.elements.length];
71         System.arraycopy(original.elements, 0, elements, 0, original.elements.length);
72         elementCount = original.elementCount;
73         replace = original.replace;
74         capacity = original.capacity;
75     }
76
77     /**
78      * Adds an element to this set. If an element with the same key already exists,
79      * replaces it depending on the replace flag.
80      * @return true if the element was added/stored, false otherwise
81      */

82     public boolean add(KeyedElement element) {
83         int hash = hash(element);
84
85         // search for an empty slot at the end of the array
86
for (int i = hash; i < elements.length; i++) {
87             if (elements[i] == null) {
88                 elements[i] = element;
89                 elementCount++;
90                 // grow if necessary
91
if (shouldGrow())
92                     expand();
93                 return true;
94             }
95             if (elements[i].compare(element)) {
96                 if (replace)
97                     elements[i] = element;
98                 return replace;
99             }
100         }
101
102         // search for an empty slot at the beginning of the array
103
for (int i = 0; i < hash - 1; i++) {
104             if (elements[i] == null) {
105                 elements[i] = element;
106                 elementCount++;
107                 // grow if necessary
108
if (shouldGrow())
109                     expand();
110                 return true;
111             }
112             if (elements[i].compare(element)) {
113                 if (replace)
114                     elements[i] = element;
115                 return replace;
116             }
117         }
118
119         // if we didn't find a free slot, then try again with the expanded set
120
expand();
121         return add(element);
122     }
123
124     /**
125      * Adds the specified list of elements to this set. Some elements may not
126      * get added if the replace flag is set.
127      * @param toAdd the list of elements to add to this set.
128      */

129     public void addAll(KeyedElement[] toAdd) {
130         for (int i = 0; i < toAdd.length; i++)
131             add(toAdd[i]);
132     }
133
134     /**
135      * Returns true if the specified element exists in this set.
136      * @param element the requested element
137      * @return true if the specified element exists in this set; false otherwise.
138      */

139     public boolean contains(KeyedElement element) {
140         return get(element) != null;
141     }
142
143     /**
144      * Returns true if an element with the specified key exists in this set.
145      * @param key the key of the requested element
146      * @return true if an element with the specified key exists in this set; false otherwise
147      */

148     public boolean containsKey(Object JavaDoc key) {
149         return getByKey(key) != null;
150     }
151
152     /**
153      * Returns all elements that exist in this set
154      * @return all elements that exist in this set
155      */

156     public KeyedElement[] elements() {
157         return (KeyedElement[]) elements(new KeyedElement[elementCount]);
158     }
159
160     /**
161      * Copies all elements that exist in this set into the specified array. No size
162      * checking is done. If the specified array is to small an ArrayIndexOutOfBoundsException
163      * will be thrown.
164      * @param result the array to copy the existing elements into.
165      * @return the specified array.
166      * @throws ArrayIndexOutOfBoundsException if the specified array is to small.
167      */

168     public Object JavaDoc[] elements(Object JavaDoc[] result) {
169         int j = 0;
170         for (int i = 0; i < elements.length; i++) {
171             KeyedElement element = elements[i];
172             if (element != null)
173                 result[j++] = element;
174         }
175         return result;
176     }
177
178     /**
179      * The array isn't large enough so double its size and rehash
180      * all its current values.
181      */

182     protected void expand() {
183         KeyedElement[] oldElements = elements;
184         elements = new KeyedElement[elements.length * 2];
185
186         int maxArrayIndex = elements.length - 1;
187         for (int i = 0; i < oldElements.length; i++) {
188             KeyedElement element = oldElements[i];
189             if (element != null) {
190                 int hash = hash(element);
191                 while (elements[hash] != null) {
192                     hash++;
193                     if (hash > maxArrayIndex)
194                         hash = 0;
195                 }
196                 elements[hash] = element;
197             }
198         }
199     }
200
201     /**
202      * Returns the element with the specified key, or null if not found.
203      * @param key the requested element's key
204      * @return the element with the specified key, or null if not found.
205      */

206     public KeyedElement getByKey(Object JavaDoc key) {
207         if (elementCount == 0)
208             return null;
209         int hash = keyHash(key);
210
211         // search the last half of the array
212
for (int i = hash; i < elements.length; i++) {
213             KeyedElement element = elements[i];
214             if (element == null)
215                 return null;
216             if (element.getKey().equals(key))
217                 return element;
218         }
219
220         // search the beginning of the array
221
for (int i = 0; i < hash - 1; i++) {
222             KeyedElement element = elements[i];
223             if (element == null)
224                 return null;
225             if (element.getKey().equals(key))
226                 return element;
227         }
228
229         // nothing found so return null
230
return null;
231     }
232
233     /**
234      * Returns the element which compares to the specified element, or null if not found.
235      * @see KeyedElement#compare(KeyedElement)
236      * @param otherElement the requested element
237      * @return the element which compares to the specified element, or null if not found.
238      */

239     public KeyedElement get(KeyedElement otherElement) {
240         if (elementCount == 0)
241             return null;
242         int hash = hash(otherElement);
243
244         // search the last half of the array
245
for (int i = hash; i < elements.length; i++) {
246             KeyedElement element = elements[i];
247             if (element == null)
248                 return null;
249             if (element.compare(otherElement))
250                 return element;
251         }
252
253         // search the beginning of the array
254
for (int i = 0; i < hash - 1; i++) {
255             KeyedElement element = elements[i];
256             if (element == null)
257                 return null;
258             if (element.compare(otherElement))
259                 return element;
260         }
261
262         // nothing found so return null
263
return null;
264     }
265
266     /**
267      * Returns true if this set is empty
268      * @return true if this set is empty
269      */

270     public boolean isEmpty() {
271         return elementCount == 0;
272     }
273
274     /**
275      * The element at the given index has been removed so move
276      * elements to keep the set properly hashed.
277      * @param anIndex the index that has been removed
278      */

279     protected void rehashTo(int anIndex) {
280
281         int target = anIndex;
282         int index = anIndex + 1;
283         if (index >= elements.length)
284             index = 0;
285         KeyedElement element = elements[index];
286         while (element != null) {
287             int hashIndex = hash(element);
288             boolean match;
289             if (index < target)
290                 match = !(hashIndex > target || hashIndex <= index);
291             else
292                 match = !(hashIndex > target && hashIndex <= index);
293             if (match) {
294                 elements[target] = element;
295                 target = index;
296             }
297             index++;
298             if (index >= elements.length)
299                 index = 0;
300             element = elements[index];
301         }
302         elements[target] = null;
303     }
304
305     /**
306      * Removes the element with the specified key
307      * @param key the requested element's key
308      * @return true if an element was removed
309      */

310     public boolean removeByKey(Object JavaDoc key) {
311         if (elementCount == 0)
312             return false;
313         int hash = keyHash(key);
314
315         for (int i = hash; i < elements.length; i++) {
316             KeyedElement element = elements[i];
317             if (element == null)
318                 return false;
319             if (element.getKey().equals(key)) {
320                 rehashTo(i);
321                 elementCount--;
322                 return true;
323             }
324         }
325
326         for (int i = 0; i < hash - 1; i++) {
327             KeyedElement element = elements[i];
328             if (element == null)
329                 return false;
330             if (element.getKey().equals(key)) {
331                 rehashTo(i);
332                 elementCount--;
333                 return true;
334             }
335         }
336
337         return true;
338     }
339
340     /**
341      * Removes the element which compares to the specified element
342      * @param toRemove the requested element to remove
343      * @return true if an element was removed
344      */

345     public boolean remove(KeyedElement toRemove) {
346         if (elementCount == 0)
347             return false;
348
349         int hash = hash(toRemove);
350
351         for (int i = hash; i < elements.length; i++) {
352             KeyedElement element = elements[i];
353             if (element == null)
354                 return false;
355             if (element.compare(toRemove)) {
356                 rehashTo(i);
357                 elementCount--;
358                 return true;
359             }
360         }
361
362         for (int i = 0; i < hash - 1; i++) {
363             KeyedElement element = elements[i];
364             if (element == null)
365                 return false;
366             if (element.compare(toRemove)) {
367                 rehashTo(i);
368                 elementCount--;
369                 return true;
370             }
371         }
372         return false;
373     }
374
375     private int hash(KeyedElement element) {
376         return Math.abs(element.getKeyHashCode()) % elements.length;
377     }
378
379     private int keyHash(Object JavaDoc key) {
380         return Math.abs(key.hashCode()) % elements.length;
381     }
382
383     /**
384      * Removes all of the specified elements from this set
385      * @param toRemove the requested elements to remove
386      */

387     public void removeAll(KeyedElement[] toRemove) {
388         for (int i = 0; i < toRemove.length; i++)
389             remove(toRemove[i]);
390     }
391
392     private boolean shouldGrow() {
393         return elementCount > elements.length * 0.75;
394     }
395
396     /**
397      * Returns the number of elements in this set
398      * @return the number of elements in this set
399      */

400     public int size() {
401         return elementCount;
402     }
403
404     public String JavaDoc toString() {
405         StringBuffer JavaDoc result = new StringBuffer JavaDoc(100);
406         result.append("{"); //$NON-NLS-1$
407
boolean first = true;
408         for (int i = 0; i < elements.length; i++) {
409             if (elements[i] != null) {
410                 if (first)
411                     first = false;
412                 else
413                     result.append(", "); //$NON-NLS-1$
414
result.append(elements[i]);
415             }
416         }
417         result.append("}"); //$NON-NLS-1$
418
return result.toString();
419     }
420
421     /**
422      * Returns the number of collisions this set currently has
423      * @return the number of collisions this set currently has
424      */

425     public int countCollisions() {
426         int result = 0;
427         int lastHash = 0;
428         boolean found = false;
429         for (int i = 0; i < elements.length; i++) {
430             KeyedElement element = elements[i];
431             if (element == null)
432                 found = false;
433             else {
434                 int hash = hash(element);
435                 if (found)
436                     if (lastHash == hash)
437                         result++;
438                     else
439                         found = false;
440                 else {
441                     lastHash = hash;
442                     found = true;
443                 }
444             }
445         }
446         return result;
447     }
448
449     /**
450      * Returns an iterator of elements in this set
451      * @return an iterator of elements in this set
452      */

453     public Iterator JavaDoc iterator() {
454         return new EquinoxSetIterator();
455     }
456
457     class EquinoxSetIterator implements Iterator JavaDoc {
458         private int currentIndex = -1;
459         private int found;
460
461         public boolean hasNext() {
462             return found < elementCount;
463         }
464
465         public Object JavaDoc next() {
466             if (!hasNext())
467                 throw new NoSuchElementException JavaDoc();
468             while (++currentIndex < elements.length)
469                 if (elements[currentIndex] != null) {
470                     found++;
471                     return elements[currentIndex];
472                 }
473             // this would mean we have less elements than we thought
474
throw new NoSuchElementException JavaDoc();
475         }
476
477         public void remove() {
478             // as allowed by the API
479
throw new UnsupportedOperationException JavaDoc();
480         }
481     }
482
483     /**
484      * Clears all elements from this set
485      */

486     public void clear() {
487         elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
488         elementCount = 0;
489     }
490 }
491
Popular Tags