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

import net.ranides.assira.collection.AIntCollection;
import net.ranides.assira.collection.iterators.IntIterator;
import net.ranides.assira.collection.sets.ASet;
import net.ranides.assira.collection.arrays.NativeArrayUtils;
import net.ranides.assira.generic.HashUtils;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import net.ranides.assira.collection.IntCollection;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArray;
import net.ranides.assira.collection.maps.BlockMap;
import net.ranides.assira.collection.utils.HashCollection;
import net.ranides.assira.generic.CompareUtils;
import net.ranides.assira.math.MathUtils;

/**
 * A type-specific hash map with primitive int values.
 */
public abstract class AHashLookup<K> extends ALookup<K> implements BlockMap<K, Integer>, java.io.Serializable {

    private static final long serialVersionUID = 4L;
    /**
     * The array of mkeys.
     */
    private transient K[] keys;
    /**
     * The array of mvalues.
     */
    private transient int[] values;
    /**
     * The array telling whether a position is used.
     */
    private transient boolean used[];
    /**
     * The acceptable load factor.
     */
    private final float factor;
    /**
     * The current table size.
     */
    private transient int n;
    /**
     * Threshold after which we rehash. It must be the table size times
     * {@link #factor}.
     */
    private transient int capacity;
    /**
     * The mask for wrapping a position counter.
     */
    private transient int mask;
    /**
     * Number of mentries in the set.
     */
    private int size;
    /**
     * Cached set of mentries.
     */
    private transient volatile Set<LookupEntry<K>> mentries;
    /**
     * Cached set of mkeys.
     */
    private transient volatile Set<K> mkeys;
    /**
     * Cached collection of mvalues.
     */
    private transient volatile IntCollection 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.
     * @param strategy the strategy.
     */
    @SuppressWarnings("unchecked")
    public AHashLookup(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 = (K[]) new Object[n];
        values = new int[n];
        used = new boolean[n];
    }
    
    protected abstract int hash(K key);
    
    protected abstract boolean compare(K key1, K key2);

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

    @Override
    public final Integer put(K key, Integer value) {
		return put(key, value.intValue());
    }

    @SuppressWarnings("unchecked")
    @Override
    public final int removeInt(Object key) {
		int pos = ifind((K)key);
        return used[pos] ? ishift(pos) : defRetValue;
    }

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

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

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

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

    @Override
    public final boolean containsValue(int v) {
        int nvalues[] = this.values;
        boolean nused[] = this.used;
        for (int i = n; i-- != 0;) {
            if (nused[i] && (nvalues[i] == v)) {
                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);
    }

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

    @Override
    public final boolean isEmpty() {
        return size == 0;
    }
	
	@Override
    public final Set<LookupEntry<K>> fastEntrySet() {
        if (mentries == null) {
            mentries = new MapEntrySet();
        }
        return mentries;
    }
	
	@Override
    public final Set<K> keySet() {
        if (mkeys == null) {
            mkeys = new KeySet();
        }
        return mkeys;
    }
	
	@Override
    public final IntCollection values() {
        if (mvalues == null) {
            mvalues = new ValuesCollection();
        }
        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() {
        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.
     */
    @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((K)keys[i]);
            }
            t ^= values[i];
            h += t;
            i++;
        }
        return h;
    }

    @Override
    public final boolean equals(Object object) {
        return super.equals(object);
    }
	

