import java.util.NoSuchElementException;

/**
 * A generic Doubly Linked List implementation.
 * @author gtowell
 * Created: October 2019
 * Modified: March 2020 by g towell
 */
public class DoubleLinkedList<T extends Comparable<T>> {

    /**
     * The node class. Each element in the linked list is an instance of Node
     */
    protected class Node<V extends Comparable<V>> {
        /** The data item in the node. An instance of the data */
        public Comparable<V> data;
        /** The next item in the linked list */
        public Node<V> next;
        /** The previous item in the linked list */
        public Node<V> prev;

        /**
         * Node constructor. Takes a rannit and another node
         */
        public Node(Comparable<V> data, Node<V> prev, Node<V> next) {
            this.data = data;
            this.next = next;
            this.prev = prev;
        }
    }

    /** The start, first element, of the linked list */
    protected Node<T> head = null;

    /** THe last element in the linked list */
    protected Node<T> tail = null;

    /** The number of items in the linked list */
    protected int size = 0;

    /**
     * The number of items in the linked list
     * 
     * @return the number of items in the linked list
     */
    public int size() {
        return size;
    }

    /**
     * Returns true iff the linked list has no elements
     * 
     * @return true iff the linked list has no elements
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Get the first element in the linked list
     * 
     * @return the first element in the linked list
     * @throws NoSuchElementException is the list is empty
     */
    @SuppressWarnings("unchecked")
    public T first() throws NoSuchElementException {
        if (head == null)
            throw new NoSuchElementException("Nothing");
        return (T) head.data;
    }

    /**
     * The last element in the linked list
     * 
     * @return the last elment
     * @throws NoSuchElementException if the linked list is empty
     */
    @SuppressWarnings("unchecked")
    public T last() throws NoSuchElementException {
        if (head == null)
            throw new NoSuchElementException("Nothing");
        return (T) tail.data;
    }

    /**
     * Add an item to the end of the list
     * 
     * @param c the item to be added
     */
    public void addLast(T c) {
        Node<T> newest = new Node<>(c, tail, null);
        if (isEmpty()) {
            head = newest;
        } else {
            tail.next = newest;
        }
        tail = newest;
        size++;
    }

    /**
     * Add an item at the front of the list
     * 
     * @param c the item to be added
     */
    public void addFirst(T c) {
        Node<T> newest = new Node<>(c, null, head);
        if (isEmpty()) {
            tail = newest;
        } else {
            head.prev = newest;
        }
        head = newest;
        size++;
    }

    /**
     * Remove the last item from the list
     * 
     * @return the last item, or null if the list is empty
     */
    @SuppressWarnings("unchecked")
    public T removeFirst() {
        if (head == null)
            return null;
        Comparable<T> rtn = head.data;
        head = head.next;
        if (head == null)
            tail = null;
        else
            head.prev = null;
        size--;
        return (T) rtn;
    }

    /**
     * Remove the last item from the list
     * 
     * @return the last item, or null if the list is empty
     */
    @SuppressWarnings("unchecked")
    public T removeLast() {
        if (head == null)
            return null;
        Comparable<T> rtn = tail.data;
        if (head == tail) {
            head = null;
            size = 0;
            tail = null;
            return (T) rtn;
        }
        tail = tail.prev;
        tail.next = null;
        size--;
        return (T) rtn;
    }

    /**
     * Remove the specified item from the list
     * 
     * @param r the item to be removed
     * @return the removed item, or null is the item was not in the list
     */
    public T remove(T r) {
        // Do something much like find, but need to trak the previous node
        Node<T> curr = head;
        while (curr != null) {
            if (0 == curr.data.compareTo(r)) {
                break;
            }
            curr = curr.next;
        }
        if (curr == null) {
            // 1. the item was not found
            return null;
        }
        size--;
        if (curr.prev != null)
            curr.prev.next = curr.next;
        if (curr.next != null)
            curr.next.prev = curr.prev;
        if (curr == tail)
            tail = curr.prev;
        return r;
    }

    /**
     * Find an item in the list by its iD
     * 
     * @param iD
     * @return the found item, or null if a match could not be found
     */
    @SuppressWarnings("unchecked")
    public T find(T rr) {
        Node<T> curr = head;
        while (curr != null) {
            if (0 == curr.data.compareTo(rr)) {
                return (T) curr.data;
            }
            curr = curr.next;
        }
        return null;
    }

    @SuppressWarnings("unchecked")
    public void addSorted(Comparable<T> t) {
        Node<T> newest = new Node<>(t, null, null);
        if (head == null) {
            head = newest;
            tail = newest;
            size = 1;
            return;
        }
        Node<T> curr = head;
        while (curr != null) {
            if (curr.data.compareTo((T) t) > 0)
                break;
            curr = curr.next;
        }
        if (curr == null) {
            tail.next = newest;
            newest.prev = tail;
            tail=newest;
        } else {
            // need to put in new node priot to curr
            Node<T> tmp = curr.prev;
            if (tmp != null)
                tmp.next = newest;
            newest.prev = tmp;
            newest.next = curr;
            curr.prev = newest;
            if (curr==head)
                head=newest;
        }
    }


    public String toString() {
        StringBuffer s = new StringBuffer();
        for (Node<T> n = head; n != null; n = n.next) {
            s.append(n.data.toString());
            s.append("\n");
        }
        return s.toString();
    }

    public static void main(String[] args) {
        DoubleLinkedList<String> dll = new DoubleLinkedList<>();
        dll.addSorted("A");
        dll.addSorted("S");
        dll.addSorted("D");
        dll.addSorted("F");
        System.out.println(dll.toString());
    }
}