/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.maps;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import net.ranides.assira.collection.ACollection;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArrayUtils;
import net.ranides.assira.collection.arrays.NativeArray;
import net.ranides.assira.collection.sets.ASet;
import net.ranides.assira.collection.utils.HashCollection;
import net.ranides.assira.generic.HashUtils;
import net.ranides.assira.generic.CompareUtils;
import net.ranides.assira.math.MathUtils;

/**
 *
 * @author Ranides Atterwim <ranides@gmail.com>
 */
public abstract class AHashMap<K,V> extends AMap<K, V> implements BlockMap<K, V>, java.io.Serializable {
   
    private static final long serialVersionUID = 4L;
    
    /**
     * The array of mkeys.
     */
    protected transient K[] keys;
    /**
     * The array of mvalues.
     */
    protected transient V[] values;
    /**
     * The array telling whether a position is used.
     */
    protected transient boolean used[];
    /**
     * The acceptable load factor.
     */
    protected final float factor;
    /**
     * The current table size.
     */
    protected transient int n;
    /**
     * Threshold after which we irehash. It must be the table size times
     * {@link #factor}.
     */
    protected transient int capacity;
    /**
     * The mask for wrapping a position counter.
     */
    protected transient int mask;
    /**
     * Number of mentries in the set.
     */
    protected int size;
    /**
     * Cached set of mentries.
     */
    protected transient volatile Set<Entry<K, V>> mentries;
    /**
     * Cached set of mkeys.
     */
    protected transient volatile Set<K> mkeys;
    /**
     * Cached collection of mvalues.
     */
    protected transient volatile Collection<V> mvalues;

    @SuppressWarnings("unchecked")
    public AHashMap(int expected, float factor) {
        if (factor <= 0 || factor > 1) {
            throw new IllegalArgumentException("Load factor must be greater than 0 and smaller than or equal to 1");
        }
        if (expected < 0) {
            throw new IllegalArgumentException("The expected number of elements must be nonnegative");
        }
        this.factor = factor;
        n = HashCollection.arraysize(expected, factor);
        mask = n - 1;
        capacity = HashCollection.factorsize(n, factor);
        keys = (K[]) new Object[n];
        values = (V[]) new Object[n];
        used = new boolean[n];
    }

    protected abstract int hash(K key);
    
    protected boolean compare(K key1, K key2) {
        return compare(key1, null, key2, null);
    }
    
    protected abstract boolean compare(K key1, V value1, K key2, V value2);
    
