package java.util;

import ej.annotation.Nullable;

/**
 * An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at
 * most one value.
 *
 * <p>
 * This interface takes the place of the <code>Dictionary</code> class, which was a totally abstract
 * class rather than an interface.
 *
 * <p>
 * The <code>Map</code> interface provides three <i>collection views</i>, which allow a map's contents
 * to be viewed as a set of keys, collection of values, or set of key-value mappings. The
 * <i>order</i> of a map is defined as the order in which the iterators on the map's collection
 * views return their elements. Some map implementations, like the <code>TreeMap</code> class, make
 * specific guarantees as to their order; others, like the <code>HashMap</code> class, do not.
 *
 * <p>
 * Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map
 * is not specified if the value of an object is changed in a manner that affects <code>equals</code>
 * comparisons while the object is a key in the map. A special case of this prohibition is that it
 * is not permissible for a map to contain itself as a key. While it is permissible for a map to
 * contain itself as a value, extreme caution is advised: the <code>equals</code> and <code>hashCode</code>
 * methods are no longer well defined on such a map.
 *
 * <p>
 * All general-purpose map implementation classes should provide two "standard" constructors: a void
 * (no arguments) constructor which creates an empty map, and a constructor with a single argument
 * of type <code>Map</code>, which creates a new map with the same key-value mappings as its argument.
 * In effect, the latter constructor allows the user to copy any map, producing an equivalent map of
 * the desired class. There is no way to enforce this recommendation (as interfaces cannot contain
 * constructors).
 *
 * <p>
 * The "destructive" methods contained in this interface, that is, the methods that modify the map
 * on which they operate, are specified to throw <code>UnsupportedOperationException</code> if this map
 * does not support the operation. If this is the case, these methods may, but are not required to,
 * throw an <code>UnsupportedOperationException</code> if the invocation would have no effect on the
 * map. For example, invoking the {@link #putAll(Map)} method on an unmodifiable map may, but is not
 * required to, throw the exception if the map whose mappings are to be "superimposed" is empty.
 *
 * <p>
 * Some map implementations have restrictions on the keys and values they may contain. For example,
 * some implementations prohibit null keys and values, and some have restrictions on the types of
 * their keys. Attempting to insert an ineligible key or value throws an unchecked exception,
 * typically <code>NullPointerException</code> or <code>ClassCastException</code>. Attempting to query the
 * presence of an ineligible key or value may throw an exception, or it may simply return false;
 * some implementations will exhibit the former behavior and some will exhibit the latter. More
 * generally, attempting an operation on an ineligible key or value whose completion would not
 * result in the insertion of an ineligible element into the map may throw an exception or it may
 * succeed, at the option of the implementation. Such exceptions are marked as "optional" in the
 * specification for this interface.
 *
 * <p>
 * This interface is a member of the Java Collections Framework
 *
 * <p>
 * Many methods in Collections Framework interfaces are defined in terms of the
 * {@link Object#equals(Object) equals} method. For example, the specification for the
 * {@link #containsKey(Object) containsKey(Object key)} method says: "returns <code>true</code> if and
 * only if this map contains a mapping for a key <code>k</code> such that
 * <code>(key==null ? k==null : key.equals(k))</code>." This specification should <i>not</i> be
 * construed to imply that invoking <code>Map.containsKey</code> with a non-null argument <code>key</code>
 * will cause <code>key.equals(k)</code> to be invoked for any key <code>k</code>. Implementations are free
 * to implement optimizations whereby the <code>equals</code> invocation is avoided, for example, by
 * first comparing the hash codes of the two keys. (The {@link Object#hashCode()} specification
 * guarantees that two objects with unequal hash codes cannot be equal.) More generally,
 * implementations of the various Collections Framework interfaces are free to take advantage of the
 * specified behavior of underlying {@link Object} methods wherever the implementor deems it
 * appropriate.
 *
 * @param <K>
 *        the type of keys maintained by this map
 * @param <V>
 *        the type of mapped values
 *
 * @see HashMap
 * @see Hashtable
 * @see Collection
 * @see Set
 */
