/*
 * @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.iterators.IntIterator;
import net.ranides.assira.collection.arrays.NativeArrayUtils;
import net.ranides.assira.generic.HashUtils;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import net.ranides.assira.collection.utils.HashCollection;
import net.ranides.assira.collection.IntCollection;
import net.ranides.assira.collection.arrays.NativeArray;
import net.ranides.assira.collection.arrays.ArrayAllocator;
import net.ranides.assira.collection.lists.IntArrayList;
import net.ranides.assira.collection.lists.IntList;
import net.ranides.assira.math.MathUtils;

/**
 * A type-specific set implementation with primitive int values
 */
public final class IntHashSet extends AIntSet implements java.io.Serializable, BlockCollection<Integer> {

    private static final long serialVersionUID = 4L;

    /**
     * The array of keys.
     */
    protected transient int[] 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 factor the load factor.
     */
    @SuppressWarnings("unchecked")
    public IntHashSet(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;
        this.n = HashCollection.arraysize(expected, factor);
        this.mask = n - 1;
        this.capacity = HashCollection.factorsize(n, factor);
        this.keys = new int[n];
        this.used = new boolean[n];
    }

    /**
     * Creates a new hash set with {@link Hash#DEFAULT_LOAD_FACTOR} as load
     * factor.
     *
     * @param expected the expected number of elements in the hash set.
     */
    public IntHashSet(int expected) {
        this(expected, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates a new hash set with initial expected
     * {@link Hash#DEFAULT_INITIAL_SIZE} elements and
     * {@link Hash#DEFAULT_LOAD_FACTOR} as load factor.
     */
    public IntHashSet() {
        this(HashCollection.INITIAL_SIZE, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates a new hash set copying a given collection.
     *
     * @param values a {@link Collection} to be copied into the new hash set.
     * @param factor the load factor.
     */
    public IntHashSet(Collection<? extends Integer> values, float factor) {
        this(values.size(), factor);
        addAll(values);
    }

    /**
     * Creates a new hash set with {@link Hash#DEFAULT_LOAD_FACTOR} as load
     * factor copying a given collection.
     *
     * @param values a {@link Collection} to be copied into the new hash set.
     */
    public IntHashSet(Collection<? extends Integer> values) {
        this(values, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates a new hash set copying a given type-specific collection.
     *
     * @param values a type-specific collection to be copied into the new hash set.
     * @param factor the load factor.
     */
    public IntHashSet(IntCollection values, float factor) {
        this(values.size(), factor);
        addAll(values);
    }

    /**
     * Creates a new hash set with {@link Hash#DEFAULT_LOAD_FACTOR} as load
     * factor copying a given type-specific collection.
     *
     * @param values a type-specific collection to be copied into the new hash set.
     */
    public IntHashSet(IntCollection values) {
        this(values, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates a new hash set using elements provided by a type-specific
     * iterator.
     *
     * @param values a type-specific iterator whose elements will fill the set.
     * @param factor the load factor.
     */
    public IntHashSet(IntIterator values, float factor) {
        this(HashCollection.INITIAL_SIZE, factor);
        while (values.hasNext()) {
            add(values.nextInt());
        }
    }

    /**
     * Creates a new hash set with {@link Hash#DEFAULT_LOAD_FACTOR} as load
     * factor using elements provided by a type-specific iterator.
     *
     * @param values a type-specific iterator whose elements will fill the set.
     */
    public IntHashSet(IntIterator values) {
        this(values, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates a new hash set using elements provided by an iterator.
     *
     * @param values an iterator whose elements will fill the set.
     * @param factor the load factor.
     */
    public IntHashSet(Iterator<? extends Integer> values, float factor) {
        this(IntIterator.wrap(values), factor);
    }

    /**
     * Creates a new hash set with {@link Hash#DEFAULT_LOAD_FACTOR} as load
     * factor using elements provided by an iterator.
     *
     * @param values an iterator whose elements will fill the set.
     */
    public IntHashSet(Iterator<? extends Integer> values) {
        this(IntIterator.wrap(values));
    }

    /**
     * Creates a new hash set and fills it with the elements of a given array.
     *
     * @param values an array whose elements will be used to fill the set.
     * @param offset the first element to use.
     * @param length the number of elements to use.
     * @param factor the load factor.
     */
    public IntHashSet(int[] values, int offset, int length, float factor) {
        this(length < 0 ? 0 : length, factor);
        ArrayAllocator.ensureOffsetLength(values, offset, length);
        for (int i = 0; i < length; i++) {
            add(values[ offset + i]);
        }
    }

    /**
     * Creates a new hash set with {@link Hash#DEFAULT_LOAD_FACTOR} as load
     * factor and fills it with the elements of a given array.
     *
     * @param values an array whose elements will be used to fill the set.
     * @param offset the first element to use.
     * @param length the number of elements to use.
     */
    public IntHashSet(int[] values, int offset, int length) {
        this(values, offset, length, HashCollection.LOAD_FACTOR);
    }

    /**
     * Creates a new hash set copying the elements of an array.
     *
     * @param values an array to be copied into the new hash set.
     * @param factor the load factor.
     */
    public IntHashSet(int[] values, float factor) {
        this(values, 0, values.length, factor);
    }

    /**
     * Creates a new hash set with {@link Hash#DEFAULT_LOAD_FACTOR} as load
     * factor copying the elements of an array.
     *
     * @param values an array to be copied into the new hash set.
     */
    public IntHashSet(int[] values) {
        this(values, HashCollection.LOAD_FACTOR);
    }
    
    @Override
    public boolean add(int value) {
        int pos = ifind(value);
        return used[pos] ? false : iinsert(pos, value);
    }

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

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

    @Override
    public void clear() {
        if (size == 0) {
            return;
        }
        size = 0;
        NativeArrayUtils.fill(NativeArray.wrap(used), false);
    }

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

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

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

    @Override
    public int capacity() {
        return capacity;
    }
    
    @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;
    }

    /**
     * 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 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 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 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;
    }
    
    /**
     * 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.
     */
    @SuppressWarnings("PMD.OverrideBothEqualsAndHashcode")
    @Override
    public int hashCode() {
        int h = 0, i = 0, j = size;
        while (j-- != 0) {
            while (!used[ i]) {
                i++;
            }
            h += keys[i];
            i++;
        }
        return h;
    }

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

    @SuppressWarnings("unchecked")
    protected void irehash(int newN) {
        int i = 0, pos;
        final boolean iused[] = this.used;
        int k;
        final int key[] = this.keys;
        final int newMask = newN - 1;
        final int newKey[] = new int[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;
            i++;
        }
        n = newN;
        mask = newMask;
        capacity = HashCollection.factorsize(n, factor);
        this.keys = newKey;
        this.used = newUsed;
    }
    
    protected int ifind(int value) {
        // There's always an unused entry.
        int i = HashUtils.murmurHash3(value) & mask;
        while (used[i] && (keys[i]!=value)) {
            i = (i+1) & mask;
        }
        return i;
    }
    
    protected boolean iinsert(int segment, int value) {
        used[segment] = true;
        keys[segment] = value;
        
        if (++size >= capacity) {
            irehash(HashCollection.arraysize(size + 1, factor));
        }
        return true;
    }
    
    protected 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 int inext(int last) {
        int pos = (last + 1) & mask;
        while (used[pos]) {
            int slot = HashUtils.murmurHash3(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 void iclear(int segment) {
        used[segment] = false;
    }

    private void writeObject(java.io.ObjectOutputStream ostream) throws java.io.IOException {
        final IntIterator iterator = iterator();
        ostream.defaultWriteObject();
        for (int j = size; j-- != 0;) {
            ostream.writeInt(iterator.nextInt());
        }
    }

    @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 boolean iused[] = this.used = new boolean[n];
        int ckey;
        for (int i = size, pos; i-- != 0;) {
            ckey = istream.readInt();
            pos = HashUtils.murmurHash3(ckey) & mask;
            while (iused[ pos]) {
                pos = (pos + 1) & mask;
            }
            iused[ pos] = true;
            ikeys[ pos] = ckey;
        }
    }
    
    
    private class SetIterator implements IntIterator {

        /**
         * 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).
         */
        IntList wrapped;
        
        public SetIterator() {
            this.mpos = IntHashSet.this.n;
            this.mlast = -1;
            this.counter = size;
            final boolean used[] = IntHashSet.this.used;
            if (counter != 0) {
                while (!used[ --mpos]) { } // NOPMD
            }
        }


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

        @Override
        public int nextInt() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            counter--;
            // We are just enumerating elements from the wrapped list.
            if (mpos < 0) {
                return wrapped.getInt(-(mlast = --mpos) - 2);
            }
            final int retVal = keys[ mlast = mpos];
            if (counter != 0) {
                final boolean used[] = IntHashSet.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) {
                    // Wrapped entry.
                    if (wrapped == null) {
                        wrapped = new IntArrayList();
                    }
                    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.
                IntHashSet.this.remove(wrapped.getInt(-mpos - 2));
                mlast = -1;
                return;
            }
            size--;
            if (ishift(mlast) == mpos && counter > 0) {
                counter++;
                nextInt();
            }
            mlast = -1; // You can no longer remove this entry.
        }
    }

}
