KeyedHashSet


1   /*******************************************************************************
2    * Copyright (c) 2000, 2005 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.core.internal.utils;
12  
13  
14  /** Adapted from a homonym class in org.eclipse.osgi. A hash table of 
15   * <code>KeyedElement</code>s.
16   */
17  
18  public class KeyedHashSet {
19      public interface KeyedElement {
20  
21          public boolean compare(KeyedElement other);
22  
23          public Object   getKey();
24  
25          public int getKeyHashCode();
26      }
27  
28      protected static final int MINIMUM_SIZE = 7;
29      private int capacity;
30      protected int elementCount = 0;
31      protected KeyedElement[] elements;
32      protected boolean replace;
33  
34      public KeyedHashSet(int capacity) {
35          this(capacity, true);
36      }
37  
38      public KeyedHashSet(int capacity, boolean replace) {
39          elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
40          this.replace = replace;
41          this.capacity = capacity;
42      }
43  
44      /**
45       * Adds an element to this set. If an element with the same key already exists,
46       * replaces it depending on the replace flag.
47       * @return true if the element was added/stored, false otherwise
48       */
49      public boolean add(KeyedElement element) {
50          int hash = hash(element);
51  
52          // search for an empty slot at the end of the array
53          for (int i = hash; i < elements.length; i++) {
54              if (elements[i] == null) {
55                  elements[i] = element;
56                  elementCount++;
57                  // grow if necessary
58                  if (shouldGrow())
59                      expand();
60                  return true;
61              }
62              if (elements[i].compare(element)) {
63                  if (replace)
64                      elements[i] = element;
65                  return replace;
66              }
67          }
68  
69          // search for an empty slot at the beginning of the array
70          for (int i = 0; i < hash - 1; i++) {
71              if (elements[i] == null) {
72                  elements[i] = element;
73                  elementCount++;
74                  // grow if necessary
75                  if (shouldGrow())
76                      expand();
77                  return true;
78              }
79              if (elements[i].compare(element)) {
80                  if (replace)
81                      elements[i] = element;
82                  return replace;
83              }
84          }
85  
86          // if we didn't find a free slot, then try again with the expanded set
87          expand();
88          return add(element);
89      }
90  
91      public void clear() {
92          elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
93          elementCount = 0;
94      }
95  
96      /**
97       * The array isn't large enough so double its size and rehash
98       * all its current values.
99       */
100     protected void expand() {
101         KeyedElement[] oldElements = elements;
102         elements = new KeyedElement[elements.length * 2];
103 
104         int maxArrayIndex = elements.length - 1;
105         for (int i = 0; i < oldElements.length; i++) {
106             KeyedElement element = oldElements[i];
107             if (element != null) {
108                 int hash = hash(element);
109                 while (elements[hash] != null) {
110                     hash++;
111                     if (hash > maxArrayIndex)
112                         hash = 0;
113                 }
114                 elements[hash] = element;
115             }
116         }
117     }
118 
119     /**
120      * Returns the set element with the given id, or null
121      * if not found.
122      */
123     public KeyedElement getByKey(Object   key) {
124         if (elementCount == 0)
125             return null;
126         int hash = keyHash(key);
127 
128         // search the last half of the array
129         for (int i = hash; i < elements.length; i++) {
130             KeyedElement element = elements[i];
131             if (element == null)
132                 return null;
133             if (element.getKey().equals(key))
134                 return element;
135         }
136 
137         // search the beginning of the array
138         for (int i = 0; i < hash - 1; i++) {
139             KeyedElement element = elements[i];
140             if (element == null)
141                 return null;
142             if (element.getKey().equals(key))
143                 return element;
144         }
145 
146         // nothing found so return null
147         return null;
148     }
149 
150     private int hash(KeyedElement key) {
151         return Math.abs(key.getKeyHashCode()) % elements.length;
152     }
153 
154     private int keyHash(Object   key) {
155         return Math.abs(key.hashCode()) % elements.length;
156     }
157 
158     /**
159      * The element at the given index has been removed so move
160      * elements to keep the set properly hashed.
161      */
162     protected void rehashTo(int anIndex) {
163 
164         int target = anIndex;
165         int index = anIndex + 1;
166         if (index >= elements.length)
167             index = 0;
168         KeyedElement element = elements[index];
169         while (element != null) {
170             int hashIndex = hash(element);
171             boolean match;
172             if (index < target)
173                 match = !(hashIndex > target || hashIndex <= index);
174             else
175                 match = !(hashIndex > target && hashIndex <= index);
176             if (match) {
177                 elements[target] = element;
178                 target = index;
179             }
180             index++;
181             if (index >= elements.length)
182                 index = 0;
183             element = elements[index];
184         }
185         elements[target] = null;
186     }
187 
188     public boolean remove(KeyedElement toRemove) {
189         if (elementCount == 0)
190             return false;
191 
192         int hash = hash(toRemove);
193 
194         for (int i = hash; i < elements.length; i++) {
195             KeyedElement element = elements[i];
196             if (element == null)
197                 return false;
198             if (element.compare(toRemove)) {
199                 rehashTo(i);
200                 elementCount--;
201                 return true;
202             }
203         }
204 
205         for (int i = 0; i < hash - 1; i++) {
206             KeyedElement element = elements[i];
207             if (element == null)
208                 return false;
209             if (element.compare(toRemove)) {
210                 rehashTo(i);
211                 elementCount--;
212                 return true;
213             }
214         }
215         return false;
216     }
217 
218     private boolean shouldGrow() {
219         return elementCount > elements.length * 0.75;
220     }
221 
222     public int size() {
223         return elementCount;
224     }
225 
226     public String   toString() {
227         StringBuffer   result = new StringBuffer  (100);
228         result.append('{');
229         boolean first = true;
230         for (int i = 0; i < elements.length; i++) {
231             if (elements[i] != null) {
232                 if (first)
233                     first = false;
234                 else
235                     result.append(", "); //$NON-NLS-1$
236                 result.append(elements[i]);
237             }
238         }
239         result.append('}');
240         return result.toString();
241     }
242 }
243
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags