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.IOException;
020    import java.io.ObjectInputStream;
021    import java.io.ObjectOutputStream;
022    import java.io.Serializable;
023    import java.util.AbstractCollection;
024    import java.util.AbstractSet;
025    import java.util.Collection;
026    import java.util.Iterator;
027    import java.util.Map;
028    import java.util.NoSuchElementException;
029    import java.util.Set;
030    
031    import org.apache.commons.collections.IterableMap;
032    import org.apache.commons.collections.MapIterator;
033    import org.apache.commons.collections.ResettableIterator;
034    import org.apache.commons.collections.iterators.EmptyIterator;
035    import org.apache.commons.collections.iterators.EmptyMapIterator;
036    
037    /**
038     * A <code>Map</code> implementation that stores data in simple fields until
039     * the size is greater than 3.
040     * <p>
041     * This map is designed for performance and can outstrip HashMap.
042     * It also has good garbage collection characteristics.
043     * <ul>
044     * <li>Optimised for operation at size 3 or less.
045     * <li>Still works well once size 3 exceeded.
046     * <li>Gets at size 3 or less are about 0-10% faster than HashMap,
047     * <li>Puts at size 3 or less are over 4 times faster than HashMap.
048     * <li>Performance 5% slower than HashMap once size 3 exceeded once.
049     * </ul>
050     * The design uses two distinct modes of operation - flat and delegate.
051     * While the map is size 3 or less, operations map straight onto fields using
052     * switch statements. Once size 4 is reached, the map switches to delegate mode
053     * and only switches back when cleared. In delegate mode, all operations are
054     * forwarded straight to a HashMap resulting in the 5% performance loss.
055     * <p>
056     * The performance gains on puts are due to not needing to create a Map Entry
057     * object. This is a large saving not only in performance but in garbage collection.
058     * <p>
059     * Whilst in flat mode this map is also easy for the garbage collector to dispatch.
060     * This is because it contains no complex objects or arrays which slow the progress.
061     * <p>
062     * Do not use <code>Flat3Map</code> if the size is likely to grow beyond 3.
063     * <p>
064     * <strong>Note that Flat3Map is not synchronized and is not thread-safe.</strong>
065     * If you wish to use this map from multiple threads concurrently, you must use
066     * appropriate synchronization. The simplest approach is to wrap this map
067     * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 
068     * exceptions when accessed by concurrent threads without synchronization.
069     *
070     * @since Commons Collections 3.0
071     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
072     *
073     * @author Stephen Colebourne
074     */
075    public class Flat3Map implements IterableMap, Serializable, Cloneable {
076    
077        /** Serialization version */
078        private static final long serialVersionUID = -6701087419741928296L;
079    
080        /** The size of the map, used while in flat mode */
081        private transient int size;
082        /** Hash, used while in flat mode */
083        private transient int hash1;
084        /** Hash, used while in flat mode */
085        private transient int hash2;
086        /** Hash, used while in flat mode */
087        private transient int hash3;
088        /** Key, used while in flat mode */
089        private transient Object key1;
090        /** Key, used while in flat mode */
091        private transient Object key2;
092        /** Key, used while in flat mode */
093        private transient Object key3;
094        /** Value, used while in flat mode */
095        private transient Object value1;
096        /** Value, used while in flat mode */
097        private transient Object value2;
098        /** Value, used while in flat mode */
099        private transient Object value3;
100        /** Map, used while in delegate mode */
101        private transient AbstractHashedMap delegateMap;
102    
103        /**
104         * Constructor.
105         */
106        public Flat3Map() {
107            super();
108        }
109    
110        /**
111         * Constructor copying elements from another map.
112         *
113         * @param map  the map to copy
114         * @throws NullPointerException if the map is null
115         */
116        public Flat3Map(Map map) {
117            super();
118            putAll(map);
119        }
120    
121        //-----------------------------------------------------------------------
122        /**
123         * Gets the value mapped to the key specified.
124         * 
125         * @param key  the key
126         * @return the mapped value, null if no match
127         */
128        public Object get(Object key) {
129            if (delegateMap != null) {
130                return delegateMap.get(key);
131            }
132            if (key == null) {
133                switch (size) {
134                    // drop through
135                    case 3:
136                        if (key3 == null) return value3;
137                    case 2:
138                        if (key2 == null) return value2;
139                    case 1:
140                        if (key1 == null) return value1;
141                }
142            } else {
143                if (size > 0) {
144                    int hashCode = key.hashCode();
145                    switch (size) {
146                        // drop through
147                        case 3:
148                            if (hash3 == hashCode && key.equals(key3)) return value3;
149                        case 2:
150                            if (hash2 == hashCode && key.equals(key2)) return value2;
151                        case 1:
152                            if (hash1 == hashCode && key.equals(key1)) return value1;
153                    }
154                }
155            }
156            return null;
157        }
158    
159        /**
160         * Gets the size of the map.
161         * 
162         * @return the size
163         */
164        public int size() {
165            if (delegateMap != null) {
166                return delegateMap.size();
167            }
168            return size;
169        }
170    
171        /**
172         * Checks whether the map is currently empty.
173         * 
174         * @return true if the map is currently size zero
175         */
176        public boolean isEmpty() {
177            return (size() == 0);
178        }
179    
180        //-----------------------------------------------------------------------
181        /**
182         * Checks whether the map contains the specified key.
183         * 
184         * @param key  the key to search for
185         * @return true if the map contains the key
186         */
187        public boolean containsKey(Object key) {
188            if (delegateMap != null) {
189                return delegateMap.containsKey(key);
190            }
191            if (key == null) {
192                switch (size) {  // drop through
193                    case 3:
194                        if (key3 == null) return true;
195                    case 2:
196                        if (key2 == null) return true;
197                    case 1:
198                        if (key1 == null) return true;
199                }
200            } else {
201                if (size > 0) {
202                    int hashCode = key.hashCode();
203                    switch (size) {  // drop through
204                        case 3:
205                            if (hash3 == hashCode && key.equals(key3)) return true;
206                        case 2:
207                            if (hash2 == hashCode && key.equals(key2)) return true;
208                        case 1:
209                            if (hash1 == hashCode && key.equals(key1)) return true;
210                    }
211                }
212            }
213            return false;
214        }
215    
216        /**
217         * Checks whether the map contains the specified value.
218         * 
219         * @param value  the value to search for
220         * @return true if the map contains the key
221         */
222        public boolean containsValue(Object value) {
223            if (delegateMap != null) {
224                return delegateMap.containsValue(value);
225            }
226            if (value == null) {  // drop through
227                switch (size) {
228                    case 3:
229                        if (value3 == null) return true;
230                    case 2:
231                        if (value2 == null) return true;
232                    case 1:
233                        if (value1 == null) return true;
234                }
235            } else {
236                switch (size) {  // drop through
237                    case 3:
238                        if (value.equals(value3)) return true;
239                    case 2:
240                        if (value.equals(value2)) return true;
241                    case 1:
242                        if (value.equals(value1)) return true;
243                }
244            }
245            return false;
246        }
247    
248        //-----------------------------------------------------------------------
249        /**
250         * Puts a key-value mapping into this map.
251         * 
252         * @param key  the key to add
253         * @param value  the value to add
254         * @return the value previously mapped to this key, null if none
255         */
256        public Object put(Object key, Object value) {
257            if (delegateMap != null) {
258                return delegateMap.put(key, value);
259            }
260            // change existing mapping
261            if (key == null) {
262                switch (size) {  // drop through
263                    case 3:
264                        if (key3 == null) {
265                            Object old = value3;
266                            value3 = value;
267                            return old;
268                        }
269                    case 2:
270                        if (key2 == null) {
271                            Object old = value2;
272                            value2 = value;
273                            return old;
274                        }
275                    case 1:
276                        if (key1 == null) {
277                            Object old = value1;
278                            value1 = value;
279                            return old;
280                        }
281                }
282            } else {
283                if (size > 0) {
284                    int hashCode = key.hashCode();
285                    switch (size) {  // drop through
286                        case 3:
287                            if (hash3 == hashCode && key.equals(key3)) {
288                                Object old = value3;
289                                value3 = value;
290                                return old;
291                            }
292                        case 2:
293                            if (hash2 == hashCode && key.equals(key2)) {
294                                Object old = value2;
295                                value2 = value;
296                                return old;
297                            }
298                        case 1:
299                            if (hash1 == hashCode && key.equals(key1)) {
300                                Object old = value1;
301                                value1 = value;
302                                return old;
303                            }
304                    }
305                }
306            }
307            
308            // add new mapping
309            switch (size) {
310                default:
311                    convertToMap();
312                    delegateMap.put(key, value);
313                    return null;
314                case 2:
315                    hash3 = (key == null ? 0 : key.hashCode());
316                    key3 = key;
317                    value3 = value;
318                    break;
319                case 1:
320                    hash2 = (key == null ? 0 : key.hashCode());
321                    key2 = key;
322                    value2 = value;
323                    break;
324                case 0:
325                    hash1 = (key == null ? 0 : key.hashCode());
326                    key1 = key;
327                    value1 = value;
328                    break;
329            }
330            size++;
331            return null;
332        }
333    
334        /**
335         * Puts all the values from the specified map into this map.
336         * 
337         * @param map  the map to add
338         * @throws NullPointerException if the map is null
339         */
340        public void putAll(Map map) {
341            int size = map.size();
342            if (size == 0) {
343                return;
344            }
345            if (delegateMap != null) {
346                delegateMap.putAll(map);
347                return;
348            }
349            if (size < 4) {
350                for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
351                    Map.Entry entry = (Map.Entry) it.next();
352                    put(entry.getKey(), entry.getValue());
353                }
354            } else {
355                convertToMap();
356                delegateMap.putAll(map);
357            }
358        }
359    
360        /**
361         * Converts the flat map data to a map.
362         */
363        private void convertToMap() {
364            delegateMap = createDelegateMap();
365            switch (size) {  // drop through
366                case 3:
367                    delegateMap.put(key3, value3);
368                case 2:
369                    delegateMap.put(key2, value2);
370                case 1:
371                    delegateMap.put(key1, value1);
372            }
373            
374            size = 0;
375            hash1 = hash2 = hash3 = 0;
376            key1 = key2 = key3 = null;
377            value1 = value2 = value3 = null;
378        }
379    
380        /**
381         * Create an instance of the map used for storage when in delegation mode.
382         * <p>
383         * This can be overridden by subclasses to provide a different map implementation.
384         * Not every AbstractHashedMap is suitable, identity and reference based maps
385         * would be poor choices.
386         *
387         * @return a new AbstractHashedMap or subclass
388         * @since Commons Collections 3.1
389         */
390        protected AbstractHashedMap createDelegateMap() {
391            return new HashedMap();
392        }
393    
394        /**
395         * Removes the specified mapping from this map.
396         * 
397         * @param key  the mapping to remove
398         * @return the value mapped to the removed key, null if key not in map
399         */
400        public Object remove(Object key) {
401            if (delegateMap != null) {
402                return delegateMap.remove(key);
403            }
404            if (size == 0) {
405                return null;
406            }
407            if (key == null) {
408                switch (size) {  // drop through
409                    case 3:
410                        if (key3 == null) {
411                            Object old = value3;
412                            hash3 = 0;
413                            key3 = null;
414                            value3 = null;
415                            size = 2;
416                            return old;
417                        }
418                        if (key2 == null) {
419                            Object old = value3;
420                            hash2 = hash3;
421                            key2 = key3;
422                            value2 = value3;
423                            hash3 = 0;
424                            key3 = null;
425                            value3 = null;
426                            size = 2;
427                            return old;
428                        }
429                        if (key1 == null) {
430                            Object old = value3;
431                            hash1 = hash3;
432                            key1 = key3;
433                            value1 = value3;
434                            hash3 = 0;
435                            key3 = null;
436                            value3 = null;
437                            size = 2;
438                            return old;
439                        }
440                        return null;
441                    case 2:
442                        if (key2 == null) {
443                            Object old = value2;
444                            hash2 = 0;
445                            key2 = null;
446                            value2 = null;
447                            size = 1;
448                            return old;
449                        }
450                        if (key1 == null) {
451                            Object old = value2;
452                            hash1 = hash2;
453                            key1 = key2;
454                            value1 = value2;
455                            hash2 = 0;
456                            key2 = null;
457                            value2 = null;
458                            size = 1;
459                            return old;
460                        }
461                        return null;
462                    case 1:
463                        if (key1 == null) {
464                            Object old = value1;
465                            hash1 = 0;
466                            key1 = null;
467                            value1 = null;
468                            size = 0;
469                            return old;
470                        }
471                }
472            } else {
473                if (size > 0) {
474                    int hashCode = key.hashCode();
475                    switch (size) {  // drop through
476                        case 3:
477                            if (hash3 == hashCode && key.equals(key3)) {
478                                Object old = value3;
479                                hash3 = 0;
480                                key3 = null;
481                                value3 = null;
482                                size = 2;
483                                return old;
484                            }
485                            if (hash2 == hashCode && key.equals(key2)) {
486                                Object old = value3;
487                                hash2 = hash3;
488                                key2 = key3;
489                                value2 = value3;
490                                hash3 = 0;
491                                key3 = null;
492                                value3 = null;
493                                size = 2;
494                                return old;
495                            }
496                            if (hash1 == hashCode && key.equals(key1)) {
497                                Object old = value3;
498                                hash1 = hash3;
499                                key1 = key3;
500                                value1 = value3;
501                                hash3 = 0;
502                                key3 = null;
503                                value3 = null;
504                                size = 2;
505                                return old;
506                            }
507                            return null;
508                        case 2:
509                            if (hash2 == hashCode && key.equals(key2)) {
510                                Object old = value2;
511                                hash2 = 0;
512                                key2 = null;
513                                value2 = null;
514                                size = 1;
515                                return old;
516                            }
517                            if (hash1 == hashCode && key.equals(key1)) {
518                                Object old = value2;
519                                hash1 = hash2;
520                                key1 = key2;
521                                value1 = value2;
522                                hash2 = 0;
523                                key2 = null;
524                                value2 = null;
525                                size = 1;
526                                return old;
527                            }
528                            return null;
529                        case 1:
530                            if (hash1 == hashCode && key.equals(key1)) {
531                                Object old = value1;
532                                hash1 = 0;
533                                key1 = null;
534                                value1 = null;
535                                size = 0;
536                                return old;
537                            }
538                    }
539                }
540            }
541            return null;
542        }
543    
544        /**
545         * Clears the map, resetting the size to zero and nullifying references
546         * to avoid garbage collection issues.
547         */
548        public void clear() {
549            if (delegateMap != null) {
550                delegateMap.clear();  // should aid gc
551                delegateMap = null;  // switch back to flat mode
552            } else {
553                size = 0;
554                hash1 = hash2 = hash3 = 0;
555                key1 = key2 = key3 = null;
556                value1 = value2 = value3 = null;
557            }
558        }
559    
560        //-----------------------------------------------------------------------
561        /**
562         * Gets an iterator over the map.
563         * Changes made to the iterator affect this map.
564         * <p>
565         * A MapIterator returns the keys in the map. It also provides convenient
566         * methods to get the key and value, and set the value.
567         * It avoids the need to create an entrySet/keySet/values object.
568         * It also avoids creating the Map Entry object.
569         * 
570         * @return the map iterator
571         */
572        public MapIterator mapIterator() {
573            if (delegateMap != null) {
574                return delegateMap.mapIterator();
575            }
576            if (size == 0) {
577                return EmptyMapIterator.INSTANCE;
578            }
579            return new FlatMapIterator(this);
580        }
581    
582        /**
583         * FlatMapIterator
584         */
585        static class FlatMapIterator implements MapIterator, ResettableIterator {
586            private final Flat3Map parent;
587            private int nextIndex = 0;
588            private boolean canRemove = false;
589            
590            FlatMapIterator(Flat3Map parent) {
591                super();
592                this.parent = parent;
593            }
594    
595            public boolean hasNext() {
596                return (nextIndex < parent.size);
597            }
598    
599            public Object next() {
600                if (hasNext() == false) {
601                    throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
602                }
603                canRemove = true;
604                nextIndex++;
605                return getKey();
606            }
607    
608            public void remove() {
609                if (canRemove == false) {
610                    throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
611                }
612                parent.remove(getKey());
613                nextIndex--;
614                canRemove = false;
615            }
616    
617            public Object getKey() {
618                if (canRemove == false) {
619                    throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
620                }
621                switch (nextIndex) {
622                    case 3:
623                        return parent.key3;
624                    case 2:
625                        return parent.key2;
626                    case 1:
627                        return parent.key1;
628                }
629                throw new IllegalStateException("Invalid map index");
630            }
631    
632            public Object getValue() {
633                if (canRemove == false) {
634                    throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
635                }
636                switch (nextIndex) {
637                    case 3:
638                        return parent.value3;
639                    case 2:
640                        return parent.value2;
641                    case 1:
642                        return parent.value1;
643                }
644                throw new IllegalStateException("Invalid map index");
645            }
646    
647            public Object setValue(Object value) {
648                if (canRemove == false) {
649                    throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
650                }
651                Object old = getValue();
652                switch (nextIndex) {
653                    case 3: 
654                        parent.value3 = value;
655                    case 2:
656                        parent.value2 = value;
657                    case 1:
658                        parent.value1 = value;
659                }
660                return old;
661            }
662            
663            public void reset() {
664                nextIndex = 0;
665                canRemove = false;
666            }
667            
668            public String toString() {
669                if (canRemove) {
670                    return "Iterator[" + getKey() + "=" + getValue() + "]";
671                } else {
672                    return "Iterator[]";
673                }
674            }
675        }
676        
677        /**
678         * Gets the entrySet view of the map.
679         * Changes made to the view affect this map.
680         * The Map Entry is not an independent object and changes as the 
681         * iterator progresses.
682         * To simply iterate through the entries, use {@link #mapIterator()}.
683         * 
684         * @return the entrySet view
685         */
686        public Set entrySet() {
687            if (delegateMap != null) {
688                return delegateMap.entrySet();
689            }
690            return new EntrySet(this);
691        }
692        
693        /**
694         * EntrySet
695         */
696        static class EntrySet extends AbstractSet {
697            private final Flat3Map parent;
698            
699            EntrySet(Flat3Map parent) {
700                super();
701                this.parent = parent;
702            }
703    
704            public int size() {
705                return parent.size();
706            }
707            
708            public void clear() {
709                parent.clear();
710            }
711            
712            public boolean remove(Object obj) {
713                if (obj instanceof Map.Entry == false) {
714                    return false;
715                }
716                Map.Entry entry = (Map.Entry) obj;
717                Object key = entry.getKey();
718                boolean result = parent.containsKey(key);
719                parent.remove(key);
720                return result;
721            }
722    
723            public Iterator iterator() {
724                if (parent.delegateMap != null) {
725                    return parent.delegateMap.entrySet().iterator();
726                }
727                if (parent.size() == 0) {
728                    return EmptyIterator.INSTANCE;
729                }
730                return new EntrySetIterator(parent);
731            }
732        }
733    
734        /**
735         * EntrySetIterator and MapEntry
736         */
737        static class EntrySetIterator implements Iterator, Map.Entry {
738            private final Flat3Map parent;
739            private int nextIndex = 0;
740            private boolean canRemove = false;
741            
742            EntrySetIterator(Flat3Map parent) {
743                super();
744                this.parent = parent;
745            }
746    
747            public boolean hasNext() {
748                return (nextIndex < parent.size);
749            }
750    
751            public Object next() {
752                if (hasNext() == false) {
753                    throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
754                }
755                canRemove = true;
756                nextIndex++;
757                return this;
758            }
759    
760            public void remove() {
761                if (canRemove == false) {
762                    throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
763                }
764                parent.remove(getKey());
765                nextIndex--;
766                canRemove = false;
767            }
768    
769            public Object getKey() {
770                if (canRemove == false) {
771                    throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
772                }
773                switch (nextIndex) {
774                    case 3:
775                        return parent.key3;
776                    case 2:
777                        return parent.key2;
778                    case 1:
779                        return parent.key1;
780                }
781                throw new IllegalStateException("Invalid map index");
782            }
783    
784            public Object getValue() {
785                if (canRemove == false) {
786                    throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
787                }
788                switch (nextIndex) {
789                    case 3:
790                        return parent.value3;
791                    case 2:
792                        return parent.value2;
793                    case 1:
794                        return parent.value1;
795                }
796                throw new IllegalStateException("Invalid map index");
797            }
798    
799            public Object setValue(Object value) {
800                if (canRemove == false) {
801                    throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
802                }
803                Object old = getValue();
804                switch (nextIndex) {
805                    case 3: 
806                        parent.value3 = value;
807                    case 2:
808                        parent.value2 = value;
809                    case 1:
810                        parent.value1 = value;
811                }
812                return old;
813            }
814            
815            public boolean equals(Object obj) {
816                if (canRemove == false) {
817                    return false;
818                }
819                if (obj instanceof Map.Entry == false) {
820                    return false;
821                }
822                Map.Entry other = (Map.Entry) obj;
823                Object key = getKey();
824                Object value = getValue();
825                return (key == null ? other.getKey() == null : key.equals(other.getKey())) &&
826                       (value == null ? other.getValue() == null : value.equals(other.getValue()));
827            }
828            
829            public int hashCode() {
830                if (canRemove == false) {
831                    return 0;
832                }
833                Object key = getKey();
834                Object value = getValue();
835                return (key == null ? 0 : key.hashCode()) ^
836                       (value == null ? 0 : value.hashCode());
837            }
838            
839            public String toString() {
840                if (canRemove) {
841                    return getKey() + "=" + getValue();
842                } else {
843                    return "";
844                }
845            }
846        }
847        
848        /**
849         * Gets the keySet view of the map.
850         * Changes made to the view affect this map.
851         * To simply iterate through the keys, use {@link #mapIterator()}.
852         * 
853         * @return the keySet view
854         */
855        public Set keySet() {
856            if (delegateMap != null) {
857                return delegateMap.keySet();
858            }
859            return new KeySet(this);
860        }
861    
862        /**
863         * KeySet
864         */
865        static class KeySet extends AbstractSet {
866            private final Flat3Map parent;
867            
868            KeySet(Flat3Map parent) {
869                super();
870                this.parent = parent;
871            }
872    
873            public int size() {
874                return parent.size();
875            }
876            
877            public void clear() {
878                parent.clear();
879            }
880            
881            public boolean contains(Object key) {
882                return parent.containsKey(key);
883            }
884    
885            public boolean remove(Object key) {
886                boolean result = parent.containsKey(key);
887                parent.remove(key);
888                return result;
889            }
890    
891            public Iterator iterator() {
892                if (parent.delegateMap != null) {
893                    return parent.delegateMap.keySet().iterator();
894                }
895                if (parent.size() == 0) {
896                    return EmptyIterator.INSTANCE;
897                }
898                return new KeySetIterator(parent);
899            }
900        }
901    
902        /**
903         * KeySetIterator
904         */
905        static class KeySetIterator extends EntrySetIterator {
906            
907            KeySetIterator(Flat3Map parent) {
908                super(parent);
909            }
910    
911            public Object next() {
912                super.next();
913                return getKey();
914            }
915        }
916        
917        /**
918         * Gets the values view of the map.
919         * Changes made to the view affect this map.
920         * To simply iterate through the values, use {@link #mapIterator()}.
921         * 
922         * @return the values view
923         */
924        public Collection values() {
925            if (delegateMap != null) {
926                return delegateMap.values();
927            }
928            return new Values(this);
929        }
930    
931        /**
932         * Values
933         */
934        static class Values extends AbstractCollection {
935            private final Flat3Map parent;
936            
937            Values(Flat3Map parent) {
938                super();
939                this.parent = parent;
940            }
941    
942            public int size() {
943                return parent.size();
944            }
945            
946            public void clear() {
947                parent.clear();
948            }
949            
950            public boolean contains(Object value) {
951                return parent.containsValue(value);
952            }
953    
954            public Iterator iterator() {
955                if (parent.delegateMap != null) {
956                    return parent.delegateMap.values().iterator();
957                }
958                if (parent.size() == 0) {
959                    return EmptyIterator.INSTANCE;
960                }
961                return new ValuesIterator(parent);
962            }
963        }
964    
965        /**
966         * ValuesIterator
967         */
968        static class ValuesIterator extends EntrySetIterator {
969            
970            ValuesIterator(Flat3Map parent) {
971                super(parent);
972            }
973    
974            public Object next() {
975                super.next();
976                return getValue();
977            }
978        }
979    
980        //-----------------------------------------------------------------------
981        /**
982         * Write the map out using a custom routine.
983         */
984        private void writeObject(ObjectOutputStream out) throws IOException {
985            out.defaultWriteObject();
986            out.writeInt(size());
987            for (MapIterator it = mapIterator(); it.hasNext();) {
988                out.writeObject(it.next());  // key
989                out.writeObject(it.getValue());  // value
990            }
991        }
992    
993        /**
994         * Read the map in using a custom routine.
995         */
996        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
997            in.defaultReadObject();
998            int count = in.readInt();
999            if (count > 3) {
1000                delegateMap = createDelegateMap();
1001            }
1002            for (int i = count; i > 0; i--) {
1003                put(in.readObject(), in.readObject());
1004            }
1005        }
1006    
1007        //-----------------------------------------------------------------------
1008        /**
1009         * Clones the map without cloning the keys or values.
1010         *
1011         * @return a shallow clone
1012         * @since Commons Collections 3.1
1013         */
1014        public Object clone() {
1015            try {
1016                Flat3Map cloned = (Flat3Map) super.clone();
1017                if (cloned.delegateMap != null) {
1018                    cloned.delegateMap = (HashedMap) cloned.delegateMap.clone();
1019                }
1020                return cloned;
1021            } catch (CloneNotSupportedException ex) {
1022                throw new InternalError();
1023            }
1024        }
1025    
1026        /**
1027         * Compares this map with another.
1028         * 
1029         * @param obj  the object to compare to
1030         * @return true if equal
1031         */
1032        public boolean equals(Object obj) {
1033            if (obj == this) {
1034                return true;
1035            }
1036            if (delegateMap != null) {
1037                return delegateMap.equals(obj);
1038            }
1039            if (obj instanceof Map == false) {
1040                return false;
1041            }
1042            Map other = (Map) obj;
1043            if (size != other.size()) {
1044                return false;
1045            }
1046            if (size > 0) {
1047                Object otherValue = null;
1048                switch (size) {  // drop through
1049                    case 3:
1050                        if (other.containsKey(key3) == false) {
1051                            return false;
1052                        }
1053                        otherValue = other.get(key3);
1054                        if (value3 == null ? otherValue != null : !value3.equals(otherValue)) {
1055                            return false;
1056                        }
1057                    case 2:
1058                        if (other.containsKey(key2) == false) {
1059                            return false;
1060                        }
1061                        otherValue = other.get(key2);
1062                        if (value2 == null ? otherValue != null : !value2.equals(otherValue)) {
1063                            return false;
1064                        }
1065                    case 1:
1066                        if (other.containsKey(key1) == false) {
1067                            return false;
1068                        }
1069                        otherValue = other.get(key1);
1070                        if (value1 == null ? otherValue != null : !value1.equals(otherValue)) {
1071                            return false;
1072                        }
1073                }
1074            }
1075            return true;
1076        }
1077    
1078        /**
1079         * Gets the standard Map hashCode.
1080         * 
1081         * @return the hash code defined in the Map interface
1082         */
1083        public int hashCode() {
1084            if (delegateMap != null) {
1085                return delegateMap.hashCode();
1086            }
1087            int total = 0;
1088            switch (size) {  // drop through
1089                case 3:
1090                    total += (hash3 ^ (value3 == null ? 0 : value3.hashCode()));
1091                case 2:
1092                    total += (hash2 ^ (value2 == null ? 0 : value2.hashCode()));
1093                case 1:
1094                    total += (hash1 ^ (value1 == null ? 0 : value1.hashCode()));
1095            }
1096            return total;
1097        }
1098    
1099        /**
1100         * Gets the map as a String.
1101         * 
1102         * @return a string version of the map
1103         */
1104        public String toString() {
1105            if (delegateMap != null) {
1106                return delegateMap.toString();
1107            }
1108            if (size == 0) {
1109                return "{}";
1110            }
1111            StringBuffer buf = new StringBuffer(128);
1112            buf.append('{');
1113            switch (size) {  // drop through
1114                case 3:
1115                    buf.append((key3 == this ? "(this Map)" : key3));
1116                    buf.append('=');
1117                    buf.append((value3 == this ? "(this Map)" : value3));
1118                    buf.append(',');
1119                case 2:
1120                    buf.append((key2 == this ? "(this Map)" : key2));
1121                    buf.append('=');
1122                    buf.append((value2 == this ? "(this Map)" : value2));
1123                    buf.append(',');
1124                case 1:
1125                    buf.append((key1 == this ? "(this Map)" : key1));
1126                    buf.append('=');
1127                    buf.append((value1 == this ? "(this Map)" : value1));
1128            }
1129            buf.append('}');
1130            return buf.toString();
1131        }
1132    
1133    }