Map.java

/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package java.util;

import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;


/**
 * A {@code Map} is a data structure consisting of a set of keys and values
 * in which each key is mapped to a single value.  The class of the objects
 * used as keys is declared when the {@code Map} is declared, as is the 
 * class of the corresponding values.
 * <p>
 * A {@code Map} provides helper methods to iterate through all of the
 * keys contained in it, as well as various methods to access and update 
 * the key/value pairs.  
 */
public interface Map<K,V> {

    /**
     * {@code Map.Entry} is a key/value mapping contained in a {@code Map}.
     */
    public static interface Entry<K,V> {
        /**
         * Compares the specified object to this {@code Map.Entry} and returns if they
         * are equal. To be equal, the object must be an instance of {@code Map.Entry} and have the
         * same key and value.
         * 
         * @param object
         *            the {@code Object} to compare with this {@code Object}.
         * @return {@code true} if the specified {@code Object} is equal to this
         *         {@code Map.Entry}, {@code false} otherwise.
         * @see #hashCode()
         */
        public boolean equals(Object object);

        /**
         * Returns the key.
         * 
         * @return the key
         */
        public K getKey();

        /**
         * Returns the value.
         * 
         * @return the value
         */
        public V getValue();

        /**
         * Returns an integer hash code for the receiver. {@code Object} which are
         * equal return the same value for this method.
         * 
         * @return the receiver's hash code.
         * @see #equals(Object)
         */
        public int hashCode();

        /**
         * Sets the value of this entry to the specified value, replacing any
         * existing value.
         * 
         * @param object
         *            the new value to set.
         * @return object the replaced value of this entry.
         */
        public V setValue(V object);

        /// Orders entries by the natural order of their keys.
        static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
            return new Comparator<Map.Entry<K, V>>() {
                @Override
                public int compare(Map.Entry<K, V> a, Map.Entry<K, V> b) {
                    return a.getKey().compareTo(b.getKey());
                }
            };
        }

