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