/* * Copyright (c) 1997, 2013, 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 {@code 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 {@code entrySet} method, which * returns a set-view of the map's mappings. Typically, the returned set * will, in turn, be implemented atop {@code AbstractSet}. This set should * not support the {@code add} or {@code remove} methods, and its iterator * should not support the {@code remove} method. * *

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

The programmer should generally provide a void (no argument) and map * constructor, as per the recommendation in the {@code 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} * * @implSpec * This implementation returns {@code entrySet().size()}. */ public int size() { return entrySet().size(); } /** * {@inheritDoc} * * @implSpec * This implementation returns {@code size() == 0}. */ public boolean isEmpty() { return size() == 0; } /** * {@inheritDoc} * * @implSpec * This implementation iterates over {@code entrySet()} searching * for an entry with the specified value. If such an entry is found, * {@code true} is returned. If the iteration terminates without * finding such an entry, {@code 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} * * @implSpec * This implementation iterates over {@code entrySet()} searching * for an entry with the specified key. If such an entry is found, * {@code true} is returned. If the iteration terminates without * finding such an entry, {@code 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} * * @implSpec * This implementation iterates over {@code 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, {@code 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} * * @implSpec * This implementation always throws an * {@code UnsupportedOperationException}. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */ public V put(K key, V value) { throw new UnsupportedOperationException(); } /** * {@inheritDoc} * * @implSpec * This implementation iterates over {@code entrySet()} searching for an * entry with the specified key. If such an entry is found, its value is * obtained with its {@code getValue} operation, the entry is removed * from the collection (and the backing map) with the iterator's * {@code remove} operation, and the saved value is returned. If the * iteration terminates without finding such an entry, {@code 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 * {@code UnsupportedOperationException} if the {@code entrySet} * iterator does not support the {@code 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} * * @implSpec * This implementation iterates over the specified map's * {@code entrySet()} collection, and calls this map's {@code put} * operation once for each entry returned by the iteration. * *

Note that this implementation throws an * {@code UnsupportedOperationException} if this map does not support * the {@code 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} * * @implSpec * This implementation calls {@code entrySet().clear()}. * *

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

Since there is no synchronization performed while accessing these fields, * it is expected that java.util.Map view classes using these fields have * no non-final fields (or any fields at all except for outer-this). Adhering * to this rule would make the races on these fields benign. * *

It is also imperative that implementations read the field only once, * as in: * * 

 {@code
     * public Set keySet() {
     *   Set ks = keySet;  // single racy read
     *   if (ks == null) {
     *     ks = new KeySet();
     *     keySet = ks;
     *   }
     *   return ks;
     * }
     *}
*/ transient Set keySet; transient Collection values; /** * {@inheritDoc} * * @implSpec * This implementation returns a set that subclasses {@link AbstractSet}. * The subclass's iterator method returns a "wrapper object" over this * map's {@code entrySet()} iterator. The {@code size} method * delegates to this map's {@code size} method and the * {@code contains} method delegates to this map's * {@code 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() { Set ks = keySet; if (ks == null) { ks = 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); } }; keySet = ks; } return ks; } /** * {@inheritDoc} * * @implSpec * This implementation returns a collection that subclasses {@link * AbstractCollection}. The subclass's iterator method returns a * "wrapper object" over this map's {@code entrySet()} iterator. * The {@code size} method delegates to this map's {@code size} * method and the {@code contains} method delegates to this map's * {@code 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() { Collection vals = values; if (vals == null) { vals = 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); } }; values = vals; } return vals; } public abstract Set> entrySet(); // Comparison and hashing /** * Compares the specified object with this map for equality. Returns * {@code true} if the given object is also a map and the two maps * represent the same mappings. More formally, two maps {@code m1} and * {@code m2} represent the same mappings if * {@code m1.entrySet().equals(m2.entrySet())}. This ensures that the * {@code equals} method works properly across different implementations * of the {@code Map} interface. * * @implSpec * This implementation first checks if the specified object is this map; * if so it returns {@code 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 {@code false}. If so, it iterates over this map's * {@code 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, {@code false} is returned. If the * iteration completes, {@code true} is returned. * * @param o object to be compared for equality with this map * @return {@code 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 { for (Entry e : entrySet()) { 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 * {@code entrySet()} view. This ensures that {@code m1.equals(m2)} * implies that {@code m1.hashCode()==m2.hashCode()} for any two maps * {@code m1} and {@code m2}, as required by the general contract of * {@link Object#hashCode}. * * @implSpec * This implementation iterates over {@code 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; for (Entry entry : entrySet()) h += entry.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 {@code entrySet} view's iterator, enclosed in braces * ({@code "{}"}). Adjacent mappings are separated by the characters * {@code ", "} (comma and space). Each key-value mapping is rendered as * the key followed by an equals sign ({@code "="}) 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 {@code 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. * * NB: Do not replace with Object.equals until JDK-8015417 is resolved. */ 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 {@code setValue} method. This class * facilitates the process of building custom map * implementations. For example, it may be convenient to return * arrays of {@code SimpleEntry} instances in method * {@code 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 ("{@code =}") * 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 {@code 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 * {@code 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 ("{@code =}") * followed by the string representation of this entry's value. * * @return a String representation of this map entry */ public String toString() { return key + "=" + value; } } }