public interface Map<K, V> {

    /**
     * A map entry (key-value pair). The <code>Map.entrySet</code> method returns a collection-view of the
     * map, whose elements are of this class. The <i>only</i> way to obtain a reference to a map entry
     * is from the iterator of this collection-view. These <code>Map.Entry</code> objects are valid
     * <i>only</i> for the duration of the iteration; more formally, the behavior of a map entry is
     * undefined if the backing map has been modified after the entry was returned by the iterator,
     * except through the <code>setValue</code> operation on the map entry.
     *
     * @param <K>
     *        the type of the keys
     * @param <V>
     *        the type of the values
     *
     * @see Map#entrySet()
     */
    interface Entry<K, V> {

        /**
         * Compares the specified object with this entry for equality. Returns <code>true</code> if the given
         * object is also a map entry and the two entries represent the same mapping. More formally, two
         * entries <code>e1</code> and <code>e2</code> represent the same mapping if
         *
         * <pre>
         * (e1.getKey() == null ? e2.getKey() == null : e1.getKey().equals(e2.getKey()))
         * 		&amp;&amp; (e1.getValue() == null ? e2.getValue() == null : e1.getValue().equals(e2.getValue()))
         * </pre>
         *
         * This ensures that the <code>equals</code> method works properly across different implementations of
         * the <code>Map.Entry</code> interface.
         *
         * @param o
         *        object to be compared for equality with this map entry
         * @return <code>true</code> if the specified object is equal to this map entry
         */
        @Override
        boolean equals(@Nullable Object o);

        /**
         * Returns the key corresponding to this entry.
         *
         * @return the key corresponding to this entry
         * @throws IllegalStateException
         *         implementations may, but are not required to, throw this exception if the entry has been
         *         removed from the backing map.
         */
        K getKey();

        /**
         * Returns the value corresponding to this entry. If the mapping has been removed from the backing
         * map (by the iterator's <code>remove</code> operation), the results of this call are undefined.
         *
         * @return the value corresponding to this entry
         * @throws IllegalStateException
         *         implementations may, but are not required to, throw this exception if the entry has been
         *         removed from the backing map.
         */
        V getValue();

        /**
         * Returns the hash code value for this map entry. The hash code of a map entry <code>e</code> is
         * defined to be:
         *
         * <pre>
         * (e.getKey() == null ? 0 : e.getKey().hashCode()) &circ; (e.getValue() == null ? 0 : e.getValue().hashCode())
         * </pre>
         *
         * This ensures that <code>e1.equals(e2)</code> implies that <code>e1.hashCode()==e2.hashCode()</code> for
         * any two Entries <code>e1</code> and <code>e2</code>, as required by the general contract of
         * <code>Object.hashCode</code>.
         *
         * @return the hash code value for this map entry
         * @see Object#hashCode()
         * @see Object#equals(Object)
         * @see #equals(Object)
         */
        @Override
        int hashCode();

        /**
         * Replaces the value corresponding to this entry with the specified value (optional operation).
         * (Writes through to the map.) The behavior of this call is undefined if the mapping has already
         * been removed from the map (by the iterator's <code>remove</code> operation).
         *
         * @param value
         *        new value to be stored in this entry
         * @return old value corresponding to the entry
         * @throws UnsupportedOperationException
         *         if the <code>put</code> operation is not supported by the backing map
         * @throws ClassCastException
         *         if the class of the specified value prevents it from being stored in the backing map
         * @throws NullPointerException
         *         if the backing map does not permit null values, and the specified value is null
         * @throws IllegalArgumentException
         *         if some property of this value prevents it from being stored in the backing map
         * @throws IllegalStateException
         *         implementations may, but are not required to, throw this exception if the entry has been
         *         removed from the backing map.
         */
        @Nullable
        V setValue(V value);
    }

