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: 885278 $ $Date: 2009-11-29 16:47:51 -0500 (Sun, 29 Nov 2009) $
037 * @since 2.0
038 */
039 public class OpenIntToDoubleHashMap implements Serializable {
040
041 /** Status indicator for free table entries. */
042 protected static final byte FREE = 0;
043
044 /** Status indicator for full table entries. */
045 protected static final byte FULL = 1;
046
047 /** Status indicator for removed table entries. */
048 protected static final byte REMOVED = 2;
049
050 /** Serializable version identifier */
051 private static final long serialVersionUID = -3646337053166149105L;
052
053 /** Message for map modification during iteration. */
054 private static final String CONCURRENT_MODIFICATION_MESSAGE =
055 "map has been modified while iterating";
056
057 /** Message for exhausted iterator. */
058 private static final String EXHAUSTED_ITERATOR_MESSAGE =
059 "iterator exhausted";
060
061 /** Load factor for the map. */
062 private static final float LOAD_FACTOR = 0.5f;
063
064 /** Default starting size.
065 * <p>This must be a power of two for bit mask to work properly. </p>
066 */
067 private static final int DEFAULT_EXPECTED_SIZE = 16;
068
069 /** Multiplier for size growth when map fills up.
070 * <p>This must be a power of two for bit mask to work properly. </p>
071 */
072 private static final int RESIZE_MULTIPLIER = 2;
073
074 /** Number of bits to perturb the index when probing for collision resolution. */
075 private static final int PERTURB_SHIFT = 5;
076
077 /** Keys table. */
078 private int[] keys;
079
080 /** Values table. */
081 private double[] values;
082
083 /** States table. */
084 private byte[] states;
085
086 /** Return value for missing entries. */
087 private final double missingEntries;
088
089 /** Current size of the map. */
090 private int size;
091
092 /** Bit mask for hash values. */
093 private int mask;
094
095 /** Modifications count. */
096 private transient int count;
097
098 /**
099 * Build an empty map with default size and using NaN for missing entries.
100 */
101 public OpenIntToDoubleHashMap() {
102 this(DEFAULT_EXPECTED_SIZE, Double.NaN);
103 }
104
105 /**
106 * Build an empty map with default size
107 * @param missingEntries value to return when a missing entry is fetched
108 */
109 public OpenIntToDoubleHashMap(final double missingEntries) {
110 this(DEFAULT_EXPECTED_SIZE, missingEntries);
111 }
112
113 /**
114 * Build an empty map with specified size and using NaN for missing entries.
115 * @param expectedSize expected number of elements in the map
116 */
117 public OpenIntToDoubleHashMap(final int expectedSize) {
118 this(expectedSize, Double.NaN);
119 }
120
121 /**
122 * Build an empty map with specified size.
123 * @param expectedSize expected number of elements in the map
124 * @param missingEntries value to return when a missing entry is fetched
125 */
126 public OpenIntToDoubleHashMap(final int expectedSize,
127 final double missingEntries) {
128 final int capacity = computeCapacity(expectedSize);
129 keys = new int[capacity];
130 values = new double[capacity];
131 states = new byte[capacity];
132 this.missingEntries = missingEntries;
133 mask = capacity - 1;
134 }
135
136 /**
137 * Copy constructor.
138 * @param source map to copy
139 */
140 public OpenIntToDoubleHashMap(final OpenIntToDoubleHashMap source) {
141 final int length = source.keys.length;
142 keys = new int[length];
143 System.arraycopy(source.keys, 0, keys, 0, length);
144 values = new double[length];
145 System.arraycopy(source.values, 0, values, 0, length);
146 states = new byte[length];
147 System.arraycopy(source.states, 0, states, 0, length);
148 missingEntries = source.missingEntries;
149 size = source.size;
150 mask = source.mask;
151 count = source.count;
152 }
153
154 /**
155 * Compute the capacity needed for a given size.
156 * @param expectedSize expected size of the map
157 * @return capacity to use for the specified size
158 */
159 private static int computeCapacity(final int expectedSize) {
160 if (expectedSize == 0) {
161 return 1;
162 }
163 final int capacity = (int) Math.ceil(expectedSize / LOAD_FACTOR);
164 final int powerOfTwo = Integer.highestOneBit(capacity);
165 if (powerOfTwo == capacity) {
166 return capacity;
167 }
168 return nextPowerOfTwo(capacity);
169 }
170
171 /**
172 * Find the smallest power of two greater than the input value
173 * @param i input value
174 * @return smallest power of two greater than the input value
175 */
176 private static int nextPowerOfTwo(final int i) {
177 return Integer.highestOneBit(i) << 1;
178 }
179
180 /**
181 * Get the stored value associated with the given key
182 * @param key key associated with the data
183 * @return data associated with the key
184 */
185 public double get(final int key) {
186
187 final int hash = hashOf(key);
188 int index = hash & mask;
189 if (containsKey(key, index)) {
190 return values[index];
191 }
192
193 if (states[index] == FREE) {
194 return missingEntries;
195 }
196
197 int j = index;
198 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
199 j = probe(perturb, j);
200 index = j & mask;
201 if (containsKey(key, index)) {
202 return values[index];
203 }
204 }
205
206 return missingEntries;
207
208 }
209
210 /**
211 * Check if a value is associated with a key.
212 * @param key key to check
213 * @return true if a value is associated with key
214 */
215 public boolean containsKey(final int key) {
216
217 final int hash = hashOf(key);
218 int index = hash & mask;
219 if (containsKey(key, index)) {
220 return true;
221 }
222
223 if (states[index] == FREE) {
224 return false;
225 }
226
227 int j = index;
228 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
229 j = probe(perturb, j);
230 index = j & mask;
231 if (containsKey(key, index)) {
232 return true;
233 }
234 }
235
236 return false;
237
238 }
239
240 /**
241 * Get an iterator over map elements.
242 * <p>The specialized iterators returned are fail-fast: they throw a
243 * <code>ConcurrentModificationException</code> when they detect the map
244 * has been modified during iteration.</p>
245 * @return iterator over the map elements
246 */
247 public Iterator iterator() {
248 return new Iterator();
249 }
250
251 /**
252 * Perturb the hash for starting probing.
253 * @param hash initial hash
254 * @return perturbed hash
255 */
256 private static int perturb(final int hash) {
257 return hash & 0x7fffffff;
258 }
259
260 /**
261 * Find the index at which a key should be inserted
262 * @param key key to lookup
263 * @return index at which key should be inserted
264 */
265 private int findInsertionIndex(final int key) {
266 return findInsertionIndex(keys, states, key, mask);
267 }
268
269 /**
270 * Find the index at which a key should be inserted
271 * @param keys keys table
272 * @param states states table
273 * @param key key to lookup
274 * @param mask bit mask for hash values
275 * @return index at which key should be inserted
276 */
277 private static int findInsertionIndex(final int[] keys, final byte[] states,
278 final int key, final int mask) {
279 final int hash = hashOf(key);
280 int index = hash & mask;
281 if (states[index] == FREE) {
282 return index;
283 } else if (states[index] == FULL && keys[index] == key) {
284 return changeIndexSign(index);
285 }
286
287 int perturb = perturb(hash);
288 int j = index;
289 if (states[index] == FULL) {
290 while (true) {
291 j = probe(perturb, j);
292 index = j & mask;
293 perturb >>= PERTURB_SHIFT;
294
295 if (states[index] != FULL || keys[index] == key) {
296 break;
297 }
298 }
299 }
300
301 if (states[index] == FREE) {
302 return index;
303 } else if (states[index] == FULL) {
304 // due to the loop exit condition,
305 // if (states[index] == FULL) then keys[index] == key
306 return changeIndexSign(index);
307 }
308
309 final int firstRemoved = index;
310 while (true) {
311 j = probe(perturb, j);
312 index = j & mask;
313
314 if (states[index] == FREE) {
315 return firstRemoved;
316 } else if (states[index] == FULL && keys[index] == key) {
317 return changeIndexSign(index);
318 }
319
320 perturb >>= PERTURB_SHIFT;
321
322 }
323
324 }
325
326 /**
327 * Compute next probe for collision resolution
328 * @param perturb perturbed hash
329 * @param j previous probe
330 * @return next probe
331 */
332 private static int probe(final int perturb, final int j) {
333 return (j << 2) + j + perturb + 1;
334 }
335
336 /**
337 * Change the index sign
338 * @param index initial index
339 * @return changed index
340 */
341 private static int changeIndexSign(final int index) {
342 return -index - 1;
343 }
344
345 /**
346 * Get the number of elements stored in the map.
347 * @return number of elements stored in the map
348 */
349 public int size() {
350 return size;
351 }
352
353
354 /**
355 * Remove the value associated with a key.
356 * @param key key to which the value is associated
357 * @return removed value
358 */
359 public double remove(final int key) {
360
361 final int hash = hashOf(key);
362 int index = hash & mask;
363 if (containsKey(key, index)) {
364 return doRemove(index);
365 }
366
367 if (states[index] == FREE) {
368 return missingEntries;
369 }
370
371 int j = index;
372 for (int perturb = perturb(hash); states[index] != FREE; perturb >>= PERTURB_SHIFT) {
373 j = probe(perturb, j);
374 index = j & mask;
375 if (containsKey(key, index)) {
376 return doRemove(index);
377 }
378 }
379
380 return missingEntries;
381
382 }
383
384 /**
385 * Check if the tables contain an element associated with specified key
386 * at specified index.
387 * @param key key to check
388 * @param index index to check
389 * @return true if an element is associated with key at index
390 */
391 private boolean containsKey(final int key, final int index) {
392 return (key != 0 || states[index] == FULL) && keys[index] == key;
393 }
394
395 /**
396 * Remove an element at specified index.
397 * @param index index of the element to remove
398 * @return removed value
399 */
400 private double doRemove(int index) {
401 keys[index] = 0;
402 states[index] = REMOVED;
403 final double previous = values[index];
404 values[index] = missingEntries;
405 --size;
406 ++count;
407 return previous;
408 }
409
410 /**
411 * Put a value associated with a key in the map.
412 * @param key key to which value is associated
413 * @param value value to put in the map
414 * @return previous value associated with the key
415 */
416 public double put(final int key, final double value) {
417 int index = findInsertionIndex(key);
418 double previous = missingEntries;
419 boolean newMapping = true;
420 if (index < 0) {
421 index = changeIndexSign(index);
422 previous = values[index];
423 newMapping = false;
424 }
425 keys[index] = key;
426 states[index] = FULL;
427 values[index] = value;
428 if (newMapping) {
429 ++size;
430 if (shouldGrowTable()) {
431 growTable();
432 }
433 ++count;
434 }
435 return previous;
436
437 }
438
439 /**
440 * Grow the tables.
441 */
442 private void growTable() {
443
444 final int oldLength = states.length;
445 final int[] oldKeys = keys;
446 final double[] oldValues = values;
447 final byte[] oldStates = states;
448
449 final int newLength = RESIZE_MULTIPLIER * oldLength;
450 final int[] newKeys = new int[newLength];
451 final double[] newValues = new double[newLength];
452 final byte[] newStates = new byte[newLength];
453 final int newMask = newLength - 1;
454 for (int i = 0; i < oldLength; ++i) {
455 if (oldStates[i] == FULL) {
456 final int key = oldKeys[i];
457 final int index = findInsertionIndex(newKeys, newStates, key, newMask);
458 newKeys[index] = key;
459 newValues[index] = oldValues[i];
460 newStates[index] = FULL;
461 }
462 }
463
464 mask = newMask;
465 keys = newKeys;
466 values = newValues;
467 states = newStates;
468
469 }
470
471 /**
472 * Check if tables should grow due to increased size.
473 * @return true if tables should grow
474 */
475 private boolean shouldGrowTable() {
476 return size > (mask + 1) * LOAD_FACTOR;
477 }
478
479 /**
480 * Compute the hash value of a key
481 * @param key key to hash
482 * @return hash value of the key
483 */
484 private static int hashOf(final int key) {
485 final int h = key ^ ((key >>> 20) ^ (key >>> 12));
486 return h ^ (h >>> 7) ^ (h >>> 4);
487 }
488
489
490 /** Iterator class for the map. */
491 public class Iterator {
492
493 /** Reference modification count. */
494 private final int referenceCount;
495
496 /** Index of current element. */
497 private int current;
498
499 /** Index of next element. */
500 private int next;
501
502 /**
503 * Simple constructor.
504 */
505 private Iterator() {
506
507 // preserve the modification count of the map to detect concurrent modifications later
508 referenceCount = count;
509
510 // initialize current index
511 next = -1;
512 try {
513 advance();
514 } catch (NoSuchElementException nsee) {
515 // ignored
516 }
517
518 }
519
520 /**
521 * Check if there is a next element in the map.
522 * @return true if there is a next element
523 */
524 public boolean hasNext() {
525 return next >= 0;
526 }
527
528 /**
529 * Get the key of current entry.
530 * @return key of current entry
531 * @exception ConcurrentModificationException if the map is modified during iteration
532 * @exception NoSuchElementException if there is no element left in the map
533 */
534 public int key()
535 throws ConcurrentModificationException, NoSuchElementException {
536 if (referenceCount != count) {
537 throw MathRuntimeException.createConcurrentModificationException(
538 CONCURRENT_MODIFICATION_MESSAGE);
539 }
540 if (current < 0) {
541 throw MathRuntimeException.createNoSuchElementException(EXHAUSTED_ITERATOR_MESSAGE);
542 }
543 return keys[current];
544 }
545
546 /**
547 * Get the value of current entry.
548 * @return value of current entry
549 * @exception ConcurrentModificationException if the map is modified during iteration
550 * @exception NoSuchElementException if there is no element left in the map
551 */
552 public double value()
553 throws ConcurrentModificationException, NoSuchElementException {
554 if (referenceCount != count) {
555 throw MathRuntimeException.createConcurrentModificationException(
556 CONCURRENT_MODIFICATION_MESSAGE);
557 }
558 if (current < 0) {
559 throw MathRuntimeException.createNoSuchElementException(EXHAUSTED_ITERATOR_MESSAGE);
560 }
561 return values[current];
562 }
563
564 /**
565 * Advance iterator one step further.
566 * @exception ConcurrentModificationException if the map is modified during iteration
567 * @exception NoSuchElementException if there is no element left in the map
568 */
569 public void advance()
570 throws ConcurrentModificationException, NoSuchElementException {
571
572 if (referenceCount != count) {
573 throw MathRuntimeException.createConcurrentModificationException(
574 CONCURRENT_MODIFICATION_MESSAGE);
575 }
576
577 // advance on step
578 current = next;
579
580 // prepare next step
581 try {
582 while (states[++next] != FULL) {
583 // nothing to do
584 }
585 } catch (ArrayIndexOutOfBoundsException e) {
586 next = -2;
587 if (current < 0) {
588 throw MathRuntimeException.createNoSuchElementException(EXHAUSTED_ITERATOR_MESSAGE);
589 }
590 }
591
592 }
593
594 }
595
596 /**
597 * Read a serialized object.
598 * @param stream input stream
599 * @throws IOException if object cannot be read
600 * @throws ClassNotFoundException if the class corresponding
601 * to the serialized object cannot be found
602 */
603 private void readObject(final ObjectInputStream stream)
604 throws IOException, ClassNotFoundException {
605 stream.defaultReadObject();
606 count = 0;
607 }
608
609
610 }