package java.util;

import ej.annotation.Nullable;

/**
 * This class provides a skeletal implementation of the <code>Map</code> interface, to minimize the
 * effort required to implement this interface.
 *
 * <p>
 * To implement an unmodifiable map, the programmer needs only to extend this class and provide an
 * implementation for the <code>entrySet</code> method, which returns a set-view of the map's mappings.
 * Typically, the returned set will, in turn, be implemented atop <code>AbstractSet</code>. This set
 * should not support the <code>add</code> or <code>remove</code> methods, and its iterator should not
 * support the <code>remove</code> method.
 *
 * <p>
 * To implement a modifiable map, the programmer must additionally override this class's
 * <code>put</code> method (which otherwise throws an <code>UnsupportedOperationException</code>), and the
 * iterator returned by <code>entrySet().iterator()</code> must additionally implement its
 * <code>remove</code> method.
 *
 * <p>
 * The programmer should generally provide a void (no argument) and map constructor, as per the
 * recommendation in the <code>Map</code> interface specification.
 *
 * <p>
 * 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.
 *
 * <p>
 * This class is a member of the Java Collections Framework
 *
 * @param <K>
 *        the type of keys maintained by this map
 * @param <V>
 *        the type of mapped values
 *
 * @see Map
 * @see Collection
 */
public abstract class AbstractMap<K, V> implements Map<K, V> {
	/**
	 * An Entry maintaining a key and a value. The value may be changed using the <code>setValue</code>
	 * method. This class facilitates the process of building custom map implementations. For example,
	 * it may be convenient to return arrays of <code>SimpleEntry</code> instances in method
	 * <code>Map.entrySet().toArray</code>.
	 *
	 * @param <K>
	 *        the type of the keys
	 * @param <V>
	 *        the type of the values
	 */
	public static class SimpleEntry<K, V> implements Entry<K, V>, java.io.Serializable {

		/**
		 * Creates an entry representing the same mapping as the specified entry.
		 *
		 * @param entry
		 *        the entry to copy
		 */
		public SimpleEntry(Entry<? extends K, ? extends V> entry) {
			throw new RuntimeException();
		}

		/**
		 * 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) {
			throw new RuntimeException();
		}

		/**
		 * 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
		 *
		 * <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} 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
		 */
		@Override
		public boolean equals(@Nullable Object o) {
			throw new RuntimeException();
		}

		/**
		 * Returns the key corresponding to this entry.
		 *
		 * @return the key corresponding to this entry
		 */
		@Override
		public K getKey() {
			throw new RuntimeException();
		}

		/**
		 * Returns the value corresponding to this entry.
		 *
		 * @return the value corresponding to this entry
		 */
		@Override
		public V getValue() {
			throw new RuntimeException();
		}

		/**
		 * Returns the hash code value for this map entry. The hash code of a map entry {@code e} 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)} 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
		 */
		@Override
		public int hashCode() {
			throw new RuntimeException();
		}

		/**
		 * 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
		 */
		@Override
		@Nullable
		public V setValue(V value) {
			throw new RuntimeException();
		}

		/**
		 * 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>=</code>") followed by
		 * the string representation of this entry's value.
		 *
		 * @return a String representation of this map entry
		 */
		@Override
		public String toString() {
			throw new RuntimeException();
		}

	}

	/**
	 * An Entry maintaining an immutable key and value. This class does not support method
	 * <code>setValue</code>. This class may be convenient in methods that return thread-safe snapshots of
	 * key-value mappings.
	 *
	 * @param <K>
	 *        the type of the keys
	 * @param <V>
	 *        the type of the values
	 */
	public static class SimpleImmutableEntry<K, V> implements Entry<K, V>, java.io.Serializable {

		/**
		 * Creates an entry representing the same mapping as the specified entry.
		 *
		 * @param entry
		 *        the entry to copy
		 */
		public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
			throw new RuntimeException();
		}

