001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018 package org.apache.commons.math.util;
019
020 import java.io.IOException;
021 import java.io.ObjectInputStream;
022 import java.io.Serializable;
023 import java.util.ConcurrentModificationException;
024 import java.util.NoSuchElementException;
025
026 import org.apache.commons.math.MathRuntimeException;
027
028 /**
029 * Open addressed map from int to double.
030 * <p>This class provides a dedicated map from integers to doubles with a
031 * much smaller memory overhead than standard <code>java.util.Map</code>.</p>
032 * <p>This class is not synchronized. The specialized iterators returned by
033 * {@link #iterator()} are fail-fast: they throw a
034 * <code>ConcurrentModificationException</code> when they detect the map has been
035 * modified during iteration.</p>
036 * @version $Revision: 746578 $ $Date: 2009-02-21 15:01:14 -0500 (Sat, 21 Feb 2009) $
037 * @since 2.0
038 */
039 public class OpenIntToDoubleHashMap implements Serializable {
040
041 /** Serializable version identifier */
042 private static final long serialVersionUID = -3646337053166149105L;
043
044 /** Load factor for the map. */
045 private static final float LOAD_FACTOR = 0.5f;
046
047 /** Default starting size.
048 * <p>This must be a power of two for bit mask to work properly. </p>
049 */
050 private static final int DEFAULT_EXPECTED_SIZE = 16;
051
052 /** Multiplier for size growth when map fills up.
053 * <p>This must be a power of two for bit mask to work properly. </p>
054 */
055 private static final int RESIZE_MULTIPLIER = 2;
056
057 /** Number of bits to perturb the index when probing for collision resolution. */
058 private static final int PERTURB_SHIFT = 5;
059
060 /** Status indicator for free table entries. */
061 protected static final byte FREE = 0;
062
063 /** Status indicator for full table entries. */
064 protected static final byte FULL = 1;
065
066 /** Status indicator for removed table entries. */
067 protected static final byte REMOVED = 2;
068
069 /** Keys table. */
070 private int[] keys;
071
072 /** Values table. */
073 private double[] values;
074
075 /** States table. */
076 private byte[] states;
077
078 /** Return value for missing entries. */
079 private final double missingEntries;
080
081 /** Current size of the map. */
082 private int size;
083
084 /** Bit mask for hash values. */
085 private int mask;
086
087 /** Modifications count. */
088 private transient int count;
089
090 /**
091 * Build an empty map with default size and using NaN for missing entries.
092 */
093 public OpenIntToDoubleHashMap() {
094 this(DEFAULT_EXPECTED_SIZE, Double.NaN);
095 }
096
097 /**
098 * Build an empty map with default size
099 * @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 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 * Check if a value is associated with a key.
203 * @param key key to check
204 * @return true if a value is associated with key
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 * Get an iterator over map elements.
232 * <p>The specialized iterators returned are fail-fast: they throw a
233 * <code>ConcurrentModificationException</code> when they detect the map
234 * has been modified during iteration.</p>
235 * @return iterator over the map elements
236 */
237 public Iterator iterator() {
238 return new Iterator();
239 }
240
241 /**
242 * Perturb the hash for starting probing.
243 * @param hash initial hash
244 * @return perturbed hash
245 */
246 private static int perturb(final int hash) {
247 return hash & 0x7fffffff;
248 }
249
250 /**
251 * Find the index at which a key should be inserted
252 * @param key key to lookup
253 * @return index at which key should be inserted
254 */
255 private int findInsertionIndex(final int key) {
256 return findInsertionIndex(keys, states, key, mask);
257 }
258
259 /**
260 * Find the index at which a key should be inserted
261 * @param keys keys table
262 * @param states states table
263 * @param key key to lookup
264 * @param mask bit mask for hash values
265 * @return index at which key should be inserted
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 // due to the loop exit condition,
295 // if (states[index] == FULL) then keys[index] == key
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 * Compute next probe for collision resolution
318 * @param perturb perturbed hash
319 * @param j previous probe
320 * @return next probe
321 */
322 private static int probe(final int perturb, final int j) {
323 return (j << 2) + j + perturb + 1;
324 }
325
326 /**
327 * Change the index sign
328 * @param index initial index
329 * @return changed index
330 */
331 private static int changeIndexSign(final int index) {
332 return -index - 1;
333 }
334
335 /**
336 * Get the number of elements stored in the map.
337 * @return number of elements stored in the map
338 */
339 public int size() {
340 return size;
341 }
342
343
344 /**
345 * Remove the value associated with a key.
346 * @param key key to which the value is associated
347 * @return removed value
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 * Check if the tables contain an element associated with specified key
375 * at specified index.
376 * @param key key to check
377 * @param index index to check
378 * @return true if an element is associated with key at index
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 * Remove an element at specified index.
386 * @param index index of the element to remove
387 * @return removed value
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 * Put a value associated with a key in the map.
401 * @param key key to which value is associated
402 * @param value value to put in the map
403 * @return previous value associated with the key
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 * Grow the tables.
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 * Check if tables should grow due to increased size.
462 * @return true if tables should grow
463 */
464 private boolean shouldGrowTable() {
465 return size > (mask + 1) * LOAD_FACTOR;
466 }
467
468 /**
469 * Compute the hash value of a key
470 * @param key key to hash
471 * @return hash value of the key
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 /** Iterator class for the map. */
480 public class Iterator {
481
482 /** Reference modification count. */
483 private final int referenceCount;
484
485 /** Index of current element. */
486 private int current;
487
488 /** Index of next element. */
489 private int next;
490
491 /**
492 * Simple constructor.
493 */
494 private Iterator() {
495
496 // preserve the modification count of the map to detect concurrent modifications later
497 referenceCount = count;
498
499 // initialize current index
500 next = -1;
501 try {
502 advance();
503 } catch (NoSuchElementException nsee) {
504 // ignored
505 }
506
507 }
508
509 /**
510 * Check if there is a next element in the map.
511 * @return true if there is a next element
512 */
513 public boolean hasNext() {
514 return next >= 0;
515 }
516
517 /**
518 * Get the key of current entry.
519 * @return key of current entry
520 * @exception ConcurrentModificationException if the map is modified during iteration
521 * @exception NoSuchElementException if there is no element left in the map
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 * Get the value of current entry.
536 * @return value of current entry
537 * @exception ConcurrentModificationException if the map is modified during iteration
538 * @exception NoSuchElementException if there is no element left in the map
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 * Advance iterator one step further.
553 * @exception ConcurrentModificationException if the map is modified during iteration
554 * @exception NoSuchElementException if there is no element left in the map
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 // advance on step
564 current = next;
565
566 // prepare next step
567 try {
568 while (states[++next] != FULL) {
569 // nothing to do
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 * Read a serialized object.
584 * @param stream input stream
585 * @throws IOException if object cannot be read
586 * @throws ClassNotFoundException if the class corresponding
587 * to the serialized object cannot be found
588 */
589 private void readObject(final ObjectInputStream stream)
590 throws IOException, ClassNotFoundException {
591 stream.defaultReadObject();
592 count = 0;
593 }
594
595
596 }