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