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