0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one or more
0003: * contributor license agreements. See the NOTICE file distributed with
0004: * this work for additional information regarding copyright ownership.
0005: * The ASF licenses this file to You under the Apache License, Version 2.0
0006: * (the "License"); you may not use this file except in compliance with
0007: * the License. You may obtain a copy of the License at
0008: *
0009: * http://www.apache.org/licenses/LICENSE-2.0
0010: *
0011: * Unless required by applicable law or agreed to in writing, software
0012: * distributed under the License is distributed on an "AS IS" BASIS,
0013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014: * See the License for the specific language governing permissions and
0015: * limitations under the License.
0016: */
0017: package org.apache.wicket.util.collections;
0018:
0019: import java.io.IOException;
0020: import java.io.Serializable;
0021: import java.util.AbstractCollection;
0022: import java.util.AbstractSet;
0023: import java.util.Collection;
0024: import java.util.ConcurrentModificationException;
0025: import java.util.Iterator;
0026: import java.util.Map;
0027: import java.util.NoSuchElementException;
0028: import java.util.Set;
0029:
0030: /**
0031: * This is a int hashmap that has the exact same features and interface as a
0032: * normal Map except that the key is directly an integer. So no hash is
0033: * calculated or key object is stored.
0034: *
0035: * @author jcompagner
0036: */
0037: public class IntHashMap implements Cloneable, Serializable {
0038: transient volatile Set keySet = null;
0039:
0040: transient volatile Collection values = null;
0041:
0042: /**
0043: * The default initial capacity - MUST be a power of two.
0044: */
0045: static final int DEFAULT_INITIAL_CAPACITY = 16;
0046:
0047: /**
0048: * The maximum capacity, used if a higher value is implicitly specified by
0049: * either of the constructors with arguments. MUST be a power of two <= 1<<30.
0050: */
0051: static final int MAXIMUM_CAPACITY = 1 << 30;
0052:
0053: /**
0054: * The load factor used when none specified in constructor.
0055: */
0056: static final float DEFAULT_LOAD_FACTOR = 0.75f;
0057:
0058: /**
0059: * The table, resized as necessary. Length MUST Always be a power of two.
0060: */
0061: transient Entry[] table;
0062:
0063: /**
0064: * The number of key-value mappings contained in this identity hash map.
0065: */
0066: transient int size;
0067:
0068: /**
0069: * The next size value at which to resize (capacity * load factor).
0070: *
0071: * @serial
0072: */
0073: int threshold;
0074:
0075: /**
0076: * The load factor for the hash table.
0077: *
0078: * @serial
0079: */
0080: final float loadFactor;
0081:
0082: /**
0083: * The number of times this HashMap has been structurally modified
0084: * Structural modifications are those that change the number of mappings in
0085: * the HashMap or otherwise modify its internal structure (e.g., rehash).
0086: * This field is used to make iterators on Collection-views of the HashMap
0087: * fail-fast. (See ConcurrentModificationException).
0088: */
0089: transient volatile int modCount;
0090:
0091: /**
0092: * Constructs an empty <tt>HashMap</tt> with the specified initial
0093: * capacity and load factor.
0094: *
0095: * @param initialCapacity
0096: * The initial capacity.
0097: * @param loadFactor
0098: * The load factor.
0099: * @throws IllegalArgumentException
0100: * if the initial capacity is negative or the load factor is
0101: * nonpositive.
0102: */
0103: public IntHashMap(int initialCapacity, float loadFactor) {
0104: if (initialCapacity < 0) {
0105: throw new IllegalArgumentException(
0106: "Illegal initial capacity: " + //$NON-NLS-1$
0107: initialCapacity);
0108: }
0109: if (initialCapacity > MAXIMUM_CAPACITY) {
0110: initialCapacity = MAXIMUM_CAPACITY;
0111: }
0112: if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
0113: throw new IllegalArgumentException("Illegal load factor: " + //$NON-NLS-1$
0114: loadFactor);
0115: }
0116:
0117: // Find a power of 2 >= initialCapacity
0118: int capacity = 1;
0119: while (capacity < initialCapacity) {
0120: capacity <<= 1;
0121: }
0122:
0123: this .loadFactor = loadFactor;
0124: threshold = (int) (capacity * loadFactor);
0125: table = new Entry[capacity];
0126: init();
0127: }
0128:
0129: /**
0130: * Constructs an empty <tt>HashMap</tt> with the specified initial
0131: * capacity and the default load factor (0.75).
0132: *
0133: * @param initialCapacity
0134: * the initial capacity.
0135: * @throws IllegalArgumentException
0136: * if the initial capacity is negative.
0137: */
0138: public IntHashMap(int initialCapacity) {
0139: this (initialCapacity, DEFAULT_LOAD_FACTOR);
0140: }
0141:
0142: /**
0143: * Constructs an empty <tt>HashMap</tt> with the default initial capacity
0144: * (16) and the default load factor (0.75).
0145: */
0146: public IntHashMap() {
0147: this .loadFactor = DEFAULT_LOAD_FACTOR;
0148: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
0149: table = new Entry[DEFAULT_INITIAL_CAPACITY];
0150: init();
0151: }
0152:
0153: // internal utilities
0154:
0155: /**
0156: * Initialization hook for subclasses. This method is called in all
0157: * constructors and pseudo-constructors (clone, readObject) after HashMap
0158: * has been initialized but before any entries have been inserted. (In the
0159: * absence of this method, readObject would require explicit knowledge of
0160: * subclasses.)
0161: */
0162: void init() {
0163: }
0164:
0165: /**
0166: * Returns index for hash code h.
0167: *
0168: * @param h
0169: * @param length
0170: * @return The index for the hash integer for the given length
0171: */
0172: static int indexFor(int h, int length) {
0173: return h & (length - 1);
0174: }
0175:
0176: /**
0177: * Returns the number of key-value mappings in this map.
0178: *
0179: * @return the number of key-value mappings in this map.
0180: */
0181: public int size() {
0182: return size;
0183: }
0184:
0185: /**
0186: * Returns <tt>true</tt> if this map contains no key-value mappings.
0187: *
0188: * @return <tt>true</tt> if this map contains no key-value mappings.
0189: */
0190: public boolean isEmpty() {
0191: return size == 0;
0192: }
0193:
0194: /**
0195: * Returns the value to which the specified key is mapped in this identity
0196: * hash map, or <tt>null</tt> if the map contains no mapping for this key.
0197: * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
0198: * that the map contains no mapping for the key; it is also possible that
0199: * the map explicitly maps the key to <tt>null</tt>. The
0200: * <tt>containsKey</tt> method may be used to distinguish these two cases.
0201: *
0202: * @param key
0203: * the key whose associated value is to be returned.
0204: * @return the value to which this map maps the specified key, or
0205: * <tt>null</tt> if the map contains no mapping for this key.
0206: * @see #put(int, Object)
0207: */
0208: public Object get(int key) {
0209: int i = indexFor(key, table.length);
0210: Entry e = table[i];
0211: while (true) {
0212: if (e == null) {
0213: return e;
0214: }
0215: if (key == e.key) {
0216: return e.value;
0217: }
0218: e = e.next;
0219: }
0220: }
0221:
0222: /**
0223: * Returns <tt>true</tt> if this map contains a mapping for the specified
0224: * key.
0225: *
0226: * @param key
0227: * The key whose presence in this map is to be tested
0228: * @return <tt>true</tt> if this map contains a mapping for the specified
0229: * key.
0230: */
0231: public boolean containsKey(int key) {
0232: int i = indexFor(key, table.length);
0233: Entry e = table[i];
0234: while (e != null) {
0235: if (key == e.key) {
0236: return true;
0237: }
0238: e = e.next;
0239: }
0240: return false;
0241: }
0242:
0243: /**
0244: * Returns the entry associated with the specified key in the HashMap.
0245: * Returns null if the HashMap contains no mapping for this key.
0246: *
0247: * @param key
0248: * @return The Entry object for the given hash key
0249: */
0250: Entry getEntry(int key) {
0251: int i = indexFor(key, table.length);
0252: Entry e = table[i];
0253: while (e != null && !(key == e.key)) {
0254: e = e.next;
0255: }
0256: return e;
0257: }
0258:
0259: /**
0260: * Associates the specified value with the specified key in this map. If the
0261: * map previously contained a mapping for this key, the old value is
0262: * replaced.
0263: *
0264: * @param key
0265: * key with which the specified value is to be associated.
0266: * @param value
0267: * value to be associated with the specified key.
0268: * @return previous value associated with specified key, or <tt>null</tt>
0269: * if there was no mapping for key. A <tt>null</tt> return can
0270: * also indicate that the HashMap previously associated
0271: * <tt>null</tt> with the specified key.
0272: */
0273: public Object put(int key, Object value) {
0274: int i = indexFor(key, table.length);
0275:
0276: for (Entry e = table[i]; e != null; e = e.next) {
0277: if (key == e.key) {
0278: Object oldValue = e.value;
0279: e.value = value;
0280: return oldValue;
0281: }
0282: }
0283:
0284: modCount++;
0285: addEntry(key, value, i);
0286: return null;
0287: }
0288:
0289: /**
0290: * This method is used instead of put by constructors and pseudoconstructors
0291: * (clone, readObject). It does not resize the table, check for
0292: * comodification, etc. It calls createEntry rather than addEntry.
0293: *
0294: * @param key
0295: * @param value
0296: */
0297: private void putForCreate(int key, Object value) {
0298: int i = indexFor(key, table.length);
0299:
0300: /**
0301: * Look for preexisting entry for key. This will never happen for clone
0302: * or deserialize. It will only happen for construction if the input Map
0303: * is a sorted map whose ordering is inconsistent w/ equals.
0304: */
0305: for (Entry e = table[i]; e != null; e = e.next) {
0306: if (key == e.key) {
0307: e.value = value;
0308: return;
0309: }
0310: }
0311:
0312: createEntry(key, value, i);
0313: }
0314:
0315: void putAllForCreate(IntHashMap m) {
0316: for (Iterator i = m.entrySet().iterator(); i.hasNext();) {
0317: Entry e = (Entry) i.next();
0318: putForCreate(e.getKey(), e.getValue());
0319: }
0320: }
0321:
0322: /**
0323: * Rehashes the contents of this map into a new array with a larger
0324: * capacity. This method is called automatically when the number of keys in
0325: * this map reaches its threshold.
0326: *
0327: * If current capacity is MAXIMUM_CAPACITY, this method does not resize the
0328: * map, but but sets threshold to Integer.MAX_VALUE. This has the effect of
0329: * preventing future calls.
0330: *
0331: * @param newCapacity
0332: * the new capacity, MUST be a power of two; must be greater than
0333: * current capacity unless current capacity is MAXIMUM_CAPACITY
0334: * (in which case value is irrelevant).
0335: */
0336: void resize(int newCapacity) {
0337: Entry[] oldTable = table;
0338: int oldCapacity = oldTable.length;
0339: if (oldCapacity == MAXIMUM_CAPACITY) {
0340: threshold = Integer.MAX_VALUE;
0341: return;
0342: }
0343:
0344: Entry[] newTable = new Entry[newCapacity];
0345: transfer(newTable);
0346: table = newTable;
0347: threshold = (int) (newCapacity * loadFactor);
0348: }
0349:
0350: /**
0351: * Transfer all entries from current table to newTable.
0352: *
0353: * @param newTable
0354: */
0355: void transfer(Entry[] newTable) {
0356: Entry[] src = table;
0357: int newCapacity = newTable.length;
0358: for (int j = 0; j < src.length; j++) {
0359: Entry e = src[j];
0360: if (e != null) {
0361: src[j] = null;
0362: do {
0363: Entry next = e.next;
0364: int i = indexFor(e.key, newCapacity);
0365: e.next = newTable[i];
0366: newTable[i] = e;
0367: e = next;
0368: } while (e != null);
0369: }
0370: }
0371: }
0372:
0373: /**
0374: * Copies all of the mappings from the specified map to this map These
0375: * mappings will replace any mappings that this map had for any of the keys
0376: * currently in the specified map.
0377: *
0378: * @param m
0379: * mappings to be stored in this map.
0380: * @throws NullPointerException
0381: * if the specified map is null.
0382: */
0383: public void putAll(IntHashMap m) {
0384: int numKeysToBeAdded = m.size();
0385: if (numKeysToBeAdded == 0) {
0386: return;
0387: }
0388:
0389: /*
0390: * Expand the map if the map if the number of mappings to be added is
0391: * greater than or equal to threshold. This is conservative; the obvious
0392: * condition is (m.size() + size) >= threshold, but this condition could
0393: * result in a map with twice the appropriate capacity, if the keys to
0394: * be added overlap with the keys already in this map. By using the
0395: * conservative calculation, we subject ourself to at most one extra
0396: * resize.
0397: */
0398: if (numKeysToBeAdded > threshold) {
0399: int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
0400: if (targetCapacity > MAXIMUM_CAPACITY) {
0401: targetCapacity = MAXIMUM_CAPACITY;
0402: }
0403: int newCapacity = table.length;
0404: while (newCapacity < targetCapacity) {
0405: newCapacity <<= 1;
0406: }
0407: if (newCapacity > table.length) {
0408: resize(newCapacity);
0409: }
0410: }
0411:
0412: for (Iterator i = m.entrySet().iterator(); i.hasNext();) {
0413: Entry e = (Entry) i.next();
0414: put(e.getKey(), e.getValue());
0415: }
0416: }
0417:
0418: /**
0419: * Removes the mapping for this key from this map if present.
0420: *
0421: * @param key
0422: * key whose mapping is to be removed from the map.
0423: * @return previous value associated with specified key, or <tt>null</tt>
0424: * if there was no mapping for key. A <tt>null</tt> return can
0425: * also indicate that the map previously associated <tt>null</tt>
0426: * with the specified key.
0427: */
0428: public Object remove(int key) {
0429: Entry e = removeEntryForKey(key);
0430: return (e == null ? e : e.value);
0431: }
0432:
0433: /**
0434: * Removes and returns the entry associated with the specified key in the
0435: * HashMap. Returns null if the HashMap contains no mapping for this key.
0436: *
0437: * @param key
0438: * @return The Entry object that was removed
0439: */
0440: Entry removeEntryForKey(int key) {
0441: int i = indexFor(key, table.length);
0442: Entry prev = table[i];
0443: Entry e = prev;
0444:
0445: while (e != null) {
0446: Entry next = e.next;
0447: if (key == e.key) {
0448: modCount++;
0449: size--;
0450: if (prev == e) {
0451: table[i] = next;
0452: } else {
0453: prev.next = next;
0454: }
0455: return e;
0456: }
0457: prev = e;
0458: e = next;
0459: }
0460:
0461: return e;
0462: }
0463:
0464: /**
0465: * Special version of remove for EntrySet.
0466: *
0467: * @param o
0468: * @return The entry that was removed
0469: */
0470: Entry removeMapping(Object o) {
0471: if (!(o instanceof Entry)) {
0472: return null;
0473: }
0474:
0475: Entry entry = (Entry) o;
0476: int key = entry.getKey();
0477: int i = indexFor(key, table.length);
0478: Entry prev = table[i];
0479: Entry e = prev;
0480:
0481: while (e != null) {
0482: Entry next = e.next;
0483: if (e.key == key && e.equals(entry)) {
0484: modCount++;
0485: size--;
0486: if (prev == e) {
0487: table[i] = next;
0488: } else {
0489: prev.next = next;
0490: }
0491: return e;
0492: }
0493: prev = e;
0494: e = next;
0495: }
0496:
0497: return e;
0498: }
0499:
0500: /**
0501: * Removes all mappings from this map.
0502: */
0503: public void clear() {
0504: modCount++;
0505: Entry tab[] = table;
0506: for (int i = 0; i < tab.length; i++) {
0507: tab[i] = null;
0508: }
0509: size = 0;
0510: }
0511:
0512: /**
0513: * Returns <tt>true</tt> if this map maps one or more keys to the
0514: * specified value.
0515: *
0516: * @param value
0517: * value whose presence in this map is to be tested.
0518: * @return <tt>true</tt> if this map maps one or more keys to the
0519: * specified value.
0520: */
0521: public boolean containsValue(Object value) {
0522: if (value == null) {
0523: return containsNullValue();
0524: }
0525:
0526: Entry tab[] = table;
0527: for (int i = 0; i < tab.length; i++) {
0528: for (Entry e = tab[i]; e != null; e = e.next) {
0529: if (value.equals(e.value)) {
0530: return true;
0531: }
0532: }
0533: }
0534: return false;
0535: }
0536:
0537: /**
0538: * Special-case code for containsValue with null argument
0539: *
0540: * @return boolean true if there is a null value in this map
0541: */
0542: private boolean containsNullValue() {
0543: Entry tab[] = table;
0544: for (int i = 0; i < tab.length; i++) {
0545: for (Entry e = tab[i]; e != null; e = e.next) {
0546: if (e.value == null) {
0547: return true;
0548: }
0549: }
0550: }
0551: return false;
0552: }
0553:
0554: /**
0555: * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
0556: * values themselves are not cloned.
0557: *
0558: * @return a shallow copy of this map.
0559: */
0560: public Object clone() throws CloneNotSupportedException {
0561: IntHashMap result = null;
0562: try {
0563: result = (IntHashMap) super .clone();
0564: result.table = new Entry[table.length];
0565: result.entrySet = null;
0566: result.modCount = 0;
0567: result.size = 0;
0568: result.init();
0569: result.putAllForCreate(this );
0570: } catch (CloneNotSupportedException e) {
0571: // assert false;
0572: }
0573: return result;
0574: }
0575:
0576: /**
0577: * @author jcompagner
0578: */
0579: public static class Entry {
0580: final int key;
0581: Object value;
0582: Entry next;
0583:
0584: /**
0585: * Create new entry.
0586: *
0587: * @param k
0588: * @param v
0589: * @param n
0590: */
0591: Entry(int k, Object v, Entry n) {
0592: value = v;
0593: next = n;
0594: key = k;
0595: }
0596:
0597: /**
0598: * @return The int key of this entry
0599: */
0600: public int getKey() {
0601: return key;
0602: }
0603:
0604: /**
0605: * @return Gets the value object of this entry
0606: */
0607: public Object getValue() {
0608: return value;
0609: }
0610:
0611: /**
0612: * @param newValue
0613: * @return The previous value
0614: */
0615: public Object setValue(Object newValue) {
0616: Object oldValue = value;
0617: value = newValue;
0618: return oldValue;
0619: }
0620:
0621: /**
0622: * @see java.lang.Object#equals(java.lang.Object)
0623: */
0624: public boolean equals(Object o) {
0625: if (!(o instanceof Entry)) {
0626: return false;
0627: }
0628: Entry e = (Entry) o;
0629: int k1 = getKey();
0630: int k2 = e.getKey();
0631: if (k1 == k2) {
0632: Object v1 = getValue();
0633: Object v2 = e.getValue();
0634: if (v1 == v2 || (v1 != null && v1.equals(v2))) {
0635: return true;
0636: }
0637: }
0638: return false;
0639: }
0640:
0641: /**
0642: * @see java.lang.Object#hashCode()
0643: */
0644: public int hashCode() {
0645: return key ^ (value == null ? 0 : value.hashCode());
0646: }
0647:
0648: /**
0649: * @see java.lang.Object#toString()
0650: */
0651: public String toString() {
0652: return getKey() + "=" + getValue(); //$NON-NLS-1$
0653: }
0654: }
0655:
0656: /**
0657: * Add a new entry with the specified key, value and hash code to the
0658: * specified bucket. It is the responsibility of this method to resize the
0659: * table if appropriate.
0660: *
0661: * Subclass overrides this to alter the behavior of put method.
0662: *
0663: * @param key
0664: * @param value
0665: * @param bucketIndex
0666: */
0667: void addEntry(int key, Object value, int bucketIndex) {
0668: table[bucketIndex] = new Entry(key, value, table[bucketIndex]);
0669: if (size++ >= threshold) {
0670: resize(2 * table.length);
0671: }
0672: }
0673:
0674: /**
0675: * Like addEntry except that this version is used when creating entries as
0676: * part of Map construction or "pseudo-construction" (cloning,
0677: * deserialization). This version needn't worry about resizing the table.
0678: *
0679: * Subclass overrides this to alter the behavior of HashMap(Map), clone, and
0680: * readObject.
0681: *
0682: * @param key
0683: * @param value
0684: * @param bucketIndex
0685: */
0686: void createEntry(int key, Object value, int bucketIndex) {
0687: table[bucketIndex] = new Entry(key, value, table[bucketIndex]);
0688: size++;
0689: }
0690:
0691: private abstract class HashIterator implements Iterator {
0692: Entry next; // next entry to return
0693: int expectedModCount; // For fast-fail
0694: int index; // current slot
0695: Entry current; // current entry
0696:
0697: HashIterator() {
0698: expectedModCount = modCount;
0699: Entry[] t = table;
0700: int i = t.length;
0701: Entry n = null;
0702: if (size != 0) { // advance to first entry
0703: while (i > 0 && (n = t[--i]) == null) {
0704: /* NoOp*/;
0705: }
0706: }
0707: next = n;
0708: index = i;
0709: }
0710:
0711: /**
0712: * @see java.util.Iterator#hasNext()
0713: */
0714: public boolean hasNext() {
0715: return next != null;
0716: }
0717:
0718: Entry nextEntry() {
0719: if (modCount != expectedModCount) {
0720: throw new ConcurrentModificationException();
0721: }
0722: Entry e = next;
0723: if (e == null) {
0724: throw new NoSuchElementException();
0725: }
0726:
0727: Entry n = e.next;
0728: Entry[] t = table;
0729: int i = index;
0730: while (n == null && i > 0) {
0731: n = t[--i];
0732: }
0733: index = i;
0734: next = n;
0735: return current = e;
0736: }
0737:
0738: /**
0739: * @see java.util.Iterator#remove()
0740: */
0741: public void remove() {
0742: if (current == null) {
0743: throw new IllegalStateException();
0744: }
0745: if (modCount != expectedModCount) {
0746: throw new ConcurrentModificationException();
0747: }
0748: int k = current.key;
0749: current = null;
0750: IntHashMap.this .removeEntryForKey(k);
0751: expectedModCount = modCount;
0752: }
0753:
0754: }
0755:
0756: private class ValueIterator extends HashIterator {
0757: /**
0758: * @see java.util.Iterator#next()
0759: */
0760: public Object next() {
0761: return nextEntry().value;
0762: }
0763: }
0764:
0765: private class KeyIterator extends HashIterator {
0766: /**
0767: * @see java.util.Iterator#next()
0768: */
0769: public Object next() {
0770: return new Integer(nextEntry().getKey());
0771: }
0772: }
0773:
0774: private class EntryIterator extends HashIterator {
0775: /**
0776: * @see java.util.Iterator#next()
0777: */
0778: public Object next() {
0779: return nextEntry();
0780: }
0781: }
0782:
0783: // Subclass overrides these to alter behavior of views' iterator() method
0784: Iterator newKeyIterator() {
0785: return new KeyIterator();
0786: }
0787:
0788: Iterator newValueIterator() {
0789: return new ValueIterator();
0790: }
0791:
0792: Iterator newEntryIterator() {
0793: return new EntryIterator();
0794: }
0795:
0796: // Views
0797:
0798: private transient Set entrySet = null;
0799:
0800: /**
0801: * Returns a set view of the keys contained in this map. The set is backed
0802: * by the map, so changes to the map are reflected in the set, and
0803: * vice-versa. The set supports element removal, which removes the
0804: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
0805: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
0806: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
0807: * <tt>addAll</tt> operations.
0808: *
0809: * @return a set view of the keys contained in this map.
0810: */
0811: public Set keySet() {
0812: Set ks = keySet;
0813: return (ks != null ? ks : (keySet = new KeySet()));
0814: }
0815:
0816: private class KeySet extends AbstractSet {
0817: /**
0818: * @see java.util.AbstractCollection#iterator()
0819: */
0820: public Iterator iterator() {
0821: return newKeyIterator();
0822: }
0823:
0824: /**
0825: * @see java.util.AbstractCollection#size()
0826: */
0827: public int size() {
0828: return size;
0829: }
0830:
0831: /**
0832: * @see java.util.AbstractCollection#contains(java.lang.Object)
0833: */
0834: public boolean contains(Object o) {
0835: if (o instanceof Number) {
0836: return containsKey(((Number) o).intValue());
0837: }
0838: return false;
0839: }
0840:
0841: /**
0842: * @see java.util.AbstractCollection#remove(java.lang.Object)
0843: */
0844: public boolean remove(Object o) {
0845: if (o instanceof Number) {
0846: return IntHashMap.this .removeEntryForKey(((Number) o)
0847: .intValue()) != null;
0848: }
0849: return false;
0850: }
0851:
0852: /**
0853: * @see java.util.AbstractCollection#clear()
0854: */
0855: public void clear() {
0856: IntHashMap.this .clear();
0857: }
0858: }
0859:
0860: /**
0861: * Returns a collection view of the values contained in this map. The
0862: * collection is backed by the map, so changes to the map are reflected in
0863: * the collection, and vice-versa. The collection supports element removal,
0864: * which removes the corresponding mapping from this map, via the
0865: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0866: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
0867: * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
0868: * operations.
0869: *
0870: * @return a collection view of the values contained in this map.
0871: */
0872: public Collection values() {
0873: Collection vs = values;
0874: return (vs != null ? vs : (values = new Values()));
0875: }
0876:
0877: private class Values extends AbstractCollection {
0878: /**
0879: * @see java.util.AbstractCollection#iterator()
0880: */
0881: public Iterator iterator() {
0882: return newValueIterator();
0883: }
0884:
0885: /**
0886: * @see java.util.AbstractCollection#size()
0887: */
0888: public int size() {
0889: return size;
0890: }
0891:
0892: /**
0893: * @see java.util.AbstractCollection#contains(java.lang.Object)
0894: */
0895: public boolean contains(Object o) {
0896: return containsValue(o);
0897: }
0898:
0899: /**
0900: * @see java.util.AbstractCollection#clear()
0901: */
0902: public void clear() {
0903: IntHashMap.this .clear();
0904: }
0905: }
0906:
0907: /**
0908: * Returns a collection view of the mappings contained in this map. Each
0909: * element in the returned collection is a <tt>Map.Entry</tt>. The
0910: * collection is backed by the map, so changes to the map are reflected in
0911: * the collection, and vice-versa. The collection supports element removal,
0912: * which removes the corresponding mapping from the map, via the
0913: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
0914: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
0915: * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
0916: * operations.
0917: *
0918: * @return a collection view of the mappings contained in this map.
0919: * @see Map.Entry
0920: */
0921: public Set entrySet() {
0922: Set es = entrySet;
0923: return (es != null ? es : (entrySet = new EntrySet()));
0924: }
0925:
0926: private class EntrySet extends AbstractSet {
0927: /**
0928: * @see java.util.AbstractCollection#iterator()
0929: */
0930: public Iterator iterator() {
0931: return newEntryIterator();
0932: }
0933:
0934: /**
0935: * @see java.util.AbstractCollection#contains(java.lang.Object)
0936: */
0937: public boolean contains(Object o) {
0938: if (!(o instanceof Entry)) {
0939: return false;
0940: }
0941: Entry e = (Entry) o;
0942: Entry candidate = getEntry(e.getKey());
0943: return candidate != null && candidate.equals(e);
0944: }
0945:
0946: /**
0947: * @see java.util.AbstractCollection#remove(java.lang.Object)
0948: */
0949: public boolean remove(Object o) {
0950: return removeMapping(o) != null;
0951: }
0952:
0953: /**
0954: * @see java.util.AbstractCollection#size()
0955: */
0956: public int size() {
0957: return size;
0958: }
0959:
0960: /**
0961: * @see java.util.AbstractCollection#clear()
0962: */
0963: public void clear() {
0964: IntHashMap.this .clear();
0965: }
0966: }
0967:
0968: /**
0969: * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
0970: * serialize it).
0971: *
0972: * @param s
0973: * The ObjectOutputStream
0974: * @throws IOException
0975: *
0976: * @serialData The <i>capacity</i> of the HashMap (the length of the bucket
0977: * array) is emitted (int), followed by the <i>size</i> of the
0978: * HashMap (the number of key-value mappings), followed by the
0979: * key (Object) and value (Object) for each key-value mapping
0980: * represented by the HashMap The key-value mappings are emitted
0981: * in the order that they are returned by
0982: * <tt>entrySet().iterator()</tt>.
0983: *
0984: */
0985: private void writeObject(java.io.ObjectOutputStream s)
0986: throws IOException {
0987: // Write out the threshold, loadfactor, and any hidden stuff
0988: s.defaultWriteObject();
0989:
0990: // Write out number of buckets
0991: s.writeInt(table.length);
0992:
0993: // Write out size (number of Mappings)
0994: s.writeInt(size);
0995:
0996: // Write out keys and values (alternating)
0997: for (Iterator i = entrySet().iterator(); i.hasNext();) {
0998: Entry e = (Entry) i.next();
0999: s.writeInt(e.getKey());
1000: s.writeObject(e.getValue());
1001: }
1002: }
1003:
1004: private static final long serialVersionUID = 362498820763181265L;
1005:
1006: /**
1007: * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
1008: * deserialize it).
1009: *
1010: * @param s
1011: * @throws IOException
1012: * @throws ClassNotFoundException
1013: */
1014: private void readObject(java.io.ObjectInputStream s)
1015: throws IOException, ClassNotFoundException {
1016: // Read in the threshold, loadfactor, and any hidden stuff
1017: s.defaultReadObject();
1018:
1019: // Read in number of buckets and allocate the bucket array;
1020: int numBuckets = s.readInt();
1021: table = new Entry[numBuckets];
1022:
1023: init(); // Give subclass a chance to do its thing.
1024:
1025: // Read in size (number of Mappings)
1026: int size = s.readInt();
1027:
1028: // Read the keys and values, and put the mappings in the HashMap
1029: for (int i = 0; i < size; i++) {
1030: int key = s.readInt();
1031: Object value = s.readObject();
1032: putForCreate(key, value);
1033: }
1034: }
1035:
1036: // These methods are used when serializing HashSets
1037: int capacity() {
1038: return table.length;
1039: }
1040:
1041: float loadFactor() {
1042: return loadFactor;
1043: }
1044: }
|