|
1
11 package org.eclipse.osgi.framework.internal.core;
12
13 import java.util.Iterator  ;
14 import java.util.NoSuchElementException ;
15
16 public class KeyedHashSet {
17 protected static final int MINIMUM_SIZE = 7;
18 protected int elementCount = 0;
19 protected KeyedElement[] elements;
20 protected boolean replace;
21 private int capacity;
22
23 public KeyedHashSet() {
24 this(MINIMUM_SIZE, true);
25 }
26
27 public KeyedHashSet(boolean replace) {
28 this(MINIMUM_SIZE, replace);
29 }
30
31 public KeyedHashSet(int capacity) {
32 this(capacity, true);
33 }
34
35 public KeyedHashSet(int capacity, boolean replace) {
36 elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
37 this.replace = replace;
38 this.capacity = capacity;
39 }
40
41 public KeyedHashSet(KeyedHashSet original) {
42 elements = new KeyedElement[original.elements.length];
43 System.arraycopy(original.elements, 0, elements, 0, original.elements.length);
44 elementCount = original.elementCount;
45 replace = original.replace;
46 capacity = original.capacity;
47 }
48
49
54 public boolean add(KeyedElement element) {
55 int hash = hash(element);
56
57 for (int i = hash; i < elements.length; i++) {
59 if (elements[i] == null) {
60 elements[i] = element;
61 elementCount++;
62 if (shouldGrow())
64 expand();
65 return true;
66 }
67 if (elements[i].compare(element)) {
68 if (replace)
69 elements[i] = element;
70 return replace;
71 }
72 }
73
74 for (int i = 0; i < hash - 1; i++) {
76 if (elements[i] == null) {
77 elements[i] = element;
78 elementCount++;
79 if (shouldGrow())
81 expand();
82 return true;
83 }
84 if (elements[i].compare(element)) {
85 if (replace)
86 elements[i] = element;
87 return replace;
88 }
89 }
90
91 expand();
93 return add(element);
94 }
95
96 public void addAll(KeyedElement[] toAdd) {
97 for (int i = 0; i < toAdd.length; i++)
98 add(toAdd[i]);
99 }
100
101 public boolean contains(KeyedElement element) {
102 return get(element) != null;
103 }
104
105 public boolean containsKey(Object key) {
106 return getByKey(key) != null;
107 }
108
109 public KeyedElement[] elements() {
110 return (KeyedElement[]) elements(new KeyedElement[elementCount]);
111 }
112
113 public Object [] elements(Object [] result) {
114 int j = 0;
115 for (int i = 0; i < elements.length; i++) {
116 KeyedElement element = elements[i];
117 if (element != null)
118 result[j++] = element;
119 }
120 return result;
121 }
122
123
127 protected void expand() {
128 KeyedElement[] oldElements = elements;
129 elements = new KeyedElement[elements.length * 2];
130
131 int maxArrayIndex = elements.length - 1;
132 for (int i = 0; i < oldElements.length; i++) {
133 KeyedElement element = oldElements[i];
134 if (element != null) {
135 int hash = hash(element);
136 while (elements[hash] != null) {
137 hash++;
138 if (hash > maxArrayIndex)
139 hash = 0;
140 }
141 elements[hash] = element;
142 }
143 }
144 }
145
146
150 public KeyedElement getByKey(Object key) {
151 if (elementCount == 0)
152 return null;
153 int hash = keyHash(key);
154
155 for (int i = hash; i < elements.length; i++) {
157 KeyedElement element = elements[i];
158 if (element == null)
159 return null;
160 if (element.getKey().equals(key))
161 return element;
162 }
163
164 for (int i = 0; i < hash - 1; i++) {
166 KeyedElement element = elements[i];
167 if (element == null)
168 return null;
169 if (element.getKey().equals(key))
170 return element;
171 }
172
173 return null;
175 }
176
177
181 public KeyedElement get(KeyedElement key) {
182 if (elementCount == 0)
183 return null;
184 int hash = hash(key);
185
186 for (int i = hash; i < elements.length; i++) {
188 KeyedElement element = elements[i];
189 if (element == null)
190 return null;
191 if (element.compare(key))
192 return element;
193 }
194
195 for (int i = 0; i < hash - 1; i++) {
197 KeyedElement element = elements[i];
198 if (element == null)
199 return null;
200 if (element.compare(key))
201 return element;
202 }
203
204 return null;
206 }
207
208 public boolean isEmpty() {
209 return elementCount == 0;
210 }
211
212
216 protected void rehashTo(int anIndex) {
217
218 int target = anIndex;
219 int index = anIndex + 1;
220 if (index >= elements.length)
221 index = 0;
222 KeyedElement element = elements[index];
223 while (element != null) {
224 int hashIndex = hash(element);
225 boolean match;
226 if (index < target)
227 match = !(hashIndex > target || hashIndex <= index);
228 else
229 match = !(hashIndex > target && hashIndex <= index);
230 if (match) {
231 elements[target] = element;
232 target = index;
233 }
234 index++;
235 if (index >= elements.length)
236 index = 0;
237 element = elements[index];
238 }
239 elements[target] = null;
240 }
241
242 public boolean removeByKey(Object key) {
243 if (elementCount == 0)
244 return false;
245 int hash = keyHash(key);
246
247 for (int i = hash; i < elements.length; i++) {
248 KeyedElement element = elements[i];
249 if (element == null)
250 return false;
251 if (element.getKey().equals(key)) {
252 rehashTo(i);
253 elementCount--;
254 return true;
255 }
256 }
257
258 for (int i = 0; i < hash - 1; i++) {
259 KeyedElement element = elements[i];
260 if (element == null)
261 return false;
262 if (element.getKey().equals(key)) {
263 rehashTo(i);
264 elementCount--;
265 return true;
266 }
267 }
268
269 return true;
270 }
271
272 public boolean remove(KeyedElement toRemove) {
273 if (elementCount == 0)
274 return false;
275
276 int hash = hash(toRemove);
277
278 for (int i = hash; i < elements.length; i++) {
279 KeyedElement element = elements[i];
280 if (element == null)
281 return false;
282 if (element.compare(toRemove)) {
283 rehashTo(i);
284 elementCount--;
285 return true;
286 }
287 }
288
289 for (int i = 0; i < hash - 1; i++) {
290 KeyedElement element = elements[i];
291 if (element == null)
292 return false;
293 if (element.compare(toRemove)) {
294 rehashTo(i);
295 elementCount--;
296 return true;
297 }
298 }
299 return false;
300 }
301
302 private int hash(KeyedElement element) {
303 return Math.abs(element.getKeyHashCode()) % elements.length;
304 }
305
306 private int keyHash(Object key) {
307 return Math.abs(key.hashCode()) % elements.length;
308 }
309
310 public void removeAll(KeyedElement[] toRemove) {
311 for (int i = 0; i < toRemove.length; i++)
312 remove(toRemove[i]);
313 }
314
315 private boolean shouldGrow() {
316 return elementCount > elements.length * 0.75;
317 }
318
319 public int size() {
320 return elementCount;
321 }
322
323 public String toString() {
324 StringBuffer result = new StringBuffer (100);
325 result.append("{"); boolean first = true;
327 for (int i = 0; i < elements.length; i++) {
328 if (elements[i] != null) {
329 if (first)
330 first = false;
331 else
332 result.append(", "); result.append(elements[i]);
334 }
335 }
336 result.append("}"); return result.toString();
338 }
339
340 public int countCollisions() {
341 int result = 0;
342 int lastHash = 0;
343 boolean found = false;
344 for (int i = 0; i < elements.length; i++) {
345 KeyedElement element = elements[i];
346 if (element == null)
347 found = false;
348 else {
349 int hash = hash(element);
350 if (found)
351 if (lastHash == hash)
352 result++;
353 else
354 found = false;
355 else {
356 lastHash = hash;
357 found = true;
358 }
359 }
360 }
361 return result;
362 }
363
364 public Iterator iterator() {
365 return new KeyedHashSetIterator();
366 }
367
368 class KeyedHashSetIterator implements Iterator {
369 private int currentIndex = -1;
370 private int found;
371
372 public boolean hasNext() {
373 return found < elementCount;
374 }
375
376 public Object next() {
377 if (!hasNext())
378 throw new NoSuchElementException ();
379 while (++currentIndex < elements.length)
380 if (elements[currentIndex] != null) {
381 found++;
382 return elements[currentIndex];
383 }
384 throw new NoSuchElementException ();
386 }
387
388 public void remove() {
389 throw new UnsupportedOperationException ();
391 }
392 }
393
394 public void clear() {
395 elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
396 elementCount = 0;
397 }
398 }
399 |
Popular Tags |
Java API By Example, From Geeks To Geeks.