package java.lang;

import java.util.AbstractSet;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * Linear-probe hash table.
 * <p/>
 * Modeled by the {@link java.util.IdentityHashMap}, but using overriddable
 * {@link #equals(Object, Object) equals} / {@link #hashCode(Object) hashCode}
 * to compare/locate elements. The API of this class is similar
 * in function and form to {@link java.util.Map}, but doesn't use separate keys
 * and values. In this API an <b>element</b> is a key and a value at the same time.
 * An element is always non-null, so the return values are unambiguous.
 * <p/>
 * Because this is a linear-probe hash table and there are no
 * {@link java.util.Map.Entry} objects involved, the underlying
 * data structure is very simple and memory efficient.
 * It is just a sparse array of elements with length that
 * is always a power of two and larger than 3 * {@link #size()} / 2.
 *
 * @param <T> Type of elements contained in the HashArray.
 */
class HashArray<T> {
    /**
     * The minimum capacity, used if a lower value is implicitly specified.
     * The value 2 corresponds to an expected maximum size of 1,
     * given a load factor of 2/3. MUST be a power of two.
     */
    private static final int MINIMUM_CAPACITY = 2;

    /**
     * The maximum capacity.
     * <p/>
     * In fact, the HashArray can hold no more than MAXIMUM_CAPACITY-1 elements
     * because it has to have at least one slot == null
     * in order to avoid infinite loops in get() and put().
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The table, re-sized as necessary.
     * Length MUST always be a power of two.
     */
    private Object[] table;

    /**
     * The number of elements contained in this HashArray.
     */
    private int size;

    /**
     * Constructor with {@code expectedSize} pre-allocates the
     * {@link #table}.
     *
     * @param expectedMaxSize expected number of elements new HashArray
     *                        will hold.
     */
    public HashArray(int expectedMaxSize) {
        if (expectedMaxSize < 0)
            throw new IllegalArgumentException("expectedMaxSize is negative: "
                                               + expectedMaxSize);
        table = new Object[capacity(expectedMaxSize)];
    }

    /**
     * Returns the appropriate capacity for the given expected maximum size.
     * Returns the smallest power of two between MINIMUM_CAPACITY and
     * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
     * expectedMaxSize)/2, if such a number exists.  Otherwise returns
     * MAXIMUM_CAPACITY.
     */
    private static int capacity(int expectedMaxSize) {
        // assert expectedMaxSize >= 0;
        return
            (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
            (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
            Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
    }

    /**
     * Returns a hash code value for an element of this HashArray or a
     * lookup object.
     * <p/>
     * By default it returns:
     * <pre>
     *     obj.{@link Object#hashCode() hashCode()}
     * </pre>
     * But can be overridden in subclasses.
     *
     * @param obj an element of this HashArray or a lookup object
     * @return a hash code value for an element or lookup object.
     * @see #equals(Object, Object)
     */
    protected int hashCode(Object obj) {
        return obj.hashCode();
    }

    /**
     * Indicates whether an element of this HashArray is "equal to"
     * a lookup object or another element.
     * <p/>
     * By default it returns:
     * <pre>
     *     element.{@link Object#equals(Object) equals(obj)}
     * </pre>
     * But can be overridden in subclasses.
     *
     * @param element an element of this HashArray
     * @param obj     a lookup object or another element
     * @return {@code true} if an element is the same
     *         as a lookup object or another element;
     *         {@code false} otherwise.
     * @see #hashCode(Object)
     */
    protected boolean equals(T element, Object obj) {
        return element.equals(obj);
    }

    /**
     * Returns index for Object x.
     */
    private int hash(Object x, int length) {
        int h = hashCode(x);
        return (h ^ (h >>> 16)) & (length - 1);
    }

    /**
     * Circularly traverses table of size length (which is a power of 2).
     */
    private static int nextKeyIndex(int i, int length) {
        return (i + 1) & (length - 1);
    }

    /**
     * @return Number of elements contained in this HashArray.
     */
    public int size() {
        return size;
    }

    /**
     * @param lookupObj a non-null lookup object
     * @return The element which is equal to specified {@code lookupObj}
     *         if it exists in this HashArray or null if it doesn't.
     *         (There can be at most one such element.)
     * @throws NullPointerException if {@code lookupObj} is null
     */
    @SuppressWarnings("unchecked")
    public T get(Object lookupObj) {
        if (lookupObj == null) throw new NullPointerException();
        final Object[] tab = table;
        int i = hash(lookupObj, tab.length);
        while (true) {
            T element = (T) tab[i];
            if (element == null) {
                return null;
            }
            if (equals(element, lookupObj)) {
                return element;
            }
            i = nextKeyIndex(i, tab.length);
        }
    }

    /**
     * @param lookupObj a non-null lookup object
     * @return {@code true} if an element which is equal to specified
     *         {@code lookupObj} exists in this HashArray or
     *         {@code false} if it doesn't.
     * @throws NullPointerException if {@code lookupObj} is null
     */
    public boolean contains(Object lookupObj) {
        return get(lookupObj) != null;
    }

    /**
     * Adds {@code newElement} if an element equal to it is not present in
     * this HashArray and returns null, or returns the existing element and
     * replaces it with {@code newElement} if such element is present.
     *
     * @param newElement new element to put into this HashArray
     * @return previous element if there was one or null if there was none
     */
    public T put(T newElement) {
        return put(newElement, true);
    }

    /**
     * Adds {@code newElement} if an element equal to it is not present in
     * this HashArray and returns null, or returns the existing element and
     * doesn't modify HashArray if such element is present.
     *
     * @param newElement new element to put into this HashArray
     * @return previous element if there was one or null if there was none
     */
    public T putIfAbsent(T newElement) {
        return put(newElement, false);
    }

    private T put(T newElement, boolean replace) {
        if (newElement == null) throw new NullPointerException();
        retryAfterResize:
        for (; ; ) {
            final Object[] tab = table;
            int i = hash(newElement, tab.length);

            for (
                T element; (element = (T) tab[i]) != null;
                i = nextKeyIndex(i, tab.length)
                ) {
                if (equals(element, newElement)) {
                    if (replace) {
                        tab[i] = newElement;
                    }
                    return element;
                }
            }

            final int s = size + 1;
            // Use optimized form of 3 * s / 2.
            // Next capacity is 2 * current capacity.
            if (s + (s >> 1) > tab.length && resize(tab.length << 1))
                continue retryAfterResize;

            tab[i] = newElement;
            size = s;
            return null;
        }
    }

    /**
     * Resizes the table if necessary to hold given capacity.
     */
    private boolean resize(int newLength) {
        Object[] oldTable = table;
        int oldLength = oldTable.length;
        if (oldLength == MAXIMUM_CAPACITY) { // can't expand any further
            if (size == MAXIMUM_CAPACITY - 1)
                throw new IllegalStateException("Capacity exhausted.");
            return false;
        }
        if (oldLength >= newLength)
            return false;

        Object[] newTable = new Object[newLength];

        for (int j = 0; j < oldLength; j++) {
            Object element = oldTable[j];
            if (element != null) {
                oldTable[j] = null;
                int i = hash(element, newLength);
                while (newTable[i] != null)
                    i = nextKeyIndex(i, newLength);
                newTable[i] = element;
            }
        }
        table = newTable;
        return true;
    }

    /**
     * Removes the element equal to {@code lookupObj} and
     * returns it if present or returns null if not present.
     *
     * @param lookupObj a non-null lookup object
     * @return the removed element if there was one or null if
     *         there was none
     * @throws NullPointerException if {@code lookupObj} is null
     */
    public T remove(Object lookupObj) {
        if (lookupObj == null) throw new NullPointerException();
        Object[] tab = table;
        int i = hash(lookupObj, tab.length);

        while (true) {
            T element = (T) tab[i];
            if (element == null) {
                return null;
            }
            if (equals(element, lookupObj)) {
                size--;
                tab[i] = null;
                closeDeletion(tab, i);
                return element;
            }
            i = nextKeyIndex(i, tab.length);
        }
    }

    /**
     * Rehash all possibly-colliding elements following a
     * deletion. This preserves the linear-probe
     * collision properties required by get, putIfAbsent, remove.
     *
     * @param d the index of a newly empty deleted slot
     */
    private void closeDeletion(Object[] tab, int d) {
        // Adapted from Knuth Section 6.4 Algorithm R

        // Look for elements to swap into newly vacated slot
        // starting at index immediately following deletion,
        // and continuing until a null slot is seen, indicating
        // the end of a run of possibly-colliding elements.
        Object element;
        for (
            int i = nextKeyIndex(d, tab.length); (element = tab[i]) != null;
            i = nextKeyIndex(i, tab.length)
            ) {
            // The following test triggers if the element at slot i (which
            // hashes to be at slot r) should take the spot vacated by d.
            // If so, we swap it in, and then continue with d now at the
            // newly vacated i.  This process will terminate when we hit
            // the null slot at the end of this run.
            // The test is messy because we are using a circular table.
            int r = hash(element, tab.length);
            if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
                tab[d] = element;
                tab[i] = null;
                d = i;
            }
        }
    }

    /**
     * Removes all of the elements from this HashArray.
     */
    public void clear() {
        Arrays.fill(table, null);
        size = 0;
    }

    /**
     * Returns a {@link Set} view of the elements contained in this HashArray.
     * The set is backed by the HashArray, so changes to the HashArray are
     * reflected in the set, and vice-versa.  If the HashArray is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own <tt>remove</tt> operation), the results of
     * the iteration are undefined.  The set supports element removal,
     * which removes the corresponding element from the HashArray, via the
     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
     * operations.  It supports the <tt>add</tt> and <tt>addAll</tt>
     * operations.
     *
     * @return a set view of the elements contained in this HashArray
     */
    public Set<T> elementSet() {
        return new AbstractSet<T>() {
            @Override
            public int size() {
                return HashArray.this.size();
            }

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

            @Override
            public boolean contains(Object o) {
                return (o != null) && HashArray.this.contains(o);
            }

            @Override
            public Iterator<T> iterator() {
                return new Iterator<T>() {
                    private int i = 0;
                    private int p = -1;
                    private final Object[] tab = HashArray.this.table;

                    @Override
                    public boolean hasNext() {
                        while (i < tab.length && tab[i] == null) i++;
                        return i < tab.length && tab[i] != null;
                    }

                    @SuppressWarnings("unchecked")
                    @Override
                    public T next() {
                        if (!hasNext()) throw new NoSuchElementException();
                        return (T) tab[p = i++];
                    }

                    @Override
                    public void remove() {
                        if (p < 0) throw new IllegalStateException();
                        tab[p] = null;
                        HashArray.this.closeDeletion(tab, p);
                        p = -1;
                    }
                };
            }

            @Override
            public boolean add(T t) {
                return HashArray.this.put(t) == null;
            }

            @Override
            public boolean remove(Object o) {
                return (o != null) && (HashArray.this.remove(o) != null);
            }

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