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 }