// Implements the association list representation of an 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 AList<K,V> extends FMapBase<K,V> {

    // Returns an empty FMap<K,V> represented as an association list.

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

    // Returns a non-empty FMap<K,V> that behaves the same as this
    // FMap except the key k is associated with the value v,
    // regardless of any value that may be associated with k
    // in this FMap.

    public FMapBase<K,V> add (K k, V v) {
        return new AList.Add<K,V>(this, k, v);
    }

    // Instances of this class represent an empty FMap<K,V>.

    private static class EmptyMap<K,V> extends AList<K,V> {

        EmptyMap () { }

        // The purposes of the following methods are documented
        // in FMapBase.java.

        public boolean isEmpty () { return true; }

        public int size () { return 0; }

        public boolean containsKey (K x) { return false; }

        public V get (K x) {
            throw new IllegalArgumentException(errorMsg);
        }

        // Implementation-specific help methods and data.

        private static final String errorMsg
            = "illegal argument passed to get";

        boolean equalsLoop (FMap m2) {
            return true;
        }

        ArrayList<K> allKeys (ArrayList<K> keys) {
            return keys;
        }
    }

    // Instances of this class represent a non-empty FMap<K,V>.

    private static class Add<K,V> extends AList<K,V> {

        private FMapBase<K,V> m0;  // the rest of this association list
        private K k0;              // the first key in this association list
        private V v0;              // the value associated with the first key

        Add (FMapBase<K,V> m0, K k0, V v0) {
            this.m0 = m0;
            this.k0 = k0;
            this.v0 = v0;
            if (SIZE_IS_FAST) {
                if (m0.containsKey(k0))
                    this.theSize = m0.size();
                else
                    this.theSize = 1 + m0.size();
            }
        }

        // The purposes of the following methods are documented
        // in FMapBase.java.

        public boolean isEmpty () { return false; }

        public int size () {
            if (SIZE_IS_FAST)
                return theSize;
            if (m0.containsKey(k0))
                return m0.size();
            else
                return 1 + m0.size();
        }

        public boolean containsKey (K x) {
            if (x.equals(k0))
                return true;
            else
                return m0.containsKey(x);
        }

        public V get (K x) {
            if (x.equals(k0))
                return v0;
            else
                return m0.get(x);
        }

        // Implementation-specific help methods and data.

        boolean equalsLoop (FMap<K,V> m2) {
            FMapBase<K,V> m1 = this;
            while (! (m1.isEmpty())) {
                Add<K,V> f = (Add<K,V>) m1;
                K k0 = f.k0;
                V v0 = f.v0;
                if (! (m2.containsKey(k0))) {
                    return false;
                }
                if (! (get(k0).equals(m2.get(k0)))) {
                    return false;
                }
                m1 = f.m0;
            }
            return true;
        }

        ArrayList<K> allKeys (ArrayList<K> keys) {
            m0.allKeys (keys);
            if (! (m0.containsKey (k0)))
                keys.add (k0);
            return keys;
        }
    }
}