001: /*
002: * Copyright 2005 Brian S O'Neill
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.cojen.util;
018:
019: import java.util.AbstractCollection;
020: import java.util.AbstractMap;
021: import java.util.AbstractSet;
022: import java.util.Collection;
023: import java.util.ConcurrentModificationException;
024: import java.util.Iterator;
025: import java.util.Map;
026: import java.util.NoSuchElementException;
027: import java.util.Set;
028:
029: import java.io.IOException;
030: import java.io.Serializable;
031:
032: /**
033: * A Map that accepts int or Integer keys only. This class is not thread-safe.
034: *
035: * @author Brian S O'Neill
036: */
037: public class IntHashMap extends AbstractMap implements Map, Cloneable,
038: Serializable {
039: /**
040: * The hash table data.
041: */
042: private transient Entry table[];
043:
044: /**
045: * The total number of mappings in the hash table.
046: */
047: private transient int count;
048:
049: /**
050: * The table is rehashed when its size exceeds this threshold. (The
051: * value of this field is (int)(capacity * loadFactor).)
052: *
053: * @serial
054: */
055: private int threshold;
056:
057: /**
058: * The load factor for the hashtable.
059: *
060: * @serial
061: */
062: private float loadFactor;
063:
064: /**
065: * The number of times this IntHashMap has been structurally modified
066: * Structural modifications are those that change the number of mappings in
067: * the IntHashMap or otherwise modify its internal structure (e.g.,
068: * rehash). This field is used to make iterators on Collection-views of
069: * the IntHashMap fail-fast. (See ConcurrentModificationException).
070: */
071: private transient int modCount = 0;
072:
073: /**
074: * Constructs a new, empty map with the specified initial
075: * capacity and the specified load factor.
076: *
077: * @param initialCapacity the initial capacity of the IntHashMap.
078: * @param loadFactor the load factor of the IntHashMap
079: * @throws IllegalArgumentException if the initial capacity is less
080: * than zero, or if the load factor is nonpositive.
081: */
082: public IntHashMap(int initialCapacity, float loadFactor) {
083: if (initialCapacity < 0) {
084: throw new IllegalArgumentException(
085: "Illegal Initial Capacity: " + initialCapacity);
086: }
087:
088: if (loadFactor <= 0) {
089: throw new IllegalArgumentException("Illegal Load factor: "
090: + loadFactor);
091: }
092:
093: if (initialCapacity == 0) {
094: initialCapacity = 1;
095: }
096:
097: this .loadFactor = loadFactor;
098: table = new Entry[initialCapacity];
099: threshold = (int) (initialCapacity * loadFactor);
100: }
101:
102: /**
103: * Constructs a new, empty map with the specified initial capacity
104: * and default load factor, which is <tt>0.75</tt>.
105: *
106: * @param initialCapacity the initial capacity of the IntHashMap.
107: * @throws IllegalArgumentException if the initial capacity is less
108: * than zero.
109: */
110: public IntHashMap(int initialCapacity) {
111: this (initialCapacity, 0.75f);
112: }
113:
114: /**
115: * Constructs a new, empty map with a default capacity and load
116: * factor, which is <tt>0.75</tt>.
117: */
118: public IntHashMap() {
119: this (101, 0.75f);
120: }
121:
122: /**
123: * Constructs a new map with the same mappings as the given map. The
124: * map is created with a capacity of twice the number of mappings in
125: * the given map or 11 (whichever is greater), and a default load factor,
126: * which is <tt>0.75</tt>.
127: */
128: public IntHashMap(Map t) {
129: this (Math.max(2 * t.size(), 11), 0.75f);
130: putAll(t);
131: }
132:
133: /**
134: * Returns the number of key-value mappings in this map.
135: *
136: * @return the number of key-value mappings in this map.
137: */
138: public int size() {
139: return count;
140: }
141:
142: /**
143: * Returns <tt>true</tt> if this map contains no key-value mappings.
144: *
145: * @return <tt>true</tt> if this map contains no key-value mappings.
146: */
147: public boolean isEmpty() {
148: return count == 0;
149: }
150:
151: /**
152: * Returns <tt>true</tt> if this map maps one or more keys to the
153: * specified value.
154: *
155: * @param value value whose presence in this map is to be tested.
156: * @return <tt>true</tt> if this map maps one or more keys to the
157: * specified value.
158: */
159: public boolean containsValue(Object value) {
160: Entry tab[] = table;
161:
162: if (value == null) {
163: for (int i = tab.length; i-- > 0;) {
164: for (Entry e = tab[i]; e != null; e = e.next) {
165: if (e.value == null) {
166: return true;
167: }
168: }
169: }
170: } else {
171: for (int i = tab.length; i-- > 0;) {
172: for (Entry e = tab[i]; e != null; e = e.next) {
173: if (value.equals(e.value)) {
174: return true;
175: }
176: }
177: }
178: }
179:
180: return false;
181: }
182:
183: /**
184: * Returns <tt>true</tt> if this map contains a mapping for the specified
185: * key.
186: *
187: * @return <tt>true</tt> if this map contains a mapping for the specified
188: * key.
189: * @param key key whose presence in this Map is to be tested.
190: */
191: public boolean containsKey(Integer key) {
192: return containsKey(key.intValue());
193: }
194:
195: /**
196: * Returns <tt>true</tt> if this map contains a mapping for the specified
197: * key.
198: *
199: * @return <tt>true</tt> if this map contains a mapping for the specified
200: * key.
201: * @param key key whose presence in this Map is to be tested.
202: */
203: public boolean containsKey(int key) {
204: Entry tab[] = table;
205:
206: int index = (key & 0x7fffffff) % tab.length;
207: for (Entry e = tab[index]; e != null; e = e.next) {
208: if (e.key == key) {
209: return true;
210: }
211: }
212:
213: return false;
214: }
215:
216: /**
217: * Returns the value to which this map maps the specified key. Returns
218: * <tt>null</tt> if the map contains no mapping for this key. A return
219: * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
220: * map contains no mapping for the key; it's also possible that the map
221: * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
222: * operation may be used to distinguish these two cases.
223: *
224: * @return the value to which this map maps the specified key.
225: * @param key key whose associated value is to be returned.
226: */
227: public Object get(Integer key) {
228: return get(key.intValue());
229: }
230:
231: /**
232: * Returns the value to which this map maps the specified key. Returns
233: * <tt>null</tt> if the map contains no mapping for this key. A return
234: * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
235: * map contains no mapping for the key; it's also possible that the map
236: * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
237: * operation may be used to distinguish these two cases.
238: *
239: * @return the value to which this map maps the specified key.
240: * @param key key whose associated value is to be returned.
241: */
242: public Object get(int key) {
243: Entry tab[] = table;
244:
245: int index = (key & 0x7fffffff) % tab.length;
246: for (Entry e = tab[index]; e != null; e = e.next) {
247: if (e.key == key) {
248: return e.value;
249: }
250: }
251:
252: return null;
253: }
254:
255: /**
256: * Rehashes the contents of this map into a new <tt>IntHashMap</tt> instance
257: * with a larger capacity. This method is called automatically when the
258: * number of keys in this map exceeds its capacity and load factor.
259: */
260: private void rehash() {
261: int oldCapacity = table.length;
262: Entry oldMap[] = table;
263:
264: int newCapacity = oldCapacity * 2 + 1;
265: Entry newMap[] = new Entry[newCapacity];
266:
267: modCount++;
268: threshold = (int) (newCapacity * loadFactor);
269: table = newMap;
270:
271: for (int i = oldCapacity; i-- > 0;) {
272: for (Entry old = oldMap[i]; old != null;) {
273: Entry e = old;
274: old = old.next;
275:
276: int index = (e.key & 0x7fffffff) % newCapacity;
277: e.next = newMap[index];
278: newMap[index] = e;
279: }
280: }
281: }
282:
283: /**
284: * Associates the specified value with the specified key in this map.
285: * If the map previously contained a mapping for this key, the old
286: * value is replaced.
287: *
288: * @param key key with which the specified value is to be associated.
289: * @param value value to be associated with the specified key.
290: * @return previous value associated with specified key, or <tt>null</tt>
291: * if there was no mapping for key. A <tt>null</tt> return can
292: * also indicate that the IntHashMap previously associated
293: * <tt>null</tt> with the specified key.
294: */
295: public Object put(Integer key, Object value) {
296: return put(key.intValue(), value);
297: }
298:
299: /**
300: * Associates the specified value with the specified key in this map.
301: * If the map previously contained a mapping for this key, the old
302: * value is replaced.
303: *
304: * @param key key with which the specified value is to be associated.
305: * @param value value to be associated with the specified key.
306: * @return previous value associated with specified key, or <tt>null</tt>
307: * if there was no mapping for key. A <tt>null</tt> return can
308: * also indicate that the IntHashMap previously associated
309: * <tt>null</tt> with the specified key.
310: */
311: public Object put(int key, Object value) {
312: // Makes sure the key is not already in the IntHashMap.
313: Entry tab[] = table;
314: int index = 0;
315:
316: index = (key & 0x7fffffff) % tab.length;
317: for (Entry e = tab[index]; e != null; e = e.next) {
318: if (e.key == key) {
319: Object old = e.value;
320: e.value = value;
321: return old;
322: }
323: }
324:
325: modCount++;
326: if (count >= threshold) {
327: // Rehash the table if the threshold is exceeded
328: rehash();
329:
330: tab = table;
331: index = (key & 0x7fffffff) % tab.length;
332: }
333:
334: // Creates the new entry.
335: Entry e = new Entry(key, value, tab[index]);
336: tab[index] = e;
337: count++;
338: return null;
339: }
340:
341: /**
342: * Removes the mapping for this key from this map if present.
343: *
344: * @param key key whose mapping is to be removed from the map.
345: * @return previous value associated with specified key, or <tt>null</tt>
346: * if there was no mapping for key. A <tt>null</tt> return can
347: * also indicate that the map previously associated <tt>null</tt>
348: * with the specified key.
349: */
350: public Object remove(Integer key) {
351: return remove(key.intValue());
352: }
353:
354: /**
355: * Removes the mapping for this key from this map if present.
356: *
357: * @param key key whose mapping is to be removed from the map.
358: * @return previous value associated with specified key, or <tt>null</tt>
359: * if there was no mapping for key. A <tt>null</tt> return can
360: * also indicate that the map previously associated <tt>null</tt>
361: * with the specified key.
362: */
363: public Object remove(int key) {
364: Entry tab[] = table;
365:
366: int index = (key & 0x7fffffff) % tab.length;
367:
368: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
369: if (e.key == key) {
370: modCount++;
371: if (prev != null) {
372: prev.next = e.next;
373: } else {
374: tab[index] = e.next;
375: }
376:
377: count--;
378: Object oldValue = e.value;
379: e.value = null;
380: return oldValue;
381: }
382: }
383:
384: return null;
385: }
386:
387: /**
388: * Removes all mappings from this map.
389: */
390: public void clear() {
391: Entry tab[] = table;
392: modCount++;
393: for (int index = tab.length; --index >= 0;) {
394: tab[index] = null;
395: }
396: count = 0;
397: }
398:
399: /**
400: * Returns a shallow copy of this <tt>IntHashMap</tt> instance: the keys and
401: * values themselves are not cloned.
402: *
403: * @return a shallow copy of this map.
404: */
405: public Object clone() {
406: try {
407: IntHashMap t = (IntHashMap) super .clone();
408: t.table = new Entry[table.length];
409: for (int i = table.length; i-- > 0;) {
410: t.table[i] = (table[i] != null) ? (Entry) table[i]
411: .clone() : null;
412: }
413: t.keySet = null;
414: t.entrySet = null;
415: t.values = null;
416: t.modCount = 0;
417: return t;
418: } catch (CloneNotSupportedException e) {
419: // this shouldn't happen, since we are Cloneable
420: throw new InternalError();
421: }
422: }
423:
424: // Views
425:
426: private transient Set keySet = null;
427: private transient Set entrySet = null;
428: private transient Collection values = null;
429:
430: /**
431: * Returns a set view of the keys contained in this map. The set is
432: * backed by the map, so changes to the map are reflected in the set, and
433: * vice-versa. The set supports element removal, which removes the
434: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
435: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
436: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
437: * <tt>addAll</tt> operations.
438: *
439: * @return a set view of the keys contained in this map.
440: */
441: public Set keySet() {
442: if (keySet == null) {
443: keySet = new AbstractSet() {
444: public Iterator iterator() {
445: return new IntHashIterator(KEYS);
446: }
447:
448: public int size() {
449: return count;
450: }
451:
452: public boolean contains(Object o) {
453: return containsKey(o);
454: }
455:
456: public boolean remove(Object o) {
457: return IntHashMap.this .remove(o) != null;
458: }
459:
460: public void clear() {
461: IntHashMap.this .clear();
462: }
463: };
464: }
465: return keySet;
466: }
467:
468: /**
469: * Returns a collection view of the values contained in this map. The
470: * collection is backed by the map, so changes to the map are reflected in
471: * the collection, and vice-versa. The collection supports element
472: * removal, which removes the corresponding mapping from this map, via the
473: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
474: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
475: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
476: *
477: * @return a collection view of the values contained in this map.
478: */
479: public Collection values() {
480: if (values == null) {
481: values = new AbstractCollection() {
482: public Iterator iterator() {
483: return (Iterator) new IntHashIterator(VALUES);
484: }
485:
486: public int size() {
487: return count;
488: }
489:
490: public boolean contains(Object o) {
491: return containsValue(o);
492: }
493:
494: public void clear() {
495: IntHashMap.this .clear();
496: }
497: };
498: }
499: return values;
500: }
501:
502: /**
503: * Returns a collection view of the mappings contained in this map. Each
504: * element in the returned collection is a <tt>Map.Entry</tt>. The
505: * collection is backed by the map, so changes to the map are reflected in
506: * the collection, and vice-versa. The collection supports element
507: * removal, which removes the corresponding mapping from the map, via the
508: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
509: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
510: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
511: *
512: * @return a collection view of the mappings contained in this map.
513: */
514: public Set entrySet() {
515: if (entrySet == null) {
516: entrySet = new AbstractSet() {
517: public Iterator iterator() {
518: return (Iterator) new IntHashIterator(ENTRIES);
519: }
520:
521: public boolean contains(Object o) {
522: if (!(o instanceof Map.Entry)) {
523: return false;
524: }
525: Map.Entry entry = (Map.Entry) o;
526: Integer key = (Integer) entry.getKey();
527: Entry tab[] = table;
528: int hash = (key == null ? 0 : key.hashCode());
529: int index = (hash & 0x7fffffff) % tab.length;
530:
531: for (Entry e = tab[index]; e != null; e = e.next) {
532: if (e.key == hash && e.equals(entry)) {
533: return true;
534: }
535: }
536: return false;
537: }
538:
539: public boolean remove(Object o) {
540: if (!(o instanceof Map.Entry)) {
541: return false;
542: }
543: Map.Entry entry = (Map.Entry) o;
544: Integer key = (Integer) entry.getKey();
545: Entry tab[] = table;
546: int hash = (key == null ? 0 : key.hashCode());
547: int index = (hash & 0x7fffffff) % tab.length;
548:
549: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
550: if (e.key == hash && e.equals(entry)) {
551: modCount++;
552: if (prev != null) {
553: prev.next = e.next;
554: } else {
555: tab[index] = e.next;
556: }
557:
558: count--;
559: e.value = null;
560: return true;
561: }
562: }
563: return false;
564: }
565:
566: public int size() {
567: return count;
568: }
569:
570: public void clear() {
571: IntHashMap.this .clear();
572: }
573: };
574: }
575:
576: return entrySet;
577: }
578:
579: /**
580: * IntHashMap collision list entry.
581: */
582: private static class Entry implements Map.Entry {
583: int key;
584: Object value;
585: Entry next;
586: private Integer objectKey;
587:
588: Entry(int key, Object value, Entry next) {
589: this .key = key;
590: this .value = value;
591: this .next = next;
592: }
593:
594: protected Object clone() {
595: return new Entry(key, value, (next == null ? null
596: : (Entry) next.clone()));
597: }
598:
599: // Map.Entry Ops
600:
601: public Object getKey() {
602: return (objectKey != null) ? objectKey
603: : (objectKey = new Integer(key));
604: }
605:
606: public Object getValue() {
607: return value;
608: }
609:
610: public Object setValue(Object value) {
611: Object oldValue = this .value;
612: this .value = value;
613: return oldValue;
614: }
615:
616: public boolean equals(Object o) {
617: if (!(o instanceof Map.Entry)) {
618: return false;
619: }
620: Map.Entry e = (Map.Entry) o;
621:
622: return (getKey().equals(e.getKey()))
623: && (value == null ? e.getValue() == null : value
624: .equals(e.getValue()));
625: }
626:
627: public int hashCode() {
628: return key ^ (value == null ? 0 : value.hashCode());
629: }
630:
631: public String toString() {
632: return String.valueOf(key) + "=" + value;
633: }
634: }
635:
636: // Types of Iterators
637: private static final int KEYS = 0;
638: private static final int VALUES = 1;
639: private static final int ENTRIES = 2;
640:
641: private class IntHashIterator implements Iterator {
642: Entry[] table = IntHashMap.this .table;
643: int index = table.length;
644: Entry entry;
645: Entry lastReturned;
646: int type;
647:
648: /**
649: * The modCount value that the iterator believes that the backing
650: * List should have. If this expectation is violated, the iterator
651: * has detected concurrent modification.
652: */
653: private int expectedModCount = modCount;
654:
655: IntHashIterator(int type) {
656: this .type = type;
657: }
658:
659: public boolean hasNext() {
660: while (entry == null && index > 0) {
661: entry = table[--index];
662: }
663:
664: return entry != null;
665: }
666:
667: public Object next() {
668: if (modCount != expectedModCount) {
669: throw new ConcurrentModificationException();
670: }
671:
672: while (entry == null && index > 0) {
673: entry = table[--index];
674: }
675:
676: if (entry != null) {
677: Entry e = lastReturned = entry;
678: entry = e.next;
679: return type == KEYS ? e.getKey()
680: : (type == VALUES ? e.value : e);
681: }
682: throw new NoSuchElementException();
683: }
684:
685: public void remove() {
686: if (lastReturned == null) {
687: throw new IllegalStateException();
688: }
689: if (modCount != expectedModCount) {
690: throw new ConcurrentModificationException();
691: }
692:
693: Entry[] tab = IntHashMap.this .table;
694: int index = (lastReturned.key & 0x7fffffff) % tab.length;
695:
696: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
697: if (e == lastReturned) {
698: modCount++;
699: expectedModCount++;
700: if (prev == null) {
701: tab[index] = e.next;
702: } else {
703: prev.next = e.next;
704: }
705: count--;
706: lastReturned = null;
707: return;
708: }
709: }
710: throw new ConcurrentModificationException();
711: }
712: }
713:
714: /**
715: * Save the state of the <tt>IntHashMap</tt> instance to a stream (i.e.,
716: * serialize it).
717: *
718: * @serialData The <i>capacity</i> of the IntHashMap (the length of the
719: * bucket array) is emitted (int), followed by the
720: * <i>size</i> of the IntHashMap (the number of key-value
721: * mappings), followed by the key (Object) and value (Object)
722: * for each key-value mapping represented by the IntHashMap
723: * The key-value mappings are emitted in no particular order.
724: */
725: private void writeObject(java.io.ObjectOutputStream s)
726: throws IOException {
727: // Write out the threshold, loadfactor, and any hidden stuff
728: s.defaultWriteObject();
729:
730: // Write out number of buckets
731: s.writeInt(table.length);
732:
733: // Write out size (number of Mappings)
734: s.writeInt(count);
735:
736: // Write out keys and values (alternating)
737: for (int index = table.length - 1; index >= 0; index--) {
738: Entry entry = table[index];
739:
740: while (entry != null) {
741: s.writeInt(entry.key);
742: s.writeObject(entry.value);
743: entry = entry.next;
744: }
745: }
746: }
747:
748: /**
749: * Reconstitute the <tt>IntHashMap</tt> instance from a stream (i.e.,
750: * deserialize it).
751: */
752: private void readObject(java.io.ObjectInputStream s)
753: throws IOException, ClassNotFoundException {
754: // Read in the threshold, loadfactor, and any hidden stuff
755: s.defaultReadObject();
756:
757: // Read in number of buckets and allocate the bucket array;
758: int numBuckets = s.readInt();
759: table = new Entry[numBuckets];
760:
761: // Read in size (number of Mappings)
762: int size = s.readInt();
763:
764: // Read the keys and values, and put the mappings in the IntHashMap
765: for (int i = 0; i < size; i++) {
766: int key = s.readInt();
767: Object value = s.readObject();
768: put(key, value);
769: }
770: }
771:
772: int capacity() {
773: return table.length;
774: }
775:
776: float loadFactor() {
777: return loadFactor;
778: }
779: }
|