    @Override
    public final V put(K key, V value) {
        int pos = AHashMap.this.ifind(key, value);
        return used[pos] ? ireplace(pos, value) : iinsert(pos, key, value);
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public final V remove(Object key) {
        int pos = ifind((K)key);
        return used[pos] ? ishift(pos) : null;
    }
    
    @Override
    public boolean remove(Object key, Object value) {
        int pos;
        if(used[pos = ifind((K)key, (V)value)] && CompareUtils.equals(values[pos], value)) {
            ishift(pos);
            return true;
        }
        return false;
    }

    @SuppressWarnings("unchecked")
    @Override
    public final V get(Object key) {
        int pos = ifind((K)key);
        return used[pos] ? values[pos] : null; 
    }

    @SuppressWarnings("unchecked")
    @Override
    public final boolean containsKey(Object key) {
        return used[ifind((K)key)];
    }

    @Override
    public final boolean containsValue(Object value) {
        final V ivalues[] = this.values;
        final boolean iused[] = this.used;
        for (int i = n; i-- != 0;) {
            if(iused[i] && CompareUtils.equals(ivalues[i], value)) {
                return true;
            }
        }
        return false;
    }
    
    @Override
    public final void clear() {
        if (size == 0) {
            return;
        }
        size = 0;
        NativeArrayUtils.fill(NativeArray.wrap(used), false);
        ArrayUtils.fill(keys, null);
        ArrayUtils.fill(values, null);
    }

    @Override
    public final int size() {
        return size;
    }

    @Override
    public final boolean isEmpty() {
        return size == 0;
    }
    
    @Override
    public final Set<Entry<K, V>> entrySet() {
        if (mentries == null) {
            mentries = new MapEntrySet();
        }
        return mentries;
    }
    
    public final Iterator<Entry<K, V>> fastEntryIterator() {
        return new FastEntryIterator();
    }
    
    @Override
    public final Set<K> keySet() {
        if (mkeys == null) {
            mkeys = new KeySet();
        }
        return mkeys;
    }

    @Override
    public final Collection<V> values() {
        if (mvalues == null) {
            mvalues = new ValueCollection();
        }
        return mvalues;
    }

    @Override
    public int capacity() {
        return capacity;
    }

    /**
     * Rehashes the map, making the table as small as possible.
     *
     * <P>This method rehashes the table to the smallest size satisfying the
     * load factor. It can be used when the set will not be changed anymore, so
     * to optimize access speed and size.
     *
     * <P>If the table size is already the minimum possible, this method does
     * nothing.
     *
     * @return true if there was enough memory to trim the map.
     * @see #trim(int)
     */
    @Override
    public final boolean trim() {
        final int l = HashCollection.arraysize(size, factor);
        if (l >= n) {
            return true;
        }
        try {
            irehash(l);
        } catch (OutOfMemoryError cantDoIt) {
            return false;
        }
        return true;
    }

    /**
     * Rehashes this map if the table is too large.
     *
     * <P>Let <var>N</var> be the smallest table size that can hold
     * <code>max(n,{@link #size()})</code> mentries, still satisfying the load
     * factor. If the current table size is smaller than or equal to
     * <var>N</var>, this method does nothing. Otherwise, it rehashes this map
     * in a table of size
     * <var>N</var>.
     *
     * <P>This method is useful when reusing maps. null null null     {@linkplain #clear() Clearing a
	 * map} leaves the table size untouched. If you are reusing a map many
     * times, you can call this method with a typical size to avoid keeping
     * around a very large table just because of a few large transient maps.
     *
     * @param n the threshold for the trimming.
     * @return true if there was enough memory to trim the map.
     * @see #trim()
     */
    @Override
    public final boolean trim(int n) {
        int l = MathUtils.pow2next((int) Math.ceil(n / factor));
        if (this.n <= l) {
            return true;
        }
        if(l<size) {
            throw new IllegalArgumentException(String.format("n= %d is too small (L=%d size=%d)", n, l, size));
        }
        try {
            irehash(l);
        } catch (OutOfMemoryError cantDoIt) {
            return false;
        }
        return true;
    }

    /**
     * Returns a hash code for this map.
     *
     * This method overrides the generic method provided by the superclass.
     * Since
     * <code>equals()</code> is not overriden, it is important that the values
     * returned by this method is the same values as the one returned by the
     * overriden method.
     *
     * @return a hash code for this map.
     */
    @Override
    public final int hashCode() {
        int h = 0;
        for (int j = size, i = 0, t = 0; j-- != 0;) {
            while (!used[ i]) {
                i++;
            }
            if (this != keys[ i]) {
                t = hash(keys[i]);
            }
            if (this != values[ i]) {
                t ^= (values[ i] == null ? 0 : values[ i]).hashCode();
            }
            h += t;
            i++;
        }
        return h;
    }
    
    @Override
    public final boolean equals(Object object) {
        return super.equals(object);
    }
 
    @SuppressWarnings("unchecked")
    protected void irehash(int newN) {
        int i = 0, pos;
        final boolean iused[] = this.used;
        K ckey;
        final K ikeys[] = this.keys;
        final V ivalues[] = this.values;
        final int newMask = newN - 1;
        final K newKey[] = (K[]) new Object[newN];
        final V newValue[] = (V[]) new Object[newN];
        final boolean newUsed[] = new boolean[newN];
        for (int j = size; j-- != 0;) {
            while (!iused[ i]) {
                i++;
            }
            ckey = ikeys[ i];
            pos = HashUtils.murmurHash3(hash((K)ckey)) & newMask;
            while (newUsed[ pos]) {
                pos = (pos + 1) & newMask;
            }
            newUsed[pos] = true;
            newKey[pos] = ckey;
            newValue[pos] = ivalues[ i];
            i++;
        }
        n = newN;
        mask = newMask;
        capacity = HashCollection.factorsize(n, factor);
        this.keys = newKey;
        this.values = newValue;
        this.used = newUsed;
    }
    
    protected int ifind(K key, V value) {
        // There's always an unused entry.
        int i = HashUtils.murmurHash3(hash((K)key)) & mask;
        while (used[i] && !compare(keys[i], values[i], key, value)) {
            i = (i+1) & mask;
        }
        return i;
    }
    
    protected int ifind(K key) {
        // There's always an unused entry.
        int i = HashUtils.murmurHash3(hash((K)key)) & mask;
        while (used[i] && !AHashMap.this.compare(keys[i], key)) {
            i = (i+1) & mask;
        }
        return i;
    }

    protected V ireplace(int segment, V value) {
        V prev = values[segment];
        values[segment] = value;
        return prev;
    }
    
    protected V iinsert(int segment, K key, V value) {
        used[segment] = true;
        keys[segment] = key;
        values[segment] = value;
        
        if (++size >= capacity) {
            irehash(HashCollection.arraysize(size + 1, factor));
        }
        return null;
    }

    protected final V ishift(int pos) {
        size--;
        V prev = values[pos];
        int last;
        for (;;) {
            last = pos;
            pos = inext(pos);
            if (!used[pos]) {
                break;
            }
            imove(last, pos);
        }
        iclear(last);
        return prev;
    }
        
    protected int inext(int last) {
        int pos = (last+1) & mask;
        while (used[pos]) {
            int slot = HashUtils.murmurHash3(hash((K)keys[pos])) & mask;
            if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) {
                break;
            }
            pos = (pos + 1) & mask;
        }
        return pos;
    }
    
