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