    /**
     * Removes all of the mappings from this map (optional operation). The map will be empty after this
     * call returns.
     *
     * @throws UnsupportedOperationException
     *         if the <code>clear</code> operation is not supported by this map
     */
    void clear();

    /**
     * Returns <code>true</code> if this map contains a mapping for the specified key. More formally,
     * returns <code>true</code> if and only if this map contains a mapping for a key <code>k</code> such that
     * <code>(key==null ? k==null : key.equals(k))</code>. (There can be at most one such mapping.)
     *
     * @param key
     *        key whose presence in this map is to be tested
     * @return <code>true</code> if this map contains a mapping for the specified key
     * @throws ClassCastException
     *         if the key is of an inappropriate type for this map
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException
     *         if the specified key is null and this map does not permit null keys
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    boolean containsKey(Object key);

    /**
     * Returns <code>true</code> if this map maps one or more keys to the specified value. More formally,
     * returns <code>true</code> if and only if this map contains at least one mapping to a value <code>v</code>
     * such that <code>(value==null ? v==null : value.equals(v))</code>. This operation will probably
     * require time linear in the map size for most implementations of the <code>Map</code> interface.
     *
     * @param value
     *        value whose presence in this map is to be tested
     * @return <code>true</code> if this map maps one or more keys to the specified value
     * @throws ClassCastException
     *         if the value is of an inappropriate type for this map
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException
     *         if the specified value is null and this map does not permit null values
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    boolean containsValue(Object value);

    /**
     * Returns a {@link Set} view of the mappings 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 (except through the iterator's own <code>remove</code>
     * operation, or through the <code>setValue</code> operation on a map entry returned by the iterator)
     * the results of the iteration are undefined. The set supports element removal, which removes the
     * corresponding mapping from the map, via the <code>Iterator.remove</code>, <code>Set.remove</code>,
     * <code>removeAll</code>, <code>retainAll</code> and <code>clear</code> operations. It does not support the
     * <code>add</code> or <code>addAll</code> operations.
     *
     * @return a set view of the mappings contained in this map
     */
    Set<Map.Entry<K, V>> entrySet();

    /**
     * Compares the specified object with this map for equality. Returns <code>true</code> if the given
     * object is also a map and the two maps represent the same mappings. More formally, two maps
     * <code>m1</code> and <code>m2</code> represent the same mappings if
     * <code>m1.entrySet().equals(m2.entrySet())</code>. This ensures that the <code>equals</code> method works
     * properly across different implementations of the <code>Map</code> interface.
     *
     * @param o
     *        object to be compared for equality with this map
     * @return <code>true</code> if the specified object is equal to this map
     */
    @Override
    boolean equals(@Nullable Object o);

    /**
     * Returns the value to which the specified key is mapped, or {@code null} if this map contains no
     * mapping for the key.
     *
     * <p>
     * More formally, if this map contains a mapping from a key {@code k} to a value {@code v} such that
     * {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise it returns {@code null}. (There
     * can be at most one such mapping.)
     *
     * <p>
     * If this map permits null values, then a return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also possible that the map explicitly
     * maps the key to {@code null}. The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @param key
     *        the key whose associated value is to be returned
     * @return the value to which the specified key is mapped, or {@code null} if this map contains no
     *         mapping for the key
     * @throws ClassCastException
     *         if the key is of an inappropriate type for this map
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException
     *         if the specified key is null and this map does not permit null keys
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    @Nullable
    V get(Object key);

    /**
     * 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()</code> view. This ensures that
     * <code>m1.equals(m2)</code> implies that <code>m1.hashCode()==m2.hashCode()</code> for any two maps
     * <code>m1</code> and <code>m2</code>, as required by the general contract of {@link Object#hashCode}.
     *
     * @return the hash code value for this map
     * @see Map.Entry#hashCode()
     * @see Object#equals(Object)
     * @see #equals(Object)
     */
    @Override
    int hashCode();

    /**
     * Returns <code>true</code> if this map contains no key-value mappings.
     *
     * @return <code>true</code> if this map contains no key-value mappings
     */
    boolean isEmpty();

