0001: /*
0002: * Copyright 2003-2005 The Apache Software Foundation
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License");
0005: * you may not use this file except in compliance with the License.
0006: * You may obtain a copy of the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS,
0012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013: * See the License for the specific language governing permissions and
0014: * limitations under the License.
0015: */
0016: package org.apache.commons.collections.map;
0017:
0018: import java.io.IOException;
0019: import java.io.ObjectInputStream;
0020: import java.io.ObjectOutputStream;
0021: import java.util.AbstractCollection;
0022: import java.util.AbstractMap;
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: import org.apache.commons.collections.IterableMap;
0032: import org.apache.commons.collections.KeyValue;
0033: import org.apache.commons.collections.MapIterator;
0034: import org.apache.commons.collections.iterators.EmptyIterator;
0035: import org.apache.commons.collections.iterators.EmptyMapIterator;
0036:
0037: /**
0038: * An abstract implementation of a hash-based map which provides numerous points for
0039: * subclasses to override.
0040: * <p>
0041: * This class implements all the features necessary for a subclass hash-based map.
0042: * Key-value entries are stored in instances of the <code>HashEntry</code> class,
0043: * which can be overridden and replaced. The iterators can similarly be replaced,
0044: * without the need to replace the KeySet, EntrySet and Values view classes.
0045: * <p>
0046: * Overridable methods are provided to change the default hashing behaviour, and
0047: * to change how entries are added to and removed from the map. Hopefully, all you
0048: * need for unusual subclasses is here.
0049: * <p>
0050: * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
0051: * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
0052: * This extends clause will be removed in v4.0.
0053: *
0054: * @since Commons Collections 3.0
0055: * @version $Revision: 171349 $ $Date: 2005-05-22 18:48:56 +0100 (Sun, 22 May 2005) $
0056: *
0057: * @author java util HashMap
0058: * @author Stephen Colebourne
0059: * @author Christian Siefkes
0060: */
0061: public class AbstractHashedMap extends AbstractMap implements
0062: IterableMap {
0063:
0064: protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
0065: protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
0066: protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
0067: protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
0068: protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
0069: protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
0070:
0071: /** The default capacity to use */
0072: protected static final int DEFAULT_CAPACITY = 16;
0073: /** The default threshold to use */
0074: protected static final int DEFAULT_THRESHOLD = 12;
0075: /** The default load factor to use */
0076: protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
0077: /** The maximum capacity allowed */
0078: protected static final int MAXIMUM_CAPACITY = 1 << 30;
0079: /** An object for masking null */
0080: protected static final Object NULL = new Object();
0081:
0082: /** Load factor, normally 0.75 */
0083: protected transient float loadFactor;
0084: /** The size of the map */
0085: protected transient int size;
0086: /** Map entries */
0087: protected transient HashEntry[] data;
0088: /** Size at which to rehash */
0089: protected transient int threshold;
0090: /** Modification count for iterators */
0091: protected transient int modCount;
0092: /** Entry set */
0093: protected transient EntrySet entrySet;
0094: /** Key set */
0095: protected transient KeySet keySet;
0096: /** Values */
0097: protected transient Values values;
0098:
0099: /**
0100: * Constructor only used in deserialization, do not use otherwise.
0101: */
0102: protected AbstractHashedMap() {
0103: super ();
0104: }
0105:
0106: /**
0107: * Constructor which performs no validation on the passed in parameters.
0108: *
0109: * @param initialCapacity the initial capacity, must be a power of two
0110: * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f
0111: * @param threshold the threshold, must be sensible
0112: */
0113: protected AbstractHashedMap(int initialCapacity, float loadFactor,
0114: int threshold) {
0115: super ();
0116: this .loadFactor = loadFactor;
0117: this .data = new HashEntry[initialCapacity];
0118: this .threshold = threshold;
0119: init();
0120: }
0121:
0122: /**
0123: * Constructs a new, empty map with the specified initial capacity and
0124: * default load factor.
0125: *
0126: * @param initialCapacity the initial capacity
0127: * @throws IllegalArgumentException if the initial capacity is less than one
0128: */
0129: protected AbstractHashedMap(int initialCapacity) {
0130: this (initialCapacity, DEFAULT_LOAD_FACTOR);
0131: }
0132:
0133: /**
0134: * Constructs a new, empty map with the specified initial capacity and
0135: * load factor.
0136: *
0137: * @param initialCapacity the initial capacity
0138: * @param loadFactor the load factor
0139: * @throws IllegalArgumentException if the initial capacity is less than one
0140: * @throws IllegalArgumentException if the load factor is less than or equal to zero
0141: */
0142: protected AbstractHashedMap(int initialCapacity, float loadFactor) {
0143: super ();
0144: if (initialCapacity < 1) {
0145: throw new IllegalArgumentException(
0146: "Initial capacity must be greater than 0");
0147: }
0148: if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
0149: throw new IllegalArgumentException(
0150: "Load factor must be greater than 0");
0151: }
0152: this .loadFactor = loadFactor;
0153: initialCapacity = calculateNewCapacity(initialCapacity);
0154: this .threshold = calculateThreshold(initialCapacity, loadFactor);
0155: this .data = new HashEntry[initialCapacity];
0156: init();
0157: }
0158:
0159: /**
0160: * Constructor copying elements from another map.
0161: *
0162: * @param map the map to copy
0163: * @throws NullPointerException if the map is null
0164: */
0165: protected AbstractHashedMap(Map map) {
0166: this (Math.max(2 * map.size(), DEFAULT_CAPACITY),
0167: DEFAULT_LOAD_FACTOR);
0168: putAll(map);
0169: }
0170:
0171: /**
0172: * Initialise subclasses during construction, cloning or deserialization.
0173: */
0174: protected void init() {
0175: }
0176:
0177: //-----------------------------------------------------------------------
0178: /**
0179: * Gets the value mapped to the key specified.
0180: *
0181: * @param key the key
0182: * @return the mapped value, null if no match
0183: */
0184: public Object get(Object key) {
0185: key = convertKey(key);
0186: int hashCode = hash(key);
0187: HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
0188: while (entry != null) {
0189: if (entry.hashCode == hashCode
0190: && isEqualKey(key, entry.key)) {
0191: return entry.getValue();
0192: }
0193: entry = entry.next;
0194: }
0195: return null;
0196: }
0197:
0198: /**
0199: * Gets the size of the map.
0200: *
0201: * @return the size
0202: */
0203: public int size() {
0204: return size;
0205: }
0206:
0207: /**
0208: * Checks whether the map is currently empty.
0209: *
0210: * @return true if the map is currently size zero
0211: */
0212: public boolean isEmpty() {
0213: return (size == 0);
0214: }
0215:
0216: //-----------------------------------------------------------------------
0217: /**
0218: * Checks whether the map contains the specified key.
0219: *
0220: * @param key the key to search for
0221: * @return true if the map contains the key
0222: */
0223: public boolean containsKey(Object key) {
0224: key = convertKey(key);
0225: int hashCode = hash(key);
0226: HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
0227: while (entry != null) {
0228: if (entry.hashCode == hashCode
0229: && isEqualKey(key, entry.key)) {
0230: return true;
0231: }
0232: entry = entry.next;
0233: }
0234: return false;
0235: }
0236:
0237: /**
0238: * Checks whether the map contains the specified value.
0239: *
0240: * @param value the value to search for
0241: * @return true if the map contains the value
0242: */
0243: public boolean containsValue(Object value) {
0244: if (value == null) {
0245: for (int i = 0, isize = data.length; i < isize; i++) {
0246: HashEntry entry = data[i];
0247: while (entry != null) {
0248: if (entry.getValue() == null) {
0249: return true;
0250: }
0251: entry = entry.next;
0252: }
0253: }
0254: } else {
0255: for (int i = 0, isize = data.length; i < isize; i++) {
0256: HashEntry entry = data[i];
0257: while (entry != null) {
0258: if (isEqualValue(value, entry.getValue())) {
0259: return true;
0260: }
0261: entry = entry.next;
0262: }
0263: }
0264: }
0265: return false;
0266: }
0267:
0268: //-----------------------------------------------------------------------
0269: /**
0270: * Puts a key-value mapping into this map.
0271: *
0272: * @param key the key to add
0273: * @param value the value to add
0274: * @return the value previously mapped to this key, null if none
0275: */
0276: public Object put(Object key, Object value) {
0277: key = convertKey(key);
0278: int hashCode = hash(key);
0279: int index = hashIndex(hashCode, data.length);
0280: HashEntry entry = data[index];
0281: while (entry != null) {
0282: if (entry.hashCode == hashCode
0283: && isEqualKey(key, entry.key)) {
0284: Object oldValue = entry.getValue();
0285: updateEntry(entry, value);
0286: return oldValue;
0287: }
0288: entry = entry.next;
0289: }
0290:
0291: addMapping(index, hashCode, key, value);
0292: return null;
0293: }
0294:
0295: /**
0296: * Puts all the values from the specified map into this map.
0297: * <p>
0298: * This implementation iterates around the specified map and
0299: * uses {@link #put(Object, Object)}.
0300: *
0301: * @param map the map to add
0302: * @throws NullPointerException if the map is null
0303: */
0304: public void putAll(Map map) {
0305: int mapSize = map.size();
0306: if (mapSize == 0) {
0307: return;
0308: }
0309: int newSize = (int) ((size + mapSize) / loadFactor + 1);
0310: ensureCapacity(calculateNewCapacity(newSize));
0311: for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
0312: Map.Entry entry = (Map.Entry) it.next();
0313: put(entry.getKey(), entry.getValue());
0314: }
0315: }
0316:
0317: /**
0318: * Removes the specified mapping from this map.
0319: *
0320: * @param key the mapping to remove
0321: * @return the value mapped to the removed key, null if key not in map
0322: */
0323: public Object remove(Object key) {
0324: key = convertKey(key);
0325: int hashCode = hash(key);
0326: int index = hashIndex(hashCode, data.length);
0327: HashEntry entry = data[index];
0328: HashEntry previous = null;
0329: while (entry != null) {
0330: if (entry.hashCode == hashCode
0331: && isEqualKey(key, entry.key)) {
0332: Object oldValue = entry.getValue();
0333: removeMapping(entry, index, previous);
0334: return oldValue;
0335: }
0336: previous = entry;
0337: entry = entry.next;
0338: }
0339: return null;
0340: }
0341:
0342: /**
0343: * Clears the map, resetting the size to zero and nullifying references
0344: * to avoid garbage collection issues.
0345: */
0346: public void clear() {
0347: modCount++;
0348: HashEntry[] data = this .data;
0349: for (int i = data.length - 1; i >= 0; i--) {
0350: data[i] = null;
0351: }
0352: size = 0;
0353: }
0354:
0355: //-----------------------------------------------------------------------
0356: /**
0357: * Converts input keys to another object for storage in the map.
0358: * This implementation masks nulls.
0359: * Subclasses can override this to perform alternate key conversions.
0360: * <p>
0361: * The reverse conversion can be changed, if required, by overriding the
0362: * getKey() method in the hash entry.
0363: *
0364: * @param key the key convert
0365: * @return the converted key
0366: */
0367: protected Object convertKey(Object key) {
0368: return (key == null ? NULL : key);
0369: }
0370:
0371: /**
0372: * Gets the hash code for the key specified.
0373: * This implementation uses the additional hashing routine from JDK1.4.
0374: * Subclasses can override this to return alternate hash codes.
0375: *
0376: * @param key the key to get a hash code for
0377: * @return the hash code
0378: */
0379: protected int hash(Object key) {
0380: // same as JDK 1.4
0381: int h = key.hashCode();
0382: h += ~(h << 9);
0383: h ^= (h >>> 14);
0384: h += (h << 4);
0385: h ^= (h >>> 10);
0386: return h;
0387: }
0388:
0389: /**
0390: * Compares two keys, in internal converted form, to see if they are equal.
0391: * This implementation uses the equals method and assumes neither key is null.
0392: * Subclasses can override this to match differently.
0393: *
0394: * @param key1 the first key to compare passed in from outside
0395: * @param key2 the second key extracted from the entry via <code>entry.key</code>
0396: * @return true if equal
0397: */
0398: protected boolean isEqualKey(Object key1, Object key2) {
0399: return (key1 == key2 || key1.equals(key2));
0400: }
0401:
0402: /**
0403: * Compares two values, in external form, to see if they are equal.
0404: * This implementation uses the equals method and assumes neither value is null.
0405: * Subclasses can override this to match differently.
0406: *
0407: * @param value1 the first value to compare passed in from outside
0408: * @param value2 the second value extracted from the entry via <code>getValue()</code>
0409: * @return true if equal
0410: */
0411: protected boolean isEqualValue(Object value1, Object value2) {
0412: return (value1 == value2 || value1.equals(value2));
0413: }
0414:
0415: /**
0416: * Gets the index into the data storage for the hashCode specified.
0417: * This implementation uses the least significant bits of the hashCode.
0418: * Subclasses can override this to return alternate bucketing.
0419: *
0420: * @param hashCode the hash code to use
0421: * @param dataSize the size of the data to pick a bucket from
0422: * @return the bucket index
0423: */
0424: protected int hashIndex(int hashCode, int dataSize) {
0425: return hashCode & (dataSize - 1);
0426: }
0427:
0428: //-----------------------------------------------------------------------
0429: /**
0430: * Gets the entry mapped to the key specified.
0431: * <p>
0432: * This method exists for subclasses that may need to perform a multi-step
0433: * process accessing the entry. The public methods in this class don't use this
0434: * method to gain a small performance boost.
0435: *
0436: * @param key the key
0437: * @return the entry, null if no match
0438: */
0439: protected HashEntry getEntry(Object key) {
0440: key = convertKey(key);
0441: int hashCode = hash(key);
0442: HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
0443: while (entry != null) {
0444: if (entry.hashCode == hashCode
0445: && isEqualKey(key, entry.key)) {
0446: return entry;
0447: }
0448: entry = entry.next;
0449: }
0450: return null;
0451: }
0452:
0453: //-----------------------------------------------------------------------
0454: /**
0455: * Updates an existing key-value mapping to change the value.
0456: * <p>
0457: * This implementation calls <code>setValue()</code> on the entry.
0458: * Subclasses could override to handle changes to the map.
0459: *
0460: * @param entry the entry to update
0461: * @param newValue the new value to store
0462: */
0463: protected void updateEntry(HashEntry entry, Object newValue) {
0464: entry.setValue(newValue);
0465: }
0466:
0467: /**
0468: * Reuses an existing key-value mapping, storing completely new data.
0469: * <p>
0470: * This implementation sets all the data fields on the entry.
0471: * Subclasses could populate additional entry fields.
0472: *
0473: * @param entry the entry to update, not null
0474: * @param hashIndex the index in the data array
0475: * @param hashCode the hash code of the key to add
0476: * @param key the key to add
0477: * @param value the value to add
0478: */
0479: protected void reuseEntry(HashEntry entry, int hashIndex,
0480: int hashCode, Object key, Object value) {
0481: entry.next = data[hashIndex];
0482: entry.hashCode = hashCode;
0483: entry.key = key;
0484: entry.value = value;
0485: }
0486:
0487: //-----------------------------------------------------------------------
0488: /**
0489: * Adds a new key-value mapping into this map.
0490: * <p>
0491: * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
0492: * and <code>checkCapacity()</code>.
0493: * It also handles changes to <code>modCount</code> and <code>size</code>.
0494: * Subclasses could override to fully control adds to the map.
0495: *
0496: * @param hashIndex the index into the data array to store at
0497: * @param hashCode the hash code of the key to add
0498: * @param key the key to add
0499: * @param value the value to add
0500: */
0501: protected void addMapping(int hashIndex, int hashCode, Object key,
0502: Object value) {
0503: modCount++;
0504: HashEntry entry = createEntry(data[hashIndex], hashCode, key,
0505: value);
0506: addEntry(entry, hashIndex);
0507: size++;
0508: checkCapacity();
0509: }
0510:
0511: /**
0512: * Creates an entry to store the key-value data.
0513: * <p>
0514: * This implementation creates a new HashEntry instance.
0515: * Subclasses can override this to return a different storage class,
0516: * or implement caching.
0517: *
0518: * @param next the next entry in sequence
0519: * @param hashCode the hash code to use
0520: * @param key the key to store
0521: * @param value the value to store
0522: * @return the newly created entry
0523: */
0524: protected HashEntry createEntry(HashEntry next, int hashCode,
0525: Object key, Object value) {
0526: return new HashEntry(next, hashCode, key, value);
0527: }
0528:
0529: /**
0530: * Adds an entry into this map.
0531: * <p>
0532: * This implementation adds the entry to the data storage table.
0533: * Subclasses could override to handle changes to the map.
0534: *
0535: * @param entry the entry to add
0536: * @param hashIndex the index into the data array to store at
0537: */
0538: protected void addEntry(HashEntry entry, int hashIndex) {
0539: data[hashIndex] = entry;
0540: }
0541:
0542: //-----------------------------------------------------------------------
0543: /**
0544: * Removes a mapping from the map.
0545: * <p>
0546: * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
0547: * It also handles changes to <code>modCount</code> and <code>size</code>.
0548: * Subclasses could override to fully control removals from the map.
0549: *
0550: * @param entry the entry to remove
0551: * @param hashIndex the index into the data structure
0552: * @param previous the previous entry in the chain
0553: */
0554: protected void removeMapping(HashEntry entry, int hashIndex,
0555: HashEntry previous) {
0556: modCount++;
0557: removeEntry(entry, hashIndex, previous);
0558: size--;
0559: destroyEntry(entry);
0560: }
0561:
0562: /**
0563: * Removes an entry from the chain stored in a particular index.
0564: * <p>
0565: * This implementation removes the entry from the data storage table.
0566: * The size is not updated.
0567: * Subclasses could override to handle changes to the map.
0568: *
0569: * @param entry the entry to remove
0570: * @param hashIndex the index into the data structure
0571: * @param previous the previous entry in the chain
0572: */
0573: protected void removeEntry(HashEntry entry, int hashIndex,
0574: HashEntry previous) {
0575: if (previous == null) {
0576: data[hashIndex] = entry.next;
0577: } else {
0578: previous.next = entry.next;
0579: }
0580: }
0581:
0582: /**
0583: * Kills an entry ready for the garbage collector.
0584: * <p>
0585: * This implementation prepares the HashEntry for garbage collection.
0586: * Subclasses can override this to implement caching (override clear as well).
0587: *
0588: * @param entry the entry to destroy
0589: */
0590: protected void destroyEntry(HashEntry entry) {
0591: entry.next = null;
0592: entry.key = null;
0593: entry.value = null;
0594: }
0595:
0596: //-----------------------------------------------------------------------
0597: /**
0598: * Checks the capacity of the map and enlarges it if necessary.
0599: * <p>
0600: * This implementation uses the threshold to check if the map needs enlarging
0601: */
0602: protected void checkCapacity() {
0603: if (size >= threshold) {
0604: int newCapacity = data.length * 2;
0605: if (newCapacity <= MAXIMUM_CAPACITY) {
0606: ensureCapacity(newCapacity);
0607: }
0608: }
0609: }
0610:
0611: /**
0612: * Changes the size of the data structure to the capacity proposed.
0613: *
0614: * @param newCapacity the new capacity of the array (a power of two, less or equal to max)
0615: */
0616: protected void ensureCapacity(int newCapacity) {
0617: int oldCapacity = data.length;
0618: if (newCapacity <= oldCapacity) {
0619: return;
0620: }
0621: if (size == 0) {
0622: threshold = calculateThreshold(newCapacity, loadFactor);
0623: data = new HashEntry[newCapacity];
0624: } else {
0625: HashEntry oldEntries[] = data;
0626: HashEntry newEntries[] = new HashEntry[newCapacity];
0627:
0628: modCount++;
0629: for (int i = oldCapacity - 1; i >= 0; i--) {
0630: HashEntry entry = oldEntries[i];
0631: if (entry != null) {
0632: oldEntries[i] = null; // gc
0633: do {
0634: HashEntry next = entry.next;
0635: int index = hashIndex(entry.hashCode,
0636: newCapacity);
0637: entry.next = newEntries[index];
0638: newEntries[index] = entry;
0639: entry = next;
0640: } while (entry != null);
0641: }
0642: }
0643: threshold = calculateThreshold(newCapacity, loadFactor);
0644: data = newEntries;
0645: }
0646: }
0647:
0648: /**
0649: * Calculates the new capacity of the map.
0650: * This implementation normalizes the capacity to a power of two.
0651: *
0652: * @param proposedCapacity the proposed capacity
0653: * @return the normalized new capacity
0654: */
0655: protected int calculateNewCapacity(int proposedCapacity) {
0656: int newCapacity = 1;
0657: if (proposedCapacity > MAXIMUM_CAPACITY) {
0658: newCapacity = MAXIMUM_CAPACITY;
0659: } else {
0660: while (newCapacity < proposedCapacity) {
0661: newCapacity <<= 1; // multiply by two
0662: }
0663: if (newCapacity > MAXIMUM_CAPACITY) {
0664: newCapacity = MAXIMUM_CAPACITY;
0665: }
0666: }
0667: return newCapacity;
0668: }
0669:
0670: /**
0671: * Calculates the new threshold of the map, where it will be resized.
0672: * This implementation uses the load factor.
0673: *
0674: * @param newCapacity the new capacity
0675: * @param factor the load factor
0676: * @return the new resize threshold
0677: */
0678: protected int calculateThreshold(int newCapacity, float factor) {
0679: return (int) (newCapacity * factor);
0680: }
0681:
0682: //-----------------------------------------------------------------------
0683: /**
0684: * Gets the <code>next</code> field from a <code>HashEntry</code>.
0685: * Used in subclasses that have no visibility of the field.
0686: *
0687: * @param entry the entry to query, must not be null
0688: * @return the <code>next</code> field of the entry
0689: * @throws NullPointerException if the entry is null
0690: * @since Commons Collections 3.1
0691: */
0692: protected HashEntry entryNext(HashEntry entry) {
0693: return entry.next;
0694: }
0695:
0696: /**
0697: * Gets the <code>hashCode</code> field from a <code>HashEntry</code>.
0698: * Used in subclasses that have no visibility of the field.
0699: *
0700: * @param entry the entry to query, must not be null
0701: * @return the <code>hashCode</code> field of the entry
0702: * @throws NullPointerException if the entry is null
0703: * @since Commons Collections 3.1
0704: */
0705: protected int entryHashCode(HashEntry entry) {
0706: return entry.hashCode;
0707: }
0708:
0709: /**
0710: * Gets the <code>key</code> field from a <code>HashEntry</code>.
0711: * Used in subclasses that have no visibility of the field.
0712: *
0713: * @param entry the entry to query, must not be null
0714: * @return the <code>key</code> field of the entry
0715: * @throws NullPointerException if the entry is null
0716: * @since Commons Collections 3.1
0717: */
0718: protected Object entryKey(HashEntry entry) {
0719: return entry.key;
0720: }
0721:
0722: /**
0723: * Gets the <code>value</code> field from a <code>HashEntry</code>.
0724: * Used in subclasses that have no visibility of the field.
0725: *
0726: * @param entry the entry to query, must not be null
0727: * @return the <code>value</code> field of the entry
0728: * @throws NullPointerException if the entry is null
0729: * @since Commons Collections 3.1
0730: */
0731: protected Object entryValue(HashEntry entry) {
0732: return entry.value;
0733: }
0734:
0735: //-----------------------------------------------------------------------
0736: /**
0737: * Gets an iterator over the map.
0738: * Changes made to the iterator affect this map.
0739: * <p>
0740: * A MapIterator returns the keys in the map. It also provides convenient
0741: * methods to get the key and value, and set the value.
0742: * It avoids the need to create an entrySet/keySet/values object.
0743: * It also avoids creating the Map.Entry object.
0744: *
0745: * @return the map iterator
0746: */
0747: public MapIterator mapIterator() {
0748: if (size == 0) {
0749: return EmptyMapIterator.INSTANCE;
0750: }
0751: return new HashMapIterator(this );
0752: }
0753:
0754: /**
0755: * MapIterator implementation.
0756: */
0757: protected static class HashMapIterator extends HashIterator
0758: implements MapIterator {
0759:
0760: protected HashMapIterator(AbstractHashedMap parent) {
0761: super (parent);
0762: }
0763:
0764: public Object next() {
0765: return super .nextEntry().getKey();
0766: }
0767:
0768: public Object getKey() {
0769: HashEntry current = currentEntry();
0770: if (current == null) {
0771: throw new IllegalStateException(
0772: AbstractHashedMap.GETKEY_INVALID);
0773: }
0774: return current.getKey();
0775: }
0776:
0777: public Object getValue() {
0778: HashEntry current = currentEntry();
0779: if (current == null) {
0780: throw new IllegalStateException(
0781: AbstractHashedMap.GETVALUE_INVALID);
0782: }
0783: return current.getValue();
0784: }
0785:
0786: public Object setValue(Object value) {
0787: HashEntry current = currentEntry();
0788: if (current == null) {
0789: throw new IllegalStateException(
0790: AbstractHashedMap.SETVALUE_INVALID);
0791: }
0792: return current.setValue(value);
0793: }
0794: }
0795:
0796: //-----------------------------------------------------------------------
0797: /**
0798: * Gets the entrySet view of the map.
0799: * Changes made to the view affect this map.
0800: * To simply iterate through the entries, use {@link #mapIterator()}.
0801: *
0802: * @return the entrySet view
0803: */
0804: public Set entrySet() {
0805: if (entrySet == null) {
0806: entrySet = new EntrySet(this );
0807: }
0808: return entrySet;
0809: }
0810:
0811: /**
0812: * Creates an entry set iterator.
0813: * Subclasses can override this to return iterators with different properties.
0814: *
0815: * @return the entrySet iterator
0816: */
0817: protected Iterator createEntrySetIterator() {
0818: if (size() == 0) {
0819: return EmptyIterator.INSTANCE;
0820: }
0821: return new EntrySetIterator(this );
0822: }
0823:
0824: /**
0825: * EntrySet implementation.
0826: */
0827: protected static class EntrySet extends AbstractSet {
0828: /** The parent map */
0829: protected final AbstractHashedMap parent;
0830:
0831: protected EntrySet(AbstractHashedMap parent) {
0832: super ();
0833: this .parent = parent;
0834: }
0835:
0836: public int size() {
0837: return parent.size();
0838: }
0839:
0840: public void clear() {
0841: parent.clear();
0842: }
0843:
0844: public boolean contains(Object entry) {
0845: if (entry instanceof Map.Entry) {
0846: Map.Entry e = (Map.Entry) entry;
0847: Entry match = parent.getEntry(e.getKey());
0848: return (match != null && match.equals(e));
0849: }
0850: return false;
0851: }
0852:
0853: public boolean remove(Object obj) {
0854: if (obj instanceof Map.Entry == false) {
0855: return false;
0856: }
0857: if (contains(obj) == false) {
0858: return false;
0859: }
0860: Map.Entry entry = (Map.Entry) obj;
0861: Object key = entry.getKey();
0862: parent.remove(key);
0863: return true;
0864: }
0865:
0866: public Iterator iterator() {
0867: return parent.createEntrySetIterator();
0868: }
0869: }
0870:
0871: /**
0872: * EntrySet iterator.
0873: */
0874: protected static class EntrySetIterator extends HashIterator {
0875:
0876: protected EntrySetIterator(AbstractHashedMap parent) {
0877: super (parent);
0878: }
0879:
0880: public Object next() {
0881: return super .nextEntry();
0882: }
0883: }
0884:
0885: //-----------------------------------------------------------------------
0886: /**
0887: * Gets the keySet view of the map.
0888: * Changes made to the view affect this map.
0889: * To simply iterate through the keys, use {@link #mapIterator()}.
0890: *
0891: * @return the keySet view
0892: */
0893: public Set keySet() {
0894: if (keySet == null) {
0895: keySet = new KeySet(this );
0896: }
0897: return keySet;
0898: }
0899:
0900: /**
0901: * Creates a key set iterator.
0902: * Subclasses can override this to return iterators with different properties.
0903: *
0904: * @return the keySet iterator
0905: */
0906: protected Iterator createKeySetIterator() {
0907: if (size() == 0) {
0908: return EmptyIterator.INSTANCE;
0909: }
0910: return new KeySetIterator(this );
0911: }
0912:
0913: /**
0914: * KeySet implementation.
0915: */
0916: protected static class KeySet extends AbstractSet {
0917: /** The parent map */
0918: protected final AbstractHashedMap parent;
0919:
0920: protected KeySet(AbstractHashedMap parent) {
0921: super ();
0922: this .parent = parent;
0923: }
0924:
0925: public int size() {
0926: return parent.size();
0927: }
0928:
0929: public void clear() {
0930: parent.clear();
0931: }
0932:
0933: public boolean contains(Object key) {
0934: return parent.containsKey(key);
0935: }
0936:
0937: public boolean remove(Object key) {
0938: boolean result = parent.containsKey(key);
0939: parent.remove(key);
0940: return result;
0941: }
0942:
0943: public Iterator iterator() {
0944: return parent.createKeySetIterator();
0945: }
0946: }
0947:
0948: /**
0949: * KeySet iterator.
0950: */
0951: protected static class KeySetIterator extends EntrySetIterator {
0952:
0953: protected KeySetIterator(AbstractHashedMap parent) {
0954: super (parent);
0955: }
0956:
0957: public Object next() {
0958: return super .nextEntry().getKey();
0959: }
0960: }
0961:
0962: //-----------------------------------------------------------------------
0963: /**
0964: * Gets the values view of the map.
0965: * Changes made to the view affect this map.
0966: * To simply iterate through the values, use {@link #mapIterator()}.
0967: *
0968: * @return the values view
0969: */
0970: public Collection values() {
0971: if (values == null) {
0972: values = new Values(this );
0973: }
0974: return values;
0975: }
0976:
0977: /**
0978: * Creates a values iterator.
0979: * Subclasses can override this to return iterators with different properties.
0980: *
0981: * @return the values iterator
0982: */
0983: protected Iterator createValuesIterator() {
0984: if (size() == 0) {
0985: return EmptyIterator.INSTANCE;
0986: }
0987: return new ValuesIterator(this );
0988: }
0989:
0990: /**
0991: * Values implementation.
0992: */
0993: protected static class Values extends AbstractCollection {
0994: /** The parent map */
0995: protected final AbstractHashedMap parent;
0996:
0997: protected Values(AbstractHashedMap parent) {
0998: super ();
0999: this .parent = parent;
1000: }
1001:
1002: public int size() {
1003: return parent.size();
1004: }
1005:
1006: public void clear() {
1007: parent.clear();
1008: }
1009:
1010: public boolean contains(Object value) {
1011: return parent.containsValue(value);
1012: }
1013:
1014: public Iterator iterator() {
1015: return parent.createValuesIterator();
1016: }
1017: }
1018:
1019: /**
1020: * Values iterator.
1021: */
1022: protected static class ValuesIterator extends HashIterator {
1023:
1024: protected ValuesIterator(AbstractHashedMap parent) {
1025: super (parent);
1026: }
1027:
1028: public Object next() {
1029: return super .nextEntry().getValue();
1030: }
1031: }
1032:
1033: //-----------------------------------------------------------------------
1034: /**
1035: * HashEntry used to store the data.
1036: * <p>
1037: * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code>
1038: * then you will not be able to access the protected fields.
1039: * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> exist
1040: * to provide the necessary access.
1041: */
1042: protected static class HashEntry implements Map.Entry, KeyValue {
1043: /** The next entry in the hash chain */
1044: protected HashEntry next;
1045: /** The hash code of the key */
1046: protected int hashCode;
1047: /** The key */
1048: protected Object key;
1049: /** The value */
1050: protected Object value;
1051:
1052: protected HashEntry(HashEntry next, int hashCode, Object key,
1053: Object value) {
1054: super ();
1055: this .next = next;
1056: this .hashCode = hashCode;
1057: this .key = key;
1058: this .value = value;
1059: }
1060:
1061: public Object getKey() {
1062: return (key == NULL ? null : key);
1063: }
1064:
1065: public Object getValue() {
1066: return value;
1067: }
1068:
1069: public Object setValue(Object value) {
1070: Object old = this .value;
1071: this .value = value;
1072: return old;
1073: }
1074:
1075: public boolean equals(Object obj) {
1076: if (obj == this ) {
1077: return true;
1078: }
1079: if (obj instanceof Map.Entry == false) {
1080: return false;
1081: }
1082: Map.Entry other = (Map.Entry) obj;
1083: return (getKey() == null ? other.getKey() == null
1084: : getKey().equals(other.getKey()))
1085: && (getValue() == null ? other.getValue() == null
1086: : getValue().equals(other.getValue()));
1087: }
1088:
1089: public int hashCode() {
1090: return (getKey() == null ? 0 : getKey().hashCode())
1091: ^ (getValue() == null ? 0 : getValue().hashCode());
1092: }
1093:
1094: public String toString() {
1095: return new StringBuffer().append(getKey()).append('=')
1096: .append(getValue()).toString();
1097: }
1098: }
1099:
1100: /**
1101: * Base Iterator
1102: */
1103: protected static abstract class HashIterator implements Iterator {
1104:
1105: /** The parent map */
1106: protected final AbstractHashedMap parent;
1107: /** The current index into the array of buckets */
1108: protected int hashIndex;
1109: /** The last returned entry */
1110: protected HashEntry last;
1111: /** The next entry */
1112: protected HashEntry next;
1113: /** The modification count expected */
1114: protected int expectedModCount;
1115:
1116: protected HashIterator(AbstractHashedMap parent) {
1117: super ();
1118: this .parent = parent;
1119: HashEntry[] data = parent.data;
1120: int i = data.length;
1121: HashEntry next = null;
1122: while (i > 0 && next == null) {
1123: next = data[--i];
1124: }
1125: this .next = next;
1126: this .hashIndex = i;
1127: this .expectedModCount = parent.modCount;
1128: }
1129:
1130: public boolean hasNext() {
1131: return (next != null);
1132: }
1133:
1134: protected HashEntry nextEntry() {
1135: if (parent.modCount != expectedModCount) {
1136: throw new ConcurrentModificationException();
1137: }
1138: HashEntry newCurrent = next;
1139: if (newCurrent == null) {
1140: throw new NoSuchElementException(
1141: AbstractHashedMap.NO_NEXT_ENTRY);
1142: }
1143: HashEntry[] data = parent.data;
1144: int i = hashIndex;
1145: HashEntry n = newCurrent.next;
1146: while (n == null && i > 0) {
1147: n = data[--i];
1148: }
1149: next = n;
1150: hashIndex = i;
1151: last = newCurrent;
1152: return newCurrent;
1153: }
1154:
1155: protected HashEntry currentEntry() {
1156: return last;
1157: }
1158:
1159: public void remove() {
1160: if (last == null) {
1161: throw new IllegalStateException(
1162: AbstractHashedMap.REMOVE_INVALID);
1163: }
1164: if (parent.modCount != expectedModCount) {
1165: throw new ConcurrentModificationException();
1166: }
1167: parent.remove(last.getKey());
1168: last = null;
1169: expectedModCount = parent.modCount;
1170: }
1171:
1172: public String toString() {
1173: if (last != null) {
1174: return "Iterator[" + last.getKey() + "="
1175: + last.getValue() + "]";
1176: } else {
1177: return "Iterator[]";
1178: }
1179: }
1180: }
1181:
1182: //-----------------------------------------------------------------------
1183: /**
1184: * Writes the map data to the stream. This method must be overridden if a
1185: * subclass must be setup before <code>put()</code> is used.
1186: * <p>
1187: * Serialization is not one of the JDK's nicest topics. Normal serialization will
1188: * initialise the superclass before the subclass. Sometimes however, this isn't
1189: * what you want, as in this case the <code>put()</code> method on read can be
1190: * affected by subclass state.
1191: * <p>
1192: * The solution adopted here is to serialize the state data of this class in
1193: * this protected method. This method must be called by the
1194: * <code>writeObject()</code> of the first serializable subclass.
1195: * <p>
1196: * Subclasses may override if they have a specific field that must be present
1197: * on read before this implementation will work. Generally, the read determines
1198: * what must be serialized here, if anything.
1199: *
1200: * @param out the output stream
1201: */
1202: protected void doWriteObject(ObjectOutputStream out)
1203: throws IOException {
1204: out.writeFloat(loadFactor);
1205: out.writeInt(data.length);
1206: out.writeInt(size);
1207: for (MapIterator it = mapIterator(); it.hasNext();) {
1208: out.writeObject(it.next());
1209: out.writeObject(it.getValue());
1210: }
1211: }
1212:
1213: /**
1214: * Reads the map data from the stream. This method must be overridden if a
1215: * subclass must be setup before <code>put()</code> is used.
1216: * <p>
1217: * Serialization is not one of the JDK's nicest topics. Normal serialization will
1218: * initialise the superclass before the subclass. Sometimes however, this isn't
1219: * what you want, as in this case the <code>put()</code> method on read can be
1220: * affected by subclass state.
1221: * <p>
1222: * The solution adopted here is to deserialize the state data of this class in
1223: * this protected method. This method must be called by the
1224: * <code>readObject()</code> of the first serializable subclass.
1225: * <p>
1226: * Subclasses may override if the subclass has a specific field that must be present
1227: * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
1228: *
1229: * @param in the input stream
1230: */
1231: protected void doReadObject(ObjectInputStream in)
1232: throws IOException, ClassNotFoundException {
1233: loadFactor = in.readFloat();
1234: int capacity = in.readInt();
1235: int size = in.readInt();
1236: init();
1237: threshold = calculateThreshold(capacity, loadFactor);
1238: data = new HashEntry[capacity];
1239: for (int i = 0; i < size; i++) {
1240: Object key = in.readObject();
1241: Object value = in.readObject();
1242: put(key, value);
1243: }
1244: }
1245:
1246: //-----------------------------------------------------------------------
1247: /**
1248: * Clones the map without cloning the keys or values.
1249: * <p>
1250: * To implement <code>clone()</code>, a subclass must implement the
1251: * <code>Cloneable</code> interface and make this method public.
1252: *
1253: * @return a shallow clone
1254: */
1255: protected Object clone() {
1256: try {
1257: AbstractHashedMap cloned = (AbstractHashedMap) super
1258: .clone();
1259: cloned.data = new HashEntry[data.length];
1260: cloned.entrySet = null;
1261: cloned.keySet = null;
1262: cloned.values = null;
1263: cloned.modCount = 0;
1264: cloned.size = 0;
1265: cloned.init();
1266: cloned.putAll(this );
1267: return cloned;
1268:
1269: } catch (CloneNotSupportedException ex) {
1270: return null; // should never happen
1271: }
1272: }
1273:
1274: /**
1275: * Compares this map with another.
1276: *
1277: * @param obj the object to compare to
1278: * @return true if equal
1279: */
1280: public boolean equals(Object obj) {
1281: if (obj == this ) {
1282: return true;
1283: }
1284: if (obj instanceof Map == false) {
1285: return false;
1286: }
1287: Map map = (Map) obj;
1288: if (map.size() != size()) {
1289: return false;
1290: }
1291: MapIterator it = mapIterator();
1292: try {
1293: while (it.hasNext()) {
1294: Object key = it.next();
1295: Object value = it.getValue();
1296: if (value == null) {
1297: if (map.get(key) != null
1298: || map.containsKey(key) == false) {
1299: return false;
1300: }
1301: } else {
1302: if (value.equals(map.get(key)) == false) {
1303: return false;
1304: }
1305: }
1306: }
1307: } catch (ClassCastException ignored) {
1308: return false;
1309: } catch (NullPointerException ignored) {
1310: return false;
1311: }
1312: return true;
1313: }
1314:
1315: /**
1316: * Gets the standard Map hashCode.
1317: *
1318: * @return the hash code defined in the Map interface
1319: */
1320: public int hashCode() {
1321: int total = 0;
1322: Iterator it = createEntrySetIterator();
1323: while (it.hasNext()) {
1324: total += it.next().hashCode();
1325: }
1326: return total;
1327: }
1328:
1329: /**
1330: * Gets the map as a String.
1331: *
1332: * @return a string version of the map
1333: */
1334: public String toString() {
1335: if (size() == 0) {
1336: return "{}";
1337: }
1338: StringBuffer buf = new StringBuffer(32 * size());
1339: buf.append('{');
1340:
1341: MapIterator it = mapIterator();
1342: boolean hasNext = it.hasNext();
1343: while (hasNext) {
1344: Object key = it.next();
1345: Object value = it.getValue();
1346: buf.append(key == this ? "(this Map)" : key).append('=')
1347: .append(value == this ? "(this Map)" : value);
1348:
1349: hasNext = it.hasNext();
1350: if (hasNext) {
1351: buf.append(',').append(' ');
1352: }
1353: }
1354:
1355: buf.append('}');
1356: return buf.toString();
1357: }
1358: }
|