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