/* * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ 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 method 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. * * @param the type of keys maintained by this map * @param the type of mapped values * * @author Josh Bloch * @author Neal Gafter * @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 /** * {@inheritDoc} * *

This implementation returns entrySet().size(). */ public int size() { return entrySet().size(); } /** * {@inheritDoc} * *

This implementation returns size() == 0. */ public boolean isEmpty() { return size() == 0; } /** * {@inheritDoc} * *

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. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} */ 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; } /** * {@inheritDoc} * *

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. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} */ 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; } /** * {@inheritDoc} * *

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. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} */ 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 /** * {@inheritDoc} * *

This implementation always throws an * UnsupportedOperationException. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */ public V put(K key, V value) { throw new UnsupportedOperationException(); } /** * {@inheritDoc} * *

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. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} */ 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 /** * {@inheritDoc} * *

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. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */ public void putAll(Map m) { for (Map.Entry e : m.entrySet()) put(e.getKey(), e.getValue()); } /** * {@inheritDoc} * *

This implementation calls entrySet().clear(). * *

Note that this implementation throws an * UnsupportedOperationException if the entrySet * does not support the clear operation. * * @throws UnsupportedOperationException {@inheritDoc} */ 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; /** * {@inheritDoc} * *

This implementation returns a set that subclasses {@link 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. */ 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 isEmpty() { return AbstractMap.this.isEmpty(); } public void clear() { AbstractMap.this.clear(); } public boolean contains(Object k) { return AbstractMap.this.containsKey(k); } }; } return keySet; } /** * {@inheritDoc} * *

This implementation returns a collection that subclasses {@link * AbstractCollection}. 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. */ 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 isEmpty() { return AbstractMap.this.isEmpty(); } public void clear() { AbstractMap.this.clear(); } public boolean contains(Object v) { return AbstractMap.this.containsValue(v); } }; } return values; } 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 m1 and * m2 represent the same mappings if * m1.entrySet().equals(m2.entrySet()). 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 map; 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 m = (Map) o; if (m.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 (!(m.get(key)==null && m.containsKey(key))) return false; } else { if (!value.equals(m.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 m1.equals(m2) * implies that m1.hashCode()==m2.hashCode() for any two maps * m1 and m2, as required by the general contract of * {@link Object#hashCode}. * *

This implementation iterates over entrySet(), calling * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the * set, and adding up the results. * * @return the hash code value for this map * @see Map.Entry#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 * {@link String#valueOf(Object)}. * * @return a string representation of this map */ public String toString() { Iterator> i = entrySet().iterator(); if (! i.hasNext()) return "{}"; StringBuilder sb = new StringBuilder(); sb.append('{'); for (;;) { Entry e = i.next(); K key = e.getKey(); V value = e.getValue(); sb.append(key == this ? "(this Map)" : key); sb.append('='); sb.append(value == this ? "(this Map)" : value); if (! i.hasNext()) return sb.append('}').toString(); sb.append(',').append(' '); } } /** * 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. * * @since 1.6 */ public static class SimpleEntry implements Entry, java.io.Serializable { private static final long serialVersionUID = -8499721149061103585L; 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; } /** * Compares the specified object with this entry for equality. * Returns {@code true} if the given object is also a map entry and * the two entries represent the same mapping. More formally, two * entries {@code e1} and {@code e2} represent the same mapping * if

         *   (e1.getKey()==null ?
         *    e2.getKey()==null :
         *    e1.getKey().equals(e2.getKey()))
         *   &&
         *   (e1.getValue()==null ?
         *    e2.getValue()==null :
         *    e1.getValue().equals(e2.getValue()))
* This ensures that the {@code equals} method works properly across * different implementations of the {@code Map.Entry} interface. * * @param o object to be compared for equality with this map entry * @return {@code true} if the specified object is equal to this map * entry * @see #hashCode */ 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()); } /** * Returns the hash code value for this map entry. The hash code * of a map entry {@code e} is defined to be: 
         *   (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
         *   (e.getValue()==null ? 0 : e.getValue().hashCode())
* This ensures that {@code e1.equals(e2)} implies that * {@code e1.hashCode()==e2.hashCode()} for any two Entries * {@code e1} and {@code e2}, as required by the general * contract of {@link Object#hashCode}. * * @return the hash code value for this map entry * @see #equals */ 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. * * @since 1.6 */ public static class SimpleImmutableEntry implements Entry, java.io.Serializable { private static final long serialVersionUID = 7138329143949025153L; 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(); } /** * Compares the specified object with this entry for equality. * Returns {@code true} if the given object is also a map entry and * the two entries represent the same mapping. More formally, two * entries {@code e1} and {@code e2} represent the same mapping * if
         *   (e1.getKey()==null ?
         *    e2.getKey()==null :
         *    e1.getKey().equals(e2.getKey()))
         *   &&
         *   (e1.getValue()==null ?
         *    e2.getValue()==null :
         *    e1.getValue().equals(e2.getValue()))
* This ensures that the {@code equals} method works properly across * different implementations of the {@code Map.Entry} interface. * * @param o object to be compared for equality with this map entry * @return {@code true} if the specified object is equal to this map * entry * @see #hashCode */ 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()); } /** * Returns the hash code value for this map entry. The hash code * of a map entry {@code e} is defined to be: 
         *   (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
         *   (e.getValue()==null ? 0 : e.getValue().hashCode())
* This ensures that {@code e1.equals(e2)} implies that * {@code e1.hashCode()==e2.hashCode()} for any two Entries * {@code e1} and {@code e2}, as required by the general * contract of {@link Object#hashCode}. * * @return the hash code value for this map entry * @see #equals */ 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; } } }