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