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

import net.ranides.assira.collection.BlockCollection;
import net.ranides.assira.collection.arrays.NativeArrayUtils;
import net.ranides.assira.generic.HashUtils;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
import net.ranides.assira.collection.arrays.ArrayUtils;
import net.ranides.assira.collection.arrays.NativeArray;
import net.ranides.assira.collection.utils.HashCollection;
import net.ranides.assira.math.MathUtils;

/**
 * A generic set map implementation
 */
public abstract class AHashSet<K> extends ASet<K> implements BlockCollection<K>, java.io.Serializable {

    private static final long serialVersionUID = 4L;

    /**
     * The array of keys.
     */
    protected transient K[] keys;
    /**
     * 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 entries in the set.
     */
    protected int size;

    /**
     * Creates a new hash set.
     *
     * <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 AHashSet(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;
        this.n = HashCollection.arraysize(expected, f);
        this.mask = n - 1;
        this.capacity = HashCollection.factorsize(n, f);
        this.keys = (K[]) new Object[n];
        this.used = new boolean[n];
    }

    protected abstract int hash(K key);
    
    protected abstract boolean compare(K key1, K key2);
    
    @Override
    public final boolean add(K value) {
        int pos = ifind(value);
        return used[pos] ? false : iinsert(pos, value);
    }

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

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

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

    @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 Iterator<K> iterator() {
        return new SetIterator();
    }

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

    
    /**
     * Rehashes this set, 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 set.
     * @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 set 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> entries, 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 set
     * in a table of size
     * <var>N</var>.
     *
     * <P>This method is useful when reusing sets. null null null null     {@linkplain #clear() Clearing a
	 * set} leaves the table size untouched. If you are reusing a set 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 sets.
     *
     * @param n the threshold for the trimming.
     * @return true if there was enough memory to trim the set.
     * @see #trim()
     */
    @Override
    public final boolean trim(int n) {
        final 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;
    }

    @Override
    public boolean reserve(int capacity) {
        final int l = HashCollection.arraysize(capacity, factor);
        if(l <= this.n) {
            return true;
        }
        try {
            irehash(l);
        } catch (OutOfMemoryError cantDoIt) {
            return false;
        }
        return true;
    }
        
    /**
     * Returns a hash code for this set.
     *
     * This method overrides the generic method provided by the superclass.
     * Since
     * <code>equals()</code> is not overriden, it is important that the value
     * returned by this method is the same value as the one returned by the
     * overriden method.
     *
     * @return a hash code for this set.
     */
    @Override
    public final int hashCode() {
        int h = 0, i = 0, j = size;
        while (j-- != 0) {
            while (!used[ i]) {
                i++;
            }
            if (this != keys[ i]) {
                h += hash(keys[i]);
            }
            i++;
        }
        return h;
    }

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

    @SuppressWarnings("unchecked")
    protected final void irehash(int newN) {
        int i = 0, pos;
        final boolean iused[] = this.used;
        K ckey;
        final K ikeys[] = this.keys;
        final int newMask = newN - 1;
        final K newKey[] = (K[]) 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;
            i++;
        }
        n = newN;
        mask = newMask;
        capacity = HashCollection.factorsize(n, factor);
        this.keys = newKey;
        this.used = newUsed;
    }
    
    protected int ifind(K value) {
        int i = HashUtils.murmurHash3(hash((K)value)) & mask;
        // There's always an unused entry.
        while (used[i] && !compare(keys[i], value)) {
            i = (i+1) & mask;
        }
        return i;
    }
    
    protected final boolean iinsert(int segment, K value) {
        used[segment] = true;
        keys[segment] = value;
        
        if (++size >= capacity) {
            irehash(HashCollection.arraysize(size + 1, factor));
        }
        return true;
    }
    
    protected final boolean ishift(int pos) {
        size--;
        int last;
        for (;;) {
            last = pos;
            pos = inext(pos);
            if (!used[ pos]) {
                break;
            }
            imove(last, pos);
        }
        iclear(last);
        return true;
    }
    
    protected final 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];
    }
    
    protected final 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 {
        final Iterator<K> i = iterator();
        ostream.defaultWriteObject();
        writeObjectDetails(ostream);
        for (int j = size; j-- != 0;) {
            ostream.writeObject(i.next());
        }
    }

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

    private final class SetIterator implements Iterator<K> {

        /**
         * 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 mpos;
        /**
         * The index of the last entry that has been returned (more precisely,
         * the value of {@link #mpos}). 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 entries must still be returned.
         */
        int counter;
        /**
         * A lazily allocated list containing 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 SetIterator() {
            this.mpos = AHashSet.this.n;
            this.mlast = -1;
            this.counter = size;
            this.wrapped = null;
            boolean used[] = AHashSet.this.used;
            if (counter != 0) {
                while (!used[ --mpos]) { } // NOPMD
            }
        }

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

        @Override
        public K next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            counter--;
            // We are just enumerating elements from the wrapped list.
            if (mpos < 0) {
                return wrapped.get(-(mlast = --mpos) - 2);
            }
            final K retVal = keys[ mlast = mpos];
            if (counter != 0) {
                final boolean used[] = AHashSet.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 retVal;
        }

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

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

}
