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 */ 17package org.apache.commons.math.util; 18 19import java.io.IOException; 20import java.io.ObjectInputStream; 21import java.io.Serializable; 22import java.lang.reflect.Array; 23import java.util.ConcurrentModificationException; 24import java.util.NoSuchElementException; 25 26import org.apache.commons.math.Field; 27import org.apache.commons.math.FieldElement; 28import org.apache.commons.math.MathRuntimeException; 29import 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 */ 43public 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} 621