1 /*
2 * Copyright 2005 Ralf Joachim
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package org.castor.core.util;
17
18 import java.util.Collection;
19 import java.util.Iterator;
20 import java.util.NoSuchElementException;
21 import java.util.Set;
22
23 /**
24 * An IdentitySet that uses reference-equality instead of object-equality. According
25 * to its special function it violates some design contracts of the <code>Set</code>
26 * interface.
27 *
28 * @author <a href="mailto:ralf DOT joachim AT syscon DOT eu">Ralf Joachim</a>
29 * @version $Revision: 7491 $ $Date: 2006-04-13 10:49:49 -0600 (Thu, 13 Apr 2006) $
30 * @since 0.9.9
31 */
32 public final class IdentitySet implements Set {
33 //--------------------------------------------------------------------------
34
35 /** Default number of buckets. */
36 private static final int DEFAULT_CAPACITY = 17;
37
38 /** Default load factor. */
39 private static final float DEFAULT_LOAD = 0.75f;
40
41 /** Default number of entries. */
42 private static final int DEFAULT_ENTRIES = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD);
43
44 /** Default factor to increment capacity. */
45 private static final int DEFAULT_INCREMENT = 2;
46
47 /** First prime number to check is 3 as we prevent 2 by design. */
48 private static final int FIRST_PRIME_TO_CHECK = 3;
49
50 //--------------------------------------------------------------------------
51
52 /** Number of buckets. */
53 private int _capacity;
54
55 /** Maximum number of entries before rehashing. */
56 private int _maximum;
57
58 /** Buckets. */
59 private Entry[] _buckets;
60
61 /** Number of map entries. */
62 private int _entries = 0;
63
64 //--------------------------------------------------------------------------
65
66 /**
67 * Construct a set with default capacity.
68 */
69 public IdentitySet() {
70 _capacity = DEFAULT_CAPACITY;
71 _maximum = DEFAULT_ENTRIES;
72 _buckets = new Entry[DEFAULT_CAPACITY];
73 }
74
75 /**
76 * Construct a set with given capacity.
77 *
78 * @param capacity The capacity of entries this set should be initialized with.
79 */
80 public IdentitySet(final int capacity) {
81 _capacity = capacity;
82 _maximum = (int) (capacity * DEFAULT_LOAD);
83 _buckets = new Entry[capacity];
84 }
85
86 /**
87 * {@inheritDoc}
88 * @see java.util.Collection#clear()
89 */
90 public void clear() {
91 _capacity = DEFAULT_CAPACITY;
92 _maximum = DEFAULT_ENTRIES;
93 _buckets = new Entry[DEFAULT_CAPACITY];
94 _entries = 0;
95 }
96
97 /**
98 * {@inheritDoc}
99 * @see java.util.Collection#size()
100 */
101 public int size() { return _entries; }
102
103 /**
104 * {@inheritDoc}
105 * @see java.util.Collection#isEmpty()
106 */
107 public boolean isEmpty() { return (_entries == 0); }
108
109 /**
110 * {@inheritDoc}
111 * @see java.util.Collection#add(java.lang.Object)
112 */
113 public boolean add(final Object key) {
114 int hash = System.identityHashCode(key);
115 int index = hash % _capacity;
116 if (index < 0) { index = -index; }
117
118 Entry entry = _buckets[index];
119 Entry prev = null;
120 while (entry != null) {
121 if (entry.getKey() == key) {
122 // There is already a mapping for this key.
123 return false;
124 }
125 prev = entry;
126 entry = entry.getNext();
127 }
128 if (prev == null) {
129 // There is no previous entry in this bucket.
130 _buckets[index] = new Entry(key, hash);
131 } else {
132 // Next entry is empty so we have no mapping for this key.
133 prev.setNext(new Entry(key, hash));
134 }
135 _entries++;
136 if (_entries > _maximum) { rehash(); }
137 return true;
138 }
139
140 /**
141 * Rehash the map into a new array with increased capacity.
142 */
143 private void rehash() {
144 long nextCapacity = _capacity * DEFAULT_INCREMENT;
145 if (nextCapacity > Integer.MAX_VALUE) { return; }
146 nextCapacity = nextPrime(nextCapacity);
147 if (nextCapacity > Integer.MAX_VALUE) { return; }
148
149 int newCapacity = (int) nextCapacity;
150 Entry[] newBuckets = new Entry[newCapacity];
151
152 Entry entry = null;
153 Entry temp = null;
154 Entry next = null;
155 int newIndex = 0;
156
157 for (int index = 0; index < _capacity; index++) {
158 entry = _buckets[index];
159 while (entry != null) {
160 next = entry.getNext();
161
162 newIndex = entry.getHash() % newCapacity;
163 if (newIndex < 0) { newIndex = -newIndex; }
164
165 temp = newBuckets[newIndex];
166 if (temp == null) {
167 // First entry of the bucket.
168 entry.setNext(null);
169 } else {
170 // Hook entry into beginning of the buckets chain.
171 entry.setNext(temp);
172 }
173 newBuckets[newIndex] = entry;
174
175 entry = next;
176 }
177 }
178
179 _capacity = newCapacity;
180 _maximum = (int) (newCapacity * DEFAULT_LOAD);
181 _buckets = newBuckets;
182 }
183
184 /**
185 * Find next prime number greater than minimum.
186 *
187 * @param minimum The minimum (exclusive) value of the next prime number.
188 * @return The next prime number greater than minimum.
189 */
190 private long nextPrime(final long minimum) {
191 long candidate = ((minimum + 1) / 2) * 2 + 1;
192 while (!isPrime(candidate)) { candidate += 2; }
193 return candidate;
194 }
195
196 /**
197 * Check for prime number.
198 *
199 * @param candidate Number to be checked for being a prime number.
200 * @return <code>true</code> if the given number is a prime number
201 * <code>false</code> otherwise.
202 */
203 private boolean isPrime(final long candidate) {
204 if ((candidate / 2) * 2 == candidate) { return false; }
205 long stop = candidate / 2;
206 for (long i = FIRST_PRIME_TO_CHECK; i < stop; i += 2) {
207 if ((candidate / i) * i == candidate) { return false; }
208 }
209 return true;
210 }
211
212 /**
213 * {@inheritDoc}
214 * @see java.util.Collection#contains(java.lang.Object)
215 */
216 public boolean contains(final Object key) {
217 int hash = System.identityHashCode(key);
218 int index = hash % _capacity;
219 if (index < 0) { index = -index; }
220
221 Entry entry = _buckets[index];
222 while (entry != null) {
223 if (entry.getKey() == key) { return true; }
224 entry = entry.getNext();
225 }
226 return false;
227 }
228
229 /**
230 * {@inheritDoc}
231 * @see java.util.Collection#remove(java.lang.Object)
232 */
233 public boolean remove(final Object key) {
234 int hash = System.identityHashCode(key);
235 int index = hash % _capacity;
236 if (index < 0) { index = -index; }
237
238 Entry entry = _buckets[index];
239 Entry prev = null;
240 while (entry != null) {
241 if (entry.getKey() == key) {
242 // Found the entry.
243 if (prev == null) {
244 // First element in bucket matches.
245 _buckets[index] = entry.getNext();
246 } else {
247 // Remove the entry from the chain.
248 prev.setNext(entry.getNext());
249 }
250 _entries--;
251 return true;
252 }
253 prev = entry;
254 entry = entry.getNext();
255 }
256 return false;
257 }
258
259 /**
260 * {@inheritDoc}
261 * @see java.util.Collection#iterator()
262 */
263 public Iterator iterator() {
264 return new IdentityIterator();
265 }
266
267 /**
268 * {@inheritDoc}
269 * @see java.util.Collection#toArray()
270 */
271 public Object[] toArray() {
272 Object[] result = new Object[_entries];
273
274 int j = 0;
275 for (int i = 0; i < _capacity; i++) {
276 Entry entry = _buckets[i];
277 while (entry != null) {
278 result[j++] = entry.getKey();
279 entry = entry.getNext();
280 }
281 }
282
283 return result;
284 }
285
286 /**
287 * {@inheritDoc}
288 * @see java.util.Collection#toArray(java.lang.Object[])
289 */
290 public Object[] toArray(final Object[] a) {
291 Object[] result = a;
292 if (result.length < _entries) {
293 result = (Object[]) java.lang.reflect.Array.newInstance(
294 result.getClass().getComponentType(), _entries);
295 }
296
297 int j = 0;
298 for (int i = 0; i < _capacity; i++) {
299 Entry entry = _buckets[i];
300 while (entry != null) {
301 result[j++] = entry.getKey();
302 entry = entry.getNext();
303 }
304 }
305
306 while (j < result.length) {
307 result[j++] = null;
308 }
309
310 return result;
311 }
312
313 /**
314 * In contrast with the design contract of the <code>Set</code> interface this method
315 * has not been implemented and throws a <code>UnsupportedOperationException</code>.
316 *
317 * {@inheritDoc}
318 * @see java.util.Set#containsAll
319 */
320 public boolean containsAll(final Collection c) {
321 throw new UnsupportedOperationException();
322 }
323
324 /**
325 * This optional method has not been implemented for <code>IdentitySet</code> instead
326 * it throws a <code>UnsupportedOperationException</code> as defined in the
327 * <code>Set</code> interface.
328 *
329 * {@inheritDoc}
330 * @see java.util.Set#addAll
331 */
332 public boolean addAll(final Collection c) {
333 throw new UnsupportedOperationException();
334 }
335
336 /**
337 * This optional method has not been implemented for <code>IdentitySet</code> instead
338 * it throws a <code>UnsupportedOperationException</code> as defined in the
339 * <code>Set</code> interface.
340 *
341 * {@inheritDoc}
342 * @see java.util.Set#removeAll
343 */
344 public boolean removeAll(final Collection c) {
345 throw new UnsupportedOperationException();
346 }
347
348 /**
349 * This optional method has not been implemented for <code>IdentitySet</code> instead
350 * it throws a <code>UnsupportedOperationException</code> as defined in the
351 * <code>Set</code> interface.
352 *
353 * {@inheritDoc}
354 * @see java.util.Set#retainAll
355 */
356 public boolean retainAll(final Collection c) {
357 throw new UnsupportedOperationException();
358 }
359
360 //--------------------------------------------------------------------------
361
362 /**
363 * An entry of the <code>IdentitySet</code>.
364 */
365 public final class Entry {
366 /** Key of entry. */
367 private Object _key;
368
369 /** Identity hashcode of key. */
370 private int _hash;
371
372 /** Reference to next entry. */
373 private Entry _next = null;
374
375 /**
376 * Construct an entry.
377 *
378 * @param key Key of entry.
379 * @param hash Identity hashcode of key.
380 */
381 public Entry(final Object key, final int hash) {
382 _key = key;
383 _hash = hash;
384 }
385
386 /**
387 * Get key of entry.
388 *
389 * @return Key of entry.
390 */
391 public Object getKey() { return _key; }
392
393 /**
394 * Get identity hashcode of key.
395 *
396 * @return Identity hashcode of key.
397 */
398 public int getHash() { return _hash; }
399
400 /**
401 * Set reference to next entry.
402 *
403 * @param next New reference to next entry.
404 */
405 public void setNext(final Entry next) { _next = next; }
406
407 /**
408 * Get reference to next entry.
409 *
410 * @return Reference to next entry.
411 */
412 public Entry getNext() { return _next; }
413 }
414
415 //--------------------------------------------------------------------------
416
417 /**
418 * An iterator over all entries of the <code>IdentitySet</code>.
419 */
420 private class IdentityIterator implements Iterator {
421 /** Index of the current bucket. */
422 private int _index = 0;
423
424 /** The next entry to be returned. <code>null</code> when there is none. */
425 private Entry _next = _buckets[0];
426
427 /**
428 * Construct a iterator over all entries of the <code>IdentitySet</code>.
429 */
430 public IdentityIterator() {
431 if (_entries > 0) {
432 while ((_next == null) && (++_index < _capacity)) {
433 _next = _buckets[_index];
434 }
435 }
436 }
437
438 /**
439 * {@inheritDoc}
440 * @see java.util.Iterator#hasNext()
441 */
442 public boolean hasNext() {
443 return (_next != null);
444 }
445
446 /**
447 * {@inheritDoc}
448 * @see java.util.Iterator#next()
449 */
450 public Object next() {
451 Entry entry = _next;
452 if (entry == null) { throw new NoSuchElementException(); }
453
454 _next = entry.getNext();
455 while ((_next == null) && (++_index < _capacity)) {
456 _next = _buckets[_index];
457 }
458
459 return entry.getKey();
460 }
461
462 /**
463 * This optional method is not implemented for <code>IdentityIterator</code>
464 * instead it throws a <code>UnsupportedOperationException</code> as defined
465 * in the <code>Iterator</code> interface.
466 *
467 * @see java.util.Iterator#remove()
468 */
469 public void remove() {
470 throw new UnsupportedOperationException();
471 }
472 }
473
474 //--------------------------------------------------------------------------
475 }