// Base class for an implementation of FMap<K,V>.

package fmap;

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Collections;                   // for its sort algorithm
import java.util.ArrayList;                     // for its iterator

abstract class FMapBase<K,V> implements FMap<K,V>, Iterable<K> {

    static final boolean DEBUGGING = false;     // set to true for debugging
    static final boolean SIZE_IS_FAST = true;   // if true, makes size() fast
    static final boolean HASH_IS_SIZE = false;  // if true, uses size as hash
    static final int HASH_OF_EMPTY_FMAP = 0;    // hash code for an empty FMap

    int theSize;    // if SIZE_IS_FAST, theSize is the size of this FMap

    FMapBase () { }

    private FMapBase (int theSize) {
        this.theSize = theSize;
    }

    static <K,V> FMapBase<K,V> emptyMap () {
        return AList.emptyMap();
    }

    static <K,V> FMapBase<K,V> emptyMap (Comparator<? super K> c) {
        return FTree.emptyTree(c);
    }

    // abstract methods

    // As specified by the algebraic specification,
    // returns an FMap<K,V> that associates key k with value v
    // but otherwise behaves like this FMap<K,V>.

    public abstract FMapBase<K,V> add (K x, V v);

    // Returns true if and only if this FMap<K,V> has size 0.

    public abstract boolean isEmpty ();

    // Returns the size of this FMap<K,V>.

    public abstract int size ();

    // Returns true if and only if k is a key of this FMap<K,V>.

    public abstract boolean containsKey (K x);

    // Returns the value associated with k in this FMap<K,V>.
    // May throw an exception if k is not a key of this FMap<K,V>.

    public abstract V get (K x);

    // Implementation-specific help method.
    // 
    // Returns true if and only if
    // m2 has every key that this FMapBase has
    // and associates the same values with those keys.

    abstract boolean equalsLoop (FMap<K,V> m2);

    // Implementation-specific help method.
    // 
    // Adds all keys in this FMap to the given ArrayList,
    // taking care to add each key only once.

    abstract ArrayList<K> allKeys (ArrayList<K> keys);

    // Implementation-specific help method.
    // 
    // Returns an ArrayList<K> of the keys in this FMap<K,V>,
    // with each key appearing only once.

    private ArrayList<K> allKeys () {
        ArrayList<K> keys = new ArrayList<K>();
        this.allKeys (keys);
        return keys;
    }

    @Override
    public String toString () {
        return "{...(" + size() + " entries)...}";
    }

    // overridden equals(Object)

    // Two FMap<K,V> objects are considered equal if and only if
    // they are defined on the same set of keys and each of those
    // keys is associated with the same value.

    @Override
    public boolean equals (Object x) {
        if (x instanceof FMap) {
            @SuppressWarnings(value="unchecked")
            FMap<K,V> f2 = (FMap<K,V>) x;
            return this.size() == f2.size()
                && this.equalsLoop (f2);
        }
        else return false;
    }

    // overridden hashCode()

    @Override
    public int hashCode() {
        if (HASH_IS_SIZE)
            return size();
        else {
            int result = HASH_OF_EMPTY_FMAP;
            for (K k : this)
                result
                    = result
                    + WEIGHT1 * k.hashCode()
                    + WEIGHT2 * get(k).hashCode()
                    + WEIGHT3;
            return result;
        }
    }

    // constants used above to spread out the hash codes

    private final int WEIGHT1 = 2072679696;
    private final int WEIGHT2 = 1693108132;
    private final int WEIGHT3 = 2442080;

    // iterator methods

    public Iterator<K> iterator () {
        ArrayList<K> a = this.allKeys();
        return new KeyIterator<K> (a.iterator());
    }

    public Iterator<K> iterator (java.util.Comparator<? super K> c) {
        ArrayList<K> a = this.allKeys();
        Collections.sort (a, c);
        return new KeyIterator<K> (a.iterator());
    }

    // FIXME: temporary hack for debugging

    V get (K k, int h) {
        return get (k);
    }

    // The iterator() method returns instances of this class.

    private static class KeyIterator<K> implements Iterator<K> {

        private Iterator<K> it;    // generator for keys not yet generated

        KeyIterator (Iterator<K> it) {
            this.it = it;
        }

        // The hasNext() and next() methods just delegate to it.

        public boolean hasNext () { return it.hasNext(); }

        public K next () { return it.next(); }

        // The optional remove() method is not supported.

        public void remove () {
            throw new UnsupportedOperationException ("remove");
        }
    }

}