/**
 * A generic Doubly Linked List implementation that requires the
 * thing being held to implement the comparable interface. This is
 * a curious requirement because, except for find,  NONE 
 * of the code here actually uses comparability.  Even find could
 * be written to just use equals instead of compareTo.
 * 
 * @author gtowell 
 * 
 * Created: Jan 2020 
 * Modified: Nov 2020
 * Modified: Nov 2021
 */
public class DoubleLinkedList<T extends Comparable<T>> implements LinkedListInterfaceComp<T>  {

    /**
     * The node class. Each element in the linked list is an instance of Node
     */
    protected class DNode<V extends Comparable<V>>{
        public V data;
	    /** The previous item in the linked list */
        public DNode<V> prev;
        public DNode<V> next;
        /**
         * Node constructor. Takes a data item and the preceding and trailing nodes.
         */
        public DNode(V data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

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

    /** The last element in the linked list */
    protected DNode<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
     */
    @Override
    public int size() {
        return size;
    }

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

    /**
     * Get the first element in the linked list
     * 
     * @return the first element in the linked list or null if list is empty
     */
    @Override
    public T first() {
        if (head == null)
            return null;
        return head.data;
    }

    /**
     * The last element in the linked list
     * 
     * @return the last elment or null if list is empty
     */
    @Override
    public T last() {
        if (head == null)
            return null;
        return tail.data;
    }

    /**
     * Remove the first item from the list
     * 
     * @return the first item, or null if the list is empty
     */
    @Override
    public T removeFirst() {
        if (head == null)
            return null;
        T rtn = head.data;
        head = head.next;
        if (head == null)
            tail = null;
        else
            head.prev = null;
        size--;
        return rtn;
    }

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

    /**
     * Remove the specified rabbit from the list
     * 
     * @param r the item to be removed
     * @return the removed item, or null is the item was not in the list
     */
    @Override
    public T remove(T r) {
        DNode<T> curr = find(r);
        if (curr == null) {
            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;
    }

    

    public String toStringBackwards() {
        StringBuffer s = new StringBuffer();
        for (DNode<T> n = tail; n != null; n = n.prev) {
            s.append(n.data.toString());
            //s.append("\n");
        }
        return s.toString();
    }


    /**
     * @param args
     */
    public static void main(String[] args) {
        new DoubleLinkedList<>().testt();
        new DoubleLinkedList<>().testu();
    }

    public boolean testt() {
        System.out.println("Test of item removal from middle of list\n----------------------------------------");
        DoubleLinkedList<Integer> s = new DoubleLinkedList<>();
        DoubleLinkedList<Integer> t = new DoubleLinkedList<>();
        for (int i = 0; i < 5; i++) {
            s.addLast(i);
            if (i != 3)
                t.addLast(i);
        }
        System.out.format("First List : %s\n", s);
        System.out.format("Second List: %s\n", t);
        System.out.println("Now remove 3:  the lists should be identical");
        s.remove(3);
        System.out.format("First List : %s\n", s);
        System.out.format("Second List: %s\n", t);
        if (s.size() != t.size()) {
            System.out.println("Test failed: lists are not equal sizes");
            return false;
        }
        while (s.size() > 0) {
            if (s.removeFirst() != t.removeFirst()) {
                System.out.println("Remove test Failed -- items are not all the same.");
                return false;
            }
        }
        System.out.println("Remove test Passed");
        return true;
    }

    public boolean testu() {
        System.out.println("Test of item removal from head of list (using remove)\n----------------------------------------");
        DoubleLinkedList<Integer> s = new DoubleLinkedList<>();
        DoubleLinkedList<Integer> t = new DoubleLinkedList<>();
        for (int i = 0; i < 5; i++) {
            s.addLast(i);
            if (i != 0)
                t.addLast(i);
        }
        System.out.format("First List : %s\n", s);
        System.out.format("Second List: %s\n", t);
        System.out.println("Now remove 0:  the lists should be identical");
        s.remove(0);
        System.out.format("First List : %s\n", s);
        System.out.format("Second List: %s\n", t);
        if (s.size() != t.size()) {
            System.out.println("Test failed: lists are not equal sizes");
            return false;
        }
        while (s.size() > 0) {
            if (s.removeFirst() != t.removeFirst()) {
                System.out.println("Remove test Failed -- items are not all the same.");
                return false;
            }
        }
        System.out.println("Remove test Passed");
        return true;
    }

    /**
     * Add an element at the end of the list
     * 
     * @param c the element to be added
     */
    @Override
    public void addLast(T c) {
        DNode<T> newNode = new DNode<>(c);
        if (head == null) {
            head = newNode;
            tail = newNode;
            size = 1;
            return;
        }
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
        size++;
    }

    /**
     * Add a element at the front of the list
     * 
     * @param c the Element to be added
     */
    @Override
    public void addFirst(T c) {
        DNode<T> newNode = new DNode<>(c);
        if (head == null) {
            head = newNode;
            tail = newNode;
            size = 1;
            return;
        }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
        size++;
    }

    private DNode<T> find(T look4) {
        DNode<T> curr = head;
        while (curr != null) {
            if (0 == curr.data.compareTo(look4)) {
                break;
            }
            curr = curr.next;
        }
        return curr;
    }

    public boolean contains(T iD) {
        DNode<T> nod = find(iD);
        return (nod != null);
    }

    

}