/*
 * @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 net.ranides.assira.collection.ACollection;
import net.ranides.assira.collection.iterators.IntIterator;
import net.ranides.assira.collection.sets.AIntSet;
import net.ranides.assira.collection.sets.ASet;
import net.ranides.assira.collection.arrays.NativeArrayUtils;
import net.ranides.assira.generic.HashUtils;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.function.Predicate;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArray;
import net.ranides.assira.collection.lists.IntArrayList;
import net.ranides.assira.collection.utils.HashCollection;
import net.ranides.assira.collection.lists.IntList;
import net.ranides.assira.collection.sets.IntSet;
import net.ranides.assira.generic.CompareUtils;
import net.ranides.assira.math.MathUtils;

/**
 * A type-specific hash map with primitive int mkeys.
 */
@SuppressWarnings({
    "PMD.AvoidReassigningParameters",
    "EqualsAndHashcode"
})
public abstract class AIntHashMap<V> extends AIntMap<V> implements BlockMap<Integer, V>, java.io.Serializable {

    private static final long serialVersionUID = 5L;

    /**
     * The array of mkeys.
     */
    protected transient int[] 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<IntEntry<V>> mentries;
    /**
     * Cached set of mkeys.
     */
    protected transient volatile IntSet mkeys;
    /**
     * Cached collection of mvalues.
     */
    protected transient volatile Collection<V> mvalues;

