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 }