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();
}