    /**
     * Creates a new hash map.
     *
     * <p>The actual table size will be the least power of two greater than
     * <code>expected</code>/
     * <code>factor</code>.
     *
     * @param expected the expected number of elements in the hash set.
     * @param f the load factor.
     */
    @SuppressWarnings("unchecked")
    public AIntHashMap(int expected, float f) {
        if (f <= 0 || f > 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 = f;
        n = HashCollection.arraysize(expected, f);
        mask = n - 1;
        capacity = HashCollection.factorsize(n, f);
        keys = new int[n];
        values = (V[]) new Object[n];
        used = new boolean[n];
    }

    protected abstract int hash(int key);
    
    protected boolean compare(int key1, int key2) {
        return compare(key1, null, key2, null);
    }
    
    protected abstract boolean compare(int key1, V value1, int key2, V value2);

    @Override
    public final V put(int key, V value) {
        int pos = ifind(key, value);
        return used[pos] ? ireplace(pos, value) : iinsert(pos, key, value);
    }

    @SuppressWarnings("unchecked")
    @Override
    public V remove(int key) {
        int pos = ifind(key);
        return used[pos] ? ishift(pos) : null;
    }
    
    @Override
    public boolean remove(int key, Object value) {
        int pos;
        if(used[pos = ifind(key, (V)value)] && CompareUtils.equals(values[pos], value)) {
            ishift(pos);
            return true;
        }
        return false;
    }

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

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

    @Override
    public 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 void clear() {
        if (size == 0) {
            return;
        }
        size = 0;
        NativeArrayUtils.fill(NativeArray.wrap(used), false);
		// ArrayUtils.fill(keys, null);
        ArrayUtils.fill(values, null);
    }

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

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
	
    @Override
    public Set<IntEntry<V>> fastEntrySet() {
        if (mentries == null) {
            mentries = new MapEntrySet();
        }
        return mentries;
    }
    
    public final Iterator<IntEntry<V>> fastEntryIterator() {
        return new FastEntryIterator();
    }

    @Override
    public IntSet keySet() {
        if (mkeys == null) {
            mkeys = new KeySet();
        }
        return mkeys;
    }
	
	@Override
    public Collection<V> values() {
        if (mvalues == null) {
            mvalues = new 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() {
                    AIntHashMap.this.clear();
                }
            };
        }
        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 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. {@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.
     */
    @SuppressWarnings("PMD.OverrideBothEqualsAndHashcode")
    @Override
    public int hashCode() {
        int h = 0;
        for (int j = size, i = 0, t; j-- != 0;) {
            while (!used[ i]) {
                i++;
            }
            t = keys[i];
            if (this != values[ i]) {
                t ^= ((values[ i]) == null ? 0 : (values[ i]).hashCode());
            }
            h += t;
            i++;
        }
        return h;
    }
	
	    @SuppressWarnings("unchecked")
    protected void irehash(int newN) {
        int i = 0, pos;
        final boolean iused[] = this.used;
        int k;
        final int key[] = this.keys;
        final V value[] = this.values;
        final int newMask = newN - 1;
        final int newKey[] = new int[newN];
        final V newValue[] = (V[]) new Object[newN];
        final boolean newUsed[] = new boolean[newN];
        for (int j = size; j-- != 0;) {
            while (!iused[ i]) {
                i++;
            }
            k = key[ i];
            pos = HashUtils.murmurHash3(k) & newMask;
            while (newUsed[ pos]) {
                pos = (pos + 1) & newMask;
            }
            newUsed[ pos] = true;
            newKey[ pos] = k;
            newValue[ pos] = value[ i];
            i++;
        }
        n = newN;
        mask = newMask;
        capacity = HashCollection.factorsize(n, factor);
        this.keys = newKey;
        this.values = newValue;
        this.used = newUsed;
    }
	
	protected int ifind(int key) {
        // There's always an unused entry.
        int i = hash(key) & mask;
        while (used[i] && !compare(keys[i], key)) {
            i = (i+1) & mask;
        }
        return i;
    }
    
    protected int ifind(int key, V value) {
        // There's always an unused entry.
        int i = hash(key) & mask;
        while (used[i] && !compare(keys[i], values[i], key, value)) {
            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, int 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 = hash(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;
        values[segment] = null;
    }

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

    @SuppressWarnings({
        "unchecked",
        "MismatchedReadAndWriteOfArray"
    })
    private void readObject(java.io.ObjectInputStream istream) throws java.io.IOException, ClassNotFoundException {
        istream.defaultReadObject();
        n = HashCollection.arraysize(size, factor);
        capacity = HashCollection.factorsize(n, factor);
        mask = n - 1;
        final int ikeys[] = this.keys = new int[n];
        final V ivalues[] = this.values = (V[]) new Object[n];
        final boolean iused[] = this.used = new boolean[n];
        int ckey;
        V cval;
        for (int i = size, pos; i-- != 0;) {
            ckey = istream.readInt();
            cval = (V) istream.readObject();
            pos = HashUtils.murmurHash3(ckey) & mask;
            while (iused[ pos]) {
                pos = (pos + 1) & mask;
            }
            iused[ pos] = true;
            ikeys[ pos] = ckey;
            ivalues[ pos] = cval;
        }
    }
	
	
	
    private final class MapEntry implements IntEntry<V>, Map.Entry<Integer, V> {
        // The table index this entry refers to, or -1 if this entry has been deleted.

        int index;

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

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

        @Override
        public int getIntKey() {
            return keys[ index];
        }

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

        @Override
        public V setValue(V value) {
            final V prev = values[ index];
            values[ index] = value;
            return prev;
        }

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

        @Override
        public int hashCode() {
            return (keys[index]) ^ ((values[index]) == null ? 0 : (values[index]).hashCode());
        }

        @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 mkeys 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).
         */
        IntList kwrapped;
        List<V> vwrapped;

		public MapIterator() {
			this.mpos = AIntHashMap.this.n;
			this.mlast = -1;
			this.counter = size;
			final boolean used[] = AIntHashMap.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 int ckey = kwrapped.getInt(-mpos - 2);
                final V cval = vwrapped.get(-mpos - 2);
                mlast = mpos;
                int pos = ifind(ckey, cval);
                if(used[pos]) {
                    return pos;
                }
            }
            mlast = mpos;
            //System.err.println( "Count: " + c );
            if (counter != 0) {
                final boolean used[] = AIntHashMap.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 IntArrayList();
                        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.
                AIntHashMap.this.remove(kwrapped.getInt(-mpos - 2), vwrapped.get(-mpos - 2));
                mlast = -1;
                return;
            }
            size--;
            if (ishift(mlast) == mpos && counter > 0) {
                counter++;
                nextEntry();
            }
            mlast = -1; // You can no longer remove this entry.
        }

    }

    private class EntryIterator extends MapIterator implements Iterator<IntEntry<V>> {

        private MapEntry entry;

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

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

    private class FastEntryIterator extends MapIterator implements Iterator<IntEntry<V>> {

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

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

    private final class MapEntrySet extends ASet<IntEntry<V>> {

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

        @SuppressWarnings("unchecked")
        @Override
        public boolean contains(Object object) {
            if (!(object instanceof Map.Entry)) {
                return false;
            }
            final Map.Entry<Integer, V> entry = (Map.Entry<Integer, 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<Integer, V> entry = (Map.Entry<Integer, V>) object;
            int pos = ifind(entry.getKey(), entry.getValue());
            if( used[pos] && CompareUtils.equals(entry.getValue(), values[pos]) ) {
                AIntHashMap.this.ishift(pos);
                return true;
            } else {
                return false;
            }
        }

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

        @Override
        public void clear() {
            AIntHashMap.this.clear();
        }
    }
	
	private final class KeyIterator implements IntIterator {

        private final MapIterator delegate = new MapIterator();

        @Override
        public int nextInt() {
            return keys[ delegate.nextEntry()];
        }

        @Override
        public Integer next() {
            return keys[delegate.nextEntry()];
        }

        @Override
        public boolean hasNext() {
            return delegate.hasNext();
        }

        @Override
        public void remove() {
            delegate.remove();
        }
    }

    private final class KeySet extends AIntSet {

        @Override
        public IntIterator iterator() {
            return new KeyIterator();
        }

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

        @Override
        public boolean contains(int k) {
            return containsKey(k);
        }

        @Override
        public boolean remove(int k) {
            final int oldSize = size;
            AIntHashMap.this.remove(k);
            return size != oldSize;
        }

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

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

        @Override
        public V next() {
            return values[ nextEntry()];
        }
    }

}
