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