    protected void imove(int target, int source) {
        keys[target] = keys[source];
        values[target] = values[source];
    }
    
    protected void iclear(int segment) {
        used[segment] = false;
        keys[segment] = null;
        values[segment] = null;
    }
    
    protected void readObjectDetails(java.io.ObjectInputStream istream) throws java.io.IOException, ClassNotFoundException {
        // do nothing
    }
    
    protected void writeObjectDetails(java.io.ObjectOutputStream ostream) throws java.io.IOException {
        // do nothing
    }

    private void writeObject(java.io.ObjectOutputStream ostream) throws java.io.IOException {
        final K key[] = this.keys;
        final V value[] = this.values;
        final MapIterator iterator = new MapIterator();
        ostream.defaultWriteObject();
        writeObjectDetails(ostream);
        for (int j = size, e; j-- != 0;) {
            e = iterator.nextEntry();
            ostream.writeObject(key[ e]);
            ostream.writeObject(value[ e]);
        }
    }

    @SuppressWarnings({
        "unchecked",
        "MismatchedReadAndWriteOfArray"
    })
    private void readObject(java.io.ObjectInputStream istream) throws java.io.IOException, ClassNotFoundException {
        istream.defaultReadObject();
        readObjectDetails(istream);
        n = HashCollection.arraysize(size, factor);
        capacity = HashCollection.factorsize(n, factor);
        mask = n - 1;
        final K key[] = this.keys = (K[]) new Object[n];
        final V value[] = this.values = (V[]) new Object[n];
        final boolean iused[] = this.used = new boolean[n];
        K ckey;
        V cval;
        for (int i = size, pos; i-- != 0;) {
            ckey = (K) istream.readObject();
            cval = (V) istream.readObject();
            pos = HashUtils.murmurHash3(hash((K)ckey)) & mask;
            while (iused[ pos]) {
                pos = (pos + 1) & mask;
            }
            iused[ pos] = true;
            key[ pos] = ckey;
            value[ pos] = cval;
        }
    }
    
    private final class MapEntry implements Map.Entry<K, V> {

        int index;

        MapEntry(int index) {
            this.index = index;
        }

        @Override
        public K getKey() {
            return keys[index];
        }

        @Override
        public V getValue() {
            return values[index];
        }

        @Override
        public V setValue(V value) {
            return ireplace(index, value);
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean equals(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
            return AHashMap.this.compare(keys[index], entry.getKey()) && CompareUtils.equals(values[index], entry.getValue());
        }

        @Override
        public int hashCode() {
            return (hash((K)keys[ index])) ^ HashUtils.hash(values[index]);
        }

        @Override
        public String toString() {
            return keys[index] + "=>" + values[index];
        }
    }

    private class MapIterator {

        /**
         * The index of the next entry to be returned, if positive or zero. If
         * negative, the next entry to be returned, if any, is that of index
         * -pos -2 from the {@link #kwrapped} list.
         */
        int mpos;
        /**
         * The index of the last entry that has been returned. It is -1 if
         * either we did not return an entry yet, or the last returned entry has
         * been removed.
         */
        int mlast;
        /**
         * A downward counter measuring how many mentries must still be returned.
         */
        int counter;
        /**
         * A lazily allocated list containing the keys of elements that have
         * wrapped around the table because of removals; such elements would not
         * be enumerated (other elements would be usually enumerated twice in
         * their place).
         */
        ArrayList<K> kwrapped;
        ArrayList<V> vwrapped;

        public MapIterator() {
            this.mpos = AHashMap.this.n;
            this.mlast = -1;
            this.counter = size;

            boolean used[] = AHashMap.this.used;
            if (counter != 0) {
                while (!used[ --mpos]) { } // NOPMD
            }
        }

        public boolean hasNext() {
            return counter != 0;
        }

