001/******************************************************************************* 002 * Copyright 2011 See AUTHORS file. 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 ******************************************************************************/ 016 017package squidpony.squidmath; 018 019import java.io.Serializable; 020import java.util.*; 021 022/** An unordered map of regions (specifically, packed data from CoordPacker or something that uses it, like FOVCache or 023 * ZOI, as short arrays) to values of a generic type. Regions can overlap, and you can technically store the same set of 024 * points as two or more different keys by appending 0 multiple times, which doesn't change the cells encoded in a short 025 * array of packed data but does cause it to be hashed differently and thus not over-write the previous region in this 026 * RegionMap. Overlapping areas can be useful, since this provides a way to find all values associated with regions 027 * containing a given point using the method allAt(), in a way that is similar to a multimap data structure. 028 * <br> 029 * Normal Java Maps aren't meant to use primitive arrays as keys, in part because they are mutable and in part because 030 * the equals() method on an array isn't exactly correct for this purpose. Here, we have the collection specialized for 031 * short[] keys (which still should not be mutated!), use Arrays.equals() for comparing equality, and use 032 * CrossHash.hash() for hashing short arrays efficiently. 033 * <br> 034 * Ported from LibGDX (original class was ObjectMap) by Tommy Ettinger on 1/25/2016. 035 * @author Nathan Sweet 036 * @author Tommy Ettinger 037 */ 038public class RegionMap<V> implements Iterable<RegionMap.Entry<V>>, Serializable { 039 private static final long serialVersionUID = -6026166931953522091L; 040 private static final int PRIME1 = 0xbe1f14b1; 041 private static final int PRIME2 = 0xb4b82e39; 042 private static final int PRIME3 = 0xced1c241; 043 private LightRNG lrng = new LightRNG(0xbadfad); 044 public int size; 045 046 short[][] keyTable; 047 V[] valueTable; 048 int capacity, stashSize; 049 050 private float loadFactor; 051 private int hashShift, mask, threshold; 052 private int stashCapacity; 053 private int pushIterations; 054 055 private Entries<V> entries1, entries2; 056 private Values<V> values1, values2; 057 private Keys keys1, keys2; 058 059 /** Creates a new map with an initial capacity of 51 and a load factor of 0.8. */ 060 public RegionMap () { 061 this(51, 0.8f); 062 } 063 064 /** Creates a new map with a load factor of 0.8. 065 * @param initialCapacity If not a power of two, it is increased to the next nearest power of two. */ 066 public RegionMap (int initialCapacity) { 067 this(initialCapacity, 0.8f); 068 } 069 070 /** Creates a new map with the specified initial capacity and load factor. This map will hold initialCapacity items before 071 * growing the backing table. 072 * @param initialCapacity If not a power of two, it is increased to the next nearest power of two. */ 073 @SuppressWarnings("unchecked") 074 public RegionMap (int initialCapacity, float loadFactor) { 075 if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be >= 0: " + initialCapacity); 076 initialCapacity = nextPowerOfTwo((int)Math.ceil(initialCapacity / loadFactor)); 077 if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large: " + initialCapacity); 078 capacity = initialCapacity; 079 080 if (loadFactor <= 0) throw new IllegalArgumentException("loadFactor must be > 0: " + loadFactor); 081 this.loadFactor = loadFactor; 082 083 threshold = (int)(capacity * loadFactor); 084 mask = capacity - 1; 085 hashShift = 31 - Integer.numberOfTrailingZeros(capacity); 086 stashCapacity = Math.max(3, (int)Math.ceil(Math.log(capacity)) * 2); 087 pushIterations = Math.max(Math.min(capacity, 8), (int)Math.sqrt(capacity) / 8); 088 089 keyTable = new short[capacity + stashCapacity][]; 090 valueTable = (V[])new Object[keyTable.length]; 091 } 092 093 /** Creates a new map identical to the specified map. */ 094 public RegionMap (RegionMap<? extends V> map) { 095 this(map.capacity, map.loadFactor); 096 stashSize = map.stashSize; 097 System.arraycopy(map.keyTable, 0, keyTable, 0, map.keyTable.length); 098 System.arraycopy(map.valueTable, 0, valueTable, 0, map.valueTable.length); 099 size = map.size; 100 } 101 102 /** Returns the old value associated with the specified key, or null. */ 103 public V put (short[] key, V value) { 104 if (key == null) throw new IllegalArgumentException("key cannot be null."); 105 return put_internal(key, value); 106 } 107 108 private V put_internal (short[] key, V value) { 109 short[][] keyTable = this.keyTable; 110 111 // Check for existing keys. 112 int hashCode = CrossHash.hash(key); 113 int index1 = hashCode & mask; 114 short[] key1 = keyTable[index1]; 115 if (Arrays.equals(key, key1)) { 116 V oldValue = valueTable[index1]; 117 valueTable[index1] = value; 118 return oldValue; 119 } 120 121 int index2 = hash2(hashCode); 122 short[] key2 = keyTable[index2]; 123 if (Arrays.equals(key, key2)) { 124 V oldValue = valueTable[index2]; 125 valueTable[index2] = value; 126 return oldValue; 127 } 128 129 int index3 = hash3(hashCode); 130 short[] key3 = keyTable[index3]; 131 if (Arrays.equals(key, key3)) { 132 V oldValue = valueTable[index3]; 133 valueTable[index3] = value; 134 return oldValue; 135 } 136 137 // Update key in the stash. 138 for (int i = capacity, n = i + stashSize; i < n; i++) { 139 if (Arrays.equals(key, keyTable[i])) { 140 V oldValue = valueTable[i]; 141 valueTable[i] = value; 142 return oldValue; 143 } 144 } 145 146 // Check for empty buckets. 147 if (key1 == null) { 148 keyTable[index1] = key; 149 valueTable[index1] = value; 150 if (size++ >= threshold) resize(capacity << 1); 151 return null; 152 } 153 154 if (key2 == null) { 155 keyTable[index2] = key; 156 valueTable[index2] = value; 157 if (size++ >= threshold) resize(capacity << 1); 158 return null; 159 } 160 161 if (key3 == null) { 162 keyTable[index3] = key; 163 valueTable[index3] = value; 164 if (size++ >= threshold) resize(capacity << 1); 165 return null; 166 } 167 168 push(key, value, index1, key1, index2, key2, index3, key3); 169 return null; 170 } 171 172 public void putAll (RegionMap<V> map) { 173 ensureCapacity(map.size); 174 for (Entry<V> entry : map) 175 put(entry.key, entry.value); 176 } 177 178 /** Skips checks for existing keys. */ 179 private void putResize (short[] key, V value) { 180 // Check for empty buckets. 181 int hashCode = CrossHash.hash(key); 182 int index1 = hashCode & mask; 183 short[] key1 = keyTable[index1]; 184 if (key1 == null) { 185 keyTable[index1] = key; 186 valueTable[index1] = value; 187 if (size++ >= threshold) resize(capacity << 1); 188 return; 189 } 190 191 int index2 = hash2(hashCode); 192 short[] key2 = keyTable[index2]; 193 if (key2 == null) { 194 keyTable[index2] = key; 195 valueTable[index2] = value; 196 if (size++ >= threshold) resize(capacity << 1); 197 return; 198 } 199 200 int index3 = hash3(hashCode); 201 short[] key3 = keyTable[index3]; 202 if (key3 == null) { 203 keyTable[index3] = key; 204 valueTable[index3] = value; 205 if (size++ >= threshold) resize(capacity << 1); 206 return; 207 } 208 209 push(key, value, index1, key1, index2, key2, index3, key3); 210 } 211 212 private void push (short[] insertKey, V insertValue, int index1, short[] key1, int index2, short[] key2, int index3, short[] key3) { 213 short[][] keyTable = this.keyTable; 214 V[] valueTable = this.valueTable; 215 int mask = this.mask; 216 217 // Push keys until an empty bucket is found. 218 short[] evictedKey; 219 V evictedValue; 220 int i = 0, pushIterations = this.pushIterations; 221 do { 222 // Replace the key and value for one of the hashes. 223 switch (lrng.nextInt(2)) { 224 case 0: 225 evictedKey = key1; 226 evictedValue = valueTable[index1]; 227 keyTable[index1] = insertKey; 228 valueTable[index1] = insertValue; 229 break; 230 case 1: 231 evictedKey = key2; 232 evictedValue = valueTable[index2]; 233 keyTable[index2] = insertKey; 234 valueTable[index2] = insertValue; 235 break; 236 default: 237 evictedKey = key3; 238 evictedValue = valueTable[index3]; 239 keyTable[index3] = insertKey; 240 valueTable[index3] = insertValue; 241 break; 242 } 243 244 // If the evicted key hashes to an empty bucket, put it there and stop. 245 int hashCode = CrossHash.hash(evictedKey); 246 index1 = hashCode & mask; 247 key1 = keyTable[index1]; 248 if (key1 == null) { 249 keyTable[index1] = evictedKey; 250 valueTable[index1] = evictedValue; 251 if (size++ >= threshold) resize(capacity << 1); 252 return; 253 } 254 255 index2 = hash2(hashCode); 256 key2 = keyTable[index2]; 257 if (key2 == null) { 258 keyTable[index2] = evictedKey; 259 valueTable[index2] = evictedValue; 260 if (size++ >= threshold) resize(capacity << 1); 261 return; 262 } 263 264 index3 = hash3(hashCode); 265 key3 = keyTable[index3]; 266 if (key3 == null) { 267 keyTable[index3] = evictedKey; 268 valueTable[index3] = evictedValue; 269 if (size++ >= threshold) resize(capacity << 1); 270 return; 271 } 272 273 if (++i == pushIterations) break; 274 275 insertKey = evictedKey; 276 insertValue = evictedValue; 277 } while (true); 278 279 putStash(evictedKey, evictedValue); 280 } 281 282 private void putStash (short[] key, V value) { 283 if (stashSize == stashCapacity) { 284 // Too many pushes occurred and the stash is full, increase the table size. 285 resize(capacity << 1); 286 put_internal(key, value); 287 return; 288 } 289 // Store key in the stash. 290 int index = capacity + stashSize; 291 keyTable[index] = key; 292 valueTable[index] = value; 293 stashSize++; 294 size++; 295 } 296 297 public V get (short[] key) { 298 int hashCode = CrossHash.hash(key); 299 int index = hashCode & mask; 300 if (!Arrays.equals(key, keyTable[index])) { 301 index = hash2(hashCode); 302 if (!Arrays.equals(key, keyTable[index])) { 303 index = hash3(hashCode); 304 if (!Arrays.equals(key, keyTable[index])) return getStash(key); 305 } 306 } 307 return valueTable[index]; 308 } 309 310 private V getStash (short[] key) { 311 short[][] keyTable = this.keyTable; 312 for (int i = capacity, n = i + stashSize; i < n; i++) 313 if (Arrays.equals(key, keyTable[i])) return valueTable[i]; 314 return null; 315 } 316 317 /** Returns the value for the specified key, or the default value if the key is not in the map. */ 318 public V get (short[] key, V defaultValue) { 319 int hashCode = CrossHash.hash(key); 320 int index = hashCode & mask; 321 if (!Arrays.equals(key, keyTable[index])) { 322 index = hash2(hashCode); 323 if (!Arrays.equals(key, keyTable[index])) { 324 index = hash3(hashCode); 325 if (!Arrays.equals(key, keyTable[index])) return getStash(key, defaultValue); 326 } 327 } 328 return valueTable[index]; 329 } 330 331 private V getStash (short[] key, V defaultValue) { 332 short[][] keyTable = this.keyTable; 333 for (int i = capacity, n = i + stashSize; i < n; i++) 334 if (Arrays.equals(key, keyTable[i])) return valueTable[i]; 335 return defaultValue; 336 } 337 338 /** 339 * Gets a List of all values associated with regions containing a given x,y point. 340 * @param x the x coordinate of the point in question 341 * @param y the y coordinate of the point in question 342 * @return an ArrayList of all V values corresponding to regions containing the given x,y point. 343 */ 344 public LinkedHashSet<V> allAt(int x, int y) 345 { 346 LinkedHashSet<V> found = new LinkedHashSet<>(capacity); 347 LinkedHashSet<short[]> regions = CoordPacker.findManyPacked(x, y, keyTable); 348 for(short[] region : regions) 349 { 350 found.add(get(region)); 351 } 352 return found; 353 } 354 355 /** 356 * Checks if a region, stored as packed data (possibly from CoordPacker or this class) overlaps with regions stored 357 * in this object as keys. Returns true if there is any overlap, false otherwise 358 * @param region the packed region to check for overlap with regions this stores values for 359 * @return true if the region overlaps at all, false otherwise 360 */ 361 public boolean containsRegion(short[] region) 362 { 363 return CoordPacker.regionsContain(region, keyTable); 364 } 365 /** 366 * Gets a List of all regions containing a given x,y point. 367 * @param x the x coordinate of the point in question 368 * @param y the y coordinate of the point in question 369 * @return an ArrayList of all regions in this data structure containing the given x,y point. 370 */ 371 public LinkedHashSet<short[]> regionsContaining(int x, int y) 372 { 373 return CoordPacker.findManyPacked(x, y, keyTable); 374 } 375 376 public V remove (short[] key) { 377 int hashCode = CrossHash.hash(key); 378 int index = hashCode & mask; 379 if (Arrays.equals(key, keyTable[index])) { 380 keyTable[index] = null; 381 V oldValue = valueTable[index]; 382 valueTable[index] = null; 383 size--; 384 return oldValue; 385 } 386 387 index = hash2(hashCode); 388 if (Arrays.equals(key, keyTable[index])) { 389 keyTable[index] = null; 390 V oldValue = valueTable[index]; 391 valueTable[index] = null; 392 size--; 393 return oldValue; 394 } 395 396 index = hash3(hashCode); 397 if (Arrays.equals(key, keyTable[index])) { 398 keyTable[index] = null; 399 V oldValue = valueTable[index]; 400 valueTable[index] = null; 401 size--; 402 return oldValue; 403 } 404 405 return removeStash(key); 406 } 407 408 V removeStash (short[] key) { 409 short[][] keyTable = this.keyTable; 410 for (int i = capacity, n = i + stashSize; i < n; i++) { 411 if (Arrays.equals(key, keyTable[i])) { 412 V oldValue = valueTable[i]; 413 removeStashIndex(i); 414 size--; 415 return oldValue; 416 } 417 } 418 return null; 419 } 420 421 void removeStashIndex (int index) { 422 // If the removed location was not last, move the last tuple to the removed location. 423 stashSize--; 424 int lastIndex = capacity + stashSize; 425 if (index < lastIndex) { 426 keyTable[index] = keyTable[lastIndex]; 427 valueTable[index] = valueTable[lastIndex]; 428 valueTable[lastIndex] = null; 429 } else 430 valueTable[index] = null; 431 } 432 433 /** Reduces the size of the backing arrays to be the specified capacity or less. If the capacity is already less, nothing is 434 * done. If the map contains more items than the specified capacity, the next highest power of two capacity is used instead. */ 435 public void shrink (int maximumCapacity) { 436 if (maximumCapacity < 0) throw new IllegalArgumentException("maximumCapacity must be >= 0: " + maximumCapacity); 437 if (size > maximumCapacity) maximumCapacity = size; 438 if (capacity <= maximumCapacity) return; 439 maximumCapacity = nextPowerOfTwo(maximumCapacity); 440 resize(maximumCapacity); 441 } 442 443 /** Clears the map and reduces the size of the backing arrays to be the specified capacity if they are larger. */ 444 public void clear (int maximumCapacity) { 445 if (capacity <= maximumCapacity) { 446 clear(); 447 return; 448 } 449 size = 0; 450 resize(maximumCapacity); 451 } 452 453 public void clear () { 454 if (size == 0) return; 455 short[][] keyTable = this.keyTable; 456 V[] valueTable = this.valueTable; 457 for (int i = capacity + stashSize; i-- > 0;) { 458 keyTable[i] = null; 459 valueTable[i] = null; 460 } 461 size = 0; 462 stashSize = 0; 463 } 464 465 /** Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may 466 * be an expensive operation. 467 * @param identity If true, uses == to compare the specified value with values in the map. If false, uses 468 * {@link #equals(Object)}. */ 469 public boolean containsValue (Object value, boolean identity) { 470 V[] valueTable = this.valueTable; 471 if (value == null) { 472 short[][] keyTable = this.keyTable; 473 for (int i = capacity + stashSize; i-- > 0;) 474 if (keyTable[i] != null && valueTable[i] == null) return true; 475 } else if (identity) { 476 for (int i = capacity + stashSize; i-- > 0;) 477 if (valueTable[i] == value) return true; 478 } else { 479 for (int i = capacity + stashSize; i-- > 0;) 480 if (value.equals(valueTable[i])) return true; 481 } 482 return false; 483 } 484 485 public boolean containsKey (short[] key) { 486 int hashCode = CrossHash.hash(key); 487 int index = hashCode & mask; 488 if (!Arrays.equals(key, keyTable[index])) { 489 index = hash2(hashCode); 490 if (!Arrays.equals(key, keyTable[index])) { 491 index = hash3(hashCode); 492 if (!Arrays.equals(key, keyTable[index])) return containsKeyStash(key); 493 } 494 } 495 return true; 496 } 497 498 private boolean containsKeyStash (short[] key) { 499 short[][] keyTable = this.keyTable; 500 for (int i = capacity, n = i + stashSize; i < n; i++) 501 if (Arrays.equals(key, keyTable[i])) return true; 502 return false; 503 } 504 505 /** Returns the key for the specified value, or null if it is not in the map. Note this traverses the entire map and compares 506 * every value, which may be an expensive operation. 507 * @param identity If true, uses == to compare the specified value with values in the map. If false, uses 508 * {@link #equals(Object)}. */ 509 public short[] findKey (Object value, boolean identity) { 510 V[] valueTable = this.valueTable; 511 if (value == null) { 512 short[][] keyTable = this.keyTable; 513 for (int i = capacity + stashSize; i-- > 0;) 514 if (keyTable[i] != null && valueTable[i] == null) return keyTable[i]; 515 } else if (identity) { 516 for (int i = capacity + stashSize; i-- > 0;) 517 if (valueTable[i] == value) return keyTable[i]; 518 } else { 519 for (int i = capacity + stashSize; i-- > 0;) 520 if (value.equals(valueTable[i])) return keyTable[i]; 521 } 522 return null; 523 } 524 525 /** Increases the size of the backing array to accommodate the specified number of additional items. Useful before adding many 526 * items to avoid multiple backing array resizes. */ 527 public void ensureCapacity (int additionalCapacity) { 528 int sizeNeeded = size + additionalCapacity; 529 if (sizeNeeded >= threshold) resize(nextPowerOfTwo((int)Math.ceil(sizeNeeded / loadFactor))); 530 } 531 532 @SuppressWarnings("unchecked") 533 private void resize (int newSize) { 534 int oldEndIndex = capacity + stashSize; 535 536 capacity = newSize; 537 threshold = (int)(newSize * loadFactor); 538 mask = newSize - 1; 539 hashShift = 31 - Integer.numberOfTrailingZeros(newSize); 540 stashCapacity = Math.max(3, (int)Math.ceil(Math.log(newSize)) * 2); 541 pushIterations = Math.max(Math.min(newSize, 8), (int)Math.sqrt(newSize) / 8); 542 543 short[][] oldKeyTable = keyTable; 544 V[] oldValueTable = valueTable; 545 546 keyTable = new short[newSize + stashCapacity][]; 547 valueTable = (V[])new Object[newSize + stashCapacity]; 548 549 int oldSize = size; 550 size = 0; 551 stashSize = 0; 552 if (oldSize > 0) { 553 for (int i = 0; i < oldEndIndex; i++) { 554 short[] key = oldKeyTable[i]; 555 if (key != null) putResize(key, oldValueTable[i]); 556 } 557 } 558 } 559 560 private int hash2 (int h) { 561 h *= PRIME2; 562 return (h ^ h >>> hashShift) & mask; 563 } 564 565 private int hash3 (int h) { 566 h *= PRIME3; 567 return (h ^ h >>> hashShift) & mask; 568 } 569 570 public int hashCode () { 571 int h = 0; 572 short[][] keyTable = this.keyTable; 573 V[] valueTable = this.valueTable; 574 for (int i = 0, n = capacity + stashSize; i < n; i++) { 575 short[] key = keyTable[i]; 576 if (key != null) { 577 h += CrossHash.hash(key) * 31; 578 579 V value = valueTable[i]; 580 if (value != null) { 581 h += value.hashCode(); 582 } 583 } 584 } 585 return h; 586 } 587 588 @SuppressWarnings("unchecked") 589 public boolean equals (Object obj) { 590 if (obj == this) return true; 591 if (!(obj instanceof RegionMap)) return false; 592 RegionMap<V> other = (RegionMap<V>)obj; 593 if (other.size != size) return false; 594 short[][] keyTable = this.keyTable; 595 V[] valueTable = this.valueTable; 596 for (int i = 0, n = capacity + stashSize; i < n; i++) { 597 short[] key = keyTable[i]; 598 if (key != null) { 599 V value = valueTable[i]; 600 if (value == null) { 601 if (!other.containsKey(key) || other.get(key) != null) { 602 return false; 603 } 604 } else { 605 if (!value.equals(other.get(key))) { 606 return false; 607 } 608 } 609 } 610 } 611 return true; 612 } 613 614 public String toString (String separator) { 615 return toString(separator, false); 616 } 617 618 @Override 619 public String toString () { 620 return toString(", ", true); 621 } 622 623 private String toString (String separator, boolean braces) { 624 if (size == 0) return braces ? "{}" : ""; 625 StringBuilder buffer = new StringBuilder(32); 626 if (braces) buffer.append('{'); 627 short[][] keyTable = this.keyTable; 628 V[] valueTable = this.valueTable; 629 int i = keyTable.length; 630 while (i-- > 0) { 631 short[] key = keyTable[i]; 632 if (key == null) continue; 633 buffer.append("Packed Region:"); 634 buffer.append(CoordPacker.encodeASCII(key)); 635 buffer.append('='); 636 buffer.append(valueTable[i]); 637 break; 638 } 639 while (i-- > 0) { 640 short[] key = keyTable[i]; 641 if (key == null) continue; 642 buffer.append(separator); 643 buffer.append("Packed Region:"); 644 buffer.append(CoordPacker.encodeASCII(key)); 645 buffer.append('='); 646 buffer.append(valueTable[i]); 647 } 648 if (braces) buffer.append('}'); 649 return buffer.toString(); 650 } 651 private static int nextPowerOfTwo(int n) 652 { 653 int highest = Integer.highestOneBit(n); 654 return (highest == Integer.lowestOneBit(n)) ? highest : highest << 1; 655 } 656 @Override 657 public Entries<V> iterator () { 658 return entries(); 659 } 660 661 /** Returns an iterator for the entries in the map. Remove is supported. Note that the same iterator instance is returned each 662 * time this method is called. Use the {@link Entries} constructor for nested or multithreaded iteration. */ 663 public Entries<V> entries () { 664 if (entries1 == null) { 665 entries1 = new Entries<>(this); 666 entries2 = new Entries<>(this); 667 } 668 if (!entries1.valid) { 669 entries1.reset(); 670 entries1.valid = true; 671 entries2.valid = false; 672 return entries1; 673 } 674 entries2.reset(); 675 entries2.valid = true; 676 entries1.valid = false; 677 return entries2; 678 } 679 680 /** Returns an iterator for the values in the map. Remove is supported. Note that the same iterator instance is returned each 681 * time this method is called. Use the {@link Values} constructor for nested or multithreaded iteration. */ 682 public Values<V> values () { 683 if (values1 == null) { 684 values1 = new Values<>(this); 685 values2 = new Values<>(this); 686 } 687 if (!values1.valid) { 688 values1.reset(); 689 values1.valid = true; 690 values2.valid = false; 691 return values1; 692 } 693 values2.reset(); 694 values2.valid = true; 695 values1.valid = false; 696 return values2; 697 } 698 699 /** Returns an iterator for the keys in the map. Remove is supported. Note that the same iterator instance is returned each 700 * time this method is called. Use the {@link Keys} constructor for nested or multithreaded iteration. */ 701 public Keys keys () { 702 if (keys1 == null) { 703 keys1 = new Keys(this); 704 keys2 = new Keys(this); 705 } 706 if (!keys1.valid) { 707 keys1.reset(); 708 keys1.valid = true; 709 keys2.valid = false; 710 return keys1; 711 } 712 keys2.reset(); 713 keys2.valid = true; 714 keys1.valid = false; 715 return keys2; 716 } 717 718 public static class Entry<V> { 719 public short[] key; 720 public V value; 721 722 @Override 723 public String toString () { 724 return "Packed Region:" + CoordPacker.encodeASCII(key) + "=" + value; 725 } 726 } 727 728 private abstract static class MapIterator<V, I> implements Iterable<I>, Iterator<I> { 729 public boolean hasNext; 730 731 final RegionMap<V> map; 732 int nextIndex, currentIndex; 733 boolean valid = true; 734 735 public MapIterator (RegionMap<V> map) { 736 this.map = map; 737 reset(); 738 } 739 740 public void reset () { 741 currentIndex = -1; 742 nextIndex = -1; 743 findNextIndex(); 744 } 745 746 void findNextIndex () { 747 hasNext = false; 748 short[][] keyTable = map.keyTable; 749 for (int n = map.capacity + map.stashSize; ++nextIndex < n;) { 750 if (keyTable[nextIndex] != null) { 751 hasNext = true; 752 break; 753 } 754 } 755 } 756 757 @Override 758 public void remove () { 759 if (currentIndex < 0) throw new IllegalStateException("next must be called before remove."); 760 if (currentIndex >= map.capacity) { 761 map.removeStashIndex(currentIndex); 762 nextIndex = currentIndex - 1; 763 findNextIndex(); 764 } else { 765 map.keyTable[currentIndex] = null; 766 map.valueTable[currentIndex] = null; 767 } 768 currentIndex = -1; 769 map.size--; 770 } 771 } 772 773 public static class Entries<V> extends MapIterator<V, Entry<V>> { 774 Entry<V> entry = new Entry<>(); 775 776 public Entries (RegionMap<V> map) { 777 super(map); 778 } 779 780 /** Note the same entry instance is returned each time this method is called. */ 781 @Override 782 public Entry<V> next () { 783 if (!hasNext) throw new NoSuchElementException(); 784 if (!valid) throw new RuntimeException("#iterator() cannot be used nested."); 785 short[][] keyTable = map.keyTable; 786 entry.key = keyTable[nextIndex]; 787 entry.value = map.valueTable[nextIndex]; 788 currentIndex = nextIndex; 789 findNextIndex(); 790 return entry; 791 } 792 793 @Override 794 public boolean hasNext () { 795 if (!valid) throw new RuntimeException("#iterator() cannot be used nested."); 796 return hasNext; 797 } 798 799 @Override 800 public Entries<V> iterator () { 801 return this; 802 } 803 } 804 805 public static class Values<V> extends MapIterator<V, V> { 806 public Values (RegionMap<V> map) { 807 super(map); 808 } 809 810 @Override 811 public boolean hasNext () { 812 if (!valid) throw new RuntimeException("#iterator() cannot be used nested."); 813 return hasNext; 814 } 815 816 @Override 817 public V next () { 818 if (!hasNext) throw new NoSuchElementException(); 819 if (!valid) throw new RuntimeException("#iterator() cannot be used nested."); 820 V value = map.valueTable[nextIndex]; 821 currentIndex = nextIndex; 822 findNextIndex(); 823 return value; 824 } 825 826 @Override 827 public Values<V> iterator () { 828 return this; 829 } 830 831 /** Returns a new list containing the remaining values. */ 832 public List<V> toList () { 833 return toList(new ArrayList<V>(map.size)); 834 } 835 836 /** Adds the remaining values to the specified list. */ 837 public List<V> toList (List<V> list) { 838 while (hasNext) 839 list.add(next()); 840 return list; 841 } 842 } 843 844 public static class Keys extends MapIterator<Object, short[]> { 845 @SuppressWarnings("unchecked") 846 public Keys (RegionMap<?> map) { 847 super((RegionMap<Object>) map); 848 } 849 850 @Override 851 public boolean hasNext () { 852 if (!valid) throw new RuntimeException("#iterator() cannot be used nested."); 853 return hasNext; 854 } 855 856 @Override 857 public short[] next () { 858 if (!hasNext) throw new NoSuchElementException(); 859 if (!valid) throw new RuntimeException("#iterator() cannot be used nested."); 860 short[] key = map.keyTable[nextIndex]; 861 currentIndex = nextIndex; 862 findNextIndex(); 863 return key; 864 } 865 866 @Override 867 public Keys iterator () { 868 return this; 869 } 870 871 /** Returns a new list containing the remaining keys. */ 872 public List<short[]> toList() { 873 return toList(new ArrayList<short[]>(map.size)); 874 } 875 876 /** Adds the remaining keys to the array. */ 877 public List<short[]> toList(List<short[]> list) { 878 while (hasNext) 879 list.add(next()); 880 return list; 881 } 882 } 883}