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.util.AbstractCollection;
023    import java.util.AbstractMap;
024    import java.util.AbstractSet;
025    import java.util.Collection;
026    import java.util.ConcurrentModificationException;
027    import java.util.Iterator;
028    import java.util.Map;
029    import java.util.NoSuchElementException;
030    import java.util.Set;
031    
032    import org.apache.commons.collections.IterableMap;
033    import org.apache.commons.collections.KeyValue;
034    import org.apache.commons.collections.MapIterator;
035    import org.apache.commons.collections.iterators.EmptyIterator;
036    import org.apache.commons.collections.iterators.EmptyMapIterator;
037    
038    /**
039     * An abstract implementation of a hash-based map which provides numerous points for
040     * subclasses to override.
041     * <p>
042     * This class implements all the features necessary for a subclass hash-based map.
043     * Key-value entries are stored in instances of the <code>HashEntry</code> class,
044     * which can be overridden and replaced. The iterators can similarly be replaced,
045     * without the need to replace the KeySet, EntrySet and Values view classes.
046     * <p>
047     * Overridable methods are provided to change the default hashing behaviour, and
048     * to change how entries are added to and removed from the map. Hopefully, all you
049     * need for unusual subclasses is here.
050     * <p>
051     * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
052     * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
053     * This extends clause will be removed in v4.0.
054     * 
055     * @since Commons Collections 3.0
056     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
057     *
058     * @author java util HashMap
059     * @author Stephen Colebourne
060     * @author Christian Siefkes
061     */
062    public class AbstractHashedMap extends AbstractMap implements IterableMap {
063        
064        protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
065        protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
066        protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
067        protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
068        protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
069        protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
070        
071        /** The default capacity to use */
072        protected static final int DEFAULT_CAPACITY = 16;
073        /** The default threshold to use */
074        protected static final int DEFAULT_THRESHOLD = 12;
075        /** The default load factor to use */
076        protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
077        /** The maximum capacity allowed */
078        protected static final int MAXIMUM_CAPACITY = 1 << 30;
079        /** An object for masking null */
080        protected static final Object NULL = new Object();
081        
082        /** Load factor, normally 0.75 */
083        protected transient float loadFactor;
084        /** The size of the map */
085        protected transient int size;
086        /** Map entries */
087        protected transient HashEntry[] data;
088        /** Size at which to rehash */
089        protected transient int threshold;
090        /** Modification count for iterators */
091        protected transient int modCount;
092        /** Entry set */
093        protected transient EntrySet entrySet;
094        /** Key set */
095        protected transient KeySet keySet;
096        /** Values */
097        protected transient Values values;
098    
099        /**
100         * Constructor only used in deserialization, do not use otherwise.
101         */
102        protected AbstractHashedMap() {
103            super();
104        }
105    
106        /**
107         * Constructor which performs no validation on the passed in parameters.
108         * 
109         * @param initialCapacity  the initial capacity, must be a power of two
110         * @param loadFactor  the load factor, must be &gt; 0.0f and generally &lt; 1.0f
111         * @param threshold  the threshold, must be sensible
112         */
113        protected AbstractHashedMap(int initialCapacity, float loadFactor, int threshold) {
114            super();
115            this.loadFactor = loadFactor;
116            this.data = new HashEntry[initialCapacity];
117            this.threshold = threshold;
118            init();
119        }
120    
121        /**
122         * Constructs a new, empty map with the specified initial capacity and
123         * default load factor. 
124         *
125         * @param initialCapacity  the initial capacity
126         * @throws IllegalArgumentException if the initial capacity is less than one
127         */
128        protected AbstractHashedMap(int initialCapacity) {
129            this(initialCapacity, DEFAULT_LOAD_FACTOR);
130        }
131    
132        /**
133         * Constructs a new, empty map with the specified initial capacity and
134         * load factor. 
135         *
136         * @param initialCapacity  the initial capacity
137         * @param loadFactor  the load factor
138         * @throws IllegalArgumentException if the initial capacity is less than one
139         * @throws IllegalArgumentException if the load factor is less than or equal to zero
140         */
141        protected AbstractHashedMap(int initialCapacity, float loadFactor) {
142            super();
143            if (initialCapacity < 1) {
144                throw new IllegalArgumentException("Initial capacity must be greater than 0");
145            }
146            if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
147                throw new IllegalArgumentException("Load factor must be greater than 0");
148            }
149            this.loadFactor = loadFactor;
150            initialCapacity = calculateNewCapacity(initialCapacity);
151            this.threshold = calculateThreshold(initialCapacity, loadFactor);
152            this.data = new HashEntry[initialCapacity];
153            init();
154        }
155    
156        /**
157         * Constructor copying elements from another map.
158         *
159         * @param map  the map to copy
160         * @throws NullPointerException if the map is null
161         */
162        protected AbstractHashedMap(Map map) {
163            this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
164            putAll(map);
165        }
166    
167        /**
168         * Initialise subclasses during construction, cloning or deserialization.
169         */
170        protected void init() {
171        }
172    
173        //-----------------------------------------------------------------------
174        /**
175         * Gets the value mapped to the key specified.
176         * 
177         * @param key  the key
178         * @return the mapped value, null if no match
179         */
180        public Object get(Object key) {
181            key = convertKey(key);
182            int hashCode = hash(key);
183            HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
184            while (entry != null) {
185                if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
186                    return entry.getValue();
187                }
188                entry = entry.next;
189            }
190            return null;
191        }
192    
193        /**
194         * Gets the size of the map.
195         * 
196         * @return the size
197         */
198        public int size() {
199            return size;
200        }
201    
202        /**
203         * Checks whether the map is currently empty.
204         * 
205         * @return true if the map is currently size zero
206         */
207        public boolean isEmpty() {
208            return (size == 0);
209        }
210    
211        //-----------------------------------------------------------------------
212        /**
213         * Checks whether the map contains the specified key.
214         * 
215         * @param key  the key to search for
216         * @return true if the map contains the key
217         */
218        public boolean containsKey(Object key) {
219            key = convertKey(key);
220            int hashCode = hash(key);
221            HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
222            while (entry != null) {
223                if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
224                    return true;
225                }
226                entry = entry.next;
227            }
228            return false;
229        }
230    
231        /**
232         * Checks whether the map contains the specified value.
233         * 
234         * @param value  the value to search for
235         * @return true if the map contains the value
236         */
237        public boolean containsValue(Object value) {
238            if (value == null) {
239                for (int i = 0, isize = data.length; i < isize; i++) {
240                    HashEntry entry = data[i];
241                    while (entry != null) {
242                        if (entry.getValue() == null) {
243                            return true;
244                        }
245                        entry = entry.next;
246                    }
247                }
248            } else {
249                for (int i = 0, isize = data.length; i < isize; i++) {
250                    HashEntry entry = data[i];
251                    while (entry != null) {
252                        if (isEqualValue(value, entry.getValue())) {
253                            return true;
254                        }
255                        entry = entry.next;
256                    }
257                }
258            }
259            return false;
260        }
261    
262        //-----------------------------------------------------------------------
263        /**
264         * Puts a key-value mapping into this map.
265         * 
266         * @param key  the key to add
267         * @param value  the value to add
268         * @return the value previously mapped to this key, null if none
269         */
270        public Object put(Object key, Object value) {
271            key = convertKey(key);
272            int hashCode = hash(key);
273            int index = hashIndex(hashCode, data.length);
274            HashEntry entry = data[index];
275            while (entry != null) {
276                if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
277                    Object oldValue = entry.getValue();
278                    updateEntry(entry, value);
279                    return oldValue;
280                }
281                entry = entry.next;
282            }
283            
284            addMapping(index, hashCode, key, value);
285            return null;
286        }
287    
288        /**
289         * Puts all the values from the specified map into this map.
290         * <p>
291         * This implementation iterates around the specified map and
292         * uses {@link #put(Object, Object)}.
293         * 
294         * @param map  the map to add
295         * @throws NullPointerException if the map is null
296         */
297        public void putAll(Map map) {
298            int mapSize = map.size();
299            if (mapSize == 0) {
300                return;
301            }
302            int newSize = (int) ((size + mapSize) / loadFactor + 1);
303            ensureCapacity(calculateNewCapacity(newSize));
304            for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
305                Map.Entry entry = (Map.Entry) it.next();
306                put(entry.getKey(), entry.getValue());
307            }
308        }
309    
310        /**
311         * Removes the specified mapping from this map.
312         * 
313         * @param key  the mapping to remove
314         * @return the value mapped to the removed key, null if key not in map
315         */
316        public Object remove(Object key) {
317            key = convertKey(key);
318            int hashCode = hash(key);
319            int index = hashIndex(hashCode, data.length);
320            HashEntry entry = data[index];
321            HashEntry previous = null;
322            while (entry != null) {
323                if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
324                    Object oldValue = entry.getValue();
325                    removeMapping(entry, index, previous);
326                    return oldValue;
327                }
328                previous = entry;
329                entry = entry.next;
330            }
331            return null;
332        }
333    
334        /**
335         * Clears the map, resetting the size to zero and nullifying references
336         * to avoid garbage collection issues.
337         */
338        public void clear() {
339            modCount++;
340            HashEntry[] data = this.data;
341            for (int i = data.length - 1; i >= 0; i--) {
342                data[i] = null;
343            }
344            size = 0;
345        }
346    
347        //-----------------------------------------------------------------------
348        /**
349         * Converts input keys to another object for storage in the map.
350         * This implementation masks nulls.
351         * Subclasses can override this to perform alternate key conversions.
352         * <p>
353         * The reverse conversion can be changed, if required, by overriding the
354         * getKey() method in the hash entry.
355         * 
356         * @param key  the key convert
357         * @return the converted key
358         */
359        protected Object convertKey(Object key) {
360            return (key == null ? NULL : key);
361        }
362        
363        /**
364         * Gets the hash code for the key specified.
365         * This implementation uses the additional hashing routine from JDK1.4.
366         * Subclasses can override this to return alternate hash codes.
367         * 
368         * @param key  the key to get a hash code for
369         * @return the hash code
370         */
371        protected int hash(Object key) {
372            // same as JDK 1.4
373            int h = key.hashCode();
374            h += ~(h << 9);
375            h ^=  (h >>> 14);
376            h +=  (h << 4);
377            h ^=  (h >>> 10);
378            return h;
379        }
380        
381        /**
382         * Compares two keys, in internal converted form, to see if they are equal.
383         * This implementation uses the equals method and assumes neither key is null.
384         * Subclasses can override this to match differently.
385         * 
386         * @param key1  the first key to compare passed in from outside
387         * @param key2  the second key extracted from the entry via <code>entry.key</code>
388         * @return true if equal
389         */
390        protected boolean isEqualKey(Object key1, Object key2) {
391            return (key1 == key2 || key1.equals(key2));
392        }
393        
394        /**
395         * Compares two values, in external form, to see if they are equal.
396         * This implementation uses the equals method and assumes neither value is null.
397         * Subclasses can override this to match differently.
398         * 
399         * @param value1  the first value to compare passed in from outside
400         * @param value2  the second value extracted from the entry via <code>getValue()</code>
401         * @return true if equal
402         */
403        protected boolean isEqualValue(Object value1, Object value2) {
404            return (value1 == value2 || value1.equals(value2));
405        }
406        
407        /**
408         * Gets the index into the data storage for the hashCode specified.
409         * This implementation uses the least significant bits of the hashCode.
410         * Subclasses can override this to return alternate bucketing.
411         * 
412         * @param hashCode  the hash code to use
413         * @param dataSize  the size of the data to pick a bucket from
414         * @return the bucket index
415         */
416        protected int hashIndex(int hashCode, int dataSize) {
417            return hashCode & (dataSize - 1);
418        }
419        
420        //-----------------------------------------------------------------------
421        /**
422         * Gets the entry mapped to the key specified.
423         * <p>
424         * This method exists for subclasses that may need to perform a multi-step
425         * process accessing the entry. The public methods in this class don't use this
426         * method to gain a small performance boost.
427         * 
428         * @param key  the key
429         * @return the entry, null if no match
430         */
431        protected HashEntry getEntry(Object key) {
432            key = convertKey(key);
433            int hashCode = hash(key);
434            HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
435            while (entry != null) {
436                if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
437                    return entry;
438                }
439                entry = entry.next;
440            }
441            return null;
442        }
443    
444        //-----------------------------------------------------------------------
445        /**
446         * Updates an existing key-value mapping to change the value.
447         * <p>
448         * This implementation calls <code>setValue()</code> on the entry.
449         * Subclasses could override to handle changes to the map.
450         * 
451         * @param entry  the entry to update
452         * @param newValue  the new value to store
453         */
454        protected void updateEntry(HashEntry entry, Object newValue) {
455            entry.setValue(newValue);
456        }
457        
458        /**
459         * Reuses an existing key-value mapping, storing completely new data.
460         * <p>
461         * This implementation sets all the data fields on the entry.
462         * Subclasses could populate additional entry fields.
463         * 
464         * @param entry  the entry to update, not null
465         * @param hashIndex  the index in the data array
466         * @param hashCode  the hash code of the key to add
467         * @param key  the key to add
468         * @param value  the value to add
469         */
470        protected void reuseEntry(HashEntry entry, int hashIndex, int hashCode, Object key, Object value) {
471            entry.next = data[hashIndex];
472            entry.hashCode = hashCode;
473            entry.key = key;
474            entry.value = value;
475        }
476        
477        //-----------------------------------------------------------------------
478        /**
479         * Adds a new key-value mapping into this map.
480         * <p>
481         * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
482         * and <code>checkCapacity()</code>.
483         * It also handles changes to <code>modCount</code> and <code>size</code>.
484         * Subclasses could override to fully control adds to the map.
485         * 
486         * @param hashIndex  the index into the data array to store at
487         * @param hashCode  the hash code of the key to add
488         * @param key  the key to add
489         * @param value  the value to add
490         */
491        protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
492            modCount++;
493            HashEntry entry = createEntry(data[hashIndex], hashCode, key, value);
494            addEntry(entry, hashIndex);
495            size++;
496            checkCapacity();
497        }
498        
499        /**
500         * Creates an entry to store the key-value data.
501         * <p>
502         * This implementation creates a new HashEntry instance.
503         * Subclasses can override this to return a different storage class,
504         * or implement caching.
505         * 
506         * @param next  the next entry in sequence
507         * @param hashCode  the hash code to use
508         * @param key  the key to store
509         * @param value  the value to store
510         * @return the newly created entry
511         */
512        protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
513            return new HashEntry(next, hashCode, key, value);
514        }
515        
516        /**
517         * Adds an entry into this map.
518         * <p>
519         * This implementation adds the entry to the data storage table.
520         * Subclasses could override to handle changes to the map.
521         *
522         * @param entry  the entry to add
523         * @param hashIndex  the index into the data array to store at
524         */
525        protected void addEntry(HashEntry entry, int hashIndex) {
526            data[hashIndex] = entry;
527        }
528        
529        //-----------------------------------------------------------------------
530        /**
531         * Removes a mapping from the map.
532         * <p>
533         * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
534         * It also handles changes to <code>modCount</code> and <code>size</code>.
535         * Subclasses could override to fully control removals from the map.
536         * 
537         * @param entry  the entry to remove
538         * @param hashIndex  the index into the data structure
539         * @param previous  the previous entry in the chain
540         */
541        protected void removeMapping(HashEntry entry, int hashIndex, HashEntry previous) {
542            modCount++;
543            removeEntry(entry, hashIndex, previous);
544            size--;
545            destroyEntry(entry);
546        }
547        
548        /**
549         * Removes an entry from the chain stored in a particular index.
550         * <p>
551         * This implementation removes the entry from the data storage table.
552         * The size is not updated.
553         * Subclasses could override to handle changes to the map.
554         * 
555         * @param entry  the entry to remove
556         * @param hashIndex  the index into the data structure
557         * @param previous  the previous entry in the chain
558         */
559        protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
560            if (previous == null) {
561                data[hashIndex] = entry.next;
562            } else {
563                previous.next = entry.next;
564            }
565        }
566        
567        /**
568         * Kills an entry ready for the garbage collector.
569         * <p>
570         * This implementation prepares the HashEntry for garbage collection.
571         * Subclasses can override this to implement caching (override clear as well).
572         * 
573         * @param entry  the entry to destroy
574         */
575        protected void destroyEntry(HashEntry entry) {
576            entry.next = null;
577            entry.key = null;
578            entry.value = null;
579        }
580        
581        //-----------------------------------------------------------------------
582        /**
583         * Checks the capacity of the map and enlarges it if necessary.
584         * <p>
585         * This implementation uses the threshold to check if the map needs enlarging
586         */
587        protected void checkCapacity() {
588            if (size >= threshold) {
589                int newCapacity = data.length * 2;
590                if (newCapacity <= MAXIMUM_CAPACITY) {
591                    ensureCapacity(newCapacity);
592                }
593            }
594        }
595        
596        /**
597         * Changes the size of the data structure to the capacity proposed.
598         * 
599         * @param newCapacity  the new capacity of the array (a power of two, less or equal to max)
600         */
601        protected void ensureCapacity(int newCapacity) {
602            int oldCapacity = data.length;
603            if (newCapacity <= oldCapacity) {
604                return;
605            }
606            if (size == 0) {
607                threshold = calculateThreshold(newCapacity, loadFactor);
608                data = new HashEntry[newCapacity];
609            } else {
610                HashEntry oldEntries[] = data;
611                HashEntry newEntries[] = new HashEntry[newCapacity];
612    
613                modCount++;
614                for (int i = oldCapacity - 1; i >= 0; i--) {
615                    HashEntry entry = oldEntries[i];
616                    if (entry != null) {
617                        oldEntries[i] = null;  // gc
618                        do {
619                            HashEntry next = entry.next;
620                            int index = hashIndex(entry.hashCode, newCapacity);  
621                            entry.next = newEntries[index];
622                            newEntries[index] = entry;
623                            entry = next;
624                        } while (entry != null);
625                    }
626                }
627                threshold = calculateThreshold(newCapacity, loadFactor);
628                data = newEntries;
629            }
630        }
631    
632        /**
633         * Calculates the new capacity of the map.
634         * This implementation normalizes the capacity to a power of two.
635         * 
636         * @param proposedCapacity  the proposed capacity
637         * @return the normalized new capacity
638         */
639        protected int calculateNewCapacity(int proposedCapacity) {
640            int newCapacity = 1;
641            if (proposedCapacity > MAXIMUM_CAPACITY) {
642                newCapacity = MAXIMUM_CAPACITY;
643            } else {
644                while (newCapacity < proposedCapacity) {
645                    newCapacity <<= 1;  // multiply by two
646                }
647                if (newCapacity > MAXIMUM_CAPACITY) {
648                    newCapacity = MAXIMUM_CAPACITY;
649                }
650            }
651            return newCapacity;
652        }
653        
654        /**
655         * Calculates the new threshold of the map, where it will be resized.
656         * This implementation uses the load factor.
657         * 
658         * @param newCapacity  the new capacity
659         * @param factor  the load factor
660         * @return the new resize threshold
661         */
662        protected int calculateThreshold(int newCapacity, float factor) {
663            return (int) (newCapacity * factor);
664        }
665        
666        //-----------------------------------------------------------------------
667        /**
668         * Gets the <code>next</code> field from a <code>HashEntry</code>.
669         * Used in subclasses that have no visibility of the field.
670         * 
671         * @param entry  the entry to query, must not be null
672         * @return the <code>next</code> field of the entry
673         * @throws NullPointerException if the entry is null
674         * @since Commons Collections 3.1
675         */
676        protected HashEntry entryNext(HashEntry entry) {
677            return entry.next;
678        }
679        
680        /**
681         * Gets the <code>hashCode</code> field from a <code>HashEntry</code>.
682         * Used in subclasses that have no visibility of the field.
683         * 
684         * @param entry  the entry to query, must not be null
685         * @return the <code>hashCode</code> field of the entry
686         * @throws NullPointerException if the entry is null
687         * @since Commons Collections 3.1
688         */
689        protected int entryHashCode(HashEntry entry) {
690            return entry.hashCode;
691        }
692        
693        /**
694         * Gets the <code>key</code> field from a <code>HashEntry</code>.
695         * Used in subclasses that have no visibility of the field.
696         * 
697         * @param entry  the entry to query, must not be null
698         * @return the <code>key</code> field of the entry
699         * @throws NullPointerException if the entry is null
700         * @since Commons Collections 3.1
701         */
702        protected Object entryKey(HashEntry entry) {
703            return entry.key;
704        }
705        
706        /**
707         * Gets the <code>value</code> field from a <code>HashEntry</code>.
708         * Used in subclasses that have no visibility of the field.
709         * 
710         * @param entry  the entry to query, must not be null
711         * @return the <code>value</code> field of the entry
712         * @throws NullPointerException if the entry is null
713         * @since Commons Collections 3.1
714         */
715        protected Object entryValue(HashEntry entry) {
716            return entry.value;
717        }
718        
719        //-----------------------------------------------------------------------
720        /**
721         * Gets an iterator over the map.
722         * Changes made to the iterator affect this map.
723         * <p>
724         * A MapIterator returns the keys in the map. It also provides convenient
725         * methods to get the key and value, and set the value.
726         * It avoids the need to create an entrySet/keySet/values object.
727         * It also avoids creating the Map.Entry object.
728         * 
729         * @return the map iterator
730         */
731        public MapIterator mapIterator() {
732            if (size == 0) {
733                return EmptyMapIterator.INSTANCE;
734            }
735            return new HashMapIterator(this);
736        }
737    
738        /**
739         * MapIterator implementation.
740         */
741        protected static class HashMapIterator extends HashIterator implements MapIterator {
742            
743            protected HashMapIterator(AbstractHashedMap parent) {
744                super(parent);
745            }
746    
747            public Object next() {
748                return super.nextEntry().getKey();
749            }
750    
751            public Object getKey() {
752                HashEntry current = currentEntry();
753                if (current == null) {
754                    throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
755                }
756                return current.getKey();
757            }
758    
759            public Object getValue() {
760                HashEntry current = currentEntry();
761                if (current == null) {
762                    throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
763                }
764                return current.getValue();
765            }
766    
767            public Object setValue(Object value) {
768                HashEntry current = currentEntry();
769                if (current == null) {
770                    throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
771                }
772                return current.setValue(value);
773            }
774        }
775        
776        //-----------------------------------------------------------------------    
777        /**
778         * Gets the entrySet view of the map.
779         * Changes made to the view affect this map.
780         * To simply iterate through the entries, use {@link #mapIterator()}.
781         * 
782         * @return the entrySet view
783         */
784        public Set entrySet() {
785            if (entrySet == null) {
786                entrySet = new EntrySet(this);
787            }
788            return entrySet;
789        }
790        
791        /**
792         * Creates an entry set iterator.
793         * Subclasses can override this to return iterators with different properties.
794         * 
795         * @return the entrySet iterator
796         */
797        protected Iterator createEntrySetIterator() {
798            if (size() == 0) {
799                return EmptyIterator.INSTANCE;
800            }
801            return new EntrySetIterator(this);
802        }
803    
804        /**
805         * EntrySet implementation.
806         */
807        protected static class EntrySet extends AbstractSet {
808            /** The parent map */
809            protected final AbstractHashedMap parent;
810            
811            protected EntrySet(AbstractHashedMap parent) {
812                super();
813                this.parent = parent;
814            }
815    
816            public int size() {
817                return parent.size();
818            }
819            
820            public void clear() {
821                parent.clear();
822            }
823            
824            public boolean contains(Object entry) {
825                if (entry instanceof Map.Entry) {
826                    Map.Entry e = (Map.Entry) entry;
827                    Entry match = parent.getEntry(e.getKey());
828                    return (match != null && match.equals(e));
829                }
830                return false;
831            }
832            
833            public boolean remove(Object obj) {
834                if (obj instanceof Map.Entry == false) {
835                    return false;
836                }
837                if (contains(obj) == false) {
838                    return false;
839                }
840                Map.Entry entry = (Map.Entry) obj;
841                Object key = entry.getKey();
842                parent.remove(key);
843                return true;
844            }
845    
846            public Iterator iterator() {
847                return parent.createEntrySetIterator();
848            }
849        }
850    
851        /**
852         * EntrySet iterator.
853         */
854        protected static class EntrySetIterator extends HashIterator {
855            
856            protected EntrySetIterator(AbstractHashedMap parent) {
857                super(parent);
858            }
859    
860            public Object next() {
861                return super.nextEntry();
862            }
863        }
864    
865        //-----------------------------------------------------------------------    
866        /**
867         * Gets the keySet view of the map.
868         * Changes made to the view affect this map.
869         * To simply iterate through the keys, use {@link #mapIterator()}.
870         * 
871         * @return the keySet view
872         */
873        public Set keySet() {
874            if (keySet == null) {
875                keySet = new KeySet(this);
876            }
877            return keySet;
878        }
879    
880        /**
881         * Creates a key set iterator.
882         * Subclasses can override this to return iterators with different properties.
883         * 
884         * @return the keySet iterator
885         */
886        protected Iterator createKeySetIterator() {
887            if (size() == 0) {
888                return EmptyIterator.INSTANCE;
889            }
890            return new KeySetIterator(this);
891        }
892    
893        /**
894         * KeySet implementation.
895         */
896        protected static class KeySet extends AbstractSet {
897            /** The parent map */
898            protected final AbstractHashedMap parent;
899            
900            protected KeySet(AbstractHashedMap parent) {
901                super();
902                this.parent = parent;
903            }
904    
905            public int size() {
906                return parent.size();
907            }
908            
909            public void clear() {
910                parent.clear();
911            }
912            
913            public boolean contains(Object key) {
914                return parent.containsKey(key);
915            }
916            
917            public boolean remove(Object key) {
918                boolean result = parent.containsKey(key);
919                parent.remove(key);
920                return result;
921            }
922    
923            public Iterator iterator() {
924                return parent.createKeySetIterator();
925            }
926        }
927    
928        /**
929         * KeySet iterator.
930         */
931        protected static class KeySetIterator extends EntrySetIterator {
932            
933            protected KeySetIterator(AbstractHashedMap parent) {
934                super(parent);
935            }
936    
937            public Object next() {
938                return super.nextEntry().getKey();
939            }
940        }
941        
942        //-----------------------------------------------------------------------    
943        /**
944         * Gets the values view of the map.
945         * Changes made to the view affect this map.
946         * To simply iterate through the values, use {@link #mapIterator()}.
947         * 
948         * @return the values view
949         */
950        public Collection values() {
951            if (values == null) {
952                values = new Values(this);
953            }
954            return values;
955        }
956    
957        /**
958         * Creates a values iterator.
959         * Subclasses can override this to return iterators with different properties.
960         * 
961         * @return the values iterator
962         */
963        protected Iterator createValuesIterator() {
964            if (size() == 0) {
965                return EmptyIterator.INSTANCE;
966            }
967            return new ValuesIterator(this);
968        }
969    
970        /**
971         * Values implementation.
972         */
973        protected static class Values extends AbstractCollection {
974            /** The parent map */
975            protected final AbstractHashedMap parent;
976            
977            protected Values(AbstractHashedMap parent) {
978                super();
979                this.parent = parent;
980            }
981    
982            public int size() {
983                return parent.size();
984            }
985            
986            public void clear() {
987                parent.clear();
988            }
989            
990            public boolean contains(Object value) {
991                return parent.containsValue(value);
992            }
993            
994            public Iterator iterator() {
995                return parent.createValuesIterator();
996            }
997        }
998    
999        /**
1000         * Values iterator.
1001         */
1002        protected static class ValuesIterator extends HashIterator {
1003            
1004            protected ValuesIterator(AbstractHashedMap parent) {
1005                super(parent);
1006            }
1007    
1008            public Object next() {
1009                return super.nextEntry().getValue();
1010            }
1011        }
1012        
1013        //-----------------------------------------------------------------------
1014        /**
1015         * HashEntry used to store the data.
1016         * <p>
1017         * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code>
1018         * then you will not be able to access the protected fields.
1019         * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> exist
1020         * to provide the necessary access.
1021         */
1022        protected static class HashEntry implements Map.Entry, KeyValue {
1023            /** The next entry in the hash chain */
1024            protected HashEntry next;
1025            /** The hash code of the key */
1026            protected int hashCode;
1027            /** The key */
1028            protected Object key;
1029            /** The value */
1030            protected Object value;
1031            
1032            protected HashEntry(HashEntry next, int hashCode, Object key, Object value) {
1033                super();
1034                this.next = next;
1035                this.hashCode = hashCode;
1036                this.key = key;
1037                this.value = value;
1038            }
1039            
1040            public Object getKey() {
1041                return (key == NULL ? null : key);
1042            }
1043            
1044            public Object getValue() {
1045                return value;
1046            }
1047            
1048            public Object setValue(Object value) {
1049                Object old = this.value;
1050                this.value = value;
1051                return old;
1052            }
1053            
1054            public boolean equals(Object obj) {
1055                if (obj == this) {
1056                    return true;
1057                }
1058                if (obj instanceof Map.Entry == false) {
1059                    return false;
1060                }
1061                Map.Entry other = (Map.Entry) obj;
1062                return
1063                    (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
1064                    (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
1065            }
1066            
1067            public int hashCode() {
1068                return (getKey() == null ? 0 : getKey().hashCode()) ^
1069                       (getValue() == null ? 0 : getValue().hashCode()); 
1070            }
1071            
1072            public String toString() {
1073                return new StringBuffer().append(getKey()).append('=').append(getValue()).toString();
1074            }
1075        }
1076        
1077        /**
1078         * Base Iterator
1079         */
1080        protected static abstract class HashIterator implements Iterator {
1081            
1082            /** The parent map */
1083            protected final AbstractHashedMap parent;
1084            /** The current index into the array of buckets */
1085            protected int hashIndex;
1086            /** The last returned entry */
1087            protected HashEntry last;
1088            /** The next entry */
1089            protected HashEntry next;
1090            /** The modification count expected */
1091            protected int expectedModCount;
1092            
1093            protected HashIterator(AbstractHashedMap parent) {
1094                super();
1095                this.parent = parent;
1096                HashEntry[] data = parent.data;
1097                int i = data.length;
1098                HashEntry next = null;
1099                while (i > 0 && next == null) {
1100                    next = data[--i];
1101                }
1102                this.next = next;
1103                this.hashIndex = i;
1104                this.expectedModCount = parent.modCount;
1105            }
1106    
1107            public boolean hasNext() {
1108                return (next != null);
1109            }
1110    
1111            protected HashEntry nextEntry() { 
1112                if (parent.modCount != expectedModCount) {
1113                    throw new ConcurrentModificationException();
1114                }
1115                HashEntry newCurrent = next;
1116                if (newCurrent == null)  {
1117                    throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
1118                }
1119                HashEntry[] data = parent.data;
1120                int i = hashIndex;
1121                HashEntry n = newCurrent.next;
1122                while (n == null && i > 0) {
1123                    n = data[--i];
1124                }
1125                next = n;
1126                hashIndex = i;
1127                last = newCurrent;
1128                return newCurrent;
1129            }
1130    
1131            protected HashEntry currentEntry() {
1132                return last;
1133            }
1134            
1135            public void remove() {
1136                if (last == null) {
1137                    throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
1138                }
1139                if (parent.modCount != expectedModCount) {
1140                    throw new ConcurrentModificationException();
1141                }
1142                parent.remove(last.getKey());
1143                last = null;
1144                expectedModCount = parent.modCount;
1145            }
1146    
1147            public String toString() {
1148                if (last != null) {
1149                    return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
1150                } else {
1151                    return "Iterator[]";
1152                }
1153            }
1154        }
1155        
1156        //-----------------------------------------------------------------------
1157        /**
1158         * Writes the map data to the stream. This method must be overridden if a
1159         * subclass must be setup before <code>put()</code> is used.
1160         * <p>
1161         * Serialization is not one of the JDK's nicest topics. Normal serialization will
1162         * initialise the superclass before the subclass. Sometimes however, this isn't
1163         * what you want, as in this case the <code>put()</code> method on read can be
1164         * affected by subclass state.
1165         * <p>
1166         * The solution adopted here is to serialize the state data of this class in
1167         * this protected method. This method must be called by the
1168         * <code>writeObject()</code> of the first serializable subclass.
1169         * <p>
1170         * Subclasses may override if they have a specific field that must be present
1171         * on read before this implementation will work. Generally, the read determines
1172         * what must be serialized here, if anything.
1173         * 
1174         * @param out  the output stream
1175         */
1176        protected void doWriteObject(ObjectOutputStream out) throws IOException {
1177            out.writeFloat(loadFactor);
1178            out.writeInt(data.length);
1179            out.writeInt(size);
1180            for (MapIterator it = mapIterator(); it.hasNext();) {
1181                out.writeObject(it.next());
1182                out.writeObject(it.getValue());
1183            }
1184        }
1185    
1186        /**
1187         * Reads the map data from the stream. This method must be overridden if a
1188         * subclass must be setup before <code>put()</code> is used.
1189         * <p>
1190         * Serialization is not one of the JDK's nicest topics. Normal serialization will
1191         * initialise the superclass before the subclass. Sometimes however, this isn't
1192         * what you want, as in this case the <code>put()</code> method on read can be
1193         * affected by subclass state.
1194         * <p>
1195         * The solution adopted here is to deserialize the state data of this class in
1196         * this protected method. This method must be called by the
1197         * <code>readObject()</code> of the first serializable subclass.
1198         * <p>
1199         * Subclasses may override if the subclass has a specific field that must be present
1200         * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
1201         * 
1202         * @param in  the input stream
1203         */
1204        protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
1205            loadFactor = in.readFloat();
1206            int capacity = in.readInt();
1207            int size = in.readInt();
1208            init();
1209            threshold = calculateThreshold(capacity, loadFactor);
1210            data = new HashEntry[capacity];
1211            for (int i = 0; i < size; i++) {
1212                Object key = in.readObject();
1213                Object value = in.readObject();
1214                put(key, value);
1215            }
1216        }
1217        
1218        //-----------------------------------------------------------------------
1219        /**
1220         * Clones the map without cloning the keys or values.
1221         * <p>
1222         * To implement <code>clone()</code>, a subclass must implement the
1223         * <code>Cloneable</code> interface and make this method public.
1224         *
1225         * @return a shallow clone
1226         */
1227        protected Object clone() {
1228            try {
1229                AbstractHashedMap cloned = (AbstractHashedMap) super.clone();
1230                cloned.data = new HashEntry[data.length];
1231                cloned.entrySet = null;
1232                cloned.keySet = null;
1233                cloned.values = null;
1234                cloned.modCount = 0;
1235                cloned.size = 0;
1236                cloned.init();
1237                cloned.putAll(this);
1238                return cloned;
1239                
1240            } catch (CloneNotSupportedException ex) {
1241                return null;  // should never happen
1242            }
1243        }
1244        
1245        /**
1246         * Compares this map with another.
1247         * 
1248         * @param obj  the object to compare to
1249         * @return true if equal
1250         */
1251        public boolean equals(Object obj) {
1252            if (obj == this) {
1253                return true;
1254            }
1255            if (obj instanceof Map == false) {
1256                return false;
1257            }
1258            Map map = (Map) obj;
1259            if (map.size() != size()) {
1260                return false;
1261            }
1262            MapIterator it = mapIterator();
1263            try {
1264                while (it.hasNext()) {
1265                    Object key = it.next();
1266                    Object value = it.getValue();
1267                    if (value == null) {
1268                        if (map.get(key) != null || map.containsKey(key) == false) {
1269                            return false;
1270                        }
1271                    } else {
1272                        if (value.equals(map.get(key)) == false) {
1273                            return false;
1274                        }
1275                    }
1276                }
1277            } catch (ClassCastException ignored)   {
1278                return false;
1279            } catch (NullPointerException ignored) {
1280                return false;
1281            }
1282            return true;
1283        }
1284    
1285        /**
1286         * Gets the standard Map hashCode.
1287         * 
1288         * @return the hash code defined in the Map interface
1289         */
1290        public int hashCode() {
1291            int total = 0;
1292            Iterator it = createEntrySetIterator();
1293            while (it.hasNext()) {
1294                total += it.next().hashCode();
1295            }
1296            return total;
1297        }
1298    
1299        /**
1300         * Gets the map as a String.
1301         * 
1302         * @return a string version of the map
1303         */
1304        public String toString() {
1305            if (size() == 0) {
1306                return "{}";
1307            }
1308            StringBuffer buf = new StringBuffer(32 * size());
1309            buf.append('{');
1310    
1311            MapIterator it = mapIterator();
1312            boolean hasNext = it.hasNext();
1313            while (hasNext) {
1314                Object key = it.next();
1315                Object value = it.getValue();
1316                buf.append(key == this ? "(this Map)" : key)
1317                   .append('=')
1318                   .append(value == this ? "(this Map)" : value);
1319    
1320                hasNext = it.hasNext();
1321                if (hasNext) {
1322                    buf.append(',').append(' ');
1323                }
1324            }
1325    
1326            buf.append('}');
1327            return buf.toString();
1328        }
1329    }