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  ;
14  import java.util.NoSuchElementException  ;
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   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  [] elements(Object  [] 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   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   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   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   toString() {
405         StringBuffer   result = new StringBuffer  (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   iterator() {
454         return new EquinoxSetIterator();
455     }
456 
457     class EquinoxSetIterator implements Iterator   {
458         private int currentIndex = -1;
459         private int found;
460 
461         public boolean hasNext() {
462             return found < elementCount;
463         }
464 
465         public Object   next() {
466             if (!hasNext())
467                 throw new NoSuchElementException  ();
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  ();
475         }
476 
477         public void remove() {
478             // as allowed by the API
479             throw new UnsupportedOperationException  ();
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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags