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