// Abstract base class for classes that implement IMap<K,V> or SortedIMap<K,V>.
//
// To define a class that implements IMap<K,V>:
//     make that class a subclass of this base class
//     within that class, define the following abstract methods:
//         public    IMap<K,V>   extend(K key, V value)
//         protected boolean     hasKey(K key)
//         protected V           getVal(K key)
//         protected Iterator<K> keyIterator()
//     within that class, override the following methods:
//         public    int         size()
//
// To define a class that implements SortedIMap<K,V>:
//     make that class a subclass of SortedIMapBase<K,V>
//     define or override the methods listed above
//     define comparator()

import java.util.Map;
import java.util.Map.Entry;
import java.util.AbstractMap;
import java.util.AbstractMap.SimpleImmutableEntry;

import java.util.Set;
import java.util.AbstractSet;

import java.util.List;
import java.util.ArrayList;

import java.util.Iterator;

// Strategy, quoted from the documentation for AbstractMap:
//
// To implement an unmodifiable map, the programmer needs only to
// extend [the AbstractMap] class and provide an implementation
// for the entrySet method, which returns a set-view of the map's
// mappings.  Typically, the returned set will, in turn, be
// implemented atop AbstractSet.  This set should not support the
// add or remove methods, and its iterator should not support the
// remove method.

abstract class IMapBase<K,V> extends AbstractMap<K,V> implements IMap<K,V> {

    // Java constructor

    protected IMapBase () { }

    // public methods listed by IMap<K,V> interface

    // Returns an IMap like this one except the given key is associated
    // with the given value.  The extend operation does not modify this
    // IMap.

    public abstract IMap<K,V> extend (K key, V value);

    // public methods listed by Map<K,V> interface

    // Returns true iff this map contains a mapping for the given key.

    @Override
    @SuppressWarnings("unchecked")
    public boolean containsKey (Object x) {
        if (x == null) {
            String nullMsg = "null values aren't allowed by IMap<K,V>";
            throw new NullPointerException (nullMsg);
        }
        else {
            K key = (K) x;
            return hasKey (key);
        }
    }

    // Returns the value associated with the given key,
    // or null if the key is not contained within the map.

    @Override
    @SuppressWarnings("unchecked")
    public V get (Object x) {
        if (containsKey (x)) {
            K key = (K) x;
            return getVal (key);
        }
        else return null;
    }

    // Returns true iff this map contains no key/value mappings.

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

    // Returns a set of the key/value pairs in this Map.

    public Set<Entry<K,V>> entrySet () {
        Iterator<K> it = keyIterator();
        List<Entry<K,V>> entries = new ArrayList<Entry<K,V>>();
        while (it.hasNext()) {
            K key = it.next();
            V value = getVal (key);
            Entry<K,V> entry = new SimpleImmutableEntry<K,V> (key, value);
            entries.add (entry);
        }
        return new ListSet<K,V> (entries);
    }

    // all other public methods are defined by AbstractMap<K,V>

    // overriding the usual triumvirate

    // Unsorted maps are equal if they have equal keys and values.
    // Unsorted maps are never considered equal to sorted maps
    // because the existence of a comparator method creates an
    // observable difference, and the comparator might not be
    // consistent with the equals method on keys.

    @SuppressWarnings("unchecked")
    public boolean equals (Object x) {
        if (x instanceof IMapBase) {
            IMapBase<K,V> m = (IMapBase<K,V>) x;
            if (x instanceof SortedIMapBase)
                return false;
            else if (this.size() != m.size())
                return false;
            else {
                Iterator<K> it = keyIterator();
                while (it.hasNext()) {
                    K key = it.next();
                    if (m.hasKey(key) &&
                        this.getVal(key).equals(m.getVal(key)))
                        ; // do nothing
                    else return false;
                }
                return true;
            }
        }
        else return false;
    }

    // The hash code of an unsorted map cannot depend on the order
    // in which keys are generated by the iterator, so we can't
    // cut this computation off early.

    public int hashCode () {
        Iterator<K> it = keyIterator();
        int result = 434937289;
        while (it.hasNext()) {
            K key = it.next();
            V val = getVal (key);
            int keyHash = key.hashCode();
            int valHash = val.hashCode();
            result = result + 1232250328 * keyHash - 1436654170 * valHash;
        }
        return result;
    }

    public String toString () {
        System.out.println (super.toString());
        return "an IMap of size " + size() + " and hash " + hashCode();
    }

    // abstract help methods

    // Returns true iff this map has a mapping for the given key.

    protected abstract boolean hasKey (K key);

    // Returns the value associated with the given key.

    protected abstract V getVal (K key);

    // Returns an iterator for the keys of this IMap.

    protected abstract Iterator<K> keyIterator();
}

class ListSet<K,V> extends AbstractSet<Entry<K,V>> {

    List<Entry<K,V>> entries;

    // Java constructors

    ListSet (List<Entry<K,V>> entries) {
        this.entries = entries;
    }

    // public methods

    // Returns an Iterator for the entries in this set.

    public Iterator<Entry<K,V>> iterator () {
        return entries.iterator ();
    }

    // Returns the size of this set.

    public int size () { return entries.size(); }
}