    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.Map;
    024import java.util.Objects;
    025
    026import org.apache.commons.collections4.MapIterator;
    027import org.apache.commons.collections4.keyvalue.MultiKey;
    028
    029/**
    030 * A {@code Map} implementation that uses multiple keys to map the value.
    031 * <p>
    032 * This class is the most efficient way to uses multiple keys to map to a value.
    033 * The best way to use this class is via the additional map-style methods.
    034 * These provide {@code get}, {@code containsKey}, {@code put} and
    035 * {@code remove} for individual keys which operate without extra object creation.
    036 * </p>
    037 * <p>
    038 * The additional methods are the main interface of this map.
    039 * As such, you will not normally hold this map in a variable of type {@code Map}.
    040 * </p>
    041 * <p>
    042 * The normal map methods take in and return a {@link MultiKey}.
    043 * If you try to use {@code put()} with any other object type a
    044 * {@code ClassCastException} is thrown. If you try to use {@code null} as
    045 * the key in {@code put()} a {@code NullPointerException} is thrown.
    046 * </p>
    047 * <p>
    048 * This map is implemented as a decorator of a {@code AbstractHashedMap} which
    049 * enables extra behavior to be added easily.
    050 * </p>
    051 * <ul>
    052 * <li>{@code MultiKeyMap.decorate(new LinkedMap())} creates an ordered map.
    053 * <li>{@code MultiKeyMap.decorate(new LRUMap())} creates an least recently used map.
    054 * <li>{@code MultiKeyMap.decorate(new ReferenceMap())} creates a garbage collector sensitive map.
    055 * </ul>
    056 * <p>
    057 * Note that {@code IdentityMap} and {@code ReferenceIdentityMap} are unsuitable
    058 * for use as the key comparison would work on the whole MultiKey, not the elements within.
    059 * </p>
    060 * <p>
    061 * As an example, consider a least recently used cache that uses a String airline code
    062 * and a Locale to lookup the airline's name:
    063 * </p>
    064 * <pre>
    065 * private MultiKeyMap cache = MultiKeyMap.multiKeyMap(new LRUMap(50));
    066 *
    067 * public String getAirlineName(String code, String locale) {
    068 *   String name = (String) cache.get(code, locale);
    069 *   if (name == null) {
    070 *     name = getAirlineNameFromDB(code, locale);
    071 *     cache.put(code, locale, name);
    072 *   }
    073 *   return name;
    074 * }
    075 * </pre>
    076 * <p>
    077 * <strong>Note that MultiKeyMap is not synchronized and is not thread-safe.</strong>
    078 * If you wish to use this map from multiple threads concurrently, you must use
    079 * appropriate synchronization. This class may throw exceptions when accessed
    080 * by concurrent threads without synchronization.
    081 * </p>
    082 *
    083 * @param <K> the type of the keys in this map
    084 * @param <V> the type of the values in this map
    085 * @since 3.1
    086 */
    087public class MultiKeyMap<K, V> extends AbstractMapDecorator<MultiKey<? extends K>, V>
    088        implements Serializable, Cloneable {
    089
    090    /** Serialisation version */
    091    private static final long serialVersionUID = -1788199231038721040L;
    092
    093    /**
    094     * Decorates the specified map to add the MultiKeyMap API and fast query.
    095     * The map must not be null and must be empty.
    096     *
    097     * @param <K>  the key type
    098     * @param <V>  the value type
    099     * @param map  the map to decorate, not null
    100     * @return a new multi key map
    101     * @throws NullPointerException if map is null
    102     * @throws IllegalArgumentException if the map is not empty
    103     * @since 4.0
    104     */
    105    public static <K, V> MultiKeyMap<K, V> multiKeyMap(final AbstractHashedMap<MultiKey<? extends K>, V> map) {
    106        Objects.requireNonNull(map, "map");
    107        if (map.isEmpty()) {
    108            return new MultiKeyMap<>(map);
    109        }
    110        throw new IllegalArgumentException("Map must be empty");
    111    }
    112
    113    /**
    114     * Constructs a new MultiKeyMap that decorates a {@code HashedMap}.
    115     */
    116    public MultiKeyMap() {
    117        this(new HashedMap<>());
    118    }
    119
    120    /**
    121     * Constructor that decorates the specified map and is called from
    122     * {@link #multiKeyMap(AbstractHashedMap)}.
    123     * The map must not be null and should be empty or only contain valid keys.
    124     * This constructor performs no validation.
    125     *
    126     * @param map  the map to decorate
    127     */
    128    protected MultiKeyMap(final AbstractHashedMap<MultiKey<? extends K>, V> map) {
    129        super(map);
    130        this.map = map;
    131    }
    132
    133    /**
    134     * Check to ensure that input keys are valid MultiKey objects.
    135     *
    136     * @param key  the key to check
    137     */
    138    protected void checkKey(final MultiKey<?> key) {
    139        Objects.requireNonNull(key, "key");
    140    }
    141
    142    /**
    143     * Clones the map without cloning the keys or values.
    144     *
    145     * @return a shallow clone
    146     */
    147    @SuppressWarnings("unchecked")
    148    @Override
    149    public MultiKeyMap<K, V> clone() {
    150        try {
    151            return (MultiKeyMap<K, V>) super.clone();
    152        } catch (final CloneNotSupportedException e) {
    153            throw new UnsupportedOperationException(e);
    154        }
    155    }
    156
    157    /**
    158     * Checks whether the map contains the specified multi-key.
    159     *
    160     * @param key1  the first key
    161     * @param key2  the second key
    162     * @return true if the map contains the key
    163     */
    164    public boolean containsKey(final Object key1, final Object key2) {
    165        final int hashCode = hash(key1, key2);
    166        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    167                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    168        while (entry != null) {
    169            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    170                return true;
    171            }
    172            entry = entry.next;
    173        }
    174        return false;
    175    }
    176
    177    /**
    178     * Checks whether the map contains the specified multi-key.
    179     *
    180     * @param key1  the first key
    181     * @param key2  the second key
    182     * @param key3  the third key
    183     * @return true if the map contains the key
    184     */
    185    public boolean containsKey(final Object key1, final Object key2, final Object key3) {
    186        final int hashCode = hash(key1, key2, key3);
    187        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    188                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    189        while (entry != null) {
    190            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    191                return true;
    192            }
    193            entry = entry.next;
    194        }
    195        return false;
    196    }
    197
    198    /**
    199     * Checks whether the map contains the specified multi-key.
    200     *
    201     * @param key1  the first key
    202     * @param key2  the second key
    203     * @param key3  the third key
    204     * @param key4  the fourth key
    205     * @return true if the map contains the key
    206     */
    207    public boolean containsKey(final Object key1, final Object key2, final Object key3, final Object key4) {
    208        final int hashCode = hash(key1, key2, key3, key4);
    209        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    210                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    211        while (entry != null) {
    212            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    213                return true;
    214            }
    215            entry = entry.next;
    216        }
    217        return false;
    218    }
    219
    220    /**
    221     * Checks whether the map contains the specified multi-key.
    222     *
    223     * @param key1  the first key
    224     * @param key2  the second key
    225     * @param key3  the third key
    226     * @param key4  the fourth key
    227     * @param key5  the fifth key
    228     * @return true if the map contains the key
    229     */
    230    public boolean containsKey(final Object key1, final Object key2, final Object key3,
    231                               final Object key4, final Object key5) {
    232        final int hashCode = hash(key1, key2, key3, key4, key5);
    233        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    234                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    235        while (entry != null) {
    236            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    237                return true;
    238            }
    239            entry = entry.next;
    240        }
    241        return false;
    242    }
    243
    244    /**
    245     * {@inheritDoc}
    246     */
    247    @Override
    248    protected AbstractHashedMap<MultiKey<? extends K>, V> decorated() {
    249        return (AbstractHashedMap<MultiKey<? extends K>, V>) super.decorated();
    250    }
    251
    252    /**
    253     * Gets the value mapped to the specified multi-key.
    254     *
    255     * @param key1  the first key
    256     * @param key2  the second key
    257     * @return the mapped value, null if no match
    258     */
    259    public V get(final Object key1, final Object key2) {
    260        final int hashCode = hash(key1, key2);
    261        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    262                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    263        while (entry != null) {
    264            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    265                return entry.getValue();
    266            }
    267            entry = entry.next;
    268        }
    269        return null;
    270    }
    271
    272    /**
    273     * Gets the value mapped to the specified multi-key.
    274     *
    275     * @param key1  the first key
    276     * @param key2  the second key
    277     * @param key3  the third key
    278     * @return the mapped value, null if no match
    279     */
    280    public V get(final Object key1, final Object key2, final Object key3) {
    281        final int hashCode = hash(key1, key2, key3);
    282        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    283                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    284        while (entry != null) {
    285            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    286                return entry.getValue();
    287            }
    288            entry = entry.next;
    289        }
    290        return null;
    291    }
    292
    293    /**
    294     * Gets the value mapped to the specified multi-key.
    295     *
    296     * @param key1  the first key
    297     * @param key2  the second key
    298     * @param key3  the third key
    299     * @param key4  the fourth key
    300     * @return the mapped value, null if no match
    301     */
    302    public V get(final Object key1, final Object key2, final Object key3, final Object key4) {
    303        final int hashCode = hash(key1, key2, key3, key4);
    304        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    305                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    306        while (entry != null) {
    307            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    308                return entry.getValue();
    309            }
    310            entry = entry.next;
    311        }
    312        return null;
    313    }
    314
    315    /**
    316     * Gets the value mapped to the specified multi-key.
    317     *
    318     * @param key1  the first key
    319     * @param key2  the second key
    320     * @param key3  the third key
    321     * @param key4  the fourth key
    322     * @param key5  the fifth key
    323     * @return the mapped value, null if no match
    324     */
    325    public V get(final Object key1, final Object key2, final Object key3, final Object key4, final Object key5) {
    326        final int hashCode = hash(key1, key2, key3, key4, key5);
    327        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry =
    328                decorated().data[decorated().hashIndex(hashCode, decorated().data.length)];
    329        while (entry != null) {
    330            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    331                return entry.getValue();
    332            }
    333            entry = entry.next;
    334        }
    335        return null;
    336    }
    337
    338    /**
    339     * Gets the hash code for the specified multi-key.
    340     *
    341     * @param key1  the first key
    342     * @param key2  the second key
    343     * @return the hash code
    344     */
    345    protected int hash(final Object key1, final Object key2) {
    346        int h = 0;
    347        if (key1 != null) {
    348            h ^= key1.hashCode();
    349        }
    350        if (key2 != null) {
    351            h ^= key2.hashCode();
    352        }
    353        h += ~(h << 9);
    354        h ^=  h >>> 14;
    355        h +=  h << 4;
    356        h ^=  h >>> 10;
    357        return h;
    358    }
    359
    360    /**
    361     * Gets the hash code for the specified multi-key.
    362     *
    363     * @param key1  the first key
    364     * @param key2  the second key
    365     * @param key3  the third key
    366     * @return the hash code
    367     */
    368    protected int hash(final Object key1, final Object key2, final Object key3) {
    369        int h = 0;
    370        if (key1 != null) {
    371            h ^= key1.hashCode();
    372        }
    373        if (key2 != null) {
    374            h ^= key2.hashCode();
    375        }
    376        if (key3 != null) {
    377            h ^= key3.hashCode();
    378        }
    379        h += ~(h << 9);
    380        h ^=  h >>> 14;
    381        h +=  h << 4;
    382        h ^=  h >>> 10;
    383        return h;
    384    }
    385
    386    /**
    387     * Gets the hash code for the specified multi-key.
    388     *
    389     * @param key1  the first key
    390     * @param key2  the second key
    391     * @param key3  the third key
    392     * @param key4  the fourth key
    393     * @return the hash code
    394     */
    395    protected int hash(final Object key1, final Object key2, final Object key3, final Object key4) {
    396        int h = 0;
    397        if (key1 != null) {
    398            h ^= key1.hashCode();
    399        }
    400        if (key2 != null) {
    401            h ^= key2.hashCode();
    402        }
    403        if (key3 != null) {
    404            h ^= key3.hashCode();
    405        }
    406        if (key4 != null) {
    407            h ^= key4.hashCode();
    408        }
    409        h += ~(h << 9);
    410        h ^=  h >>> 14;
    411        h +=  h << 4;
    412        h ^=  h >>> 10;
    413        return h;
    414    }
    415
    416    /**
    417     * Gets the hash code for the specified multi-key.
    418     *
    419     * @param key1  the first key
    420     * @param key2  the second key
    421     * @param key3  the third key
    422     * @param key4  the fourth key
    423     * @param key5  the fifth key
    424     * @return the hash code
    425     */
    426    protected int hash(final Object key1, final Object key2, final Object key3, final Object key4, final Object key5) {
    427        int h = 0;
    428        if (key1 != null) {
    429            h ^= key1.hashCode();
    430        }
    431        if (key2 != null) {
    432            h ^= key2.hashCode();
    433        }
    434        if (key3 != null) {
    435            h ^= key3.hashCode();
    436        }
    437        if (key4 != null) {
    438            h ^= key4.hashCode();
    439        }
    440        if (key5 != null) {
    441            h ^= key5.hashCode();
    442        }
    443        h += ~(h << 9);
    444        h ^=  h >>> 14;
    445        h +=  h << 4;
    446        h ^=  h >>> 10;
    447        return h;
    448    }
    449
    450    /**
    451     * Is the key equal to the combined key.
    452     *
    453     * @param entry  the entry to compare to
    454     * @param key1  the first key
    455     * @param key2  the second key
    456     * @return true if the key matches
    457     */
    458    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    459            final Object key1, final Object key2) {
    460        final MultiKey<? extends K> multi = entry.getKey();
    461        return
    462            multi.size() == 2 &&
    463            (key1 == multi.getKey(0) || key1 != null && key1.equals(multi.getKey(0))) &&
    464            (key2 == multi.getKey(1) || key2 != null && key2.equals(multi.getKey(1)));
    465    }
    466
    467    /**
    468     * Is the key equal to the combined key.
    469     *
    470     * @param entry  the entry to compare to
    471     * @param key1  the first key
    472     * @param key2  the second key
    473     * @param key3  the third key
    474     * @return true if the key matches
    475     */
    476    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    477                                 final Object key1, final Object key2, final Object key3) {
    478        final MultiKey<? extends K> multi = entry.getKey();
    479        return
    480            multi.size() == 3 &&
    481            (key1 == multi.getKey(0) || key1 != null && key1.equals(multi.getKey(0))) &&
    482            (key2 == multi.getKey(1) || key2 != null && key2.equals(multi.getKey(1))) &&
    483            (key3 == multi.getKey(2) || key3 != null && key3.equals(multi.getKey(2)));
    484    }
    485
    486    /**
    487     * Is the key equal to the combined key.
    488     *
    489     * @param entry  the entry to compare to
    490     * @param key1  the first key
    491     * @param key2  the second key
    492     * @param key3  the third key
    493     * @param key4  the fourth key
    494     * @return true if the key matches
    495     */
    496    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    497                                 final Object key1, final Object key2, final Object key3, final Object key4) {
    498        final MultiKey<? extends K> multi = entry.getKey();
    499        return
    500            multi.size() == 4 &&
    501            (key1 == multi.getKey(0) || key1 != null && key1.equals(multi.getKey(0))) &&
    502            (key2 == multi.getKey(1) || key2 != null && key2.equals(multi.getKey(1))) &&
    503            (key3 == multi.getKey(2) || key3 != null && key3.equals(multi.getKey(2))) &&
    504            (key4 == multi.getKey(3) || key4 != null && key4.equals(multi.getKey(3)));
    505    }
    506
    507    /**
    508     * Is the key equal to the combined key.
    509     *
    510     * @param entry  the entry to compare to
    511     * @param key1  the first key
    512     * @param key2  the second key
    513     * @param key3  the third key
    514     * @param key4  the fourth key
    515     * @param key5  the fifth key
    516     * @return true if the key matches
    517     */
    518    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    519            final Object key1, final Object key2, final Object key3, final Object key4, final Object key5) {
    520        final MultiKey<? extends K> multi = entry.getKey();
    521        return
    522            multi.size() == 5 &&
    523            (key1 == multi.getKey(0) || key1 != null && key1.equals(multi.getKey(0))) &&
    524            (key2 == multi.getKey(1) || key2 != null && key2.equals(multi.getKey(1))) &&
    525            (key3 == multi.getKey(2) || key3 != null && key3.equals(multi.getKey(2))) &&
    526            (key4 == multi.getKey(3) || key4 != null && key4.equals(multi.getKey(3))) &&
    527            (key5 == multi.getKey(4) || key5 != null && key5.equals(multi.getKey(4)));
    528    }
    529
    530    @Override
    531    public MapIterator<MultiKey<? extends K>, V> mapIterator() {
    532        return decorated().mapIterator();
    533    }
    534
    535    /**
    536     * Stores the value against the specified multi-key.
    537     *
    538     * @param key1  the first key
    539     * @param key2  the second key
    540     * @param key3  the third key
    541     * @param key4  the fourth key
    542     * @param key5  the fifth key
    543     * @param value  the value to store
    544     * @return the value previously mapped to this combined key, null if none
    545     */
    546    public V put(final K key1, final K key2, final K key3, final K key4, final K key5, final V value) {
    547        final int hashCode = hash(key1, key2, key3, key4, key5);
    548        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    549        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    550        while (entry != null) {
    551            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    552                final V oldValue = entry.getValue();
    553                decorated().updateEntry(entry, value);
    554                return oldValue;
    555            }
    556            entry = entry.next;
    557        }
    558        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2, key3, key4, key5), value);
    559        return null;
    560    }
    561
    562    /**
    563     * Stores the value against the specified multi-key.
    564     *
    565     * @param key1  the first key
    566     * @param key2  the second key
    567     * @param key3  the third key
    568     * @param key4  the fourth key
    569     * @param value  the value to store
    570     * @return the value previously mapped to this combined key, null if none
    571     */
    572    public V put(final K key1, final K key2, final K key3, final K key4, final V value) {
    573        final int hashCode = hash(key1, key2, key3, key4);
    574        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    575        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    576        while (entry != null) {
    577            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    578                final V oldValue = entry.getValue();
    579                decorated().updateEntry(entry, value);
    580                return oldValue;
    581            }
    582            entry = entry.next;
    583        }
    584        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2, key3, key4), value);
    585        return null;
    586    }
    587
    588    /**
    589     * Stores the value against the specified multi-key.
    590     *
    591     * @param key1  the first key
    592     * @param key2  the second key
    593     * @param key3  the third key
    594     * @param value  the value to store
    595     * @return the value previously mapped to this combined key, null if none
    596     */
    597    public V put(final K key1, final K key2, final K key3, final V value) {
    598        final int hashCode = hash(key1, key2, key3);
    599        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    600        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    601        while (entry != null) {
    602            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    603                final V oldValue = entry.getValue();
    604                decorated().updateEntry(entry, value);
    605                return oldValue;
    606            }
    607            entry = entry.next;
    608        }
    609        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2, key3), value);
    610        return null;
    611    }
    612
    613    /**
    614     * Stores the value against the specified multi-key.
    615     *
    616     * @param key1  the first key
    617     * @param key2  the second key
    618     * @param value  the value to store
    619     * @return the value previously mapped to this combined key, null if none
    620     */
    621    public V put(final K key1, final K key2, final V value) {
    622        final int hashCode = hash(key1, key2);
    623        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    624        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    625        while (entry != null) {
    626            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    627                final V oldValue = entry.getValue();
    628                decorated().updateEntry(entry, value);
    629                return oldValue;
    630            }
    631            entry = entry.next;
    632        }
    633        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2), value);
    634        return null;
    635    }
    636
    637    /**
    638     * Puts the key and value into the map, where the key must be a non-null
    639     * MultiKey object.
    640     *
    641     * @param key  the non-null MultiKey object
    642     * @param value  the value to store
    643     * @return the previous value for the key
    644     * @throws NullPointerException if the key is null
    645     * @throws ClassCastException if the key is not a MultiKey
    646     */
    647    @Override
    648    public V put(final MultiKey<? extends K> key, final V value) {
    649        checkKey(key);
    650        return super.put(key, value);
    651    }
    652
    653    /**
    654     * Copies all of the keys and values from the specified map to this map.
    655     * Each key must be non-null and a MultiKey object.
    656     *
    657     * @param mapToCopy  to this map
    658     * @throws NullPointerException if the mapToCopy or any key within is null
    659     * @throws ClassCastException if any key in mapToCopy is not a MultiKey
    660     */
    661    @Override
    662    public void putAll(final Map<? extends MultiKey<? extends K>, ? extends V> mapToCopy) {
    663        for (final MultiKey<? extends K> key : mapToCopy.keySet()) {
    664            checkKey(key);
    665        }
    666        super.putAll(mapToCopy);
    667    }
    668
    669    /**
    670     * Read the map in using a custom routine.
    671     *
    672     * @param in  the input stream
    673     * @throws IOException if an error occurs while reading from the stream
    674     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    675     */
    676    @SuppressWarnings("unchecked")
    677    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    678        in.defaultReadObject();
    679        map = (Map<MultiKey<? extends K>, V>) in.readObject();
    680    }
    681
    682    /**
    683     * Removes all mappings where the first key is that specified.
    684     * <p>
    685     * This method removes all the mappings where the {@code MultiKey}
    686     * has one or more keys, and the first matches that specified.
    687     *
    688     * @param key1  the first key
    689     * @return true if any elements were removed
    690     */
    691    public boolean removeAll(final Object key1) {
    692        boolean modified = false;
    693        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    694        while (it.hasNext()) {
    695            final MultiKey<? extends K> multi = it.next();
    696            if (multi.size() >= 1 &&
    697                (key1 == null ? multi.getKey(0) == null : key1.equals(multi.getKey(0)))) {
    698                it.remove();
    699                modified = true;
    700            }
    701        }
    702        return modified;
    703    }
    704
    705    /**
    706     * Removes all mappings where the first two keys are those specified.
    707     * <p>
    708     * This method removes all the mappings where the {@code MultiKey}
    709     * has two or more keys, and the first two match those specified.
    710     *
    711     * @param key1  the first key
    712     * @param key2  the second key
    713     * @return true if any elements were removed
    714     */
    715    public boolean removeAll(final Object key1, final Object key2) {
    716        boolean modified = false;
    717        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    718        while (it.hasNext()) {
    719            final MultiKey<? extends K> multi = it.next();
    720            if (multi.size() >= 2 &&
    721                (key1 == null ? multi.getKey(0) == null : key1.equals(multi.getKey(0))) &&
    722                (key2 == null ? multi.getKey(1) == null : key2.equals(multi.getKey(1)))) {
    723                it.remove();
    724                modified = true;
    725            }
    726        }
    727        return modified;
    728    }
    729
    730    /**
    731     * Removes all mappings where the first three keys are those specified.
    732     * <p>
    733     * This method removes all the mappings where the {@code MultiKey}
    734     * has three or more keys, and the first three match those specified.
    735     *
    736     * @param key1  the first key
    737     * @param key2  the second key
    738     * @param key3  the third key
    739     * @return true if any elements were removed
    740     */
    741    public boolean removeAll(final Object key1, final Object key2, final Object key3) {
    742        boolean modified = false;
    743        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    744        while (it.hasNext()) {
    745            final MultiKey<? extends K> multi = it.next();
    746            if (multi.size() >= 3 &&
    747                (key1 == null ? multi.getKey(0) == null : key1.equals(multi.getKey(0))) &&
    748                (key2 == null ? multi.getKey(1) == null : key2.equals(multi.getKey(1))) &&
    749                (key3 == null ? multi.getKey(2) == null : key3.equals(multi.getKey(2)))) {
    750                it.remove();
    751                modified = true;
    752            }
    753        }
    754        return modified;
    755    }
    756
    757    /**
    758     * Removes all mappings where the first four keys are those specified.
    759     * <p>
    760     * This method removes all the mappings where the {@code MultiKey}
    761     * has four or more keys, and the first four match those specified.
    762     *
    763     * @param key1  the first key
    764     * @param key2  the second key
    765     * @param key3  the third key
    766     * @param key4  the fourth key
    767     * @return true if any elements were removed
    768     */
    769    public boolean removeAll(final Object key1, final Object key2, final Object key3, final Object key4) {
    770        boolean modified = false;
    771        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    772        while (it.hasNext()) {
    773            final MultiKey<? extends K> multi = it.next();
    774            if (multi.size() >= 4 &&
    775                (key1 == null ? multi.getKey(0) == null : key1.equals(multi.getKey(0))) &&
    776                (key2 == null ? multi.getKey(1) == null : key2.equals(multi.getKey(1))) &&
    777                (key3 == null ? multi.getKey(2) == null : key3.equals(multi.getKey(2))) &&
    778                (key4 == null ? multi.getKey(3) == null : key4.equals(multi.getKey(3)))) {
    779                it.remove();
    780                modified = true;
    781            }
    782        }
    783        return modified;
    784    }
    785
    786    /**
    787     * Removes the specified multi-key from this map.
    788     *
    789     * @param key1  the first key
    790     * @param key2  the second key
    791     * @return the value mapped to the removed key, null if key not in map
    792     * @since 4.0 (previous name: remove(Object, Object))
    793     */
    794    public V removeMultiKey(final Object key1, final Object key2) {
    795        final int hashCode = hash(key1, key2);
    796        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    797        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    798        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    799        while (entry != null) {
    800            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    801                final V oldValue = entry.getValue();
    802                decorated().removeMapping(entry, index, previous);
    803                return oldValue;
    804            }
    805            previous = entry;
    806            entry = entry.next;
    807        }
    808        return null;
    809    }
    810
    811    /**
    812     * Removes the specified multi-key from this map.
    813     *
    814     * @param key1  the first key
    815     * @param key2  the second key
    816     * @param key3  the third key
    817     * @return the value mapped to the removed key, null if key not in map
    818     * @since 4.0 (previous name: remove(Object, Object, Object))
    819     */
    820    public V removeMultiKey(final Object key1, final Object key2, final Object key3) {
    821        final int hashCode = hash(key1, key2, key3);
    822        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    823        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    824        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    825        while (entry != null) {
    826            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    827                final V oldValue = entry.getValue();
    828                decorated().removeMapping(entry, index, previous);
    829                return oldValue;
    830            }
    831            previous = entry;
    832            entry = entry.next;
    833        }
    834        return null;
    835    }
    836
    837    /**
    838     * Removes the specified multi-key from this map.
    839     *
    840     * @param key1  the first key
    841     * @param key2  the second key
    842     * @param key3  the third key
    843     * @param key4  the fourth key
    844     * @return the value mapped to the removed key, null if key not in map
    845     * @since 4.0 (previous name: remove(Object, Object, Object, Object))
    846     */
    847    public V removeMultiKey(final Object key1, final Object key2, final Object key3, final Object key4) {
    848        final int hashCode = hash(key1, key2, key3, key4);
    849        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    850        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    851        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    852        while (entry != null) {
    853            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    854                final V oldValue = entry.getValue();
    855                decorated().removeMapping(entry, index, previous);
    856                return oldValue;
    857            }
    858            previous = entry;
    859            entry = entry.next;
    860        }
    861        return null;
    862    }
    863
    864    /**
    865     * Removes the specified multi-key from this map.
    866     *
    867     * @param key1  the first key
    868     * @param key2  the second key
    869     * @param key3  the third key
    870     * @param key4  the fourth key
    871     * @param key5  the fifth key
    872     * @return the value mapped to the removed key, null if key not in map
    873     * @since 4.0 (previous name: remove(Object, Object, Object, Object, Object))
    874     */
    875    public V removeMultiKey(final Object key1, final Object key2, final Object key3,
    876                            final Object key4, final Object key5) {
    877        final int hashCode = hash(key1, key2, key3, key4, key5);
    878        final int index = decorated().hashIndex(hashCode, decorated().data.length);
    879        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    880        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    881        while (entry != null) {
    882            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    883                final V oldValue = entry.getValue();
    884                decorated().removeMapping(entry, index, previous);
    885                return oldValue;
    886            }
    887            previous = entry;
    888            entry = entry.next;
    889        }
    890        return null;
    891    }
    892
    893    /**
    894     * Write the map out using a custom routine.
    895     *
    896     * @param out  the output stream
    897     * @throws IOException if an error occurs while writing to the stream
    898     */
    899    private void writeObject(final ObjectOutputStream out) throws IOException {
    900        out.defaultWriteObject();
    901        out.writeObject(map);
    902    }
    903
    904}