		/**
		 * 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) {
			throw new RuntimeException();
		}

		/**
		 * 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
		 *
		 * <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} 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
		 */
		@Override
		public boolean equals(@Nullable Object o) {
			throw new RuntimeException();
		}

		/**
		 * Returns the key corresponding to this entry.
		 *
		 * @return the key corresponding to this entry
		 */
		@Override
		public K getKey() {
			throw new RuntimeException();
		}

		/**
		 * Returns the value corresponding to this entry.
		 *
		 * @return the value corresponding to this entry
		 */
		@Override
		public V getValue() {
			throw new RuntimeException();
		}

		/**
		 * Returns the hash code value for this map entry. The hash code of a map entry {@code e} 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)} 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
		 */
		@Override
		public int hashCode() {
			throw new RuntimeException();
		}

		/**
		 * Replaces the value corresponding to this entry with the specified value (optional operation).
		 * This implementation simply throws <code>UnsupportedOperationException</code>, as this class
		 * implements an <i>immutable</i> map entry.
		 *
		 * @param value
		 *        new value to be stored in this entry
		 * @return (Does not return)
		 * @throws UnsupportedOperationException
		 *         always
		 */
		@Override
		@Nullable
		public V setValue(V value) {
			throw new RuntimeException();
		}

		/**
		 * 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>=</code>") followed by
		 * the string representation of this entry's value.
		 *
		 * @return a String representation of this map entry
		 */
		@Override
		public String toString() {
			throw new RuntimeException();
		}

	}

	/**
	 * Sole constructor. (For invocation by subclass constructors, typically implicit.)
	 */
	protected AbstractMap() {
	}

	/**
	 * Removes all of the mappings from this map (optional operation). The map will be empty after this
	 * call returns.
	 *
	 * <p>
	 * This implementation calls <code>entrySet().clear()</code>.
	 *
	 * <p>
	 * Note that this implementation throws an <code>UnsupportedOperationException</code> if the
	 * <code>entrySet</code> does not support the <code>clear</code> operation.
	 *
	 * @throws UnsupportedOperationException
	 *         if the <code>clear</code> operation is not supported by this map
	 */
	@Override
	public void clear() {
		throw new RuntimeException();
	}

	/**
	 * Returns a shallow copy of this <code>AbstractMap</code> instance: the keys and values themselves are
	 * not cloned.
	 *
	 * @return a shallow copy of this map
	 */
	@Override
	protected Object clone() throws CloneNotSupportedException {
		throw new RuntimeException();
	}

	/**
	 * 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.)
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for an entry with the specified
	 * key. If such an entry is found, <code>true</code> is returned. If the iteration terminates without
	 * finding such an entry, <code>false</code> is returned. Note that this implementation requires linear
	 * time in the size of the map; many implementations will override this method.
	 *
	 * @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>)
	 */
	@Override
	public boolean containsKey(Object key) {
		throw new RuntimeException();
	}

	/**
	 * 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.
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for an entry with the specified
	 * value. If such an entry is found, <code>true</code> is returned. If the iteration terminates without
	 * finding such an entry, <code>false</code> is returned. Note that this implementation requires linear
	 * time in the size of the map.
	 *
	 * @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>)
	 */
	@Override
	public boolean containsValue(Object value) {
		throw new RuntimeException();
	}

	@Override
	public abstract Set<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.
	 *
	 * <p>
	 * This implementation first checks if the specified object is this map; if so it returns
	 * <code>true</code>. 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</code>. If so, it iterates over this map's
	 * <code>entrySet</code> 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</code> is returned.
	 * If the iteration completes, <code>true</code> is returned.
	 *
	 * @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
	public boolean equals(@Nullable Object o) {
		throw new RuntimeException();
	}

	/**
	 * 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.
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> 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</code> is returned. Note that this implementation requires
	 * linear time in the size of the map; many implementations will override this method.
	 *
	 * @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>)
	 */
	@Override
	@Nullable
	public V get(Object key) {
		throw new RuntimeException();
	}

	/**
	 * 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}.
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code>, 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)
	 */
	@Override
	public int hashCode() {
		throw new RuntimeException();
	}

	/**
	 * Returns <code>true</code> if this map contains no key-value mappings.
	 *
	 * <p>
	 * This implementation returns <code>size() == 0</code>.
	 *
	 * @return <code>true</code> if this map contains no key-value mappings
	 */
	@Override
	public boolean isEmpty() {
		throw new RuntimeException();
	}

	/**
	 * 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.
	 *
	 * <p>
	 * This implementation returns a set that subclasses {@link AbstractSet}. The subclass's iterator
	 * method returns a "wrapper object" over this map's <code>entrySet()</code> iterator. The <code>size</code>
	 * method delegates to this map's <code>size</code> method and the <code>contains</code> method delegates to
	 * this map's <code>containsKey</code> method.
	 *
	 * <p>
	 * 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.
	 *
	 * @return a set view of the keys contained in this map
	 */
	@Override
	public Set<K> keySet() {
		throw new RuntimeException();
	}

	/**
	 * 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>.)
	 *
	 * <p>
	 * This implementation always throws an <code>UnsupportedOperationException</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
	 */
	@Override
	@Nullable
	public V put(K key, V value) {
		throw new RuntimeException();
	}

	/**
	 * 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.
	 *
	 * <p>
	 * This implementation iterates over the specified map's <code>entrySet()</code> collection, and calls
	 * this map's <code>put</code> operation once for each entry returned by the iteration.
	 *
	 * <p>
	 * Note that this implementation throws an <code>UnsupportedOperationException</code> if this map does
	 * not support the <code>put</code> operation and the specified map is nonempty.
	 *
	 * @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
	 */
	@Override
	public void putAll(Map<? extends K, ? extends V> m) {
		throw new RuntimeException();
	}

	/**
	 * 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.
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for an entry with the specified
	 * key. If such an entry is found, its value is obtained with its <code>getValue</code> operation, the
	 * entry is removed from the collection (and the backing map) with the iterator's <code>remove</code>
	 * operation, and the saved value is returned. If the iteration terminates without finding such an
	 * entry, <code>null</code> is returned. Note that this implementation requires linear time in the size
	 * of the map; many implementations will override this method.
	 *
	 * <p>
	 * Note that this implementation throws an <code>UnsupportedOperationException</code> if the
	 * <code>entrySet</code> iterator does not support the <code>remove</code> method and this map contains a
	 * mapping for the specified key.
	 *
	 * @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>)
	 */
	@Override
	@Nullable
	public V remove(Object key) {
		throw new RuntimeException();
	}

	/**
	 * 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>.
	 *
	 * <p>
	 * This implementation returns <code>entrySet().size()</code>.
	 *
	 * @return the number of key-value mappings in this map
	 */
	@Override
	public int size() {
		throw new RuntimeException();
	}

	/**
	 * 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</code> view's iterator, enclosed
	 * in braces (<code>"{}"</code>). Adjacent mappings are separated by the characters <code>", "</code> (comma
	 * and space). Each key-value mapping is rendered as the key followed by an equals sign
	 * (<code>"="</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
	 */
	@Override
	public String toString() {
		throw new RuntimeException();
	}

	/**
	 * 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.
	 *
	 * <p>
	 * This implementation returns a collection that subclasses {@link AbstractCollection}. The
	 * subclass's iterator method returns a "wrapper object" over this map's <code>entrySet()</code>
	 * iterator. The <code>size</code> method delegates to this map's <code>size</code> method and the
	 * <code>contains</code> method delegates to this map's <code>containsValue</code> method.
	 *
	 * <p>
	 * 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.
	 *
	 * @return a collection view of the values contained in this map
	 */
	@Override
	public Collection<V> values() {
		throw new RuntimeException();
	}

}