// 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;
    static final boolean SIZE_IS_FAST = true;
    static final boolean HASH_IS_SIZE = false;
    static final int HASH_OF_EMPTY_FMAP = 0;

    int theSize; // initialized only if SIZE_IS_FAST

    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

    public abstract FMapBase<K,V> add (K x, V v);
    public abstract boolean isEmpty ();
    public abstract int size ();
    public abstract boolean containsKey (K x);
    public abstract V get (K x);

    // 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);
    abstract ArrayList<K> allKeys (ArrayList<K> keys);

    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)

    @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);
    }

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

        private Iterator<K> it;

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

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

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

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

}