package java.util;

import java.io.Serializable;
import ej.annotation.Nullable;

/**
 * Hash table based implementation of the <code>Map</code> interface. This implementation provides all
 * of the optional map operations, and permits <code>null</code> values and the <code>null</code> key. (The
 * <code>HashMap</code> class is roughly equivalent to <code>Hashtable</code>, except that it is
 * unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in
 * particular, it does not guarantee that the order will remain constant over time.
 *
 * <p>
 * This implementation provides constant-time performance for the basic operations (<code>get</code> and
 * <code>put</code>), assuming the hash function disperses the elements properly among the buckets.
 * Iteration over collection views requires time proportional to the "capacity" of the
 * <code>HashMap</code> instance (the number of buckets) plus its size (the number of key-value
 * mappings). Thus, it's very important not to set the initial capacity too high (or the load factor
 * too low) if iteration performance is important.
 *
 * <p>
 * An instance of <code>HashMap</code> has two parameters that affect its performance: <i>initial
 * capacity</i> and <i>load factor</i>. The <i>capacity</i> is the number of buckets in the hash
 * table, and the initial capacity is simply the capacity at the time the hash table is created. The
 * <i>load factor</i> is a measure of how full the hash table is allowed to get before its capacity
 * is automatically increased. When the number of entries in the hash table exceeds the product of
 * the load factor and the current capacity, the hash table is <i>rehashed</i> (that is, internal
 * data structures are rebuilt) so that the hash table has approximately twice the number of
 * buckets.
 *
 * <p>
 * As a general rule, the default load factor (.75) offers a good tradeoff between time and space
 * costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most
 * of the operations of the <code>HashMap</code> class, including <code>get</code> and <code>put</code>). The
 * expected number of entries in the map and its load factor should be taken into account when
 * setting its initial capacity, so as to minimize the number of rehash operations. If the initial
 * capacity is greater than the maximum number of entries divided by the load factor, no rehash
 * operations will ever occur.
 *
 * <p>
 * If many mappings are to be stored in a <code>HashMap</code> instance, creating it with a sufficiently
 * large capacity will allow the mappings to be stored more efficiently than letting it perform
 * automatic rehashing as needed to grow the table.
 *
 * <p>
 * <strong>Note that this implementation is not synchronized.</strong> If multiple threads access a
 * hash map concurrently, and at least one of the threads modifies the map structurally, it
 * <i>must</i> be synchronized externally. (A structural modification is any operation that adds or
 * deletes one or more mappings; merely changing the value associated with a key that an instance
 * already contains is not a structural modification.) This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the map.
 *
 * <p>
 * The iterators returned by all of this class's "collection view methods" are <i>fail-fast</i>: if
 * the map is structurally modified at any time after the iterator is created, in any way except
 * through the iterator's own <code>remove</code> method, the iterator will throw a
 * {@link ConcurrentModificationException}. Thus, in the face of concurrent modification, the
 * iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at
 * an undetermined time in the future.
 *
 * <p>
 * Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally
 * speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent
 * modification. Fail-fast iterators throw <code>ConcurrentModificationException</code> on a best-effort
 * basis. Therefore, it would be wrong to write a program that depended on this exception for its
 * correctness: <i>the fail-fast behavior of iterators should be used only to detect bugs.</i>
 *
 * <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 Object#hashCode()
 * @see Collection
 * @see Map
 * @see Hashtable
 */
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {

    /**
     * Constructs an empty <code>HashMap</code> with the default initial capacity (16) and the default load
     * factor (0.75).
     */
    public HashMap() {
        throw new RuntimeException();
    }

    /**
     * Constructs an empty <code>HashMap</code> with the specified initial capacity and the default load
     * factor (0.75).
     *
     * @param initialCapacity
     *        the initial capacity.
     * @throws IllegalArgumentException
     *         if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        throw new RuntimeException();
    }

    /**
     * Constructs an empty <code>HashMap</code> with the specified initial capacity and load factor.
     *
     * @param initialCapacity
     *        the initial capacity
     * @param loadFactor
     *        the load factor
     * @throws IllegalArgumentException
     *         if the initial capacity is negative or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        throw new RuntimeException();
    }

    /**
     * Constructs a new <code>HashMap</code> with the same mappings as the specified <code>Map</code>. The
     * <code>HashMap</code> is created with default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <code>Map</code>.
     *
     * @param m
     *        the map whose mappings are to be placed in this map
     * @throws NullPointerException
     *         if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        throw new RuntimeException();
    }

    /**
     * Removes all of the mappings from this map. The map will be empty after this call returns.
     */
    @Override
    public void clear() {
        throw new RuntimeException();
    }

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

    /**
     * Returns <code>true</code> if this map contains a mapping for the specified key.
     *
     * @param key
     *        The key whose presence in this map is to be tested
     * @return <code>true</code> if this map contains a mapping for the specified key.
     */
    @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.
     *
     * @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
     */
    @Override
    public boolean containsValue(Object value) {
        throw new RuntimeException();
    }

    /**
     * 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
     */
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        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>
     * 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.
     *
     * @see #put(Object, Object)
     */
    @Override
    @Nullable
    public V get(Object key) {
        throw new RuntimeException();
    }

    /**
     * Returns <code>true</code> if this map contains no key-value mappings.
     *
     * @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.
     */
    @Override
    public Set<K> keySet() {
        throw new RuntimeException();
    }

    /**
     * Associates the specified value with the specified key in this map. If the map previously
     * contained a mapping for the key, the old value is replaced.
     *
     * @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>.)
     */
    @Override
    @Nullable
    public V put(K key, V value) {
        throw new RuntimeException();
    }

    /**
     * Copies all of the mappings from the specified map to this map. These mappings will replace any
     * mappings that this map had for any of the keys currently in the specified map.
     *
     * @param m
     *        mappings to be stored in this map
     * @throws NullPointerException
     *         if the specified map is null
     */
    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        throw new RuntimeException();
    }

    /**
     * Removes the mapping for the specified key from this map if present.
     *
     * @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>. (A <code>null</code> return can also indicate that the map previously
     *         associated <code>null</code> with <code>key</code>.)
     */
    @Override
    @Nullable
    public V remove(Object key) {
        throw new RuntimeException();
    }

    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    @Override
    public int size() {
        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.
     */
    @Override
    public Collection<V> values() {
        throw new RuntimeException();
    }
}