1 /******************************************************************************* 2 * Copyright 2011 See AUTHORS file. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 ******************************************************************************/ 16 17 package com.badlogic.gdx.utils; 18 19 import java.util.Iterator; 20 import java.util.NoSuchElementException; 21 22 import com.badlogic.gdx.math.MathUtils; 23 24 /** An unordered map that uses long keys. This implementation is a cuckoo hash map using 3 hashes, random walking, and a small 25 * stash for problematic keys. Null values are allowed. No allocation is done except when growing the table size. <br> 26 * <br> 27 * This map performs very fast get, containsKey, and remove (typically O(1), worst case O(log(n))). Put may be a bit slower, 28 * depending on hash collisions. Load factors greater than 0.91 greatly increase the chances the map will have to rehash to the 29 * next higher POT size. 30 * @author Nathan Sweet */ 31 public class LongMap<V> implements Iterable<LongMap.Entry<V>> { 32 private static final int PRIME1 = 0xbe1f14b1; 33 private static final int PRIME2 = 0xb4b82e39; 34 private static final int PRIME3 = 0xced1c241; 35 private static final int EMPTY = 0; 36 37 public int size; 38 39 long[] keyTable; 40 V[] valueTable; 41 int capacity, stashSize; 42 V zeroValue; 43 boolean hasZeroValue; 44 45 private float loadFactor; 46 private int hashShift, mask, threshold; 47 private int stashCapacity; 48 private int pushIterations; 49 50 private Entries entries1, entries2; 51 private Values values1, values2; 52 private Keys keys1, keys2; 53 54 /** Creates a new map with an initial capacity of 51 and a load factor of 0.8. */ 55 public LongMap () { 56 this(51, 0.8f); 57 } 58 59 /** Creates a new map with a load factor of 0.8. 60 * @param initialCapacity If not a power of two, it is increased to the next nearest power of two. */ 61 public LongMap (int initialCapacity) { 62 this(initialCapacity, 0.8f); 63 } 64 65 /** Creates a new map with the specified initial capacity and load factor. This map will hold initialCapacity items before 66 * growing the backing table. 67 * @param initialCapacity If not a power of two, it is increased to the next nearest power of two. */ 68 public LongMap (int initialCapacity, float loadFactor) { 69 if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be >= 0: " + initialCapacity); 70 initialCapacity = MathUtils.nextPowerOfTwo((int)Math.ceil(initialCapacity / loadFactor)); 71 if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large: " + initialCapacity); 72 capacity = initialCapacity; 73 74 if (loadFactor <= 0) throw new IllegalArgumentException("loadFactor must be > 0: " + loadFactor); 75 this.loadFactor = loadFactor; 76 77 threshold = (int)(capacity * loadFactor); 78 mask = capacity - 1; 79 hashShift = 63 - Long.numberOfTrailingZeros(capacity); 80 stashCapacity = Math.max(3, (int)Math.ceil(Math.log(capacity)) * 2); 81 pushIterations = Math.max(Math.min(capacity, 8), (int)Math.sqrt(capacity) / 8); 82 83 keyTable = new long[capacity + stashCapacity]; 84 valueTable = (V[])new Object[keyTable.length]; 85 } 86 87 /** Creates a new map identical to the specified map. */ 88 public LongMap (LongMap<? extends V> map) { 89 this((int)Math.floor(map.capacity * map.loadFactor), map.loadFactor); 90 stashSize = map.stashSize; 91 System.arraycopy(map.keyTable, 0, keyTable, 0, map.keyTable.length); 92 System.arraycopy(map.valueTable, 0, valueTable, 0, map.valueTable.length); 93 size = map.size; 94 zeroValue = map.zeroValue; 95 hasZeroValue = map.hasZeroValue; 96 } 97 98 public V put (long key, V value) { 99 if (key == 0) { 100 V oldValue = zeroValue; 101 zeroValue = value; 102 if (!hasZeroValue) { 103 hasZeroValue = true; 104 size++; 105 } 106 return oldValue; 107 } 108 109 long[] keyTable = this.keyTable; 110 111 // Check for existing keys. 112 int index1 = (int)(key & mask); 113 long key1 = keyTable[index1]; 114 if (key1 == key) { 115 V oldValue = valueTable[index1]; 116 valueTable[index1] = value; 117 return oldValue; 118 } 119 120 int index2 = hash2(key); 121 long key2 = keyTable[index2]; 122 if (key2 == key) { 123 V oldValue = valueTable[index2]; 124 valueTable[index2] = value; 125 return oldValue; 126 } 127 128 int index3 = hash3(key); 129 long key3 = keyTable[index3]; 130 if (key3 == key) { 131 V oldValue = valueTable[index3]; 132 valueTable[index3] = value; 133 return oldValue; 134 } 135 136 // Update key in the stash. 137 for (int i = capacity, n = i + stashSize; i < n; i++) { 138 if (keyTable[i] == key) { 139 V oldValue = valueTable[i]; 140 valueTable[i] = value; 141 return oldValue; 142 } 143 } 144 145 // Check for empty buckets. 146 if (key1 == EMPTY) { 147 keyTable[index1] = key; 148 valueTable[index1] = value; 149 if (size++ >= threshold) resize(capacity << 1); 150 return null; 151 } 152 153 if (key2 == EMPTY) { 154 keyTable[index2] = key; 155 valueTable[index2] = value; 156 if (size++ >= threshold) resize(capacity << 1); 157 return null; 158 } 159 160 if (key3 == EMPTY) { 161 keyTable[index3] = key; 162 valueTable[index3] = value; 163 if (size++ >= threshold) resize(capacity << 1); 164 return null; 165 } 166 167 push(key, value, index1, key1, index2, key2, index3, key3); 168 return null; 169 } 170 171 public void putAll (LongMap<V> map) { 172 for (Entry<V> entry : map.entries()) 173 put(entry.key, entry.value); 174 } 175 176 /** Skips checks for existing keys. */ 177 private void putResize (long key, V value) { 178 if (key == 0) { 179 zeroValue = value; 180 hasZeroValue = true; 181 return; 182 } 183 184 // Check for empty buckets. 185 int index1 = (int)(key & mask); 186 long key1 = keyTable[index1]; 187 if (key1 == EMPTY) { 188 keyTable[index1] = key; 189 valueTable[index1] = value; 190 if (size++ >= threshold) resize(capacity << 1); 191 return; 192 } 193 194 int index2 = hash2(key); 195 long key2 = keyTable[index2]; 196 if (key2 == EMPTY) { 197 keyTable[index2] = key; 198 valueTable[index2] = value; 199 if (size++ >= threshold) resize(capacity << 1); 200 return; 201 } 202 203 int index3 = hash3(key); 204 long key3 = keyTable[index3]; 205 if (key3 == EMPTY) { 206 keyTable[index3] = key; 207 valueTable[index3] = value; 208 if (size++ >= threshold) resize(capacity << 1); 209 return; 210 } 211 212 push(key, value, index1, key1, index2, key2, index3, key3); 213 } 214 215 private void push (long insertKey, V insertValue, int index1, long key1, int index2, long key2, int index3, long key3) { 216 long[] keyTable = this.keyTable; 217 V[] valueTable = this.valueTable; 218 int mask = this.mask; 219 220 // Push keys until an empty bucket is found. 221 long evictedKey; 222 V evictedValue; 223 int i = 0, pushIterations = this.pushIterations; 224 do { 225 // Replace the key and value for one of the hashes. 226 switch (MathUtils.random(2)) { 227 case 0: 228 evictedKey = key1; 229 evictedValue = valueTable[index1]; 230 keyTable[index1] = insertKey; 231 valueTable[index1] = insertValue; 232 break; 233 case 1: 234 evictedKey = key2; 235 evictedValue = valueTable[index2]; 236 keyTable[index2] = insertKey; 237 valueTable[index2] = insertValue; 238 break; 239 default: 240 evictedKey = key3; 241 evictedValue = valueTable[index3]; 242 keyTable[index3] = insertKey; 243 valueTable[index3] = insertValue; 244 break; 245 } 246 247 // If the evicted key hashes to an empty bucket, put it there and stop. 248 index1 = (int)(evictedKey & mask); 249 key1 = keyTable[index1]; 250 if (key1 == EMPTY) { 251 keyTable[index1] = evictedKey; 252 valueTable[index1] = evictedValue; 253 if (size++ >= threshold) resize(capacity << 1); 254 return; 255 } 256 257 index2 = hash2(evictedKey); 258 key2 = keyTable[index2]; 259 if (key2 == EMPTY) { 260 keyTable[index2] = evictedKey; 261 valueTable[index2] = evictedValue; 262 if (size++ >= threshold) resize(capacity << 1); 263 return; 264 } 265 266 index3 = hash3(evictedKey); 267 key3 = keyTable[index3]; 268 if (key3 == EMPTY) { 269 keyTable[index3] = evictedKey; 270 valueTable[index3] = evictedValue; 271 if (size++ >= threshold) resize(capacity << 1); 272 return; 273 } 274 275 if (++i == pushIterations) break; 276 277 insertKey = evictedKey; 278 insertValue = evictedValue; 279 } while (true); 280 281 putStash(evictedKey, evictedValue); 282 } 283 284 private void putStash (long key, V value) { 285 if (stashSize == stashCapacity) { 286 // Too many pushes occurred and the stash is full, increase the table size. 287 resize(capacity << 1); 288 put(key, value); 289 return; 290 } 291 // Store key in the stash. 292 int index = capacity + stashSize; 293 keyTable[index] = key; 294 valueTable[index] = value; 295 stashSize++; 296 size++; 297 } 298 299 public V get (long key) { 300 if (key == 0) { 301 if (!hasZeroValue) return null; 302 return zeroValue; 303 } 304 int index = (int)(key & mask); 305 if (keyTable[index] != key) { 306 index = hash2(key); 307 if (keyTable[index] != key) { 308 index = hash3(key); 309 if (keyTable[index] != key) return getStash(key, null); 310 } 311 } 312 return valueTable[index]; 313 } 314 315 public V get (long key, V defaultValue) { 316 if (key == 0) { 317 if (!hasZeroValue) return defaultValue; 318 return zeroValue; 319 } 320 int index = (int)(key & mask); 321 if (keyTable[index] != key) { 322 index = hash2(key); 323 if (keyTable[index] != key) { 324 index = hash3(key); 325 if (keyTable[index] != key) return getStash(key, defaultValue); 326 } 327 } 328 return valueTable[index]; 329 } 330 331 private V getStash (long key, V defaultValue) { 332 long[] keyTable = this.keyTable; 333 for (int i = capacity, n = i + stashSize; i < n; i++) 334 if (keyTable[i] == key) return valueTable[i]; 335 return defaultValue; 336 } 337 338 public V remove (long key) { 339 if (key == 0) { 340 if (!hasZeroValue) return null; 341 V oldValue = zeroValue; 342 zeroValue = null; 343 hasZeroValue = false; 344 size--; 345 return oldValue; 346 } 347 348 int index = (int)(key & mask); 349 if (keyTable[index] == key) { 350 keyTable[index] = EMPTY; 351 V oldValue = valueTable[index]; 352 valueTable[index] = null; 353 size--; 354 return oldValue; 355 } 356 357 index = hash2(key); 358 if (keyTable[index] == key) { 359 keyTable[index] = EMPTY; 360 V oldValue = valueTable[index]; 361 valueTable[index] = null; 362 size--; 363 return oldValue; 364 } 365 366 index = hash3(key); 367 if (keyTable[index] == key) { 368 keyTable[index] = EMPTY; 369 V oldValue = valueTable[index]; 370 valueTable[index] = null; 371 size--; 372 return oldValue; 373 } 374 375 return removeStash(key); 376 } 377 378 V removeStash (long key) { 379 long[] keyTable = this.keyTable; 380 for (int i = capacity, n = i + stashSize; i < n; i++) { 381 if (keyTable[i] == key) { 382 V oldValue = valueTable[i]; 383 removeStashIndex(i); 384 size--; 385 return oldValue; 386 } 387 } 388 return null; 389 } 390 391 void removeStashIndex (int index) { 392 // If the removed location was not last, move the last tuple to the removed location. 393 stashSize--; 394 int lastIndex = capacity + stashSize; 395 if (index < lastIndex) { 396 keyTable[index] = keyTable[lastIndex]; 397 valueTable[index] = valueTable[lastIndex]; 398 valueTable[lastIndex] = null; 399 } else 400 valueTable[index] = null; 401 } 402 403 /** Reduces the size of the backing arrays to be the specified capacity or less. If the capacity is already less, nothing is 404 * done. If the map contains more items than the specified capacity, the next highest power of two capacity is used instead. */ 405 public void shrink (int maximumCapacity) { 406 if (maximumCapacity < 0) throw new IllegalArgumentException("maximumCapacity must be >= 0: " + maximumCapacity); 407 if (size > maximumCapacity) maximumCapacity = size; 408 if (capacity <= maximumCapacity) return; 409 maximumCapacity = MathUtils.nextPowerOfTwo(maximumCapacity); 410 resize(maximumCapacity); 411 } 412 413 /** Clears the map and reduces the size of the backing arrays to be the specified capacity if they are larger. */ 414 public void clear (int maximumCapacity) { 415 if (capacity <= maximumCapacity) { 416 clear(); 417 return; 418 } 419 zeroValue = null; 420 hasZeroValue = false; 421 size = 0; 422 resize(maximumCapacity); 423 } 424 425 public void clear () { 426 if (size == 0) return; 427 long[] keyTable = this.keyTable; 428 V[] valueTable = this.valueTable; 429 for (int i = capacity + stashSize; i-- > 0;) { 430 keyTable[i] = EMPTY; 431 valueTable[i] = null; 432 } 433 size = 0; 434 stashSize = 0; 435 zeroValue = null; 436 hasZeroValue = false; 437 } 438 439 /** Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may be 440 * an expensive operation. */ 441 public boolean containsValue (Object value, boolean identity) { 442 V[] valueTable = this.valueTable; 443 if (value == null) { 444 if (hasZeroValue && zeroValue == null) return true; 445 long[] keyTable = this.keyTable; 446 for (int i = capacity + stashSize; i-- > 0;) 447 if (keyTable[i] != EMPTY && valueTable[i] == null) return true; 448 } else if (identity) { 449 if (value == zeroValue) return true; 450 for (int i = capacity + stashSize; i-- > 0;) 451 if (valueTable[i] == value) return true; 452 } else { 453 if (hasZeroValue && value.equals(zeroValue)) return true; 454 for (int i = capacity + stashSize; i-- > 0;) 455 if (value.equals(valueTable[i])) return true; 456 } 457 return false; 458 } 459 460 public boolean containsKey (long key) { 461 if (key == 0) return hasZeroValue; 462 int index = (int)(key & mask); 463 if (keyTable[index] != key) { 464 index = hash2(key); 465 if (keyTable[index] != key) { 466 index = hash3(key); 467 if (keyTable[index] != key) return containsKeyStash(key); 468 } 469 } 470 return true; 471 } 472 473 private boolean containsKeyStash (long key) { 474 long[] keyTable = this.keyTable; 475 for (int i = capacity, n = i + stashSize; i < n; i++) 476 if (keyTable[i] == key) return true; 477 return false; 478 } 479 480 /** Returns the key for the specified value, or <tt>notFound</tt> if it is not in the map. Note this traverses the entire map 481 * and compares every value, which may be an expensive operation. 482 * @param identity If true, uses == to compare the specified value with values in the map. If false, uses 483 * {@link #equals(Object)}. */ 484 public long findKey (Object value, boolean identity, long notFound) { 485 V[] valueTable = this.valueTable; 486 if (value == null) { 487 if (hasZeroValue && zeroValue == null) return 0; 488 long[] keyTable = this.keyTable; 489 for (int i = capacity + stashSize; i-- > 0;) 490 if (keyTable[i] != EMPTY && valueTable[i] == null) return keyTable[i]; 491 } else if (identity) { 492 if (value == zeroValue) return 0; 493 for (int i = capacity + stashSize; i-- > 0;) 494 if (valueTable[i] == value) return keyTable[i]; 495 } else { 496 if (hasZeroValue && value.equals(zeroValue)) return 0; 497 for (int i = capacity + stashSize; i-- > 0;) 498 if (value.equals(valueTable[i])) return keyTable[i]; 499 } 500 return notFound; 501 } 502 503 /** Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many 504 * items to avoid multiple backing array resizes. */ 505 public void ensureCapacity (int additionalCapacity) { 506 int sizeNeeded = size + additionalCapacity; 507 if (sizeNeeded >= threshold) resize(MathUtils.nextPowerOfTwo((int)Math.ceil(sizeNeeded / loadFactor))); 508 } 509 510 private void resize (int newSize) { 511 int oldEndIndex = capacity + stashSize; 512 513 capacity = newSize; 514 threshold = (int)(newSize * loadFactor); 515 mask = newSize - 1; 516 hashShift = 63 - Long.numberOfTrailingZeros(newSize); 517 stashCapacity = Math.max(3, (int)Math.ceil(Math.log(newSize)) * 2); 518 pushIterations = Math.max(Math.min(newSize, 8), (int)Math.sqrt(newSize) / 8); 519 520 long[] oldKeyTable = keyTable; 521 V[] oldValueTable = valueTable; 522 523 keyTable = new long[newSize + stashCapacity]; 524 valueTable = (V[])new Object[newSize + stashCapacity]; 525 526 int oldSize = size; 527 size = hasZeroValue ? 1 : 0; 528 stashSize = 0; 529 if (oldSize > 0) { 530 for (int i = 0; i < oldEndIndex; i++) { 531 long key = oldKeyTable[i]; 532 if (key != EMPTY) putResize(key, oldValueTable[i]); 533 } 534 } 535 } 536 537 private int hash2 (long h) { 538 h *= PRIME2; 539 return (int)((h ^ h >>> hashShift) & mask); 540 } 541 542 private int hash3 (long h) { 543 h *= PRIME3; 544 return (int)((h ^ h >>> hashShift) & mask); 545 } 546 547 public int hashCode () { 548 int h = 0; 549 if (hasZeroValue && zeroValue != null) { 550 h += zeroValue.hashCode(); 551 } 552 long[] keyTable = this.keyTable; 553 V[] valueTable = this.valueTable; 554 for (int i = 0, n = capacity + stashSize; i < n; i++) { 555 long key = keyTable[i]; 556 if (key != EMPTY) { 557 h += (int)(key ^ (key >>> 32)) * 31; 558 559 V value = valueTable[i]; 560 if (value != null) { 561 h += value.hashCode(); 562 } 563 } 564 } 565 return h; 566 } 567 568 public boolean equals (Object obj) { 569 if (obj == this) return true; 570 if (!(obj instanceof LongMap)) return false; 571 LongMap<V> other = (LongMap)obj; 572 if (other.size != size) return false; 573 if (other.hasZeroValue != hasZeroValue) return false; 574 if (hasZeroValue) { 575 if (other.zeroValue == null) { 576 if (zeroValue != null) return false; 577 } else { 578 if (!other.zeroValue.equals(zeroValue)) return false; 579 } 580 } 581 long[] keyTable = this.keyTable; 582 V[] valueTable = this.valueTable; 583 for (int i = 0, n = capacity + stashSize; i < n; i++) { 584 long key = keyTable[i]; 585 if (key != EMPTY) { 586 V value = valueTable[i]; 587 if (value == null) { 588 if (!other.containsKey(key) || other.get(key) != null) { 589 return false; 590 } 591 } else { 592 if (!value.equals(other.get(key))) { 593 return false; 594 } 595 } 596 } 597 } 598 return true; 599 } 600 601 public String toString () { 602 if (size == 0) return "[]"; 603 StringBuilder buffer = new StringBuilder(32); 604 buffer.append('['); 605 long[] keyTable = this.keyTable; 606 V[] valueTable = this.valueTable; 607 int i = keyTable.length; 608 while (i-- > 0) { 609 long key = keyTable[i]; 610 if (key == EMPTY) continue; 611 buffer.append(key); 612 buffer.append('='); 613 buffer.append(valueTable[i]); 614 break; 615 } 616 while (i-- > 0) { 617 long key = keyTable[i]; 618 if (key == EMPTY) continue; 619 buffer.append(", "); 620 buffer.append(key); 621 buffer.append('='); 622 buffer.append(valueTable[i]); 623 } 624 buffer.append(']'); 625 return buffer.toString(); 626 } 627 628 public Iterator<Entry<V>> iterator () { 629 return entries(); 630 } 631 632 /** Returns an iterator for the entries in the map. Remove is supported. Note that the same iterator instance is returned each 633 * time this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. */ 634 public Entries<V> entries () { 635 if (entries1 == null) { 636 entries1 = new Entries(this); 637 entries2 = new Entries(this); 638 } 639 if (!entries1.valid) { 640 entries1.reset(); 641 entries1.valid = true; 642 entries2.valid = false; 643 return entries1; 644 } 645 entries2.reset(); 646 entries2.valid = true; 647 entries1.valid = false; 648 return entries2; 649 } 650 651 /** Returns an iterator for the values in the map. Remove is supported. Note that the same iterator instance is returned each 652 * time this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. */ 653 public Values<V> values () { 654 if (values1 == null) { 655 values1 = new Values(this); 656 values2 = new Values(this); 657 } 658 if (!values1.valid) { 659 values1.reset(); 660 values1.valid = true; 661 values2.valid = false; 662 return values1; 663 } 664 values2.reset(); 665 values2.valid = true; 666 values1.valid = false; 667 return values2; 668 } 669 670 /** Returns an iterator for the keys in the map. Remove is supported. Note that the same iterator instance is returned each time 671 * this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. */ 672 public Keys keys () { 673 if (keys1 == null) { 674 keys1 = new Keys(this); 675 keys2 = new Keys(this); 676 } 677 if (!keys1.valid) { 678 keys1.reset(); 679 keys1.valid = true; 680 keys2.valid = false; 681 return keys1; 682 } 683 keys2.reset(); 684 keys2.valid = true; 685 keys1.valid = false; 686 return keys2; 687 } 688 689 static public class Entry<V> { 690 public long key; 691 public V value; 692 693 public String toString () { 694 return key + "=" + value; 695 } 696 } 697 698 static private class MapIterator<V> { 699 static final int INDEX_ILLEGAL = -2; 700 static final int INDEX_ZERO = -1; 701 702 public boolean hasNext; 703 704 final LongMap<V> map; 705 int nextIndex, currentIndex; 706 boolean valid = true; 707 708 public MapIterator (LongMap<V> map) { 709 this.map = map; 710 reset(); 711 } 712 713 public void reset () { 714 currentIndex = INDEX_ILLEGAL; 715 nextIndex = INDEX_ZERO; 716 if (map.hasZeroValue) 717 hasNext = true; 718 else 719 findNextIndex(); 720 } 721 722 void findNextIndex () { 723 hasNext = false; 724 long[] keyTable = map.keyTable; 725 for (int n = map.capacity + map.stashSize; ++nextIndex < n;) { 726 if (keyTable[nextIndex] != EMPTY) { 727 hasNext = true; 728 break; 729 } 730 } 731 } 732 733 public void remove () { 734 if (currentIndex == INDEX_ZERO && map.hasZeroValue) { 735 map.zeroValue = null; 736 map.hasZeroValue = false; 737 } else if (currentIndex < 0) { 738 throw new IllegalStateException("next must be called before remove."); 739 } else if (currentIndex >= map.capacity) { 740 map.removeStashIndex(currentIndex); 741 nextIndex = currentIndex - 1; 742 findNextIndex(); 743 } else { 744 map.keyTable[currentIndex] = EMPTY; 745 map.valueTable[currentIndex] = null; 746 } 747 currentIndex = INDEX_ILLEGAL; 748 map.size--; 749 } 750 } 751 752 static public class Entries<V> extends MapIterator<V> implements Iterable<Entry<V>>, Iterator<Entry<V>> { 753 private Entry<V> entry = new Entry(); 754 755 public Entries (LongMap map) { 756 super(map); 757 } 758 759 /** Note the same entry instance is returned each time this method is called. */ 760 public Entry<V> next () { 761 if (!hasNext) throw new NoSuchElementException(); 762 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 763 long[] keyTable = map.keyTable; 764 if (nextIndex == INDEX_ZERO) { 765 entry.key = 0; 766 entry.value = map.zeroValue; 767 } else { 768 entry.key = keyTable[nextIndex]; 769 entry.value = map.valueTable[nextIndex]; 770 } 771 currentIndex = nextIndex; 772 findNextIndex(); 773 return entry; 774 } 775 776 public boolean hasNext () { 777 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 778 return hasNext; 779 } 780 781 public Iterator<Entry<V>> iterator () { 782 return this; 783 } 784 785 public void remove () { 786 super.remove(); 787 } 788 } 789 790 static public class Values<V> extends MapIterator<V> implements Iterable<V>, Iterator<V> { 791 public Values (LongMap<V> map) { 792 super(map); 793 } 794 795 public boolean hasNext () { 796 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 797 return hasNext; 798 } 799 800 public V next () { 801 if (!hasNext) throw new NoSuchElementException(); 802 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 803 V value; 804 if (nextIndex == INDEX_ZERO) 805 value = map.zeroValue; 806 else 807 value = map.valueTable[nextIndex]; 808 currentIndex = nextIndex; 809 findNextIndex(); 810 return value; 811 } 812 813 public Iterator<V> iterator () { 814 return this; 815 } 816 817 /** Returns a new array containing the remaining values. */ 818 public Array<V> toArray () { 819 Array array = new Array(true, map.size); 820 while (hasNext) 821 array.add(next()); 822 return array; 823 } 824 825 public void remove () { 826 super.remove(); 827 } 828 } 829 830 static public class Keys extends MapIterator { 831 public Keys (LongMap map) { 832 super(map); 833 } 834 835 public long next () { 836 if (!hasNext) throw new NoSuchElementException(); 837 if (!valid) throw new GdxRuntimeException("#iterator() cannot be used nested."); 838 long key = nextIndex == INDEX_ZERO ? 0 : map.keyTable[nextIndex]; 839 currentIndex = nextIndex; 840 findNextIndex(); 841 return key; 842 } 843 844 /** Returns a new array containing the remaining values. */ 845 public LongArray toArray () { 846 LongArray array = new LongArray(true, map.size); 847 while (hasNext) 848 array.add(next()); 849 return array; 850 } 851 } 852 } 853