        public int nextEntry() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            counter--;
            // We are just enumerating elements from the wrapped list.
            if (mpos < 0) {
                mpos--;
                final K ckey = kwrapped.get(-mpos - 2);
                final V cval = vwrapped.get(-mpos - 2);
                mlast = mpos;
                int pos = ifind(ckey, cval);
                if(used[pos]) {
                    return pos;
                }
            }
            mlast = mpos;
            if (counter != 0) {
                final boolean used[] = AHashMap.this.used;
                while (mpos-- != 0 && !used[ mpos]) { } // NOPMD
                // When here pos < 0 there are no more elements to be enumerated by scanning, but wrapped might be nonempty.
            }
            return mlast;
        }

        protected final int ishift(int pos) {
            int last;
            for (;;) {
                last = pos;
                pos = inext(last);
                if (!used[ pos]) {
                    break;
                }
                if (pos < last) {
                    if (kwrapped == null) {
                        kwrapped = new ArrayList<>();
                        vwrapped = new ArrayList<>();
                    }
                    kwrapped.add(keys[pos]);
                    vwrapped.add(values[pos]);
                }
                imove(last, pos);
            }
            iclear(last);
            return last;
        }

        @SuppressWarnings("unchecked")
        public void remove() {
            if (mlast == -1) {
                throw new IllegalStateException();
            }
            if (mpos < -1) {
                // We're removing wrapped mentries.
                AHashMap.this.remove(kwrapped.set(-mpos - 2, null), vwrapped.set(-mpos - 2, null));
                mlast = -1;
                return;
            }
            size--;
            if (ishift(mlast) == mpos && counter > 0) {
                counter++;
                nextEntry();
            }
            mlast = -1; // You can no longer remove this entry.
        }

    }

    private final class EntryIterator extends MapIterator implements Iterator<Entry<K, V>> {

        private MapEntry entry;

        @Override
        public Entry<K, V> next() {
            return (entry = new MapEntry(nextEntry()));
        }

        @Override
        public void remove() {
            super.remove();
            entry.index = -1; // You cannot use a deleted entry.
        }
    }

    private final class FastEntryIterator extends MapIterator implements Iterator<Entry<K, V>> {

        final BasicEntry<K, V> entry = new BasicEntry<>(null, null);

        @Override
        public BasicEntry<K, V> next() {
            int index = nextEntry();
            entry.key = keys[index];
            entry.value = values[index];
            return entry;
        }
    }

    private final class MapEntrySet extends ASet<Entry<K, V>> {

        @Override
        public Iterator<Entry<K, V>> iterator() {
            return new EntryIterator();
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean contains(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
			int pos = ifind(entry.getKey(), entry.getValue());
			return used[pos] && CompareUtils.equals(entry.getValue(), values[pos]);
        }

        @SuppressWarnings("unchecked")
        @Override
        public boolean remove(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            Map.Entry<K, V> entry = (Map.Entry<K, V>) object;
            int pos = ifind(entry.getKey(), entry.getValue());
            if( used[pos] && CompareUtils.equals(entry.getValue(), values[pos]) ) {
                AHashMap.this.ishift(pos);
                return true;
            } else {
                return false;
            }
        }

        @Override
        public int size() {
            return size;
        }

        @Override
        public void clear() {
            AHashMap.this.clear();
        }
    }

    private final class KeyIterator extends MapIterator implements Iterator<K> {

        @Override
        public K next() {
            return keys[nextEntry()];
        }
    }

    private final class KeySet extends ASet<K> {

        @Override
        public Iterator<K> iterator() {
            return new KeyIterator();
        }

        @Override
        public int size() {
            return size;
        }

        @Override
        @SuppressWarnings("element-type-mismatch")
        public boolean contains(Object key) {
            return containsKey(key);
        }

        @Override
        @SuppressWarnings("element-type-mismatch")
        public boolean remove(Object key) {
            final int prev = size;
            AHashMap.this.remove(key);
            return size != prev;
        }

        @Override
        public void clear() {
            AHashMap.this.clear();
        }
    }

    private final class ValueIterator extends MapIterator implements Iterator<V> {

        @Override
        public V next() {
            return values[ nextEntry()];
        }
    }
    
    private final class ValueCollection extends ACollection<V> {
        @Override
        public Iterator<V> iterator() {
            return new ValueIterator();
        }

        @Override
        public int size() {
            return size;
        }

        @Override
        @SuppressWarnings("element-type-mismatch")
        public boolean contains(Object value) {
            return containsValue(value);
        }

        @Override
        public void clear() {
            AHashMap.this.clear();
        }
    }
    
}
