import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * Resizable implementation of the Deque and List interface via a standard
 * HashSet implementation. Does not allow for insertion of {@code null}
 * elements.
 * 
 * @author Max Bender
 */
@SuppressWarnings("unchecked")
public class HashSet<T> implements Deque<T>, Cloneable, List<T> {

    private static class HashNode<T> implements Iterable<T> {
        HashNode<T> next, after, before, prev;
        T data;

        public HashNode(T data) {
            this.data = data;
        }

        @Override
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                HashNode<T> cur = HashNode.this;

                public T next() {
                    T toReturn = cur.data;
                    cur = cur.next;
                    return toReturn;
                }

                public boolean hasNext() {
                    return cur != null;
                }
            };
        }
    }

    private HashNode<T>[] set;
    /**
     * The number of items in this HashSet
     */
    protected int size;
    private HashNode<T> head, tail;

    /**
     * Creates an empty HashSet.
     */
    public HashSet() {
        set = (HashNode<T>[]) new HashNode[16];
        size = 0;
        head = tail = null;
    }

    /**
     * Returns the number of items in this HashSet.
     * 
     * @return the number of items in this HashSet.
     */
    public int size() {
        return size;
    }

    private int hash(Object item) {
        return Math.abs(item.hashCode() % set.length);
    }

    private void resize(int newSize) {
        HashNode<T> cur = head;
        head = null;
        tail = null;
        size = 0;
        set = (HashNode<T>[]) new HashNode[newSize];
        while (cur != null) {
            add(cur.data);
            cur = cur.after;
        }
    }

    /**
     * Returns an iterator over this HashSet in the proper sequence.
     * 
     * @return an iterator over this HashSet in the proper sequence.
     */
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            HashNode<T> before;
            HashNode<T> cur = HashSet.this.head;

            public T next() {
                before = cur;
                cur = cur.after;
                return before.data;
            }

            public boolean hasNext() {
                return cur != null;
            }

            public void remove() {
                if (before == null)
                    return;
                removeNode(before);
            }
        };
    }

    /**
     * Returns the item in this HashSet that is equal to the specified item, or
     * {@code null} if no such item exists
     * 
     * <p>
     * Note that these need not be explicitly the same item.
     * 
     * @param item the item to be found in the HashSet
     * @return the item in this HashSet that is equal to the specified item, or
     *         {@code null} if no such item exists
     */
    public T get(T item) {
        if (set[hash(item)] == null)
            return null;
        for (T t : set[hash(item)]) {
            if (t.equals(item))
                return t;
        }
        return null;
    }

    /**
     * Retrieves, but does not remove, the first element of this HashSet.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T getFirst() {
        return size > 0 ? head.data : null;
    }

    /**
     * Retrieves, but does not remove, the last element of this HashSet.
     * 
     * @return the last element of this HashSet.
     */
    public T getLast() {
        return size > 0 ? tail.data : null;
    }

    /**
     * Returns {@code true} if this HashSet contains the specified element.
     * 
     * <p>
     * More formally, returns {@code true} if and only if this HashSet contains an
     * element {@code e} such that {@code Objects.equals(o, e)}.
     * 
     * @param o element whose presence in this HashSet is to be tested
     * 
     * @return {@code true} if this HashSet contains the specified element.
     */
    public boolean contains(Object o) {
        if (set[hash(o)] == null)
            return false;
        for (T item : set[hash(o)])
            if (item.equals(o))
                return true;
        return false;
    }

    /**
     * Returns {@code true} if this collection contains all of the elements in the
     * specified collection.
     * 
     * @param items collection to be checked for containment in this collection
     * 
     * @return {@code true} if this collection contains all of the elements in the
     *         specified collection.
     */
    public boolean containsAll(Collection<?> items) {
        for (Object item : items)
            if (!contains(item))
                return false;
        return true;
    }

    private void removeNode(HashNode<T> node) {
        if (node.prev != null)
            node.prev.next = node.next;
        else
            set[hash(node.data)] = node.next;

        if (node.next != null)
            node.next.prev = node.prev;

        if (node.before != null)
            node.before.after = node.after;
        else
            head = node.after;

        if (node.after != null)
            node.after.before = node.before;
        else
            tail = node.before;

        if (head == null || tail == null)
            head = tail = null;
    }

    private void decrementSize(int x) {
        size -= x;
        if (size * 4 < set.length && set.length / 2 >= 16)
            resize(set.length / 2);
    }

    /**
     * Retrieves and removes the first element of this HashSet.
     * 
     * @return the first element of this HashSet.
     */
    public T removeFirst() {
        T toReturn = head.data;
        removeNode(head);
        decrementSize(1);
        return toReturn;
    }

    /**
     * Retrieves and removes the last element of this HashSet.
     * 
     * @return the last element of this HashSet.
     */
    public T removeLast() {
        T toReturn = tail.data;
        removeNode(tail);
        decrementSize(1);
        return toReturn;
    }

    /**
     * Inserts the specified element into the queue represented by this HashSet if
     * it is possible to do so (ie, if this item isn't already contained in the
     * set), returning true upon success.
     * 
     * @param item the item to add
     * 
     * @return {@code true} if item was successfully added to the set.
     */
    public boolean add(T item) {
        int oldSize = size;
        addLast(item);
        return size > oldSize;
    }

    /**
     * Returns a string representation of the object.
     * 
     * @return a string representation of the object.
     */
    public String toString() {
        if (size == 0)
            return "[]";
        StringBuilder sb = new StringBuilder();
        sb.append("[" + head.data);
        HashNode<T> cur = head.after;
        while (cur != null) {
            sb.append(", " + cur.data);
            cur = cur.after;
        }
        sb.append("]");
        return sb.toString();
    }

    /**
     * Returns {@code true} if this collection contains no elements.
     * 
     * @return {@code true} if this collection contains no elements.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns an array containing all of the elements in this collection in the
     * correct order. The returned array's runtime component type is Object.
     * 
     * @return an array containing all of the elements in this collection in the
     *         correct order.
     */
    @Override
    public Object[] toArray() {
        return toArray(new Object[size]);
    }

    /**
     * Returns an array containing all of the elements in this collection in the
     * correct order; the runtime type of the returned array is that of the
     * specified array. If the collection fits in the specified array, it is
     * returned therein. Otherwise, a new array is allocated with the runtime type
     * of the specified array and the size of this collection.
     * 
     * @param a the array into which the elements of this collection are to be
     *          stored, if it is big enough; otherwise, a new array of the same
     *          runtime type is allocated for this purpose.
     * 
     * @return an array containing all of the elements in this collection in the
     *         correct order.
     */
    @Override
    public <A> A[] toArray(A[] a) {
        if (a.length >= size) {
            int index = 0;
            for (T item : this) {
                a[index] = (A) item;
                index++;
            }
            if (index < a.length)
                a[index] = null;
            return a;
        }
        return toArray((A[]) new Object[size]);
    }

    /**
     * Removes the specified element from this HashSet. If the HashSet does not
     * contain the element, it is unchanged. More formally, removes the element
     * {@code e} such that {@code Objects.equals(o, e)} (if such an element exists).
     * Returns {@code true} if this HashSet contained the specified element (or
     * equivalently, if this HashSet changed as a result of the call).
     * 
     * @param o element to be removed from this HashSet, if present
     * 
     * @return {@code true} if this HashSet contained the specified element.
     */
    @Override
    public boolean remove(Object o) {
        for (HashNode<T> node = set[hash(o)]; node != null; node = node.next) {
            if (node.data.equals(o)) {
                removeNode(node);
                decrementSize(1);
                return true;
            }
        }
        return false;
    }

    /**
     * Adds all of the elements in the specified collection at the end of this
     * HashSet, as if by calling {@link addLast} on each one, in the order that they
     * are returned by the collection's iterator.
     * 
     * @param c the elements to be inserted into this HashSet
     * 
     * @return {@code true} if this HashSet changed as a result of the call.
     */
    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean added = false;
        for (T item : c) {
            added = added || add(item);
        }
        return added;
    }

    /**
     * Removes all of this collection's elements that are also contained in the
     * specified collection. After this call returns, this collection will contain
     * no elements in common with the specified collection.
     * 
     * @param c collection containing elements to be removed from this collection
     * 
     * @return {@code true} if this collection changed as a result of the call.
     */
    @Override
    public boolean removeAll(Collection<?> c) {
        int removed = 0;
        for (Object item : c) {
            if (remove(item))
                removed++;
        }
        decrementSize(removed);
        return removed > 0;
    }

    /**
     * Retains only the elements in this collection that are contained in the
     * specified collection. In other words, removes from this collection all of its
     * elements that are not contained in the specified collection.
     * 
     * @param c collection containing elements to be retained in this collection
     * 
     * @return {@code true} if this collection changed as a result of the call.
     */
    @Override
    public boolean retainAll(Collection<?> c) {
        int removed = 0;
        for (HashNode<T> cur = head; cur != null; cur = cur.after) {
            if (!c.contains(cur.data)) {
                removeNode(cur);
                removed++;
            }
        }
        decrementSize(removed);
        return removed > 0;
    }

    /**
     * Removes all of the elements from this collection. The collection will be
     * empty after this method returns.
     */
    @Override
    public void clear() {
        set = (HashNode<T>[]) new HashNode[16];
        size = 0;
        head = tail = null;
    }

    /**
     * Inserts the specified element at the front of this HashSet if it is possible
     * to do so (ie, if the item is not already contained in this HashSet).
     */
    @Override
    public void addFirst(T item) {
        if (item == null || contains(item))
            return;
        HashNode<T> newNode = new HashNode<T>(item);

        newNode.after = head;
        if (head != null)
            head.before = newNode;
        head = newNode;
        if (tail == null)
            tail = head;

        newNode.next = set[hash(item)];
        set[hash(item)] = newNode;
        size++;
        if (size * 2 > set.length)
            resize(set.length * 2);
    }

    /**
     * Inserts the specified element at the end of this HashSet if it is possible to
     * do so (ie, if the item is not already contained in this HashSet).
     */
    @Override
    public void addLast(T item) {
        if (item == null || get(item) != null)
            return;
        HashNode<T> newNode = new HashNode<T>(item);

        newNode.before = tail;
        if (tail != null)
            tail.after = newNode;
        tail = newNode;
        if (head == null)
            head = tail;

        newNode.next = set[hash(item)];
        set[hash(item)] = newNode;

        size++;
        if (size * 2 > set.length)
            resize(set.length * 2);
    }

    /**
     * Inserts the specified element at the front of this HashSet if it is possible
     * to do so (ie, if the item is not already contained in this HashSet).
     * 
     * @param item the element to add
     * 
     * @return {@code true} if the element was added to this HashSet, else
     *         {@code false}.
     */
    @Override
    public boolean offerFirst(T item) {
        int oldSize = size;
        addFirst(item);
        return size > oldSize;
    }

    /**
     * Equivalent to {@link #add(Object)}.
     * 
     * @param item the element to add
     * 
     * @return {@code true} if the element was added to this HashSet, else
     *         {@code false}.
     */
    @Override
    public boolean offerLast(T item) {
        return add(item);
    }

    /**
     * Equivalent to {@link removeFirst}.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T pollFirst() {
        return removeFirst();
    }

    /**
     * Equivalent to {@link removeLast}.
     * 
     * @return the last element of this HashSet.
     */
    @Override
    public T pollLast() {
        return removeLast();
    }

    /**
     * Equivalent to {@link getFirst}.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T peekFirst() {
        return getFirst();
    }

    /**
     * Equivalent to {@link getLast}.
     * 
     * @return the last element of this HashSet.
     */
    @Override
    public T peekLast() {
        return getLast();
    }

    /**
     * Equivalent to {@link #remove(Object)}
     * 
     * @param o element to be removed from this HashSet, if present
     * 
     * @return {@code true} if this HashSet contained the specified element.
     */
    @Override
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    /**
     * Equivalent to {@link #remove(Object)}
     * 
     * @param o element to be removed from this HashSet, if present
     * 
     * @return {@code true} if this HashSet contained the specified element.
     */
    @Override
    public boolean removeLastOccurrence(Object o) {
        return remove(o);
    }

    /**
     * Equivalent to {@link #add(Object)}.
     * 
     * @param item the element to add
     * 
     * @return {@code true} if the element was added to this HashSet, else
     *         {@code false}.
     */
    @Override
    public boolean offer(T item) {
        return add(item);
    }

    /**
     * Equivalent to {@link removeFirst}.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T remove() {
        return removeFirst();
    }

    /**
     * Equivalent to {@link removeFirst}.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T poll() {
        return removeFirst();
    }

    /**
     * Equivalent to {@link getFirst}.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T element() {
        return getFirst();
    }

    /**
     * Equivalent to {@link getFirst}.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T peek() {
        return getFirst();
    }

    /**
     * Equivalent to {@link addFirst}.
     */
    @Override
    public void push(T item) {
        addFirst(item);
    }

    /**
     * Equivalent to {@link removeFirst}.
     * 
     * @return the first element of this HashSet.
     */
    @Override
    public T pop() {
        return removeFirst();
    }

    /**
     * Returns an iterator over the elements in this HashSet in reverse sequential
     * order.
     * 
     * @return an iterator over the elements in this HashSet in reverse sequential
     *         order.
     */
    @Override
    public Iterator<T> descendingIterator() {
        return new Iterator<T>() {
            HashNode<T> cur = tail;

            public boolean hasNext() {
                return cur != null;
            }

            public T next() {
                T toReturn = cur.data;
                cur = cur.before;
                return toReturn;
            }
        };
    }

    /**
     * Creates and returns a shallow copy of this object.
     * 
     * @return a shallow copy of this object.
     */
    @Override
    public HashSet<T> clone() {
        HashSet<T> hashSet = new HashSet<T>();
        for (T t : this) {
            hashSet.add(t);
        }
        return hashSet;
    }

    /**
     * Unsupported method.
     * 
     * @throws UnsupportedOperationException
     * 
     * @return N/A: this method isn't supported
     */
    @Override
    public boolean addAll(int index, Collection<? extends T> c) {
        throw new UnsupportedOperationException("Adding by index is not supported by this HashSet");
    }

    /**
     * Returns the element at the specified position in this list.
     * 
     * @param index of the element to return
     * 
     * @return the element at the specified position in this list
     */
    @Override
    public T get(int index) {
        if (index == 0)
            return getFirst();
        else if (index == size - 1)
            return getLast();
        else if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index " + index + " out of bounds for a list of size " + size);
        else {
            HashNode<T> cur = head;
            for (int i = 0; i < index; i++)
                cur = cur.after;
            return cur.data;
        }
    }

    /**
     * Unsupported method.
     * 
     * @throws UnsupportedOperationException
     * 
     * @return N/A: this method isn't supported
     */
    @Override
    public T set(int index, T element) {
        throw new UnsupportedOperationException("Adding by index is not supported by this HashSet");
    }

    /**
     * This method is unsupported, except for the case when
     * {@code index == 0 || index == size}
     */
    @Override
    public void add(int index, T item) {
        if (index == 0)
            addFirst(item);
        else if (index == size)
            addLast(item);
        else if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index " + index + " out of bounds for a list of size " + size);
        else
            throw new UnsupportedOperationException("Adding by index is not supported by this HashSet");
    }

    /**
     * Removes the element at the specified position in this list.
     * 
     * @param index the index of the element to be removed
     * 
     * @return the element previously at the specified position
     */
    @Override
    public T remove(int index) {
        if (index == 0)
            return removeFirst();
        else if (index == size - 1)
            return removeLast();
        else if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index " + index + " out of bounds for a list of size " + size);
        else {
            HashNode<T> cur = head;
            for (int i = 0; i < index; i++)
                cur = cur.after;
            return cur.data;
        }
    }

    /**
     * Returns the index of the first occurrence of the specified element in this
     * list, or {@code -1} if this list does not contain the element.
     * 
     * @param o element to search for
     * 
     * @return the index of the first occurrence of the specified element in this
     *         list, or -1 if this list does not contain the element.
     */
    @Override
    public int indexOf(Object o) {
        HashNode<T> cur = head;
        for (int i = 0; i < size; i++) {
            if (cur.data.equals(o))
                return i;
            cur = cur.after;
        }
        return -1;
    }

    /**
     * Equivalent to {@link indexOf}.
     * 
     * @param o element to search for
     * 
     * @return the index of the first occurrence of the specified element in this
     *         list, or -1 if this list does not contain the element.
     */
    @Override
    public int lastIndexOf(Object o) {
        return indexOf(o);
    }

    /**
     * Returns a list iterator over the elements in this list (in proper sequence).
     * 
     * @return a list iterator over the elements in this list (in proper sequence).
     */
    @Override
    public ListIterator<T> listIterator() {
        return listIterator(0);
    }

    private HashNode<T> getNode(int index) {
        HashNode<T> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * Returns a list iterator over the elements in this list (in proper sequence),
     * starting at the specified position in the list. The specified index indicates
     * the first element that would be returned by an initial call to next. An
     * initial call to previous would return the element with the specified index
     * minus one.
     * 
     * @param index index of the first element to be returned from the list iterator
     *              (by a call to next)
     * 
     * @return a list iterator over the elements in this list (in proper sequence),
     *         starting at the specified position in the list
     */
    @Override
    public ListIterator<T> listIterator(int index) {
        return new ListIterator<T>() {
            HashNode<T> next = getNode(index);
            HashNode<T> prev = next != null ? next.before : tail;
            int nextIndex = index;

            @Override
            public boolean hasNext() {
                return next != null;
            }

            @Override
            public T next() {
                nextIndex++;
                T data = next.data;
                prev = next;
                next = next.after;
                return data;
            }

            @Override
            public boolean hasPrevious() {
                return prev != null;
            }

            @Override
            public T previous() {
                nextIndex--;
                T data = prev.data;
                next = prev;
                prev = prev.before;
                return data;
            }

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

            @Override
            public int previousIndex() {
                return nextIndex - 1;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("This iterator does not support removal.");
            }

            @Override
            public void set(T e) {
                throw new UnsupportedOperationException("This iterator does not support setting.");
            }

            @Override
            public void add(T e) {
                throw new UnsupportedOperationException("This iterator does not support adding.");
            }
        };
    }

    /**
     * Returns a view of the portion of this list between the specified
     * {@code fromIndex}, {@code inclusive}, and {@code toIndex}, exclusive. (If
     * {@code fromIndex} and {@code toIndex} are equal, the returned list is empty.)
     * 
     * @param fromIndex low endpoint (inclusive) of the subList
     * @param toIndex   high endpoint (exclusive) of the subList
     * 
     * @return a view of the specified range within this list
     */
    @Override
    public List<T> subList(int fromIndex, int toIndex) {
        if (fromIndex < 0 || toIndex > size || toIndex < fromIndex)
            throw new IndexOutOfBoundsException();
        HashSet<T> newSet = new HashSet<>();
        HashNode<T> curNode = getNode(fromIndex);
        for (int i = fromIndex; i < toIndex; i++, curNode = curNode.after) {
            newSet.add(curNode.data);
        }
        return newSet;
    }
}