    /**
     * Returns a {@link 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 (except through the iterator's own <code>remove</code>
     * operation), the results of the iteration are undefined. The set supports element removal, which
     * removes the corresponding mapping from the map, via the <code>Iterator.remove</code>,
     * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>, and <code>clear</code> operations. It
     * does not support the <code>add</code> or <code>addAll</code> operations.
     *
     * @return a set view of the keys contained in this map
     */
    Set<K> keySet();

    /**
     * Associates the specified value with the specified key in this map (optional operation). If the
     * map previously contained a mapping for the key, the old value is replaced by the specified value.
     * (A map <code>m</code> is said to contain a mapping for a key <code>k</code> if and only if
     * {@link #containsKey(Object) m.containsKey(k)} would return <code>true</code>.)
     *
     * @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 <code>key</code>, or <code>null</code> if there was no mapping
     *         for <code>key</code>. (A <code>null</code> return can also indicate that the map previously
     *         associated <code>null</code> with <code>key</code>, if the implementation supports <code>null</code>
     *         values.)
     * @throws UnsupportedOperationException
     *         if the <code>put</code> 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 NullPointerException
     *         if the specified key or value is null and this map does not permit null keys or values
     * @throws IllegalArgumentException
     *         if some property of the specified key or value prevents it from being stored in this map
     */
    @Nullable
    V put(K key, V value);

    /**
     * Copies all of the mappings from the specified map to this map (optional operation). The effect of
     * this call is equivalent to that of calling {@link #put(Object,Object) put(k, v)} on this map once
     * for each mapping from key <code>k</code> to value <code>v</code> in the specified map. The behavior of
     * this operation is undefined if the specified map is modified while the operation is in progress.
     *
     * @param m
     *        mappings to be stored in this map
     * @throws UnsupportedOperationException
     *         if the <code>putAll</code> 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 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
     * @throws IllegalArgumentException
     *         if some property of a key or value in the specified map prevents it from being stored in
     *         this map
     */
    void putAll(Map<? extends K, ? extends V> m);

    /**
     * Removes the mapping for a key from this map if it is present (optional operation). More formally,
     * if this map contains a mapping from key <code>k</code> to value <code>v</code> such that
     * <code>(key==null ?  k==null : key.equals(k))</code>, that mapping is removed. (The map can
     * contain at most one such mapping.)
     *
     * <p>
     * Returns the value to which this map previously associated the key, or <code>null</code> if the map
     * contained no mapping for the key.
     *
     * <p>
     * If this map permits null values, then a return value of <code>null</code> does not <i>necessarily</i>
     * indicate that the map contained no mapping for the key; it's also possible that the map
     * explicitly mapped the key to <code>null</code>.
     *
     * <p>
     * The map will not contain a mapping for the specified key once the call returns.
     *
     * @param key
     *        key whose mapping is to be removed from the map
     * @return the previous value associated with <code>key</code>, or <code>null</code> if there was no mapping
     *         for <code>key</code>.
     * @throws UnsupportedOperationException
     *         if the <code>remove</code> operation is not supported by this map
     * @throws ClassCastException
     *         if the key is of an inappropriate type for this map
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException
     *         if the specified key is null and this map does not permit null keys
     *         (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    @Nullable
    V remove(Object key);

    /**
     * Returns the number of key-value mappings in this map. If the map contains more than
     * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>.
     *
     * @return the number of key-value mappings in this map
     */
    int size();

    /**
     * Returns a {@link 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 (except through the iterator's own
     * <code>remove</code> operation), the results of the iteration are undefined. The collection supports
     * element removal, which removes the corresponding mapping from the map, via the
     * <code>Iterator.remove</code>, <code>Collection.remove</code>, <code>removeAll</code>, <code>retainAll</code> and
     * <code>clear</code> operations. It does not support the <code>add</code> or <code>addAll</code> operations.
     *
     * @return a collection view of the values contained in this map
     */
    Collection<V> values();
}