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