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