package class9_1_HashMap;

import java.util.*;

/**
 * Note: This class has problems, as discussed in class.
 *
 * @param <K> key contained.
 * @param <V> value associated with key
 */
public class ChainingHashMap<K,V> implements Map<K,V> {
    private int MAX_SIZE = 3;
    // 1024 == 2^10 ~= 10^3  KB KiB = 1024 bytes
    private List<Entry>[] table;
    private int size;

    private class Entry {
        private K key;
        private V value;
        private Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        // TODO: Ought to implement hashCode, too
        // though I think the class will work without it.
        public boolean equals(Object obj) {
            return key.equals(((Entry)obj).key);
        }
    }

    public ChainingHashMap() {
        table = (List<Entry>[]) new List[MAX_SIZE];
        size = 0;
    }

    /**
     * Returns <tt>true</tt> if this map contains a mapping for the specified
     * key.  More formally, returns <tt>true</tt> if and only if
     * this map contains a mapping for a key <tt>k</tt> such that
     * <tt>(key==null ? k==null : key.equals(k))</tt>.  (There can be
     * at most one such mapping.)
     *
     * @param key key whose presence in this map is to be tested
     * @return <tt>true</tt> 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="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified key is null and this map
     *                              does not permit null keys
     *                              (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
     */
    @Override
    public boolean containsKey(Object key) {
        throw new UnsupportedOperationException("TODO: Homework");
    }

    /**
     * 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 by the specified value.
     *
     * @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 <tt>key</tt>, or
     * <tt>null</tt> if there was no mapping for <tt>key</tt>.
     * (A <tt>null</tt> return can also indicate that the map
     * previously associated <tt>null</tt> with <tt>key</tt>,
     * if the implementation supports <tt>null</tt> values.)
     * @throws NullPointerException          if the specified key or value is null
     *                                       and this map does not permit null keys or values
     */
    @Override
    public V put(K key, V value) {
        if(key == null) {
            throw new NullPointerException("Key is null. (Null keys not accepted in this implementation.)");
        }

        boolean isChanged = false;

        int hash = key.hashCode();
        hash = Math.abs(hash) % MAX_SIZE;

        V oldValue;
        if(table[hash] == null) {
            table[hash] = new LinkedList<Entry>();
            table[hash].add(new Entry(key, value));
            oldValue = null;
            size++;
        } else {
            if(table[hash].contains(key)) {
                System.out.println("DEBUG: Key found; replacing. Key:"+key);
                int oldIndex = table[hash].indexOf(new Entry(key,null));
                oldValue = table[hash].remove(oldIndex).value;
            } else {
                System.out.println("DEBUG: Key not found. Adding: "+ key);
                table[hash].add(new Entry(key, value));
                oldValue = null;
                size++;
            }
        }

        return oldValue;
    }

    @Override
    public void clear() {
        for(int i=0; i<table.length; i++) {
            table[i] = null;
        }
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }



    @Override
    public V remove(Object keyObj) {
        // Checking the type requires the USER to pass in the class information, since
        // the compiler doesn't have it at runtime due to type erasure.
        //
        // So I'm just going to let Java throw the exception for me...
        // if it does...
//        if(!(classK.isInstance(key))) {
//            throw new ClassCastException("Must provide an object of the Key class K");
//        }
        K key = (K) keyObj;

        V oldValue;

        int hash = key.hashCode();
        hash = Math.abs(hash)%MAX_SIZE;

        if(table[hash] == null) {
            oldValue = null;
        } else {
            int oldIndex = table[hash].indexOf(new Entry(key, null));
            oldValue = table[hash].remove(oldIndex).value;
            if(table[hash].isEmpty()) {
                table[hash] = null;
            }
            size--;
        }

        return oldValue;
    }

    @Override
    public int size() {
        return size;
    }


    // === NOT-IMPLEMENTED METHODS ===
    /**
     * Returns <tt>true</tt> if this map maps one or more keys to the
     * specified value.  More formally, returns <tt>true</tt> if and only if
     * this map contains at least one mapping to a value <tt>v</tt> such that
     * <tt>(value==null ? v==null : value.equals(v))</tt>.  This operation
     * will probably require time linear in the map size for most
     * implementations of the <tt>Map</tt> interface.
     *
     * @param value value whose presence in this map is to be tested
     * @return <tt>true</tt> 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="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified value is null and this
     *                              map does not permit null values
     *                              (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
     */
    @Override
    public boolean containsValue(Object value) {
        return false;
    }

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     * <p>
     * <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>
     * <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="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified key is null and this map
     *                              does not permit null keys
     *                              (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
     */
    @Override
    public V get(Object key) {
        return null;
    }

    /**
     * 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 <tt>k</tt> to value <tt>v</tt> 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 <tt>putAll</tt> 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) {

    }

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

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

    /**
     * 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 <tt>remove</tt> operation, or through the
     * <tt>setValue</tt> 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 <tt>Iterator.remove</tt>,
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
     * <tt>clear</tt> operations.  It does not support the
     * <tt>add</tt> or <tt>addAll</tt> operations.
     *
     * @return a set view of the mappings contained in this map
     */
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return null;
    }
}