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