/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

package ds.destructive.map;

/** Implementation of maps with hash maps implemeted as arrays

    hash maps require a a hash function on the
    keys of a map. These hashes are used for indexing the
    hash table.

    This is a DESTRUCTIVE implementation.
*/

import ds.interfaces.Map;

import ds.util.K;  // example class for keys
import ds.util.V;  // example class for values
import ds.util.KV; // key value pair
import static ds.util.KV.mkPair;

import ds.util.Function2;
import ds.util.Invariant;
import ds.util.Pair;
import ds.util.Predicate;

import java.util.Iterator;

import static ds.util.Undef.undefined;

//----------------------------------------

public
    class SimpleHashMap
    implements Map {

    //----------------------------------------

    private int     card;
    private KV []  elems;

    SimpleHashMap (int len) {
        card   = 0;
        elems  = new KV [len];
        ++cntMap;
    }

    //----------------------------------------
    // the smart constructors

    // empty list
    public static SimpleHashMap empty() {
        return
            empty(16); // why 16?
    }

    public static SimpleHashMap empty(int length) {
        int l = 16;
        while (l < length) l *= 2;

        // length of hash table is always a power of 2
        // for efficient modulo operations

        return
            new SimpleHashMap(length);
    }

    public static
        SimpleHashMap fromIterator(Iterator<KV> elems) {

        SimpleHashMap res = empty();
        while ( elems.hasNext() ) {
            KV p = elems.next();
            res  = res.insert(p);
        }
        return
            res;
    }

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

    public boolean member(K k) {
        return
            lookup(k) != null;
    }

    public int size() {
        return
            card;
    }

    public V lookup(K k) {
        int ix = keyToHash(k);
        KV  kv = elems[ix];

        while ( kv != null
                &&
                ! kv.fst.equalTo(k)
                ) {
            incr(ix);
            kv = elems[ix];
        }

        return
            kv == null ? null : kv.snd;
    }

    public KV findMin() {
        return
            undefined("findMin not implemented");
    }

    public KV findMax() {
        return
            undefined("findMax not implemented");
    }

    public SimpleHashMap insert(K k, V v) {
        return
            insert(mkPair(k,v));
    }

    public SimpleHashMap insert(KV p) {
        K   k  = p.fst;
        int ix = keyToHash(k);
        KV  kv = elems[ix];

        while ( kv != null
                &&
                ! kv.fst.equalTo(k)
                ) {
            incr(ix);
            kv = elems[ix];
        }

        if (kv == null) {
            // new elem
            elems[ix] = p;
            ++card;
        } else {
            // update of value
            elems[ix] = p;
        }

        return
            checkExpand();
    }

    public SimpleHashMap remove(K k) {
        return
            undefined("remove not implemented");
    }

    public SimpleHashMap union(Map m2) {
        return
            unionWith(const2, m2);
    }

    public
    SimpleHashMap unionWith(Function2<V,V,V> op,
				Map m2) {
        return undefined("unionWith not implemented");
    }

    public
    SimpleHashMap difference(Map m2) {
        return
            differenceWith(null2, m2);
    }

    public
    SimpleHashMap differenceWith(Function2<V,V,V> op,
				 Map m2) {
        return
            undefined("differenceWith not implemented");
    }

    public SimpleHashMap copy() {
        return
            this;
    }

    public Iterator<KV> iterator() {
        ++cntIter;
        return
            new HashMapIterator(this);
    }

    public boolean inv() {
        for (int i = 0; i < elems.length; ++i) {
            if (elems[i] != null) {
                int ix = keyToHash(elems[i].fst);

                /* all entries in hashtable
                   in the intervall [ix..i]
                   must be filled, otherwise the hash does not
                   fit to the position
                */
                int j = i;
                while (j != ix) {
                    decr(j);
                    if (elems[j] == null)
                        // unused cell found
                        return
                            false;
                }
            }
        }

        return true;
    }

    //----------------------------------------
    // internal methods

    private static Function2<V,V,V> const2
        = new Function2<V,V,V>() {
        public V apply(V x, V y) {
            return y;
        }
    };

    private static Function2<V,V,V> null2
        = new Function2<V,V,V>() {
        public V apply(V x, V y) {
            return null;
        }
    };

    private int keyToHash(K k) {
        return
            k.hash() & (elems.length - 1);
    }

    private int incr(int i) {
        ++i;
        return
            i == elems.length ? 0 : i;
    }

    private int decr(int i) {
        return
            (i == 0 ? elems.length : i) - 1;
    }

    private SimpleHashMap checkExpand() {
        if (card > elems.length) {
            return
                reorganize(2 * elems.length);
        }
        return this;
    }

    private SimpleHashMap reorganize(int newSize) {
        SimpleHashMap nm = empty(newSize);
        for (int i = 0; i < elems.length; ++i) {
            nm = nm.insert(elems[i]);
        }
        return
            nm;
    }

    private static
        class HashMapIterator
        extends ds.util.Iterator<KV> {

        SimpleHashMap map;
        int len;
        int ix;

        HashMapIterator(SimpleHashMap m) {
            map = m;
            ix  = 0;
            len = m.elems.length;
            advance();
            ++cntIter;
        }

        public boolean hasNext() {
            return
                ix < len;
        }

        private void advance() {
            while ( ix < len
                    &&
                    map.elems[ix] == null
                  ) {
                ++ix;
            }
        }

        public KV next() {
            if ( ix == len )
                return
                    undefined("empty hashmap");
            KV res = map.elems[ix];
            ++ix;
            advance();
            return
                res;
        }
    }

    //----------------------------------------
    // profiling

    private static int cntMap  = 0;
    private static int spcMap = 0;
    private static int cntIter = 0;

    public static String stats() {
        return
            "stats for ds.destructive.map.SimpleHashMap:\n" +
            "# new SimpleHashMap()      : " + cntMap + "\n" +
            "# words SimpleHashMap()    : " + spcMap + "\n" +
            "# new Iterator()           : " + cntIter + "\n";
    }

    public String objStats() {
        int o =
            1 +   // SimpleHashMap
            1 +   // array
            card; // KV

        int f =
            2 +                // SimpleHashMap
            elems.length + 1 + // array
            card * 2;          // KV
        int m = o + f;

        return
            "mem stats for ds.destructive.map.SimpleHashMap object:\n" +
            "# objects              : " + o + "\n" +
            "# fields               : " + f + "\n" +
            "# mem words            : " + m + "\n";
    }
}