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}