Source code

001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.wicket.util.collections;
018
019import java.io.IOException;
020import java.io.Serializable;
021import java.util.AbstractCollection;
022import java.util.AbstractSet;
023import java.util.Collection;
024import java.util.ConcurrentModificationException;
025import java.util.Iterator;
026import java.util.NoSuchElementException;
027import java.util.Set;
028import java.util.concurrent.atomic.AtomicInteger;
029
030/**
031 * This is an integer hashmap that has the exact same features and interface as a normal Map except
032 * that the key is directly an integer. So no hash is calculated or key object is stored.
033 * 
034 * @author jcompagner
035 * 
036 * @param <V>
037 *            The value in the map
038 */
039public class IntHashMap<V> implements Cloneable, Serializable
040{
041        transient volatile Set<Integer> keySet = null;
042
043        transient volatile Collection<V> values = null;
044
045        /**
046         * The default initial capacity - MUST be a power of two.
047         */
048        static final int DEFAULT_INITIAL_CAPACITY = 16;
049
050        /**
051         * The maximum capacity, used if a higher value is implicitly specified by either of the
052         * constructors with arguments. MUST be a power of two <= 1<<30.
053         */
054        static final int MAXIMUM_CAPACITY = 1 << 30;
055
056        /**
057         * The load factor used when none specified in constructor.
058         */
059        static final float DEFAULT_LOAD_FACTOR = 0.75f;
060
061        /**
062         * The table, resized as necessary. Length MUST Always be a power of two.
063         */
064        transient Entry<V>[] table;
065
066        /**
067         * The number of key-value mappings contained in this identity hash map.
068         */
069        transient int size;
070
071        /**
072         * The next size value at which to resize (capacity * load factor).
073         * 
074         * @serial
075         */
076        int threshold;
077
078        /**
079         * The load factor for the hash table.
080         * 
081         * @serial
082         */
083        final float loadFactor;
084
085        /**
086         * The number of times this HashMap has been structurally modified Structural modifications are
087         * those that change the number of mappings in the HashMap or otherwise modify its internal
088         * structure (e.g., rehash). This field is used to make iterators on Collection-views of the
089         * HashMap fail-fast. (See ConcurrentModificationException).
090         */
091        transient AtomicInteger modCount = new AtomicInteger(0);
092
093        /**
094         * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and load factor.
095         * 
096         * @param initialCapacity
097         *            The initial capacity.
098         * @param loadFactor
099         *            The load factor.
100         * @throws IllegalArgumentException
101         *             if the initial capacity is negative or the load factor is nonpositive.
102         */
103        @SuppressWarnings("unchecked")
104        public IntHashMap(int initialCapacity, final float loadFactor)
105        {
106                if (initialCapacity < 0)
107                {
108                        throw new IllegalArgumentException("Illegal initial capacity: " + //$NON-NLS-1$
109                                initialCapacity);
110                }
111                if (initialCapacity > MAXIMUM_CAPACITY)
112                {
113                        initialCapacity = MAXIMUM_CAPACITY;
114                }
115                if ((loadFactor <= 0) || Float.isNaN(loadFactor))
116                {
117                        throw new IllegalArgumentException("Illegal load factor: " + //$NON-NLS-1$
118                                loadFactor);
119                }
120
121                // Find a power of 2 >= initialCapacity
122                int capacity = 1;
123                while (capacity < initialCapacity)
124                {
125                        capacity <<= 1;
126                }
127
128                this.loadFactor = loadFactor;
129                threshold = (int)(capacity * loadFactor);
130                table = new Entry[capacity];
131                init();
132        }
133
134        /**
135         * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and the default load
136         * factor (0.75).
137         * 
138         * @param initialCapacity
139         *            the initial capacity.
140         * @throws IllegalArgumentException
141         *             if the initial capacity is negative.
142         */
143        public IntHashMap(final int initialCapacity)
144        {
145                this(initialCapacity, DEFAULT_LOAD_FACTOR);
146        }
147
148        /**
149         * Constructs an empty <tt>HashMap</tt> with the default initial capacity (16) and the default
150         * load factor (0.75).
151         */
152        @SuppressWarnings("unchecked")
153        public IntHashMap()
154        {
155                loadFactor = DEFAULT_LOAD_FACTOR;
156                threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
157                table = new Entry[DEFAULT_INITIAL_CAPACITY];
158                init();
159        }
160
161        // internal utilities
162
163        /**
164         * Initialization hook for subclasses. This method is called in all constructors and
165         * pseudo-constructors (clone, readObject) after HashMap has been initialized but before any
166         * entries have been inserted. (In the absence of this method, readObject would require explicit
167         * knowledge of subclasses.)
168         */
169        void init()
170        {
171        }
172
173        /**
174         * Returns index for hash code h.
175         * 
176         * @param h
177         * @param length
178         * @return The index for the hash integer for the given length
179         */
180        static int indexFor(final int h, final int length)
181        {
182                return h & (length - 1);
183        }
184
185        /**
186         * Returns the number of key-value mappings in this map.
187         * 
188         * @return the number of key-value mappings in this map.
189         */
190        public int size()
191        {
192                return size;
193        }
194
195        /**
196         * Returns <tt>true</tt> if this map contains no key-value mappings.
197         * 
198         * @return <tt>true</tt> if this map contains no key-value mappings.
199         */
200        public boolean isEmpty()
201        {
202                return size == 0;
203        }
204
205        /**
206         * Returns the value to which the specified key is mapped in this identity hash map, or
207         * <tt>null</tt> if the map contains no mapping for this key. A return value of <tt>null</tt>
208         * does not <i>necessarily</i> indicate that the map contains no mapping for the key; it is also
209         * possible that the map explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
210         * method may be used to distinguish these two cases.
211         * 
212         * @param key
213         *            the key whose associated value is to be returned.
214         * @return the value to which this map maps the specified key, or <tt>null</tt> if the map
215         *         contains no mapping for this key.
216         * @see #put(int, Object)
217         */
218        public V get(final int key)
219        {
220                int i = indexFor(key, table.length);
221                Entry<V> e = table[i];
222                while (true)
223                {
224                        if (e == null)
225                        {
226                                return null;
227                        }
228                        if (key == e.key)
229                        {
230                                return e.value;
231                        }
232                        e = e.next;
233                }
234        }
235
236        /**
237         * Returns <tt>true</tt> if this map contains a mapping for the specified key.
238         * 
239         * @param key
240         *            The key whose presence in this map is to be tested
241         * @return <tt>true</tt> if this map contains a mapping for the specified key.
242         */
243        public boolean containsKey(final int key)
244        {
245                int i = indexFor(key, table.length);
246                Entry<V> e = table[i];
247                while (e != null)
248                {
249                        if (key == e.key)
250                        {
251                                return true;
252                        }
253                        e = e.next;
254                }
255                return false;
256        }
257
258        /**
259         * Returns the entry associated with the specified key in the HashMap. Returns null if the
260         * HashMap contains no mapping for this key.
261         * 
262         * @param key
263         * @return The Entry object for the given hash key
264         */
265        Entry<V> getEntry(final int key)
266        {
267                int i = indexFor(key, table.length);
268                Entry<V> e = table[i];
269                while ((e != null) && !(key == e.key))
270                {
271                        e = e.next;
272                }
273                return e;
274        }
275
276        /**
277         * Associates the specified value with the specified key in this map. If the map previously
278         * contained a mapping for this key, the old value is replaced.
279         * 
280         * @param key
281         *            key with which the specified value is to be associated.
282         * @param value
283         *            value to be associated with the specified key.
284         * @return previous value associated with specified key, or <tt>null</tt> if there was no
285         *         mapping for key. A <tt>null</tt> return can also indicate that the HashMap previously
286         *         associated <tt>null</tt> with the specified key.
287         */
288        public V put(final int key, final V value)
289        {
290                int i = indexFor(key, table.length);
291
292                for (Entry<V> e = table[i]; e != null; e = e.next)
293                {
294                        if (key == e.key)
295                        {
296                                V oldValue = e.value;
297                                e.value = value;
298                                return oldValue;
299                        }
300                }
301
302                modCount.incrementAndGet();
303                addEntry(key, value, i);
304                return null;
305        }
306
307        /**
308         * This method is used instead of put by constructors and pseudoconstructors (clone,
309         * readObject). It does not resize the table, check for comodification, etc. It calls
310         * createEntry rather than addEntry.
311         * 
312         * @param key
313         * @param value
314         */
315        private void putForCreate(final int key, final V value)
316        {
317                int i = indexFor(key, table.length);
318
319                /**
320                 * Look for preexisting entry for key. This will never happen for clone or deserialize. It
321                 * will only happen for construction if the input Map is a sorted map whose ordering is
322                 * inconsistent w/ equals.
323                 */
324                for (Entry<V> e = table[i]; e != null; e = e.next)
325                {
326                        if (key == e.key)
327                        {
328                                e.value = value;
329                                return;
330                        }
331                }
332
333                createEntry(key, value, i);
334        }
335
336        void putAllForCreate(final IntHashMap<V> m)
337        {
338                for (Entry<V> entry : m.entrySet())
339                {
340                        putForCreate(entry.getKey(), entry.getValue());
341                }
342        }
343
344        /**
345         * Rehashes the contents of this map into a new array with a larger capacity. This method is
346         * called automatically when the number of keys in this map reaches its threshold.
347         * 
348         * If current capacity is MAXIMUM_CAPACITY, this method does not resize the map, but but sets
349         * threshold to Integer.MAX_VALUE. This has the effect of preventing future calls.
350         * 
351         * @param newCapacity
352         *            the new capacity, MUST be a power of two; must be greater than current capacity
353         *            unless current capacity is MAXIMUM_CAPACITY (in which case value is irrelevant).
354         */
355        @SuppressWarnings("unchecked")
356        void resize(final int newCapacity)
357        {
358                Entry<V>[] oldTable = table;
359                int oldCapacity = oldTable.length;
360                if (oldCapacity == MAXIMUM_CAPACITY)
361                {
362                        threshold = Integer.MAX_VALUE;
363                        return;
364                }
365
366                Entry<V>[] newTable = new Entry[newCapacity];
367                transfer(newTable);
368                table = newTable;
369                threshold = (int)(newCapacity * loadFactor);
370        }
371
372        /**
373         * Transfer all entries from current table to newTable.
374         * 
375         * @param newTable
376         */
377        void transfer(final Entry<V>[] newTable)
378        {
379                Entry<V>[] src = table;
380                int newCapacity = newTable.length;
381                for (int j = 0; j < src.length; j++)
382                {
383                        Entry<V> e = src[j];
384                        if (e != null)
385                        {
386                                src[j] = null;
387                                do
388                                {
389                                        Entry<V> next = e.next;
390                                        int i = indexFor(e.key, newCapacity);
391                                        e.next = newTable[i];
392                                        newTable[i] = e;
393                                        e = next;
394                                }
395                                while (e != null);
396                        }
397                }
398        }
399
400        /**
401         * Copies all of the mappings from the specified map to this map These mappings will replace any
402         * mappings that this map had for any of the keys currently in the specified map.
403         * 
404         * @param m
405         *            mappings to be stored in this map.
406         * @throws NullPointerException
407         *             if the specified map is null.
408         */
409        public void putAll(final IntHashMap<V> m)
410        {
411                int numKeysToBeAdded = m.size();
412                if (numKeysToBeAdded == 0)
413                {
414                        return;
415                }
416
417                /*
418                 * Expand the map if the map if the number of mappings to be added is greater than or equal
419                 * to threshold. This is conservative; the obvious condition is (m.size() + size) >=
420                 * threshold, but this condition could result in a map with twice the appropriate capacity,
421                 * if the keys to be added overlap with the keys already in this map. By using the
422                 * conservative calculation, we subject ourself to at most one extra resize.
423                 */
424                if (numKeysToBeAdded > threshold)
425                {
426                        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
427                        if (targetCapacity > MAXIMUM_CAPACITY)
428                        {
429                                targetCapacity = MAXIMUM_CAPACITY;
430                        }
431                        int newCapacity = table.length;
432                        while (newCapacity < targetCapacity)
433                        {
434                                newCapacity <<= 1;
435                        }
436                        if (newCapacity > table.length)
437                        {
438                                resize(newCapacity);
439                        }
440                }
441
442                for (Entry<V> entry : m.entrySet())
443                {
444                        put(entry.getKey(), entry.getValue());
445                }
446        }
447
448        /**
449         * Removes the mapping for this key from this map if present.
450         * 
451         * @param key
452         *            key whose mapping is to be removed from the map.
453         * @return previous value associated with specified key, or <tt>null</tt> if there was no
454         *         mapping for key. A <tt>null</tt> return can also indicate that the map previously
455         *         associated <tt>null</tt> with the specified key.
456         */
457        public V remove(final int key)
458        {
459                Entry<V> e = removeEntryForKey(key);
460                return (e == null ? null : e.value);
461        }
462
463        /**
464         * Removes and returns the entry associated with the specified key in the HashMap. Returns null
465         * if the HashMap contains no mapping for this key.
466         * 
467         * @param key
468         * @return The Entry object that was removed
469         */
470        Entry<V> removeEntryForKey(final int key)
471        {
472                int i = indexFor(key, table.length);
473                Entry<V> prev = table[i];
474                Entry<V> e = prev;
475
476                while (e != null)
477                {
478                        Entry<V> next = e.next;
479                        if (key == e.key)
480                        {
481                                modCount.incrementAndGet();
482                                size--;
483                                if (prev == e)
484                                {
485                                        table[i] = next;
486                                }
487                                else
488                                {
489                                        prev.next = next;
490                                }
491                                return e;
492                        }
493                        prev = e;
494                        e = next;
495                }
496
497                return e;
498        }
499
500        /**
501         * Special version of remove for EntrySet.
502         * 
503         * @param o
504         * @return The entry that was removed
505         */
506        @SuppressWarnings("unchecked")
507        Entry<V> removeMapping(final Object o)
508        {
509                if (!(o instanceof Entry))
510                {
511                        return null;
512                }
513
514                Entry<V> entry = (Entry<V>)o;
515                int key = entry.getKey();
516                int i = indexFor(key, table.length);
517                Entry<V> prev = table[i];
518                Entry<V> e = prev;
519
520                while (e != null)
521                {
522                        Entry<V> next = e.next;
523                        if ((e.key == key) && e.equals(entry))
524                        {
525                                modCount.incrementAndGet();
526                                size--;
527                                if (prev == e)
528                                {
529                                        table[i] = next;
530                                }
531                                else
532                                {
533                                        prev.next = next;
534                                }
535                                return e;
536                        }
537                        prev = e;
538                        e = next;
539                }
540
541                return e;
542        }
543
544        /**
545         * Removes all mappings from this map.
546         */
547        public void clear()
548        {
549                modCount.incrementAndGet();
550                Entry<V> tab[] = table;
551                for (int i = 0; i < tab.length; i++)
552                {
553                        tab[i] = null;
554                }
555                size = 0;
556        }
557
558        /**
559         * Returns <tt>true</tt> if this map maps one or more keys to the specified value.
560         * 
561         * @param value
562         *            value whose presence in this map is to be tested.
563         * @return <tt>true</tt> if this map maps one or more keys to the specified value.
564         */
565        public boolean containsValue(final Object value)
566        {
567                if (value == null)
568                {
569                        return containsNullValue();
570                }
571
572                for (Entry<V> entry : table)
573                {
574                        for (Entry<V> e = entry; e != null; e = e.next)
575                        {
576                                if (value.equals(e.value))
577                                {
578                                        return true;
579                                }
580                        }
581                }
582                return false;
583        }
584
585        /**
586         * Special-case code for containsValue with null argument
587         * 
588         * @return boolean true if there is a null value in this map
589         */
590        private boolean containsNullValue()
591        {
592                Entry<V> tab[] = table;
593                for (Entry<V> tabEntry : tab)
594                {
595                        for (Entry<V> e = tabEntry; e != null; e = e.next)
596                        {
597                                if (e.value == null)
598                                {
599                                        return true;
600                                }
601                        }
602                }
603                return false;
604        }
605
606        /**
607         * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and values themselves are
608         * not cloned.
609         * 
610         * @return a shallow copy of this map.
611         */
612        @SuppressWarnings("unchecked")
613        @Override
614        public Object clone() throws CloneNotSupportedException
615        {
616                IntHashMap<V> result = null;
617                try
618                {
619                        result = (IntHashMap<V>)super.clone();
620                        result.table = new Entry[table.length];
621                        result.entrySet = null;
622                        result.modCount.set(0);
623                        result.size = 0;
624                        result.init();
625                        result.putAllForCreate(this);
626                }
627                catch (CloneNotSupportedException e)
628                {
629                        // assert false;
630                }
631                return result;
632        }
633
634        /**
635         * @author jcompagner
636         * @param <V>
637         *            type of value object
638         */
639        public static class Entry<V>
640        {
641                final int key;
642                V value;
643                Entry<V> next;
644
645                /**
646                 * Create new entry.
647                 * 
648                 * @param k
649                 * @param v
650                 * @param n
651                 */
652                Entry(final int k, final V v, final Entry<V> n)
653                {
654                        value = v;
655                        next = n;
656                        key = k;
657                }
658
659                /**
660                 * @return The int key of this entry
661                 */
662                public int getKey()
663                {
664                        return key;
665                }
666
667                /**
668                 * @return Gets the value object of this entry
669                 */
670                public V getValue()
671                {
672                        return value;
673                }
674
675                /**
676                 * @param newValue
677                 * @return The previous value
678                 */
679                public V setValue(final V newValue)
680                {
681                        V oldValue = value;
682                        value = newValue;
683                        return oldValue;
684                }
685
686                /**
687                 * @see java.lang.Object#equals(java.lang.Object)
688                 */
689                @SuppressWarnings("unchecked")
690                @Override
691                public boolean equals(final Object o)
692                {
693                        if (!(o instanceof Entry))
694                        {
695                                return false;
696                        }
697                        Entry<V> e = (Entry<V>)o;
698                        int k1 = getKey();
699                        int k2 = e.getKey();
700                        if (k1 == k2)
701                        {
702                                Object v1 = getValue();
703                                Object v2 = e.getValue();
704                                if ((v1 == v2) || ((v1 != null) && v1.equals(v2)))
705                                {
706                                        return true;
707                                }
708                        }
709                        return false;
710                }
711
712                /**
713                 * @see java.lang.Object#hashCode()
714                 */
715                @Override
716                public int hashCode()
717                {
718                        return key ^ (value == null ? 0 : value.hashCode());
719                }
720
721                /**
722                 * @see java.lang.Object#toString()
723                 */
724                @Override
725                public String toString()
726                {
727                        return getKey() + "=" + getValue(); //$NON-NLS-1$
728                }
729        }
730
731        /**
732         * Add a new entry with the specified key, value and hash code to the specified bucket. It is
733         * the responsibility of this method to resize the table if appropriate.
734         * 
735         * Subclass overrides this to alter the behavior of put method.
736         * 
737         * @param key
738         * @param value
739         * @param bucketIndex
740         */
741        void addEntry(final int key, final V value, final int bucketIndex)
742        {
743                table[bucketIndex] = new Entry<>(key, value, table[bucketIndex]);
744                if (size++ >= threshold)
745                {
746                        resize(2 * table.length);
747                }
748        }
749
750        /**
751         * Like addEntry except that this version is used when creating entries as part of Map
752         * construction or "pseudo-construction" (cloning, deserialization). This version needn't worry
753         * about resizing the table.
754         * 
755         * Subclass overrides this to alter the behavior of HashMap(Map), clone, and readObject.
756         * 
757         * @param key
758         * @param value
759         * @param bucketIndex
760         */
761        void createEntry(final int key, final V value, final int bucketIndex)
762        {
763                table[bucketIndex] = new Entry<>(key, value, table[bucketIndex]);
764                size++;
765        }
766
767        private abstract class HashIterator<H> implements Iterator<H>
768        {
769                Entry<V> next; // next entry to return
770                int expectedModCount; // For fast-fail
771                int index; // current slot
772                Entry<V> current; // current entry
773
774                HashIterator()
775                {
776                        expectedModCount = modCount.get();
777                        Entry<V>[] t = table;
778                        int i = t.length;
779                        Entry<V> n = null;
780                        if (size != 0)
781                        { // advance to first entry
782                                while ((i > 0) && ((n = t[--i]) == null))
783                                {
784                                        /* NoOp */
785                                }
786                        }
787                        next = n;
788                        index = i;
789                }
790
791                /**
792                 * @see java.util.Iterator#hasNext()
793                 */
794                @Override
795                public boolean hasNext()
796                {
797                        return next != null;
798                }
799
800                Entry<V> nextEntry()
801                {
802                        if (!modCount.compareAndSet(expectedModCount, expectedModCount))
803                        {
804                                throw new ConcurrentModificationException();
805                        }
806                        Entry<V> e = next;
807                        if (e == null)
808                        {
809                                throw new NoSuchElementException();
810                        }
811
812                        Entry<V> n = e.next;
813                        Entry<V>[] t = table;
814                        int i = index;
815                        while ((n == null) && (i > 0))
816                        {
817                                n = t[--i];
818                        }
819                        index = i;
820                        next = n;
821                        return current = e;
822                }
823
824                /**
825                 * @see java.util.Iterator#remove()
826                 */
827                @Override
828                public void remove()
829                {
830                        if (current == null)
831                        {
832                                throw new IllegalStateException();
833                        }
834                        if (!modCount.compareAndSet(expectedModCount, expectedModCount))
835                        {
836                                throw new ConcurrentModificationException();
837                        }
838                        int k = current.key;
839                        current = null;
840                        removeEntryForKey(k);
841                        expectedModCount = modCount.get();
842                }
843
844        }
845
846        private class ValueIterator extends HashIterator<V>
847        {
848                /**
849                 * @see java.util.Iterator#next()
850                 */
851                @Override
852                public V next()
853                {
854                        return nextEntry().value;
855                }
856        }
857
858        private class KeyIterator extends HashIterator<Integer>
859        {
860                /**
861                 * @see java.util.Iterator#next()
862                 */
863                @Override
864                public Integer next()
865                {
866                        return nextEntry().getKey();
867                }
868        }
869
870        private class EntryIterator extends HashIterator<Entry<V>>
871        {
872                /**
873                 * @see java.util.Iterator#next()
874                 */
875                @Override
876                public Entry<V> next()
877                {
878                        return nextEntry();
879                }
880        }
881
882        // Subclass overrides these to alter behavior of views' iterator() method
883        Iterator<Integer> newKeyIterator()
884        {
885                return new KeyIterator();
886        }
887
888        Iterator<V> newValueIterator()
889        {
890                return new ValueIterator();
891        }
892
893        Iterator<Entry<V>> newEntryIterator()
894        {
895                return new EntryIterator();
896        }
897
898        // Views
899
900        private transient Set<Entry<V>> entrySet = null;
901
902        /**
903         * Returns a set view of the keys contained in this map. The set is backed by the map, so
904         * changes to the map are reflected in the set, and vice-versa. The set supports element
905         * removal, which removes the corresponding mapping from this map, via the
906         * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
907         * <tt>clear</tt> operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
908         * operations.
909         * 
910         * @return a set view of the keys contained in this map.
911         */
912        public Set<Integer> keySet()
913        {
914                Set<Integer> ks = keySet;
915                return (ks != null ? ks : (keySet = new KeySet()));
916        }
917
918        private class KeySet extends AbstractSet<Integer>
919        {
920                /**
921                 * @see java.util.AbstractCollection#iterator()
922                 */
923                @Override
924                public Iterator<Integer> iterator()
925                {
926                        return newKeyIterator();
927                }
928
929                /**
930                 * @see java.util.AbstractCollection#size()
931                 */
932                @Override
933                public int size()
934                {
935                        return size;
936                }
937
938                /**
939                 * @see java.util.AbstractCollection#contains(java.lang.Object)
940                 */
941                @Override
942                public boolean contains(final Object o)
943                {
944                        if (o instanceof Number)
945                        {
946                                return containsKey(((Number)o).intValue());
947                        }
948                        return false;
949                }
950
951                /**
952                 * @see java.util.AbstractCollection#remove(java.lang.Object)
953                 */
954                @Override
955                public boolean remove(final Object o)
956                {
957                        if (o instanceof Number)
958                        {
959                                return removeEntryForKey(((Number)o).intValue()) != null;
960                        }
961                        return false;
962                }
963
964                /**
965                 * @see java.util.AbstractCollection#clear()
966                 */
967                @Override
968                public void clear()
969                {
970                        IntHashMap.this.clear();
971                }
972        }
973
974        /**
975         * Returns a collection view of the values contained in this map. The collection is backed by
976         * the map, so changes to the map are reflected in the collection, and vice-versa. The
977         * collection supports element removal, which removes the corresponding mapping from this map,
978         * via the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, <tt>removeAll</tt>,
979         * <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support the <tt>add</tt> or
980         * <tt>addAll</tt> operations.
981         * 
982         * @return a collection view of the values contained in this map.
983         */
984        public Collection<V> values()
985        {
986                Collection<V> vs = values;
987                return (vs != null ? vs : (values = new Values()));
988        }
989
990        private class Values extends AbstractCollection<V>
991        {
992                /**
993                 * @see java.util.AbstractCollection#iterator()
994                 */
995                @Override
996                public Iterator<V> iterator()
997                {
998                        return newValueIterator();
999                }
1000
1001                /**
1002                 * @see java.util.AbstractCollection#size()
1003                 */
1004                @Override
1005                public int size()
1006                {
1007                        return size;
1008                }
1009
1010                /**
1011                 * @see java.util.AbstractCollection#contains(java.lang.Object)
1012                 */
1013                @Override
1014                public boolean contains(final Object o)
1015                {
1016                        return containsValue(o);
1017                }
1018
1019                /**
1020                 * @see java.util.AbstractCollection#clear()
1021                 */
1022                @Override
1023                public void clear()
1024                {
1025                        IntHashMap.this.clear();
1026                }
1027        }
1028
1029        /**
1030         * Returns a collection view of the mappings contained in this map. Each element in the returned
1031         * collection is a <tt>Map.Entry</tt>. The collection is backed by the map, so changes to the
1032         * map are reflected in the collection, and vice-versa. The collection supports element removal,
1033         * which removes the corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
1034         * <tt>Collection.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
1035         * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1036         * 
1037         * @return a collection view of the mappings contained in this map.
1038         * @see java.util.Map.Entry
1039         */
1040        public Set<Entry<V>> entrySet()
1041        {
1042                Set<Entry<V>> es = entrySet;
1043                return (es != null ? es : (entrySet = new EntrySet()));
1044        }
1045
1046        private class EntrySet extends AbstractSet<Entry<V>>
1047        {
1048                /**
1049                 * @see java.util.AbstractCollection#iterator()
1050                 */
1051                @Override
1052                public Iterator<Entry<V>> iterator()
1053                {
1054                        return newEntryIterator();
1055                }
1056
1057                /**
1058                 * @see java.util.AbstractCollection#contains(java.lang.Object)
1059                 */
1060                @SuppressWarnings("unchecked")
1061                @Override
1062                public boolean contains(final Object o)
1063                {
1064                        if (!(o instanceof Entry))
1065                        {
1066                                return false;
1067                        }
1068                        Entry<V> e = (Entry<V>)o;
1069                        Entry<V> candidate = getEntry(e.getKey());
1070                        return (candidate != null) && candidate.equals(e);
1071                }
1072
1073                /**
1074                 * @see java.util.AbstractCollection#remove(java.lang.Object)
1075                 */
1076                @Override
1077                public boolean remove(final Object o)
1078                {
1079                        return removeMapping(o) != null;
1080                }
1081
1082                /**
1083                 * @see java.util.AbstractCollection#size()
1084                 */
1085                @Override
1086                public int size()
1087                {
1088                        return size;
1089                }
1090
1091                /**
1092                 * @see java.util.AbstractCollection#clear()
1093                 */
1094                @Override
1095                public void clear()
1096                {
1097                        IntHashMap.this.clear();
1098                }
1099        }
1100
1101        /**
1102         * Save the state of the <tt>HashMap</tt> instance to a stream (i.e., serialize it).
1103         * 
1104         * @param s
1105         *            The ObjectOutputStream
1106         * @throws IOException
1107         * 
1108         * @serialData The <i>capacity</i> of the HashMap (the length of the bucket array) is emitted
1109         *             (int), followed by the <i>size</i> of the HashMap (the number of key-value
1110         *             mappings), followed by the key (Object) and value (Object) for each key-value
1111         *             mapping represented by the HashMap The key-value mappings are emitted in the
1112         *             order that they are returned by <tt>entrySet().iterator()</tt>.
1113         * 
1114         */
1115        private void writeObject(final java.io.ObjectOutputStream s) throws IOException
1116        {
1117                // Write out the threshold, loadfactor, and any hidden stuff
1118                s.defaultWriteObject();
1119
1120                // Write out number of buckets
1121                s.writeInt(table.length);
1122
1123                // Write out size (number of Mappings)
1124                s.writeInt(size);
1125
1126                // Write out keys and values (alternating)
1127                for (Entry<V> entry : entrySet())
1128                {
1129                        s.writeInt(entry.getKey());
1130                        s.writeObject(entry.getValue());
1131                }
1132        }
1133
1134        private static final long serialVersionUID = 362498820763181265L;
1135
1136        /**
1137         * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e., deserialize it).
1138         * 
1139         * @param s
1140         * @throws IOException
1141         * @throws ClassNotFoundException
1142         */
1143        @SuppressWarnings("unchecked")
1144        private void readObject(final java.io.ObjectInputStream s) throws IOException,
1145                ClassNotFoundException
1146        {
1147                modCount = new AtomicInteger(0);
1148
1149                // Read in the threshold, loadfactor, and any hidden stuff
1150                s.defaultReadObject();
1151
1152                // Read in number of buckets and allocate the bucket array;
1153                int numBuckets = s.readInt();
1154                table = new Entry[numBuckets];
1155
1156                init(); // Give subclass a chance to do its thing.
1157
1158                // Read in size (number of Mappings)
1159                int size = s.readInt();
1160
1161                // Read the keys and values, and put the mappings in the HashMap
1162                for (int i = 0; i < size; i++)
1163                {
1164                        int key = s.readInt();
1165                        V value = (V)s.readObject();
1166                        putForCreate(key, value);
1167                }
1168        }
1169
1170        // These methods are used when serializing HashSets
1171        int capacity()
1172        {
1173                return table.length;
1174        }
1175
1176        float loadFactor()
1177        {
1178                return loadFactor;
1179        }
1180}