import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * The MyHashSet API is similar to the Java Set interface. This
 * collection is backed by a hash table.
 */
public class MyHashSet<E> implements Iterable<E> {

    /**
     * Unless otherwise specified, the table will start as
     * an array (ArrayList) of this size.
     */
    private final static int DEFAULT_INITIAL_CAPACITY = 4;

    /**
     * When the ratio of size/capacity exceeds this
     * value, the table will be expanded.
     */
    private final static double MAX_LOAD_FACTOR = 0.75;

    /* STUDENTS: LEAVE THIS AS PUBLIC */
    public ArrayList<Node<E>> hashTable;

    private int size;  // number of elements in the table


    // STUDENTS: DO NOT ADD ANY OTHER INSTANCE VARIABLES OR STATIC
    // VARIABLES TO THIS CLASS!


    /* STUDENTS: LEAVE THIS PUBLIC, and do not modify the Node class. */
    public static class Node<T> {
        private T data;
        public Node<T> next;  // STUDENTS: Leave this public, too!

        private Node(T data) {
            this.data = data;
            next = null;
        }

    }

    /**
     * Initializes an empty table with the specified capacity.
     *
     * @param initialCapacity initial capacity (length) of the
     *                        underlying table
     */
    // STUDENTS: Calling the ArrayList constructor that takes
    // an int argument doesn't do what we want here.
    // You need to make an empty ArrayList, and then add a bunch
    // of null values to it until the size reaches the
    // initialCapacity requested.
    public MyHashSet(int initialCapacity) {
        hashTable = new ArrayList<Node<E>>();
        for (int i = 0; i < initialCapacity; i++) {
            hashTable.add(null);
        }
    }


    /**
     * Initializes an empty table of length equal to
     * DEFAULT_INITIAL_CAPACITY
     */
    // STUDENTS:  This constructor should just call the other
    // constructor
    public MyHashSet() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    /**
     * Returns the number of elements stored in the table.
     *
     * @return number of elements in the table
     */
    public int size() {
        return size;
    }

    /**
     * Returns the length of the table (the number of buckets).
     *
     * @return length of the table (capacity)
     */
    public int getCapacity() {
        return hashTable.size();
    }

    /**
     * Looks for the specified element in the table.
     *
     * @param element to be found
     * @return true if the element is in the table, false otherwise
     */
    public boolean contains(Object element) {
        int index = Math.abs(element.hashCode() % hashTable.size());
        Node<E> indexNode = hashTable.get(index);

        if (indexNode != null && indexNode.data.equals(element)) return true;

        Iterator<E> iterator = iterator();
        while (iterator.hasNext()) {
              Object o = iterator.next();
              if (o instanceof Node) {
                  Node<E> n = (Node<E>) o;
                  while (n.next != null){
                      if (n.data.equals(element)) return true;
                  }
              }
        }

        return false;
    }

    /**
     * Adds the specified element to the collection, if it is not
     * already present.  If the element is already in the collection,
     * then this method does nothing.
     *
     * @param element the element to be added to the collection
     */
    // STUDENTS:  After adding the element to the table, consider
    // the load factor. If it is greater than MAX_LOAD_FACTOR then
    // you must double the size of the table. [Create a new table
    // that is twice as big as the current one and then re-hash
    // of all of the data from the old table into the new one.
    // Hint: It's OK to iterate over the original table.]
    public void add(E element) {
        if (contains(element)) return;

        rehash();

        int index = getHash(element) % hashTable.size();

        Node<E> n = hashTable.get(index);

        Node<E> newNode = new Node<>(element);

        if (n == null) {
            hashTable.set(index, newNode);
            size++;
            return;
        }

        while (n.next != null) {
            if (n.data.equals(element)) {
                return;
            }
            n = n.next;
        }

        // add only if last element doesn't have the value being added
        if (!n.data.equals(element)) {
            n.next = newNode;
            size++;
        }
    }

    private void rehash() {
        if (size == 0.75 * getCapacity()) {
            // rehash
            ArrayList<Node<E>> gList = new ArrayList<>();
            for (int i = 0; i < getCapacity() * 2; i++) {
                gList.add(null);
            }
            hashTable = gList;

            for (Node<E> bucket : hashTable) {
                while (bucket != null) {
                    hashTable.add(bucket);
                    bucket = bucket.next;
                }
            }
        }
    }

    /**
     * Removes the specified element from the collection.  If the
     * element is not present then this method should do nothing.
     *
     * @param element the element to be removed
     */
    public boolean remove(E element) {
        // mapping hash code to the index
        int index = getHash(element) % hashTable.size();

        Node<E> indexNode = hashTable.get(index);

        if (indexNode == null) return false;

        if (indexNode.data.equals(element)) {
            hashTable.set(index, indexNode.next); // if there is such an element, "removing" it by replacing with the following
            size--;
            return true;
        }

        Node<E> previous = indexNode;

        while (indexNode != null) {
            if (indexNode.data.equals(element)) {
                previous.next = indexNode.next;
                size--;
                return true;
            }
            previous = indexNode;
            indexNode = previous.next;
        }

        return true;
    }

    private int getHash(Object o){
        return Math.abs(o.hashCode());
    }

    /**
     * Returns an Iterator that can be used to iterate over
     * all of the elements in the collection.
     * <p>
     * The order of the elements is unspecified.
     */
    // STUDENTS: You may NOT copy the data from the hash table
    // into a different structure.  You must write an iterator
    // that iterates over your hash table directly, without
    // copying the data anywhere.
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = 0;

            @Override
            public boolean hasNext() {
                return (hashTable.size() > index) && hashTable.get(index) != null;
            }

            @Override
            public E next() {
                Node<E> node = hashTable.get(index++);
                return node == null ? null : node.data;
            }
        };
    }
}