1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math.util;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.Serializable;
22 import java.lang.reflect.Array;
23 import java.util.ConcurrentModificationException;
24 import java.util.NoSuchElementException;
25
26 import org.apache.commons.math.Field;
27 import org.apache.commons.math.FieldElement;
28 import org.apache.commons.math.MathRuntimeException;
29
30
31
32
33
34
35
36
37
38
39
40
41
42 public class OpenIntToFieldHashMap<T extends FieldElement<T>> implements Serializable {
43
44
45 private static final long serialVersionUID = -9179080286849120720L;
46
47
48 private static final float LOAD_FACTOR = 0.5f;
49
50
51
52
53 private static final int DEFAULT_EXPECTED_SIZE = 16;
54
55
56
57
58 private static final int RESIZE_MULTIPLIER = 2;
59
60
61 private static final int PERTURB_SHIFT = 5;
62
63
64 protected static final byte FREE = 0;
65
66
67 protected static final byte FULL = 1;
68
69
70 protected static final byte REMOVED = 2;
71
72
73 private final Field<T> field;
74
75
76 private int[] keys;
77
78
79 private T[] values;
80
81
82 private byte[] states;
83
84
85 private final T missingEntries;
86
87
88 private int size;
89
90
91 private int mask;
92
93
94 private transient int count;
95
96
97
98
99
100 public OpenIntToFieldHashMap(final Field<T>field) {
101 this(field, DEFAULT_EXPECTED_SIZE, field.getZero());
102 }
103
104
105
106
107
108
109 public OpenIntToFieldHashMap(final Field<T>field, final T missingEntries) {
110 this(field,DEFAULT_EXPECTED_SIZE, missingEntries);
111 }
112
113
114
115
116
117
118 public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize) {
119 this(field,expectedSize, field.getZero());
120 }
121
122
123
124
125
126
127
128 public OpenIntToFieldHashMap(final Field<T> field,final int expectedSize,
129 final T missingEntries) {
130 this.field = field;
131 final int capacity = computeCapacity(expectedSize);
132 keys = new int[capacity];
133 values = buildArray(capacity);
134 states = new byte[capacity];
135 this.missingEntries = missingEntries;
136 mask = capacity - 1;
137 }
138
139
140
141
142
143 public OpenIntToFieldHashMap(final OpenIntToFieldHashMap<T> source) {
144 field = source.field;
145 final int length = source.keys.length;
146 keys = new int[length];
147 System.arraycopy(source.keys, 0, keys, 0, length);
148 values = buildArray(length);
149 System.arraycopy(source.values, 0, values, 0, length);
150 states = new byte[length];
151 System.arraycopy(source.states, 0, states, 0, length);
152 missingEntries = source.missingEntries;
153 size = source.size;
154 mask = source.mask;
155 count = source.count;
156 }
157
158
159
160
161
162
163 private static int computeCapacity(final int expectedSize) {
164 if (expectedSize == 0) {
165 return 1;
166 }
167 final int capacity = (int) Math.ceil(expectedSize / LOAD_FACTOR);
168 final int powerOfTwo = Integer.highestOneBit(capacity);
169 if (powerOfTwo == capacity) {
170 return capacity;
171 }
172 return nextPowerOfTwo(capacity);
173 }
174
175
176
177
178
179
180 private static int nextPowerOfTwo(final int i) {
181 return Integer.highestOneBit(i) << 1;
182 }
183
184
185
186
187
188
189 public T get(final int key) {
190
191 final int hash = hashOf(key);
192 int index = hash & mask;
193 if (containsKey(key, index)) {
194 return values[index];
195 }
196
197 if (states[index] == FREE) {
198 return missingEntries;
199 }
200
201 for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
202 j = probe(perturb, j);
203 index = j & mask;
204 if (containsKey(key, index)) {
205 return values[index];
206 }
207 }
208
209 return missingEntries;
210
211 }
212
213
214
215
216
217
218 public boolean containsKey(final int key) {
219
220 final int hash = hashOf(key);
221 int index = hash & mask;
222 if (containsKey(key, index)) {
223 return true;
224 }
225
226 if (states[index] == FREE) {
227 return false;
228 }
229
230 for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
231 j = probe(perturb, j);
232 index = j & mask;
233 if (containsKey(key, index)) {
234 return true;
235 }
236 }
237
238 return false;
239
240 }
241
242
243
244
245
246
247
248
249 public Iterator iterator() {
250 return new Iterator();
251 }
252
253
254
255
256
257
258 private static int perturb(final int hash) {
259 return hash & 0x7fffffff;
260 }
261
262
263
264
265
266
267 private int findInsertionIndex(final int key) {
268 return findInsertionIndex(keys, states, key, mask);
269 }
270
271
272
273
274
275
276
277
278
279 private static int findInsertionIndex(final int[] keys, final byte[] states,
280 final int key, final int mask) {
281 final int hash = hashOf(key);
282 int index = hash & mask;
283 if (states[index] == FREE) {
284 return index;
285 } else if (states[index] == FULL && keys[index] == key) {
286 return changeIndexSign(index);
287 }
288
289 int perturb = perturb(hash);
290 int j = index;
291 if (states[index] == FULL) {
292 while (true) {
293 j = probe(perturb, j);
294 index = j & mask;
295 perturb >>= PERTURB_SHIFT;
296
297 if (states[index] != FULL || keys[index] == key) {
298 break;
299 }
300 }
301 }
302
303 if (states[index] == FREE) {
304 return index;
305 } else if (states[index] == FULL) {
306
307
308 return changeIndexSign(index);
309 }
310
311 final int firstRemoved = index;
312 while (true) {
313 j = probe(perturb, j);
314 index = j & mask;
315
316 if (states[index] == FREE) {
317 return firstRemoved;
318 } else if (states[index] == FULL && keys[index] == key) {
319 return changeIndexSign(index);
320 }
321
322 perturb >>= PERTURB_SHIFT;
323
324 }
325
326 }
327
328
329
330
331
332
333
334 private static int probe(final int perturb, final int j) {
335 return (j << 2) + j + perturb + 1;
336 }
337
338
339
340
341
342
343 private static int changeIndexSign(final int index) {
344 return -index - 1;
345 }
346
347
348
349
350
351 public int size() {
352 return size;
353 }
354
355
356
357
358
359
360
361 public T remove(final int key) {
362
363 final int hash = hashOf(key);
364 int index = hash & mask;
365 if (containsKey(key, index)) {
366 return doRemove(index);
367 }
368
369 if (states[index] == FREE) {
370 return missingEntries;
371 }
372
373 for (int perturb = perturb(hash), j = index; states[index] != FREE; perturb >>= PERTURB_SHIFT) {
374 j = probe(perturb, j);
375 index = j & mask;
376 if (containsKey(key, index)) {
377 return doRemove(index);
378 }
379 }
380
381 return missingEntries;
382
383 }
384
385
386
387
388
389
390
391
392 private boolean containsKey(final int key, final int index) {
393 return (key != 0 || states[index] == FULL) && keys[index] == key;
394 }
395
396
397
398
399
400
401 private T doRemove(int index) {
402 keys[index] = 0;
403 states[index] = REMOVED;
404 final T previous = values[index];
405 values[index] = missingEntries;
406 --size;
407 ++count;
408 return previous;
409 }
410
411
412
413
414
415
416
417 public T put(final int key, final T value) {
418 int index = findInsertionIndex(key);
419 T previous = missingEntries;
420 boolean newMapping = true;
421 if (index < 0) {
422 index = changeIndexSign(index);
423 previous = values[index];
424 newMapping = false;
425 }
426 keys[index] = key;
427 states[index] = FULL;
428 values[index] = value;
429 if (newMapping) {
430 ++size;
431 if (shouldGrowTable()) {
432 growTable();
433 }
434 ++count;
435 }
436 return previous;
437
438 }
439
440
441
442
443 private void growTable() {
444
445 final int oldLength = states.length;
446 final int[] oldKeys = keys;
447 final T[] oldValues = values;
448 final byte[] oldStates = states;
449
450 final int newLength = RESIZE_MULTIPLIER * oldLength;
451 final int[] newKeys = new int[newLength];
452 final T[] newValues = buildArray(newLength);
453 final byte[] newStates = new byte[newLength];
454 final int newMask = newLength - 1;
455 for (int i = 0; i < oldLength; ++i) {
456 if (oldStates[i] == FULL) {
457 final int key = oldKeys[i];
458 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
459 newKeys[index] = key;
460 newValues[index] = oldValues[i];
461 newStates[index] = FULL;
462 }
463 }
464
465 mask = newMask;
466 keys = newKeys;
467 values = newValues;
468 states = newStates;
469
470 }
471
472
473
474
475
476 private boolean shouldGrowTable() {
477 return size > (mask + 1) * LOAD_FACTOR;
478 }
479
480
481
482
483
484
485 private static int hashOf(final int key) {
486 final int h = key ^ ((key >>> 20) ^ (key >>> 12));
487 return h ^ (h >>> 7) ^ (h >>> 4);
488 }
489
490
491
492 public class Iterator {
493
494
495 private final int referenceCount;
496
497
498 private int current;
499
500
501 private int next;
502
503
504
505
506 private Iterator() {
507
508
509 referenceCount = count;
510
511
512 next = -1;
513 try {
514 advance();
515 } catch (NoSuchElementException nsee) {
516
517 }
518
519 }
520
521
522
523
524
525 public boolean hasNext() {
526 return next >= 0;
527 }
528
529
530
531
532
533
534
535 public int key()
536 throws ConcurrentModificationException, NoSuchElementException {
537 if (referenceCount != count) {
538 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
539 }
540 if (current < 0) {
541 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
542 }
543 return keys[current];
544 }
545
546
547
548
549
550
551
552 public T value()
553 throws ConcurrentModificationException, NoSuchElementException {
554 if (referenceCount != count) {
555 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
556 }
557 if (current < 0) {
558 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
559 }
560 return values[current];
561 }
562
563
564
565
566
567
568 public void advance()
569 throws ConcurrentModificationException, NoSuchElementException {
570
571 if (referenceCount != count) {
572 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
573 }
574
575
576 current = next;
577
578
579 try {
580 while (states[++next] != FULL) {
581
582 }
583 } catch (ArrayIndexOutOfBoundsException e) {
584 next = -2;
585 if (current < 0) {
586 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
587 }
588 }
589
590 }
591
592 }
593
594
595
596
597
598
599
600
601 private void readObject(final ObjectInputStream stream)
602 throws IOException, ClassNotFoundException {
603 stream.defaultReadObject();
604 count = 0;
605 }
606
607
608
609
610
611 @SuppressWarnings("unchecked")
612 private T[] buildArray(final int length) {
613 return (T[]) Array.newInstance(field.getZero().getClass(), length);
614 }
615
616 }