/* * %W% %E% * * Copyright 2004 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; import java.util.Map.Entry; /** * This class provides a skeletal implementation of the Map * interface, to minimize the effort required to implement this interface.

* * To implement an unmodifiable map, the programmer needs only to extend this * class and provide an implementation for the entrySet method, which * returns a set-view of the map's mappings. Typically, the returned set * will, in turn, be implemented atop AbstractSet. This set should * not support the add or remove methods, and its iterator * should not support the remove method.

* * To implement a modifiable map, the programmer must additionally override * this class's put method (which otherwise throws an * UnsupportedOperationException), and the iterator returned by * entrySet().iterator() must additionally implement its * remove method.

* * The programmer should generally provide a void (no argument) and map * constructor, as per the recommendation in the Map interface * specification.

* * The documentation for each non-abstract methods in this class describes its * implementation in detail. Each of these methods may be overridden if the * map being implemented admits a more efficient implementation.

* * This class is a member of the * * Java Collections Framework. * * @author Josh Bloch * @author Neal Gafter * @version %I%, %G% * @see Map * @see Collection * @since 1.2 */ public abstract class AbstractMap implements Map { /** * Sole constructor. (For invocation by subclass constructors, typically * implicit.) */ protected AbstractMap() { } // Query Operations /** * Returns the number of key-value mappings in this map. If the map * contains more than Integer.MAX_VALUE elements, returns * Integer.MAX_VALUE.

* * This implementation returns entrySet().size(). * * @return the number of key-value mappings in this map. */ public int size() { return entrySet().size(); } /** * Returns true if this map contains no key-value mappings.

* * This implementation returns size() == 0. * * @return true if this map contains no key-value mappings. */ public boolean isEmpty() { return size() == 0; } /** * Returns true if this map maps one or more keys to this value. * More formally, returns true if and only if this map contains * at least one mapping to a value v such that (value==null ? * v==null : value.equals(v)). This operation will probably require * time linear in the map size for most implementations of map.

* * This implementation iterates over entrySet() searching for an entry * with the specified value. If such an entry is found, true is * returned. If the iteration terminates without finding such an entry, * false is returned. Note that this implementation requires * linear time in the size of the map. * * @param value value whose presence in this map is to be tested. * * @return true if this map maps one or more keys to this value. */ public boolean containsValue(Object value) { Iterator> i = entrySet().iterator(); if (value==null) { while (i.hasNext()) { Entry e = i.next(); if (e.getValue()==null) return true; } } else { while (i.hasNext()) { Entry e = i.next(); if (value.equals(e.getValue())) return true; } } return false; } /** * Returns true if this map contains a mapping for the specified * key.

* * This implementation iterates over entrySet() searching for an * entry with the specified key. If such an entry is found, true * is returned. If the iteration terminates without finding such an * entry, false is returned. Note that this implementation * requires linear time in the size of the map; many implementations will * override this method. * * @param key key whose presence in this map is to be tested. * @return true if this map contains a mapping for the specified * key. * * @throws NullPointerException if the key is null and this map * does not permit null keys. */ public boolean containsKey(Object key) { Iterator> i = entrySet().iterator(); if (key==null) { while (i.hasNext()) { Entry e = i.next(); if (e.getKey()==null) return true; } } else { while (i.hasNext()) { Entry e = i.next(); if (key.equals(e.getKey())) return true; } } return false; } /** * Returns the value to which this map maps the specified key. Returns * null if the map contains no mapping for this key. A return * value of null does not necessarily indicate that the * map contains no mapping for the key; it's also possible that the map * explicitly maps the key to null. The containsKey operation * may be used to distinguish these two cases.

* * This implementation iterates over entrySet() searching for an * entry with the specified key. If such an entry is found, the entry's * value is returned. If the iteration terminates without finding such an * entry, null is returned. Note that this implementation * requires linear time in the size of the map; many implementations will * override this method. * * @param key key whose associated value is to be returned. * @return the value to which this map maps the specified key. * * @throws NullPointerException if the key is null and this map * does not permit null keys. * * @see #containsKey(Object) */ public V get(Object key) { Iterator> i = entrySet().iterator(); if (key==null) { while (i.hasNext()) { Entry e = i.next(); if (e.getKey()==null) return e.getValue(); } } else { while (i.hasNext()) { Entry e = i.next(); if (key.equals(e.getKey())) return e.getValue(); } } return null; } // Modification Operations /** * Associates the specified value with the specified key in this map * (optional operation). If the map previously contained a mapping for * this key, the old value is replaced.

* * This implementation always throws an * UnsupportedOperationException. * * @param key key with which the specified value is to be associated. * @param value value to be associated with the specified key. * * @return the previous value associated with specified key, or null * if there was no mapping for key. (A null return can * also indicate that the map previously associated null * with the specified key, if the implementation supports * null values.) * * @throws UnsupportedOperationException if the put operation is * not supported by this map. * * @throws ClassCastException if the class of the specified key or value * prevents it from being stored in this map. * * @throws IllegalArgumentException if some aspect of this key or value * * prevents it from being stored in this map. * * @throws NullPointerException if this map does not permit null * keys or values, and the specified key or value is * null. */ public V put(K key, V value) { throw new UnsupportedOperationException(); } /** * Removes the mapping for this key from this map if present (optional * operation).

* * This implementation iterates over entrySet() searching for an * entry with the specified key. If such an entry is found, its value is * obtained with its getValue operation, the entry is removed * from the Collection (and the backing map) with the iterator's * remove operation, and the saved value is returned. If the * iteration terminates without finding such an entry, null is * returned. Note that this implementation requires linear time in the * size of the map; many implementations will override this method.

* * Note that this implementation throws an * UnsupportedOperationException if the entrySet iterator * does not support the remove method and this map contains a * mapping for the specified key. * * @param key key whose mapping is to be removed from the map. * @return the previous value associated with specified key, or null * if there was no entry for key. (A null return can * also indicate that the map previously associated null * with the specified key, if the implementation supports * null values.) * @throws UnsupportedOperationException if the remove operation * is not supported by this map. */ public V remove(Object key) { Iterator> i = entrySet().iterator(); Entry correctEntry = null; if (key==null) { while (correctEntry==null && i.hasNext()) { Entry e = i.next(); if (e.getKey()==null) correctEntry = e; } } else { while (correctEntry==null && i.hasNext()) { Entry e = i.next(); if (key.equals(e.getKey())) correctEntry = e; } } V oldValue = null; if (correctEntry !=null) { oldValue = correctEntry.getValue(); i.remove(); } return oldValue; } // Bulk Operations /** * Copies all of the mappings from the specified map to this map * (optional operation). These mappings will replace any mappings that * this map had for any of the keys currently in the specified map.

* * This implementation iterates over the specified map's * entrySet() collection, and calls this map's put * operation once for each entry returned by the iteration.

* * Note that this implementation throws an * UnsupportedOperationException if this map does not support * the put operation and the specified map is nonempty. * * @param t mappings to be stored in this map. * * @throws UnsupportedOperationException if the putAll operation * is not supported by this map. * * @throws ClassCastException if the class of a key or value in the * specified map prevents it from being stored in this map. * * @throws IllegalArgumentException if some aspect of a key or value in * the specified map prevents it from being stored in this map. * @throws NullPointerException if the specified map is null, or if * this map does not permit null keys or values, and the * specified map contains null keys or values. */ public void putAll(Map t) { Iterator> i = t.entrySet().iterator(); while (i.hasNext()) { Entry e = i.next(); put(e.getKey(), e.getValue()); } } /** * Removes all mappings from this map (optional operation).

* * This implementation calls entrySet().clear(). * * Note that this implementation throws an * UnsupportedOperationException if the entrySet * does not support the clear operation. * * @throws UnsupportedOperationException clear is not supported * by this map. */ public void clear() { entrySet().clear(); } // Views /** * Each of these fields are initialized to contain an instance of the * appropriate view the first time this view is requested. The views are * stateless, so there's no reason to create more than one of each. */ transient volatile Set keySet = null; transient volatile Collection values = null; /** * Returns a Set view of the keys contained in this map. The Set is * backed by the map, so changes to the map are reflected in the Set, * and vice-versa. (If the map is modified while an iteration over * the Set is in progress, the results of the iteration are undefined.) * The Set supports element removal, which removes the corresponding entry * from the map, via the Iterator.remove, Set.remove, removeAll * retainAll, and clear operations. It does not support the add or * addAll operations.

* * This implementation returns a Set that subclasses * AbstractSet. The subclass's iterator method returns a "wrapper * object" over this map's entrySet() iterator. The size method delegates * to this map's size method and the contains method delegates to this * map's containsKey method.

* * The Set is created the first time this method is called, * and returned in response to all subsequent calls. No synchronization * is performed, so there is a slight chance that multiple calls to this * method will not all return the same Set. * * @return a Set view of the keys contained in this map. */ public Set keySet() { if (keySet == null) { keySet = new AbstractSet() { public Iterator iterator() { return new Iterator() { private Iterator> i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public K next() { return i.next().getKey(); } public void remove() { i.remove(); } }; } public int size() { return AbstractMap.this.size(); } public boolean contains(Object k) { return AbstractMap.this.containsKey(k); } }; } return keySet; } /** * Returns a collection view of the values contained in this map. The * collection is backed by the map, so changes to the map are reflected in * the collection, and vice-versa. (If the map is modified while an * iteration over the collection is in progress, the results of the * iteration are undefined.) The collection supports element removal, * which removes the corresponding entry from the map, via the * Iterator.remove, Collection.remove, * removeAll, retainAll and clear operations. * It does not support the add or addAll operations.

* * This implementation returns a collection that subclasses abstract * collection. The subclass's iterator method returns a "wrapper object" * over this map's entrySet() iterator. The size method * delegates to this map's size method and the contains method delegates * to this map's containsValue method.

* * The collection is created the first time this method is called, and * returned in response to all subsequent calls. No synchronization is * performed, so there is a slight chance that multiple calls to this * method will not all return the same Collection. * * @return a collection view of the values contained in this map. */ public Collection values() { if (values == null) { values = new AbstractCollection() { public Iterator iterator() { return new Iterator() { private Iterator> i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public V next() { return i.next().getValue(); } public void remove() { i.remove(); } }; } public int size() { return AbstractMap.this.size(); } public boolean contains(Object v) { return AbstractMap.this.containsValue(v); } }; } return values; } /** * Returns a set view of the mappings contained in this map. Each element * in this set is a Map.Entry. The set is backed by the map, so changes * to the map are reflected in the set, and vice-versa. (If the map is * modified while an iteration over the set is in progress, the results of * the iteration are undefined.) The set supports element removal, which * removes the corresponding entry from the map, via the * Iterator.remove, Set.remove, removeAll, * retainAll and clear operations. It does not support * the add or addAll operations. * * @return a set view of the mappings contained in this map. */ public abstract Set> entrySet(); // Comparison and hashing /** * Compares the specified object with this map for equality. Returns * true if the given object is also a map and the two maps * represent the same mappings. More formally, two maps t1 and * t2 represent the same mappings if * t1.keySet().equals(t2.keySet()) and for every key k * in t1.keySet(), (t1.get(k)==null ? t2.get(k)==null : * t1.get(k).equals(t2.get(k))) . This ensures that the * equals method works properly across different implementations * of the map interface.

* * This implementation first checks if the specified object is this map; * if so it returns true. Then, it checks if the specified * object is a map whose size is identical to the size of this set; if * not, it returns false. If so, it iterates over this map's * entrySet collection, and checks that the specified map * contains each mapping that this map contains. If the specified map * fails to contain such a mapping, false is returned. If the * iteration completes, true is returned. * * @param o object to be compared for equality with this map. * @return true if the specified object is equal to this map. */ public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Map)) return false; Map t = (Map) o; if (t.size() != size()) return false; try { Iterator> i = entrySet().iterator(); while (i.hasNext()) { Entry e = i.next(); K key = e.getKey(); V value = e.getValue(); if (value == null) { if (!(t.get(key)==null && t.containsKey(key))) return false; } else { if (!value.equals(t.get(key))) return false; } } } catch(ClassCastException unused) { return false; } catch(NullPointerException unused) { return false; } return true; } /** * Returns the hash code value for this map. The hash code of a map is * defined to be the sum of the hash codes of each entry in the map's * entrySet() view. This ensures that t1.equals(t2) * implies that t1.hashCode()==t2.hashCode() for any two maps * t1 and t2, as required by the general contract of * Object.hashCode.

* * This implementation iterates over entrySet(), calling * hashCode on each element (entry) in the Collection, and adding * up the results. * * @return the hash code value for this map. * @see Map.Entry#hashCode() * @see Object#hashCode() * @see Object#equals(Object) * @see Set#equals(Object) */ public int hashCode() { int h = 0; Iterator> i = entrySet().iterator(); while (i.hasNext()) h += i.next().hashCode(); return h; } /** * Returns a string representation of this map. The string representation * consists of a list of key-value mappings in the order returned by the * map's entrySet view's iterator, enclosed in braces * ("{}"). Adjacent mappings are separated by the characters * ", " (comma and space). Each key-value mapping is rendered as * the key followed by an equals sign ("=") followed by the * associated value. Keys and values are converted to strings as by * String.valueOf(Object).

* * This implementation creates an empty string buffer, appends a left * brace, and iterates over the map's entrySet view, appending * the string representation of each map.entry in turn. After * appending each entry except the last, the string ", " is * appended. Finally a right brace is appended. A string is obtained * from the stringbuffer, and returned. * * @return a String representation of this map. */ public String toString() { StringBuffer buf = new StringBuffer(); buf.append("{"); Iterator> i = entrySet().iterator(); boolean hasNext = i.hasNext(); while (hasNext) { Entry e = i.next(); K key = e.getKey(); V value = e.getValue(); if (key == this) buf.append("(this Map)"); else buf.append(key); buf.append("="); if (value == this) buf.append("(this Map)"); else buf.append(value); hasNext = i.hasNext(); if (hasNext) buf.append(", "); } buf.append("}"); return buf.toString(); } /** * Returns a shallow copy of this AbstractMap instance: the keys * and values themselves are not cloned. * * @return a shallow copy of this map. */ protected Object clone() throws CloneNotSupportedException { AbstractMap result = (AbstractMap)super.clone(); result.keySet = null; result.values = null; return result; } /** * Utility method for SimpleEntry and SimpleImmutableEntry. * Test for equality, checking for nulls. */ private static boolean eq(Object o1, Object o2) { return (o1 == null ? o2 == null : o1.equals(o2)); } // Implementation Note: SimpleEntry and SimpleImmutableEntry // are distinct unrelated classes, even though they share // some code. Since you can't add or subtract final-ness // of a field in a subclass, they can't share representations, // and the amount of duplicated code is too small to warrant // exposing a common abstract class. /** * An Entry maintaining a key and a value. The value may be * changed using the setValue method. This class * facilitates the process of building custom map * implementations. For example, it may be convenient to return * arrays of SimpleEntry instances in method * Map.entrySet().toArray */ public static class SimpleEntry implements Entry { private final K key; private V value; /** * Creates an entry representing a mapping from the specified * key to the specified value. * * @param key the key represented by this entry * @param value the value represented by this entry */ public SimpleEntry(K key, V value) { this.key = key; this.value = value; } /** * Creates an entry representing the same mapping as the * specified entry. * * @param entry the entry to copy. */ public SimpleEntry(Entry entry) { this.key = entry.getKey(); this.value = entry.getValue(); } /** * Returns the key corresponding to this entry. * * @return the key corresponding to this entry. */ public K getKey() { return key; } /** * Returns the value corresponding to this entry. * * @return the value corresponding to this entry. */ public V getValue() { return value; } /** * Replaces the value corresponding to this entry with the specified * value. * * @param value new value to be stored in this entry. * @return the old value corresponding to the entry. */ public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; return eq(key, e.getKey()) && eq(value, e.getValue()); } public int hashCode() { return ((key == null) ? 0 : key.hashCode()) ^ ((value == null) ? 0 : value.hashCode()); } /** * Returns a String representation of this map entry. This * implementation returns the string representation of this * entry's key followed by the equals character ("=") * followed by the string representation of this entry's value. * * @return a String representation of this map entry. */ public String toString() { return key + "=" + value; } } /** * An Entry maintaining an immutable key and value, This class * does not support method setValue. This class may be * convenient in methods that return thread-safe snapshots of * key-value mappings. */ public static class SimpleImmutableEntry implements Entry { private final K key; private final V value; /** * Creates an entry representing a mapping from the specified * key to the specified value. * * @param key the key represented by this entry * @param value the value represented by this entry */ public SimpleImmutableEntry(K key, V value) { this.key = key; this.value = value; } /** * Creates an entry representing the same mapping as the * specified entry. * * @param entry the entry to copy. */ public SimpleImmutableEntry(Entry entry) { this.key = entry.getKey(); this.value = entry.getValue(); } /** * Returns the key corresponding to this entry. * * @return the key corresponding to this entry. */ public K getKey() { return key; } /** * Returns the value corresponding to this entry. * * @return the value corresponding to this entry. */ public V getValue() { return value; } /** * Replaces the value corresponding to this entry with the specified * value (optional operation). This implementation simply throws * UnsupportedOperationException, as this class implements * an immutable map entry. * * @param value new value to be stored in this entry. * @return (Does not return) * @throws UnsupportedOperationException always */ public V setValue(V value) { throw new UnsupportedOperationException(); } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; return eq(key, e.getKey()) && eq(value, e.getValue()); } public int hashCode() { return ((key == null) ? 0 : key.hashCode()) ^ ((value == null) ? 0 : value.hashCode()); } /** * Returns a String representation of this map entry. This * implementation returns the string representation of this * entry's key followed by the equals character ("=") * followed by the string representation of this entry's value. * * @return a String representation of this map entry. */ public String toString() { return key + "=" + value; } } }