import java.util.Objects;
import java.util.NoSuchElementException;
import java.util.Iterator;

/**
 * Doubly Linked List implementation of a CSList.
 * @author cs416
 * @version 2
 * @param <E> Type
 */
public class CSLinkedList<E> implements CSList<E> {

    private final class Node<D> {
        D data;
        Node<D> next;
        Node<D> prev;

        Node(D data) {
            this.data = data;
            next = null;
            prev = null;
        }
    }

    private Node<E> head = null;
    private Node<E> tail = null;
    private int size = 0;

    /**
     * Appends the specified value to the end of this list.
     * This list does not allow duplicate values.
     *
     * @param e The value to add
     * @return boolean True if the value is inserted, false otherwise
     */
    public boolean add(E e) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Removes all of the elements from this list.
     */
    public void clear() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns true if this list contains the specified element. More formally,
     * returns true if and only if this list contains at least one element e
     * such that Objects.equals(o, e).
     *
     * @param o element whose presence in this list is to be tested
     * @return boolean true if this list contains the specified element
     */
    public boolean contains(Object o) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns the element at the specified position in this list.
     *
     * throws IndexOutOfBoundsException - if the index is out of range
     *
     * @param index The index at which to insert
     * @return E the element at the specified position in this list
     */
    public E get(int index) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Gets the first element of this collection.
     *
     * throws NoSuchElementException - if this collection is empty
     *
     * @return E the retrieved element
     */
    public E getFirst() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Gets the last element of this collection.
     *
     * throws NoSuchElementException - if this collection is empty
     *
     * @return E the retrieved element
     */
    public E getLast() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns the index of the first occurrence of the specified element in
     * this list, or -1 if this list does not contain the element.
     *
     * @param o element to search for
     * @return int the index of the first occurrence of the specified element
     *  in this list, or -1 if this list does not contain the element
     */
    public int indexOf(Object o) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns true if this list contains no elements.
     * @return boolean true if this list contains no elements
     */
    public boolean isEmpty() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Removes the first occurrence of the specified element from this list,
     *  if it is present. If this list does not contain
     *  the element, it is unchanged.
     *
     * @param o - element to be removed from this list, if present
     * @return boolean true if this list contained the specified element
     */
    public boolean remove(Object o) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns the number of elements in this list.
     * @return int the number of elements in this list
     */
    public int size() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Compares the specified object with this list for equality. Returns true
     *  if and only if the specified object is also a list, both lists have the
     *  same size, and all corresponding pairs of elements in the two lists are
     *  equal. (Two elements e1 and e2 are equal if Objects.equals(e1, e2).)
     *  In other words, two lists are defined to be equal if they contain the
     *  same elements in the same order.
     *
     * @param o - the object to be compared for equality with this list
     * @return boolean true if the specified object is equal to this list
     */
    @Override
    public boolean equals(Object o) {

        if (this == o) {
            return true;
        }

        if (o == null || getClass() != o.getClass()) {
            return false;
        }

        CSLinkedList<?> that = (CSLinkedList<?>) o;

        if (this.size() != that.size()) {
            return false;
        }

        Node<?> thisRef = head;
        CSLinkedList<?>.Node<?> thatRef = that.head;

	// Complete the iteration using thisRef and thatRef to compare elements

	throw new UnsupportedOperationException("TO BE IMPLEMENTED");

    }



    /**
     * Returns a string representation of the object.
     *
     * If the List contains the Strings A, B, C, D this
     * method returns a String in the format "A <--> B <--> C <--> D"
     *
     * @return String a string representation of the object.
     */
    @Override
    public String toString() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**************************************************************************
     **************************************************************************
     * Do Not change any code below this point, needed to testing and for     *
     * complete implementation (hashCode needs to be overridden if equals is) *
     **************************************************************************
     **************************************************************************/

    /**
     * Returns the hash code value for this list.
     *
     * @return the hash code value for this list
     */
    @Override
    public int hashCode() {
        int hashCode = 1;
        Node<E> temp = head;

        while (temp != null) {
            hashCode = 31 * hashCode + (temp.data == null ? 0 : temp.data.hashCode());
            temp = temp.next;
        }

        return hashCode;
    }

    /**
    * A forward iterator that traverses using the "next" references.
    * @return ForwardIterator
    */
    public CSLinkedList<E>.ForwardIterator forwardIterator() {
        return new ForwardIterator();
    }

    /**
    * A reverse iterator that traverses using the "prev" references.
    * @return ReverseIterator
    */
    public CSLinkedList<E>.ReverseIterator reverseIterator() {
        return new ReverseIterator();
    }

    /**
    * Iterator to traverse the CSLinkedList "forward" using next references.
    */
    public class ForwardIterator implements Iterator<E> {

        private Node<E> cur;

        /**
        * Constructor.
        */
        public ForwardIterator() {
            cur = head;
        }

        /**
         * returns true if the Iterator has another value.
         * @return boolean
         */
        public boolean hasNext() {
            return cur != null;
        }

        /**
         * Returns the next element of the Iterator.
         * @return E
         */
        public E next() {

            if (cur == null) {
                throw new NoSuchElementException();
            }

            E val = cur.data;
            cur = cur.next;
            return val;
        }
    }

    /**
    * Iterator to traverse the CSLinkedList "backward" using next references.
    */
    public class ReverseIterator implements Iterator<E> {

        private Node<E> cur;

        /**
        * Consructor.
        */
        public ReverseIterator() {
            cur = tail;
        }

        /**
         * returns true if the Iterator has another value.
         * @return boolean
         */
        public boolean hasNext() {
            return cur != null;
        }

        /**
         * Returns the next element of the Iterator.
         * @return E
         */
        public E next() {

            if (cur == null) {
                throw new NoSuchElementException();
            }

            E val = cur.data;
            cur = cur.prev;
            return val;
        }
    }
}