1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
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 * Open addressed map from int to double.
30 * <p>This class provides a dedicated map from integers to doubles with a
31 * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
32 * <p>This class is not synchronized. The specialized iterators returned by
33 * {@link #iterator()} are fail-fast: they throw a
34 * <code>ConcurrentModificationException</code> when they detect the map has been
35 * modified during iteration.</p>
36 * @version $Revision: 825919 $ $Date: 2009-10-16 10:51:55 -0400 (Fri, 16 Oct 2009) $
37 * @since 2.0
38 */
39 public class OpenIntToDoubleHashMap implements Serializable {
40
41 /** Status indicator for free table entries. */
42 protected static final byte FREE = 0;
43
44 /** Status indicator for full table entries. */
45 protected static final byte FULL = 1;
46
47 /** Status indicator for removed table entries. */
48 protected static final byte REMOVED = 2;
49
50 /** Serializable version identifier */
51 private static final long serialVersionUID = -3646337053166149105L;
52
53 /** Load factor for the map. */
54 private static final float LOAD_FACTOR = 0.5f;
55
56 /** Default starting size.
57 * <p>This must be a power of two for bit mask to work properly. </p>
58 */
59 private static final int DEFAULT_EXPECTED_SIZE = 16;
60
61 /** Multiplier for size growth when map fills up.
62 * <p>This must be a power of two for bit mask to work properly. </p>
63 */
64 private static final int RESIZE_MULTIPLIER = 2;
65
66 /** Number of bits to perturb the index when probing for collision resolution. */
67 private static final int PERTURB_SHIFT = 5;
68
69 /** Keys table. */
70 private int[] keys;
71
72 /** Values table. */
73 private double[] values;
74
75 /** States table. */
76 private byte[] states;
77
78 /** Return value for missing entries. */
79 private final double missingEntries;
80
81 /** Current size of the map. */
82 private int size;
83
84 /** Bit mask for hash values. */
85 private int mask;
86
87 /** Modifications count. */
88 private transient int count;
89
90 /**
91 * Build an empty map with default size and using NaN for missing entries.
92 */
93 public OpenIntToDoubleHashMap() {
94 this(DEFAULT_EXPECTED_SIZE, Double.NaN);
95 }
96
97 /**
98 * Build an empty map with default size
99 * @param missingEntries value to return when a missing entry is fetched
100 */
101 public OpenIntToDoubleHashMap(final double missingEntries) {
102 this(DEFAULT_EXPECTED_SIZE, missingEntries);
103 }
104
105 /**
106 * Build an empty map with specified size and using NaN for missing entries.
107 * @param expectedSize expected number of elements in the map
108 */
109 public OpenIntToDoubleHashMap(final int expectedSize) {
110 this(expectedSize, Double.NaN);
111 }
112
113 /**
114 * Build an empty map with specified size.
115 * @param expectedSize expected number of elements in the map
116 * @param missingEntries value to return when a missing entry is fetched
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 * Copy constructor.
130 * @param source map to copy
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 * Compute the capacity needed for a given size.
148 * @param expectedSize expected size of the map
149 * @return capacity to use for the specified size
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 * Find the smallest power of two greater than the input value
165 * @param i input value
166 * @return smallest power of two greater than the input value
167 */
168 private static int nextPowerOfTwo(final int i) {
169 return Integer.highestOneBit(i) << 1;
170 }
171
172 /**
173 * Get the stored value associated with the given key
174 * @param key key associated with the data
175 * @return data associated with the key
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 int j = index;
190 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
191 j = probe(perturb, j);
192 index = j & mask;
193 if (containsKey(key, index)) {
194 return values[index];
195 }
196 }
197
198 return missingEntries;
199
200 }
201
202 /**
203 * Check if a value is associated with a key.
204 * @param key key to check
205 * @return true if a value is associated with key
206 */
207 public boolean containsKey(final int key) {
208
209 final int hash = hashOf(key);
210 int index = hash & mask;
211 if (containsKey(key, index)) {
212 return true;
213 }
214
215 if (states[index] == FREE) {
216 return false;
217 }
218
219 int j = index;
220 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
221 j = probe(perturb, j);
222 index = j & mask;
223 if (containsKey(key, index)) {
224 return true;
225 }
226 }
227
228 return false;
229
230 }
231
232 /**
233 * Get an iterator over map elements.
234 * <p>The specialized iterators returned are fail-fast: they throw a
235 * <code>ConcurrentModificationException</code> when they detect the map
236 * has been modified during iteration.</p>
237 * @return iterator over the map elements
238 */
239 public Iterator iterator() {
240 return new Iterator();
241 }
242
243 /**
244 * Perturb the hash for starting probing.
245 * @param hash initial hash
246 * @return perturbed hash
247 */
248 private static int perturb(final int hash) {
249 return hash & 0x7fffffff;
250 }
251
252 /**
253 * Find the index at which a key should be inserted
254 * @param key key to lookup
255 * @return index at which key should be inserted
256 */
257 private int findInsertionIndex(final int key) {
258 return findInsertionIndex(keys, states, key, mask);
259 }
260
261 /**
262 * Find the index at which a key should be inserted
263 * @param keys keys table
264 * @param states states table
265 * @param key key to lookup
266 * @param mask bit mask for hash values
267 * @return index at which key should be inserted
268 */
269 private static int findInsertionIndex(final int[] keys, final byte[] states,
270 final int key, final int mask) {
271 final int hash = hashOf(key);
272 int index = hash & mask;
273 if (states[index] == FREE) {
274 return index;
275 } else if (states[index] == FULL && keys[index] == key) {
276 return changeIndexSign(index);
277 }
278
279 int perturb = perturb(hash);
280 int j = index;
281 if (states[index] == FULL) {
282 while (true) {
283 j = probe(perturb, j);
284 index = j & mask;
285 perturb >>= PERTURB_SHIFT;
286
287 if (states[index] != FULL || keys[index] == key) {
288 break;
289 }
290 }
291 }
292
293 if (states[index] == FREE) {
294 return index;
295 } else if (states[index] == FULL) {
296 // due to the loop exit condition,
297 // if (states[index] == FULL) then keys[index] == key
298 return changeIndexSign(index);
299 }
300
301 final int firstRemoved = index;
302 while (true) {
303 j = probe(perturb, j);
304 index = j & mask;
305
306 if (states[index] == FREE) {
307 return firstRemoved;
308 } else if (states[index] == FULL && keys[index] == key) {
309 return changeIndexSign(index);
310 }
311
312 perturb >>= PERTURB_SHIFT;
313
314 }
315
316 }
317
318 /**
319 * Compute next probe for collision resolution
320 * @param perturb perturbed hash
321 * @param j previous probe
322 * @return next probe
323 */
324 private static int probe(final int perturb, final int j) {
325 return (j << 2) + j + perturb + 1;
326 }
327
328 /**
329 * Change the index sign
330 * @param index initial index
331 * @return changed index
332 */
333 private static int changeIndexSign(final int index) {
334 return -index - 1;
335 }
336
337 /**
338 * Get the number of elements stored in the map.
339 * @return number of elements stored in the map
340 */
341 public int size() {
342 return size;
343 }
344
345
346 /**
347 * Remove the value associated with a key.
348 * @param key key to which the value is associated
349 * @return removed value
350 */
351 public double remove(final int key) {
352
353 final int hash = hashOf(key);
354 int index = hash & mask;
355 if (containsKey(key, index)) {
356 return doRemove(index);
357 }
358
359 if (states[index] == FREE) {
360 return missingEntries;
361 }
362
363 int j = index;
364 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
365 j = probe(perturb, j);
366 index = j & mask;
367 if (containsKey(key, index)) {
368 return doRemove(index);
369 }
370 }
371
372 return missingEntries;
373
374 }
375
376 /**
377 * Check if the tables contain an element associated with specified key
378 * at specified index.
379 * @param key key to check
380 * @param index index to check
381 * @return true if an element is associated with key at index
382 */
383 private boolean containsKey(final int key, final int index) {
384 return (key != 0 || states[index] == FULL) && keys[index] == key;
385 }
386
387 /**
388 * Remove an element at specified index.
389 * @param index index of the element to remove
390 * @return removed value
391 */
392 private double doRemove(int index) {
393 keys[index] = 0;
394 states[index] = REMOVED;
395 final double previous = values[index];
396 values[index] = missingEntries;
397 --size;
398 ++count;
399 return previous;
400 }
401
402 /**
403 * Put a value associated with a key in the map.
404 * @param key key to which value is associated
405 * @param value value to put in the map
406 * @return previous value associated with the key
407 */
408 public double put(final int key, final double value) {
409 int index = findInsertionIndex(key);
410 double previous = missingEntries;
411 boolean newMapping = true;
412 if (index < 0) {
413 index = changeIndexSign(index);
414 previous = values[index];
415 newMapping = false;
416 }
417 keys[index] = key;
418 states[index] = FULL;
419 values[index] = value;
420 if (newMapping) {
421 ++size;
422 if (shouldGrowTable()) {
423 growTable();
424 }
425 ++count;
426 }
427 return previous;
428
429 }
430
431 /**
432 * Grow the tables.
433 */
434 private void growTable() {
435
436 final int oldLength = states.length;
437 final int[] oldKeys = keys;
438 final double[] oldValues = values;
439 final byte[] oldStates = states;
440
441 final int newLength = RESIZE_MULTIPLIER * oldLength;
442 final int[] newKeys = new int[newLength];
443 final double[] newValues = new double[newLength];
444 final byte[] newStates = new byte[newLength];
445 final int newMask = newLength - 1;
446 for (int i = 0; i < oldLength; ++i) {
447 if (oldStates[i] == FULL) {
448 final int key = oldKeys[i];
449 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
450 newKeys[index] = key;
451 newValues[index] = oldValues[i];
452 newStates[index] = FULL;
453 }
454 }
455
456 mask = newMask;
457 keys = newKeys;
458 values = newValues;
459 states = newStates;
460
461 }
462
463 /**
464 * Check if tables should grow due to increased size.
465 * @return true if tables should grow
466 */
467 private boolean shouldGrowTable() {
468 return size > (mask + 1) * LOAD_FACTOR;
469 }
470
471 /**
472 * Compute the hash value of a key
473 * @param key key to hash
474 * @return hash value of the key
475 */
476 private static int hashOf(final int key) {
477 final int h = key ^ ((key >>> 20) ^ (key >>> 12));
478 return h ^ (h >>> 7) ^ (h >>> 4);
479 }
480
481
482 /** Iterator class for the map. */
483 public class Iterator {
484
485 /** Reference modification count. */
486 private final int referenceCount;
487
488 /** Index of current element. */
489 private int current;
490
491 /** Index of next element. */
492 private int next;
493
494 /**
495 * Simple constructor.
496 */
497 private Iterator() {
498
499 // preserve the modification count of the map to detect concurrent modifications later
500 referenceCount = count;
501
502 // initialize current index
503 next = -1;
504 try {
505 advance();
506 } catch (NoSuchElementException nsee) {
507 // ignored
508 }
509
510 }
511
512 /**
513 * Check if there is a next element in the map.
514 * @return true if there is a next element
515 */
516 public boolean hasNext() {
517 return next >= 0;
518 }
519
520 /**
521 * Get the key of current entry.
522 * @return key of current entry
523 * @exception ConcurrentModificationException if the map is modified during iteration
524 * @exception NoSuchElementException if there is no element left in the map
525 */
526 public int key()
527 throws ConcurrentModificationException, NoSuchElementException {
528 if (referenceCount != count) {
529 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
530 }
531 if (current < 0) {
532 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
533 }
534 return keys[current];
535 }
536
537 /**
538 * Get the value of current entry.
539 * @return value of current entry
540 * @exception ConcurrentModificationException if the map is modified during iteration
541 * @exception NoSuchElementException if there is no element left in the map
542 */
543 public double value()
544 throws ConcurrentModificationException, NoSuchElementException {
545 if (referenceCount != count) {
546 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
547 }
548 if (current < 0) {
549 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
550 }
551 return values[current];
552 }
553
554 /**
555 * Advance iterator one step further.
556 * @exception ConcurrentModificationException if the map is modified during iteration
557 * @exception NoSuchElementException if there is no element left in the map
558 */
559 public void advance()
560 throws ConcurrentModificationException, NoSuchElementException {
561
562 if (referenceCount != count) {
563 throw MathRuntimeException.createConcurrentModificationException("map has been modified while iterating");
564 }
565
566 // advance on step
567 current = next;
568
569 // prepare next step
570 try {
571 while (states[++next] != FULL) {
572 // nothing to do
573 }
574 } catch (ArrayIndexOutOfBoundsException e) {
575 next = -2;
576 if (current < 0) {
577 throw MathRuntimeException.createNoSuchElementException("iterator exhausted");
578 }
579 }
580
581 }
582
583 }
584
585 /**
586 * Read a serialized object.
587 * @param stream input stream
588 * @throws IOException if object cannot be read
589 * @throws ClassNotFoundException if the class corresponding
590 * to the serialized object cannot be found
591 */
592 private void readObject(final ObjectInputStream stream)
593 throws IOException, ClassNotFoundException {
594 stream.defaultReadObject();
595 count = 0;
596 }
597
598
599 }