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