001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4.map;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.ObjectOutputStream;
022import java.io.Serializable;
023import java.util.AbstractCollection;
024import java.util.AbstractSet;
025import java.util.Collection;
026import java.util.Iterator;
027import java.util.Map;
028import java.util.NoSuchElementException;
029import java.util.Set;
030
031import org.apache.commons.collections4.IterableMap;
032import org.apache.commons.collections4.MapIterator;
033import org.apache.commons.collections4.ResettableIterator;
034import org.apache.commons.collections4.iterators.EmptyIterator;
035import org.apache.commons.collections4.iterators.EmptyMapIterator;
036
037/**
038 * A <code>Map</code> implementation that stores data in simple fields until
039 * the size is greater than 3.
040 * <p>
041 * This map is designed for performance and can outstrip HashMap.
042 * It also has good garbage collection characteristics.
043 * <ul>
044 * <li>Optimised for operation at size 3 or less.
045 * <li>Still works well once size 3 exceeded.
046 * <li>Gets at size 3 or less are about 0-10% faster than HashMap,
047 * <li>Puts at size 3 or less are over 4 times faster than HashMap.
048 * <li>Performance 5% slower than HashMap once size 3 exceeded once.
049 * </ul>
050 * The design uses two distinct modes of operation - flat and delegate.
051 * While the map is size 3 or less, operations map straight onto fields using
052 * switch statements. Once size 4 is reached, the map switches to delegate mode
053 * and only switches back when cleared. In delegate mode, all operations are
054 * forwarded straight to a HashMap resulting in the 5% performance loss.
055 * <p>
056 * The performance gains on puts are due to not needing to create a Map Entry
057 * object. This is a large saving not only in performance but in garbage collection.
058 * <p>
059 * Whilst in flat mode this map is also easy for the garbage collector to dispatch.
060 * This is because it contains no complex objects or arrays which slow the progress.
061 * <p>
062 * Do not use <code>Flat3Map</code> if the size is likely to grow beyond 3.
063 * <p>
064 * <strong>Note that Flat3Map is not synchronized and is not thread-safe.</strong>
065 * If you wish to use this map from multiple threads concurrently, you must use
066 * appropriate synchronization. The simplest approach is to wrap this map
067 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
068 * exceptions when accessed by concurrent threads without synchronization.
069 *
070 * @since 3.0
071 * @version $Id: Flat3Map.html 1015642 2017-07-18 12:10:19Z chtompki $
072 */
073public class Flat3Map<K, V> implements IterableMap<K, V>, Serializable, Cloneable {
074
075    /** Serialization version */
076    private static final long serialVersionUID = -6701087419741928296L;
077
078    /** The size of the map, used while in flat mode */
079    private transient int size;
080    /** Hash, used while in flat mode */
081    private transient int hash1;
082    /** Hash, used while in flat mode */
083    private transient int hash2;
084    /** Hash, used while in flat mode */
085    private transient int hash3;
086    /** Key, used while in flat mode */
087    private transient K key1;
088    /** Key, used while in flat mode */
089    private transient K key2;
090    /** Key, used while in flat mode */
091    private transient K key3;
092    /** Value, used while in flat mode */
093    private transient V value1;
094    /** Value, used while in flat mode */
095    private transient V value2;
096    /** Value, used while in flat mode */
097    private transient V value3;
098    /** Map, used while in delegate mode */
099    private transient AbstractHashedMap<K, V> delegateMap;
100
101    /**
102     * Constructor.
103     */
104    public Flat3Map() {
105        super();
106    }
107
108    /**
109     * Constructor copying elements from another map.
110     *
111     * @param map  the map to copy
112     * @throws NullPointerException if the map is null
113     */
114    public Flat3Map(final Map<? extends K, ? extends V> map) {
115        super();
116        putAll(map);
117    }
118
119    //-----------------------------------------------------------------------
120    /**
121     * Gets the value mapped to the key specified.
122     *
123     * @param key  the key
124     * @return the mapped value, null if no match
125     */
126    @Override
127    public V get(final Object key) {
128        if (delegateMap != null) {
129            return delegateMap.get(key);
130        }
131        if (key == null) {
132            switch (size) {
133                // drop through
134                case 3:
135                    if (key3 == null) {
136                        return value3;
137                    }
138                case 2:
139                    if (key2 == null) {
140                        return value2;
141                    }
142                case 1:
143                    if (key1 == null) {
144                        return value1;
145                    }
146            }
147        } else {
148            if (size > 0) {
149                final int hashCode = key.hashCode();
150                switch (size) {
151                    // drop through
152                    case 3:
153                        if (hash3 == hashCode && key.equals(key3)) {
154                            return value3;
155                        }
156                    case 2:
157                        if (hash2 == hashCode && key.equals(key2)) {
158                            return value2;
159                        }
160                    case 1:
161                        if (hash1 == hashCode && key.equals(key1)) {
162                            return value1;
163                        }
164                }
165            }
166        }
167        return null;
168    }
169
170    /**
171     * Gets the size of the map.
172     *
173     * @return the size
174     */
175    @Override
176    public int size() {
177        if (delegateMap != null) {
178            return delegateMap.size();
179        }
180        return size;
181    }
182
183    /**
184     * Checks whether the map is currently empty.
185     *
186     * @return true if the map is currently size zero
187     */
188    @Override
189    public boolean isEmpty() {
190        return size() == 0;
191    }
192
193    //-----------------------------------------------------------------------
194    /**
195     * Checks whether the map contains the specified key.
196     *
197     * @param key  the key to search for
198     * @return true if the map contains the key
199     */
200    @Override
201    public boolean containsKey(final Object key) {
202        if (delegateMap != null) {
203            return delegateMap.containsKey(key);
204        }
205        if (key == null) {
206            switch (size) {  // drop through
207                case 3:
208                    if (key3 == null) {
209                        return true;
210                    }
211                case 2:
212                    if (key2 == null) {
213                        return true;
214                    }
215                case 1:
216                    if (key1 == null) {
217                        return true;
218                    }
219            }
220        } else {
221            if (size > 0) {
222                final int hashCode = key.hashCode();
223                switch (size) {  // drop through
224                    case 3:
225                        if (hash3 == hashCode && key.equals(key3)) {
226                            return true;
227                        }
228                    case 2:
229                        if (hash2 == hashCode && key.equals(key2)) {
230                            return true;
231                        }
232                    case 1:
233                        if (hash1 == hashCode && key.equals(key1)) {
234                            return true;
235                        }
236                }
237            }
238        }
239        return false;
240    }
241
242    /**
243     * Checks whether the map contains the specified value.
244     *
245     * @param value  the value to search for
246     * @return true if the map contains the key
247     */
248    @Override
249    public boolean containsValue(final Object value) {
250        if (delegateMap != null) {
251            return delegateMap.containsValue(value);
252        }
253        if (value == null) {  // drop through
254            switch (size) {
255                case 3:
256                    if (value3 == null) {
257                        return true;
258                    }
259                case 2:
260                    if (value2 == null) {
261                        return true;
262                    }
263                case 1:
264                    if (value1 == null) {
265                        return true;
266                    }
267            }
268        } else {
269            switch (size) {  // drop through
270                case 3:
271                    if (value.equals(value3)) {
272                        return true;
273                    }
274                case 2:
275                    if (value.equals(value2)) {
276                        return true;
277                    }
278                case 1:
279                    if (value.equals(value1)) {
280                        return true;
281                    }
282            }
283        }
284        return false;
285    }
286
287    //-----------------------------------------------------------------------
288    /**
289     * Puts a key-value mapping into this map.
290     *
291     * @param key  the key to add
292     * @param value  the value to add
293     * @return the value previously mapped to this key, null if none
294     */
295    @Override
296    public V put(final K key, final V value) {
297        if (delegateMap != null) {
298            return delegateMap.put(key, value);
299        }
300        // change existing mapping
301        if (key == null) {
302            switch (size) {  // drop through
303                case 3:
304                    if (key3 == null) {
305                        final V old = value3;
306                        value3 = value;
307                        return old;
308                    }
309                case 2:
310                    if (key2 == null) {
311                        final V old = value2;
312                        value2 = value;
313                        return old;
314                    }
315                case 1:
316                    if (key1 == null) {
317                        final V old = value1;
318                        value1 = value;
319                        return old;
320                    }
321            }
322        } else {
323            if (size > 0) {
324                final int hashCode = key.hashCode();
325                switch (size) {  // drop through
326                    case 3:
327                        if (hash3 == hashCode && key.equals(key3)) {
328                            final V old = value3;
329                            value3 = value;
330                            return old;
331                        }
332                    case 2:
333                        if (hash2 == hashCode && key.equals(key2)) {
334                            final V old = value2;
335                            value2 = value;
336                            return old;
337                        }
338                    case 1:
339                        if (hash1 == hashCode && key.equals(key1)) {
340                            final V old = value1;
341                            value1 = value;
342                            return old;
343                        }
344                }
345            }
346        }
347
348        // add new mapping
349        switch (size) {
350            default:
351                convertToMap();
352                delegateMap.put(key, value);
353                return null;
354            case 2:
355                hash3 = key == null ? 0 : key.hashCode();
356                key3 = key;
357                value3 = value;
358                break;
359            case 1:
360                hash2 = key == null ? 0 : key.hashCode();
361                key2 = key;
362                value2 = value;
363                break;
364            case 0:
365                hash1 = key == null ? 0 : key.hashCode();
366                key1 = key;
367                value1 = value;
368                break;
369        }
370        size++;
371        return null;
372    }
373
374    /**
375     * Puts all the values from the specified map into this map.
376     *
377     * @param map  the map to add
378     * @throws NullPointerException if the map is null
379     */
380    @Override
381    public void putAll(final Map<? extends K, ? extends V> map) {
382        final int size = map.size();
383        if (size == 0) {
384            return;
385        }
386        if (delegateMap != null) {
387            delegateMap.putAll(map);
388            return;
389        }
390        if (size < 4) {
391            for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
392                put(entry.getKey(), entry.getValue());
393            }
394        } else {
395            convertToMap();
396            delegateMap.putAll(map);
397        }
398    }
399
400    /**
401     * Converts the flat map data to a map.
402     */
403    private void convertToMap() {
404        delegateMap = createDelegateMap();
405        switch (size) {  // drop through
406            case 3:
407                delegateMap.put(key3, value3);
408            case 2:
409                delegateMap.put(key2, value2);
410            case 1:
411                delegateMap.put(key1, value1);
412            case 0:
413                break;
414            default:
415                throw new IllegalStateException("Invalid map index: " + size);
416        }
417
418        size = 0;
419        hash1 = hash2 = hash3 = 0;
420        key1 = key2 = key3 = null;
421        value1 = value2 = value3 = null;
422    }
423
424    /**
425     * Create an instance of the map used for storage when in delegation mode.
426     * <p>
427     * This can be overridden by subclasses to provide a different map implementation.
428     * Not every AbstractHashedMap is suitable, identity and reference based maps
429     * would be poor choices.
430     *
431     * @return a new AbstractHashedMap or subclass
432     * @since 3.1
433     */
434    protected AbstractHashedMap<K, V> createDelegateMap() {
435        return new HashedMap<K, V>();
436    }
437
438    /**
439     * Removes the specified mapping from this map.
440     *
441     * @param key  the mapping to remove
442     * @return the value mapped to the removed key, null if key not in map
443     */
444    @Override
445    public V remove(final Object key) {
446        if (delegateMap != null) {
447            return delegateMap.remove(key);
448        }
449        if (size == 0) {
450            return null;
451        }
452        if (key == null) {
453            switch (size) {  // drop through
454                case 3:
455                    if (key3 == null) {
456                        final V old = value3;
457                        hash3 = 0;
458                        key3 = null;
459                        value3 = null;
460                        size = 2;
461                        return old;
462                    }
463                    if (key2 == null) {
464                        final V old = value2;
465                        hash2 = hash3;
466                        key2 = key3;
467                        value2 = value3;
468                        hash3 = 0;
469                        key3 = null;
470                        value3 = null;
471                        size = 2;
472                        return old;
473                    }
474                    if (key1 == null) {
475                        final V old = value1;
476                        hash1 = hash3;
477                        key1 = key3;
478                        value1 = value3;
479                        hash3 = 0;
480                        key3 = null;
481                        value3 = null;
482                        size = 2;
483                        return old;
484                    }
485                    return null;
486                case 2:
487                    if (key2 == null) {
488                        final V old = value2;
489                        hash2 = 0;
490                        key2 = null;
491                        value2 = null;
492                        size = 1;
493                        return old;
494                    }
495                    if (key1 == null) {
496                        final V old = value1;
497                        hash1 = hash2;
498                        key1 = key2;
499                        value1 = value2;
500                        hash2 = 0;
501                        key2 = null;
502                        value2 = null;
503                        size = 1;
504                        return old;
505                    }
506                    return null;
507                case 1:
508                    if (key1 == null) {
509                        final V old = value1;
510                        hash1 = 0;
511                        key1 = null;
512                        value1 = null;
513                        size = 0;
514                        return old;
515                    }
516            }
517        } else {
518            if (size > 0) {
519                final int hashCode = key.hashCode();
520                switch (size) {  // drop through
521                    case 3:
522                        if (hash3 == hashCode && key.equals(key3)) {
523                            final V old = value3;
524                            hash3 = 0;
525                            key3 = null;
526                            value3 = null;
527                            size = 2;
528                            return old;
529                        }
530                        if (hash2 == hashCode && key.equals(key2)) {
531                            final V old = value2;
532                            hash2 = hash3;
533                            key2 = key3;
534                            value2 = value3;
535                            hash3 = 0;
536                            key3 = null;
537                            value3 = null;
538                            size = 2;
539                            return old;
540                        }
541                        if (hash1 == hashCode && key.equals(key1)) {
542                            final V old = value1;
543                            hash1 = hash3;
544                            key1 = key3;
545                            value1 = value3;
546                            hash3 = 0;
547                            key3 = null;
548                            value3 = null;
549                            size = 2;
550                            return old;
551                        }
552                        return null;
553                    case 2:
554                        if (hash2 == hashCode && key.equals(key2)) {
555                            final V old = value2;
556                            hash2 = 0;
557                            key2 = null;
558                            value2 = null;
559                            size = 1;
560                            return old;
561                        }
562                        if (hash1 == hashCode && key.equals(key1)) {
563                            final V old = value1;
564                            hash1 = hash2;
565                            key1 = key2;
566                            value1 = value2;
567                            hash2 = 0;
568                            key2 = null;
569                            value2 = null;
570                            size = 1;
571                            return old;
572                        }
573                        return null;
574                    case 1:
575                        if (hash1 == hashCode && key.equals(key1)) {
576                            final V old = value1;
577                            hash1 = 0;
578                            key1 = null;
579                            value1 = null;
580                            size = 0;
581                            return old;
582                        }
583                }
584            }
585        }
586        return null;
587    }
588
589    /**
590     * Clears the map, resetting the size to zero and nullifying references
591     * to avoid garbage collection issues.
592     */
593    @Override
594    public void clear() {
595        if (delegateMap != null) {
596            delegateMap.clear();  // should aid gc
597            delegateMap = null;  // switch back to flat mode
598        } else {
599            size = 0;
600            hash1 = hash2 = hash3 = 0;
601            key1 = key2 = key3 = null;
602            value1 = value2 = value3 = null;
603        }
604    }
605
606    //-----------------------------------------------------------------------
607    /**
608     * Gets an iterator over the map.
609     * Changes made to the iterator affect this map.
610     * <p>
611     * A MapIterator returns the keys in the map. It also provides convenient
612     * methods to get the key and value, and set the value.
613     * It avoids the need to create an entrySet/keySet/values object.
614     * It also avoids creating the Map Entry object.
615     *
616     * @return the map iterator
617     */
618    @Override
619    public MapIterator<K, V> mapIterator() {
620        if (delegateMap != null) {
621            return delegateMap.mapIterator();
622        }
623        if (size == 0) {
624            return EmptyMapIterator.<K, V>emptyMapIterator();
625        }
626        return new FlatMapIterator<K, V>(this);
627    }
628
629    /**
630     * FlatMapIterator
631     */
632    static class FlatMapIterator<K, V> implements MapIterator<K, V>, ResettableIterator<K> {
633        private final Flat3Map<K, V> parent;
634        private int nextIndex = 0;
635        private boolean canRemove = false;
636
637        FlatMapIterator(final Flat3Map<K, V> parent) {
638            super();
639            this.parent = parent;
640        }
641
642        @Override
643        public boolean hasNext() {
644            return nextIndex < parent.size;
645        }
646
647        @Override
648        public K next() {
649            if (hasNext() == false) {
650                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
651            }
652            canRemove = true;
653            nextIndex++;
654            return getKey();
655        }
656
657        @Override
658        public void remove() {
659            if (canRemove == false) {
660                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
661            }
662            parent.remove(getKey());
663            nextIndex--;
664            canRemove = false;
665        }
666
667        @Override
668        public K getKey() {
669            if (canRemove == false) {
670                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
671            }
672            switch (nextIndex) {
673                case 3:
674                    return parent.key3;
675                case 2:
676                    return parent.key2;
677                case 1:
678                    return parent.key1;
679            }
680            throw new IllegalStateException("Invalid map index: " + nextIndex);
681        }
682
683        @Override
684        public V getValue() {
685            if (canRemove == false) {
686                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
687            }
688            switch (nextIndex) {
689                case 3:
690                    return parent.value3;
691                case 2:
692                    return parent.value2;
693                case 1:
694                    return parent.value1;
695            }
696            throw new IllegalStateException("Invalid map index: " + nextIndex);
697        }
698
699        @Override
700        public V setValue(final V value) {
701            if (canRemove == false) {
702                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
703            }
704            final V old = getValue();
705            switch (nextIndex) {
706                case 3:
707                    parent.value3 = value;
708                    break;
709                case 2:
710                    parent.value2 = value;
711                    break;
712                case 1:
713                    parent.value1 = value;
714                    break;
715                default:
716                    throw new IllegalStateException("Invalid map index: " + nextIndex);
717            }
718            return old;
719        }
720
721        @Override
722        public void reset() {
723            nextIndex = 0;
724            canRemove = false;
725        }
726
727        @Override
728        public String toString() {
729            if (canRemove) {
730                return "Iterator[" + getKey() + "=" + getValue() + "]";
731            }
732            return "Iterator[]";
733        }
734    }
735
736    /**
737     * Gets the entrySet view of the map.
738     * Changes made to the view affect this map.
739     * <p>
740     * NOTE: from 4.0, the returned Map Entry will be an independent object and will
741     * not change anymore as the iterator progresses. To avoid this additional object
742     * creation and simply iterate through the entries, use {@link #mapIterator()}.
743     *
744     * @return the entrySet view
745     */
746    @Override
747    public Set<Map.Entry<K, V>> entrySet() {
748        if (delegateMap != null) {
749            return delegateMap.entrySet();
750        }
751        return new EntrySet<K, V>(this);
752    }
753
754    /**
755     * EntrySet
756     */
757    static class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> {
758        private final Flat3Map<K, V> parent;
759
760        EntrySet(final Flat3Map<K, V> parent) {
761            super();
762            this.parent = parent;
763        }
764
765        @Override
766        public int size() {
767            return parent.size();
768        }
769
770        @Override
771        public void clear() {
772            parent.clear();
773        }
774
775        @Override
776        public boolean remove(final Object obj) {
777            if (obj instanceof Map.Entry == false) {
778                return false;
779            }
780            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
781            final Object key = entry.getKey();
782            final boolean result = parent.containsKey(key);
783            parent.remove(key);
784            return result;
785        }
786
787        @Override
788        public Iterator<Map.Entry<K, V>> iterator() {
789            if (parent.delegateMap != null) {
790                return parent.delegateMap.entrySet().iterator();
791            }
792            if (parent.size() == 0) {
793                return EmptyIterator.<Map.Entry<K, V>>emptyIterator();
794            }
795            return new EntrySetIterator<K, V>(parent);
796        }
797    }
798
799    static class FlatMapEntry<K, V> implements Map.Entry<K, V> {
800        private final Flat3Map<K, V> parent;
801        private final int index;
802        private volatile boolean removed;
803
804        public FlatMapEntry(final Flat3Map<K, V> parent, final int index) {
805            this.parent = parent;
806            this.index = index;
807            this.removed = false;
808        }
809
810        /**
811         * Used by the iterator that created this entry to indicate that
812         * {@link java.util.Iterator#remove()} has been called.
813         * <p>
814         * As a consequence, all subsequent call to {@link #getKey()},
815         * {@link #setValue(Object)} and {@link #getValue()} will fail.
816         *
817         * @param flag
818         */
819        void setRemoved(final boolean flag) {
820            this.removed = flag;
821        }
822
823        @Override
824        public K getKey() {
825            if (removed) {
826                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
827            }
828            switch (index) {
829                case 3:
830                    return parent.key3;
831                case 2:
832                    return parent.key2;
833                case 1:
834                    return parent.key1;
835            }
836            throw new IllegalStateException("Invalid map index: " + index);
837        }
838
839        @Override
840        public V getValue() {
841            if (removed) {
842                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
843            }
844            switch (index) {
845                case 3:
846                    return parent.value3;
847                case 2:
848                    return parent.value2;
849                case 1:
850                    return parent.value1;
851            }
852            throw new IllegalStateException("Invalid map index: " + index);
853        }
854
855        @Override
856        public V setValue(final V value) {
857            if (removed) {
858                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
859            }
860            final V old = getValue();
861            switch (index) {
862                case 3:
863                    parent.value3 = value;
864                    break;
865                case 2:
866                    parent.value2 = value;
867                    break;
868                case 1:
869                    parent.value1 = value;
870                    break;
871                default:
872                    throw new IllegalStateException("Invalid map index: " + index);
873            }
874            return old;
875        }
876
877        @Override
878        public boolean equals(final Object obj) {
879            if (removed) {
880                return false;
881            }
882            if (obj instanceof Map.Entry == false) {
883                return false;
884            }
885            final Map.Entry<?, ?> other = (Map.Entry<?, ?>) obj;
886            final Object key = getKey();
887            final Object value = getValue();
888            return (key == null ? other.getKey() == null : key.equals(other.getKey())) &&
889                   (value == null ? other.getValue() == null : value.equals(other.getValue()));
890        }
891
892        @Override
893        public int hashCode() {
894            if (removed) {
895                return 0;
896            }
897            final Object key = getKey();
898            final Object value = getValue();
899            return (key == null ? 0 : key.hashCode()) ^
900                   (value == null ? 0 : value.hashCode());
901        }
902
903        @Override
904        public String toString() {
905            if (!removed) {
906                return getKey() + "=" + getValue();
907            }
908            return "";
909        }
910
911    }
912
913    static abstract class EntryIterator<K, V> {
914        private final Flat3Map<K, V> parent;
915        private int nextIndex = 0;
916        private FlatMapEntry<K, V> currentEntry = null;
917
918        /**
919         * Create a new Flat3Map.EntryIterator.
920         */
921        public EntryIterator(final Flat3Map<K, V> parent) {
922            this.parent = parent;
923        }
924
925        public boolean hasNext() {
926            return nextIndex < parent.size;
927        }
928
929        public Map.Entry<K, V> nextEntry() {
930            if (!hasNext()) {
931                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
932            }
933            currentEntry = new FlatMapEntry<K, V>(parent, ++nextIndex);
934            return currentEntry;
935        }
936
937        public void remove() {
938            if (currentEntry == null) {
939                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
940            }
941            currentEntry.setRemoved(true);
942            parent.remove(currentEntry.getKey());
943            nextIndex--;
944            currentEntry = null;
945        }
946
947    }
948
949    /**
950     * EntrySetIterator and MapEntry
951     */
952    static class EntrySetIterator<K, V> extends EntryIterator<K, V> implements Iterator<Map.Entry<K, V>> {
953        EntrySetIterator(final Flat3Map<K, V> parent) {
954            super(parent);
955        }
956
957        @Override
958        public Map.Entry<K, V> next() {
959            return nextEntry();
960        }
961    }
962
963    /**
964     * Gets the keySet view of the map.
965     * Changes made to the view affect this map.
966     * To simply iterate through the keys, use {@link #mapIterator()}.
967     *
968     * @return the keySet view
969     */
970    @Override
971    public Set<K> keySet() {
972        if (delegateMap != null) {
973            return delegateMap.keySet();
974        }
975        return new KeySet<K>(this);
976    }
977
978    /**
979     * KeySet
980     */
981    static class KeySet<K> extends AbstractSet<K> {
982        private final Flat3Map<K, ?> parent;
983
984        KeySet(final Flat3Map<K, ?> parent) {
985            super();
986            this.parent = parent;
987        }
988
989        @Override
990        public int size() {
991            return parent.size();
992        }
993
994        @Override
995        public void clear() {
996            parent.clear();
997        }
998
999        @Override
1000        public boolean contains(final Object key) {
1001            return parent.containsKey(key);
1002        }
1003
1004        @Override
1005        public boolean remove(final Object key) {
1006            final boolean result = parent.containsKey(key);
1007            parent.remove(key);
1008            return result;
1009        }
1010
1011        @Override
1012        public Iterator<K> iterator() {
1013            if (parent.delegateMap != null) {
1014                return parent.delegateMap.keySet().iterator();
1015            }
1016            if (parent.size() == 0) {
1017                return EmptyIterator.<K>emptyIterator();
1018            }
1019            return new KeySetIterator<K>(parent);
1020        }
1021    }
1022
1023    /**
1024     * KeySetIterator
1025     */
1026    static class KeySetIterator<K> extends EntryIterator<K, Object> implements Iterator<K>{
1027
1028        @SuppressWarnings("unchecked")
1029        KeySetIterator(final Flat3Map<K, ?> parent) {
1030            super((Flat3Map<K, Object>) parent);
1031        }
1032
1033        @Override
1034        public K next() {
1035            return nextEntry().getKey();
1036        }
1037    }
1038
1039    /**
1040     * Gets the values view of the map.
1041     * Changes made to the view affect this map.
1042     * To simply iterate through the values, use {@link #mapIterator()}.
1043     *
1044     * @return the values view
1045     */
1046    @Override
1047    public Collection<V> values() {
1048        if (delegateMap != null) {
1049            return delegateMap.values();
1050        }
1051        return new Values<V>(this);
1052    }
1053
1054    /**
1055     * Values
1056     */
1057    static class Values<V> extends AbstractCollection<V> {
1058        private final Flat3Map<?, V> parent;
1059
1060        Values(final Flat3Map<?, V> parent) {
1061            super();
1062            this.parent = parent;
1063        }
1064
1065        @Override
1066        public int size() {
1067            return parent.size();
1068        }
1069
1070        @Override
1071        public void clear() {
1072            parent.clear();
1073        }
1074
1075        @Override
1076        public boolean contains(final Object value) {
1077            return parent.containsValue(value);
1078        }
1079
1080        @Override
1081        public Iterator<V> iterator() {
1082            if (parent.delegateMap != null) {
1083                return parent.delegateMap.values().iterator();
1084            }
1085            if (parent.size() == 0) {
1086                return EmptyIterator.<V>emptyIterator();
1087            }
1088            return new ValuesIterator<V>(parent);
1089        }
1090    }
1091
1092    /**
1093     * ValuesIterator
1094     */
1095    static class ValuesIterator<V> extends EntryIterator<Object, V> implements Iterator<V> {
1096
1097        @SuppressWarnings("unchecked")
1098        ValuesIterator(final Flat3Map<?, V> parent) {
1099            super((Flat3Map<Object, V>) parent);
1100        }
1101
1102        @Override
1103        public V next() {
1104            return nextEntry().getValue();
1105        }
1106    }
1107
1108    //-----------------------------------------------------------------------
1109    /**
1110     * Write the map out using a custom routine.
1111     */
1112    private void writeObject(final ObjectOutputStream out) throws IOException {
1113        out.defaultWriteObject();
1114        out.writeInt(size());
1115        for (final MapIterator<?, ?> it = mapIterator(); it.hasNext();) {
1116            out.writeObject(it.next());  // key
1117            out.writeObject(it.getValue());  // value
1118        }
1119    }
1120
1121    /**
1122     * Read the map in using a custom routine.
1123     */
1124    @SuppressWarnings("unchecked")
1125    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
1126        in.defaultReadObject();
1127        final int count = in.readInt();
1128        if (count > 3) {
1129            delegateMap = createDelegateMap();
1130        }
1131        for (int i = count; i > 0; i--) {
1132            put((K) in.readObject(), (V) in.readObject());
1133        }
1134    }
1135
1136    //-----------------------------------------------------------------------
1137    /**
1138     * Clones the map without cloning the keys or values.
1139     *
1140     * @return a shallow clone
1141     * @since 3.1
1142     */
1143    @Override
1144    @SuppressWarnings("unchecked")
1145    public Flat3Map<K, V> clone() {
1146        try {
1147            final Flat3Map<K, V> cloned = (Flat3Map<K, V>) super.clone();
1148            if (cloned.delegateMap != null) {
1149                cloned.delegateMap = cloned.delegateMap.clone();
1150            }
1151            return cloned;
1152        } catch (final CloneNotSupportedException ex) {
1153            throw new InternalError();
1154        }
1155    }
1156
1157    /**
1158     * Compares this map with another.
1159     *
1160     * @param obj  the object to compare to
1161     * @return true if equal
1162     */
1163    @Override
1164    public boolean equals(final Object obj) {
1165        if (obj == this) {
1166            return true;
1167        }
1168        if (delegateMap != null) {
1169            return delegateMap.equals(obj);
1170        }
1171        if (obj instanceof Map == false) {
1172            return false;
1173        }
1174        final Map<?, ?> other = (Map<?, ?>) obj;
1175        if (size != other.size()) {
1176            return false;
1177        }
1178        if (size > 0) {
1179            Object otherValue = null;
1180            switch (size) {  // drop through
1181                case 3:
1182                    if (other.containsKey(key3) == false) {
1183                        return false;
1184                    }
1185                    otherValue = other.get(key3);
1186                    if (value3 == null ? otherValue != null : !value3.equals(otherValue)) {
1187                        return false;
1188                    }
1189                case 2:
1190                    if (other.containsKey(key2) == false) {
1191                        return false;
1192                    }
1193                    otherValue = other.get(key2);
1194                    if (value2 == null ? otherValue != null : !value2.equals(otherValue)) {
1195                        return false;
1196                    }
1197                case 1:
1198                    if (other.containsKey(key1) == false) {
1199                        return false;
1200                    }
1201                    otherValue = other.get(key1);
1202                    if (value1 == null ? otherValue != null : !value1.equals(otherValue)) {
1203                        return false;
1204                    }
1205            }
1206        }
1207        return true;
1208    }
1209
1210    /**
1211     * Gets the standard Map hashCode.
1212     *
1213     * @return the hash code defined in the Map interface
1214     */
1215    @Override
1216    public int hashCode() {
1217        if (delegateMap != null) {
1218            return delegateMap.hashCode();
1219        }
1220        int total = 0;
1221        switch (size) {  // drop through
1222            case 3:
1223                total += hash3 ^ (value3 == null ? 0 : value3.hashCode());
1224            case 2:
1225                total += hash2 ^ (value2 == null ? 0 : value2.hashCode());
1226            case 1:
1227                total += hash1 ^ (value1 == null ? 0 : value1.hashCode());
1228            case 0:
1229                break;
1230            default:
1231                throw new IllegalStateException("Invalid map index: " + size);
1232        }
1233        return total;
1234    }
1235
1236    /**
1237     * Gets the map as a String.
1238     *
1239     * @return a string version of the map
1240     */
1241    @Override
1242    public String toString() {
1243        if (delegateMap != null) {
1244            return delegateMap.toString();
1245        }
1246        if (size == 0) {
1247            return "{}";
1248        }
1249        final StringBuilder buf = new StringBuilder(128);
1250        buf.append('{');
1251        switch (size) {  // drop through
1252            case 3:
1253                buf.append(key3 == this ? "(this Map)" : key3);
1254                buf.append('=');
1255                buf.append(value3 == this ? "(this Map)" : value3);
1256                buf.append(',');
1257            case 2:
1258                buf.append(key2 == this ? "(this Map)" : key2);
1259                buf.append('=');
1260                buf.append(value2 == this ? "(this Map)" : value2);
1261                buf.append(',');
1262            case 1:
1263                buf.append(key1 == this ? "(this Map)" : key1);
1264                buf.append('=');
1265                buf.append(value1 == this ? "(this Map)" : value1);
1266                break;
1267            // case 0: has already been dealt with
1268            default:
1269                throw new IllegalStateException("Invalid map index: " + size);
1270        }
1271        buf.append('}');
1272        return buf.toString();
1273    }
1274
1275}