        /// Orders entries by the natural order of their values.
        static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
            return new Comparator<Map.Entry<K, V>>() {
                @Override
                public int compare(Map.Entry<K, V> a, Map.Entry<K, V> b) {
                    return a.getValue().compareTo(b.getValue());
                }
            };
        }

        /// Orders entries by their keys, as `comparator` orders them.
        static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(final Comparator<? super K> comparator) {
            if (comparator == null) {
                throw new NullPointerException();
            }
            return new Comparator<Map.Entry<K, V>>() {
                @Override
                public int compare(Map.Entry<K, V> a, Map.Entry<K, V> b) {
                    return comparator.compare(a.getKey(), b.getKey());
                }
            };
        }

        /// Orders entries by their values, as `comparator` orders them.
        static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(final Comparator<? super V> comparator) {
            if (comparator == null) {
                throw new NullPointerException();
            }
            return new Comparator<Map.Entry<K, V>>() {
                @Override
                public int compare(Map.Entry<K, V> a, Map.Entry<K, V> b) {
                    return comparator.compare(a.getValue(), b.getValue());
                }
            };
        }
    }

    /**
     * Removes all elements from this {@code Map}, leaving it empty.
     * 
     * @throws UnsupportedOperationException
     *                if removing elements from this {@code Map} is not supported.
     * @see #isEmpty()
     * @see #size()
     */
    public void clear();

    /**
     * Returns whether this {@code Map} contains the specified key.
     * 
     * @param key
     *            the key to search for.
     * @return {@code true} if this map contains the specified key,
     *         {@code false} otherwise.
     */
    public boolean containsKey(Object key);

    /**
     * Returns whether this {@code Map} contains the specified value.
     * 
     * @param value
     *            the value to search for.
     * @return {@code true} if this map contains the specified value,
     *         {@code false} otherwise.
     */
    public boolean containsValue(Object value);

    /**
     * Returns a {@code Set} containing all of the mappings in this {@code Map}. Each mapping is
     * an instance of {@link Map.Entry}. As the {@code Set} is backed by this {@code Map},
     * changes in one will be reflected in the other.
     * 
     * @return a set of the mappings
     */
    public Set<Map.Entry<K,V>> entrySet();

    /**
     * Compares the argument to the receiver, and returns {@code true} if the
     * specified object is a {@code Map} and both {@code Map}s contain the same mappings.
     * 
     * @param object
     *            the {@code Object} to compare with this {@code Object}.
     * @return boolean {@code true} if the {@code Object} is the same as this {@code Object}
     *         {@code false} if it is different from this {@code Object}.
     * @see #hashCode()
     * @see #entrySet()
     */
    public boolean equals(Object object);

    /**
     * Returns the value of the mapping with the specified key.
     * 
     * @param key
     *            the key.
     * @return the value of the mapping with the specified key, or {@code null}
     *         if no mapping for the specified key is found.
     */
    public V get(Object key);

    /**
     * Returns an integer hash code for the receiver. {@code Object}s which are equal
     * return the same value for this method.
     * 
     * @return the receiver's hash.
     * @see #equals(Object)
     */
    public int hashCode();

    /**
     * Returns whether this map is empty.
     * 
     * @return {@code true} if this map has no elements, {@code false}
     *         otherwise.
     * @see #size()
     */
    public boolean isEmpty();

    /**
     * Returns a set of the keys contained in this {@code Map}. The {@code Set} is backed by
     * this {@code Map} so changes to one are reflected by the other. The {@code Set} does not
     * support adding.
     * 
     * @return a set of the keys.
     */
    public Set<K> keySet();

    /**
     * Maps the specified key to the specified value.
     * 
     * @param key
     *            the key.
     * @param value
     *            the value.
     * @return the value of any previous mapping with the specified key or
     *         {@code null} if there was no mapping.
     * @throws UnsupportedOperationException
     *                if adding to this {@code Map} is not supported.
     * @throws ClassCastException
     *                if the class of the key or value is inappropriate for
     *                this {@code Map}.
     * @throws IllegalArgumentException
     *                if the key or value cannot be added to this {@code Map}.
     * @throws NullPointerException
     *                if the key or value is {@code null} and this {@code Map} does
     *                not support {@code null} keys or values.
     */
    public V put(K key, V value);

    /**
     * Copies every mapping in the specified {@code Map} to this {@code Map}.
     * 
     * @param map
     *            the {@code Map} to copy mappings from.
     * @throws UnsupportedOperationException
     *                if adding to this {@code Map} is not supported.
     * @throws ClassCastException
     *                if the class of a key or a value of the specified {@code Map} is
     *                inappropriate for this {@code Map}.
     * @throws IllegalArgumentException
     *                if a key or value cannot be added to this {@code Map}.
     * @throws NullPointerException
     *                if a key or value is {@code null} and this {@code Map} does not
     *                support {@code null} keys or values.
     */
    public void putAll(Map<? extends K,? extends V> map);

    /**
     * Removes a mapping with the specified key from this {@code Map}.
     * 
     * @param key
     *            the key of the mapping to remove.
     * @return the value of the removed mapping or {@code null} if no mapping
     *         for the specified key was found.
     * @throws UnsupportedOperationException
     *                if removing from this {@code Map} is not supported.
     */
    public V remove(Object key);

    /**
     * Returns the number of mappings in this {@code Map}.
     * 
     * @return the number of mappings in this {@code Map}.
     */
    public int size();

    /**
     * Returns a {@code Collection} of the values contained in this {@code Map}. The {@code Collection}
     * is backed by this {@code Map} so changes to one are reflected by the other. The
     * {@code Collection} supports {@link Collection#remove}, {@link Collection#removeAll}, 
     * {@link Collection#retainAll}, and {@link Collection#clear} operations,
     * and it does not support {@link Collection#add} or {@link Collection#addAll} operations.
     * <p>
     * This method returns a {@code Collection} which is the subclass of
     * {@link AbstractCollection}. The {@link AbstractCollection#iterator} method of this subclass returns a
     * "wrapper object" over the iterator of this {@code Map}'s {@link #entrySet()}. The {@link AbstractCollection#size} method
     * wraps this {@code Map}'s {@link #size} method and the {@link AbstractCollection#contains} method wraps this {@code Map}'s
     * {@link #containsValue} method.
     * <p>
     * The collection is created when this method is called at first time and
     * returned in response to all subsequent calls. This method may return
     * different Collection when multiple calls to this method, since it has no
     * synchronization performed.
     * 
     * @return a collection of the values contained in this map.
     */
    public Collection<V> values();

    // ---- Java 8 default methods. Mirror of the same set in
    // ---- Ports/CLDC11/src/java/util/Map.java; kept in sync.

    /**
     * Returns the value to which the specified key is mapped, or
     * {@code defaultValue} if this map contains no mapping for the key.
     */
    default V getOrDefault(Object key, V defaultValue) {
        V v = get(key);
        return v != null ? v : defaultValue;
    }

    /**
     * If the specified key is not already associated with a value (or is
     * mapped to {@code null}) associates it with the given value and returns
     * {@code null}, else returns the current value.
     */
    default V putIfAbsent(K key, V value) {
        V v = get(key);
        if (v == null) {
            v = put(key, value);
        }
        return v;
    }

    /**
     * Removes the entry for the specified key only if it is currently mapped
     * to the specified value.
     */
    default boolean remove(Object key, Object value) {
        Object curr = get(key);
        if (curr == null ? value != null : !curr.equals(value)) {
            return false;
        }
        if (curr == null && !containsKey(key)) {
            return false;
        }
        remove(key);
        return true;
    }

    /**
     * Replaces the entry for the specified key only if currently mapped to
     * the specified value.
     */
    default boolean replace(K key, V oldValue, V newValue) {
        Object curr = get(key);
        if (curr == null ? oldValue != null : !curr.equals(oldValue)) {
            return false;
        }
        if (curr == null && !containsKey(key)) {
            return false;
        }
        put(key, newValue);
        return true;
    }

    /**
     * Replaces the entry for the specified key only if it is currently
     * mapped to some value.
     */
    default V replace(K key, V value) {
        V curr = get(key);
        if (curr != null || containsKey(key)) {
            curr = put(key, value);
        }
        return curr;
    }

    /**
     * Performs the given action for each entry in this map until all entries
     * have been processed or the action throws an exception.
     */
    default void forEach(BiConsumer<? super K, ? super V> action) {
        if (action == null) {
            throw new NullPointerException();
        }
        for (Map.Entry<K, V> entry : entrySet()) {
            action.accept(entry.getKey(), entry.getValue());
        }
    }

    /**
     * Replaces each entry's value with the result of invoking the given
     * function on that entry.
     */
    default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        if (function == null) {
            throw new NullPointerException();
        }
        for (Map.Entry<K, V> entry : entrySet()) {
            entry.setValue(function.apply(entry.getKey(), entry.getValue()));
        }
    }

    /**
     * If the specified key is not already associated with a value, attempts to
     * compute its value using the given mapping function and enters it into
     * this map unless {@code null}.
     */
    default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
        if (mappingFunction == null) {
            throw new NullPointerException();
        }
        V v = get(key);
        if (v == null) {
            V newValue = mappingFunction.apply(key);
            if (newValue != null) {
                put(key, newValue);
                return newValue;
            }
        }
        return v;
    }

    /**
     * If the value for the specified key is present and non-null, attempts to
     * compute a new mapping.
     */
    default V computeIfPresent(K key,
            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null) {
            throw new NullPointerException();
        }
        V old = get(key);
        if (old != null) {
            V newValue = remappingFunction.apply(key, old);
            if (newValue != null) {
                put(key, newValue);
                return newValue;
            }
            remove(key);
        }
        return null;
    }

    /**
     * Attempts to compute a mapping for the specified key and its current
     * mapped value (or {@code null} if there is no current mapping).
     */
    default V compute(K key,
            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null) {
            throw new NullPointerException();
        }
        V old = get(key);
        V newValue = remappingFunction.apply(key, old);
        if (newValue == null) {
            if (old != null || containsKey(key)) {
                remove(key);
            }
            return null;
        }
        put(key, newValue);
        return newValue;
    }

    /**
     * If the specified key is not already associated with a value or is
     * associated with null, associates it with the given non-null value;
     * otherwise replaces the associated value with the results of the
     * remapping function, or removes if the result is {@code null}.
     */
    default V merge(K key, V value,
            BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null || value == null) {
            throw new NullPointerException();
        }
        V old = get(key);
        V newValue = old == null ? value : remappingFunction.apply(old, value);
        if (newValue == null) {
            remove(key);
        } else {
            put(key, newValue);
        }
        return newValue;
    }

    /// An unmodifiable map of no mappings.
    static <K, V> Map<K, V> of() {
        return ImmutableCollections.map(new Object[0]);
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1) {
        return ImmutableCollections.map(new Object[] {k1, v1});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3, k4, v4});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3, k4, v4, k5, v5});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7, k8, v8});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7, k8, v8, k9, v9});
    }

    /// An unmodifiable map of the given keys and values, none of which may be
    /// null, and no key given twice.
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9, K k10, V v10) {
        return ImmutableCollections.map(new Object[] {k1, v1, k2, v2, k3, v3, k4, v4, k5, v5, k6, v6, k7, v7, k8, v8, k9, v9, k10, v10});
    }

    /// An unmodifiable map of the keys and values of `entries`, none of which
    /// may be null, and no key given twice.
    @SafeVarargs
    static <K, V> Map<K, V> ofEntries(Map.Entry<? extends K, ? extends V>... entries) {
        return ImmutableCollections.mapOfEntries(entries);
    }

    /// An unmodifiable entry of `key` and `value`, neither of which may be null.
    static <K, V> Map.Entry<K, V> entry(K key, V value) {
        return new ImmutableCollections.ImmutableEntry<K, V>(key, value);
    }

    /// An unmodifiable map of the mappings of `map`, which may not hold null;
    /// `map` itself when it is already such a map.
    static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map) {
        return ImmutableCollections.mapCopyOf(map);
    }

}