    /**
     * Resizes the map.
     *
     * <P>This method implements the basic rehashing strategy, and may be
     * overriden by subclasses implementing different rehashing strategies
     * (e.g., disk-based rehashing). However, you should not override this
     * method unless you understand the internal workings of this class.
     *
     * @param newN the new size
     */
    @SuppressWarnings("unchecked")
    protected final void irehash(int newN) {
        int i = 0, pos;
        boolean nused[] = this.used;
        K ckey;
        K ikeys[] = this.keys;
        int ivalues[] = this.values;
        int newMask = newN - 1;
        K newKey[] = (K[]) new Object[newN];
        int newValue[] = new int[newN];
        boolean newUsed[] = new boolean[newN];
        for (int j = size; j-- != 0;) {
            while (!nused[ 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) {
        // There's always an unused entry.
        int i = HashUtils.murmurHash3(hash((K)key)) & mask;
        while (used[i] && !compare(keys[i], key)) {
            i = (i+1) & mask;
        }
        return i;
    }
    
    protected int ireplace(int segment, int value) {
        int prev = values[segment];
        values[segment] = value;
        return prev;
    }
    
    protected int iinsert(int segment, K key, int value) {
        used[segment] = true;
        keys[segment] = key;
        values[segment] = value;
        
        if (++size >= capacity) {
            irehash(HashCollection.arraysize(size + 1, factor));
        }
        return defRetValue;
    }

    protected final int ishift(int pos) {
        size--;
        int 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;
    }
    
    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 {
        K ikeys[] = this.keys;
        int ivalues[] = this.values;
        MapIterator iterator = new MapIterator();
        ostream.defaultWriteObject();
        writeObjectDetails(ostream);
        for (int j = size, element; j-- != 0;) {
            element = iterator.nextEntry();
            ostream.writeObject(ikeys[ element]);
            ostream.writeInt(ivalues[ element]);
        }
    }

    @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;
        K ikeys[] = this.keys = (K[]) new Object[n];
        int ivalues[] = this.values = new int[n];
        boolean iused[] = this.used = new boolean[n];
        for (int i = size, pos; i-- != 0;) {
            K ckey = (K) istream.readObject();
            int cval = istream.readInt();
            pos = HashUtils.murmurHash3(hash((K)ckey)) & mask;
            while (iused[ pos]) {
                pos = (pos + 1) & mask;
            }
            iused[pos] = true;
            ikeys[pos] = ckey;
            ivalues[pos] = cval;
        }
    }

    private final class MapEntry implements LookupEntry<K>, Map.Entry<K, Integer> {
        // 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 K getKey() {
            return keys[ index];
        }

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

        @Override
        public int getIntValue() {
            return values[ index];
        }

        @Override
        public int setValue(int v) {
            int oldValue = values[ index];
            values[ index] = v;
            return oldValue;
        }

        @Override
        public Integer setValue(Integer value) {
            return setValue(value.intValue());
        }

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

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

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

    /**
     * An iterator over a hash map.
     */
    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 #wrapped} list.
         */
        int pos;
        /**
         * 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 last;
        /**
         * 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).
         */
        ArrayList<K> wrapped;
       
        public MapIterator() {
            this.pos = AHashLookup.this.n;
            this.last = -1;
            this.counter = size;
            this.wrapped = null;
            
            boolean used[] = AHashLookup.this.used;
            if (counter != 0) {
                while (!used[ --pos]) { } // 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 (pos < 0) {
                K ckey = wrapped.get(-(last = --pos) - 2);
				int ipos = ifind(ckey);
                if(used[ipos]) {
                    return ipos;
                }
            }
            last = pos;
            //System.err.println( "Count: " + c );
            if (counter != 0) {
                boolean used[] = AHashLookup.this.used;
                while (pos-- != 0 && !used[ pos]) { } // NOPMD
                // When here pos < 0 there are no more elements to be enumerated by scanning, but wrapped might be nonempty.
            }
            return last;
        }

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

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

    }

    private class FastEntryIterator extends MapIterator implements Iterator<LookupEntry<K>> {

        final MapEntry entry = new MapEntry(0);
        
        public FastEntryIterator() { }

        @Override
        public LookupEntry<K> next() {
            entry.index = nextEntry();
            return entry;
        }
    }

	private final class MapEntrySet extends ASet<LookupEntry<K>> {

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

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

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

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

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

        public KeyIterator() {
            super();
        }

        @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) {
            int oldSize = size;
            AHashLookup.this.remove(key);
            return size != oldSize;
        }

        @Override
        public void clear() {
            AHashLookup.this.clear();
        }
    }
    
    private final class ValuesCollection extends AIntCollection {
        @Override
        public IntIterator iterator() {
            return new ValueIterator();
        }

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

        @Override
        public boolean contains(int v) {
            return containsValue(v);
        }

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

    private final class ValueIterator implements IntIterator {

        private final MapIterator delegate = new MapIterator();

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

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

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

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

}
