/* File: DLLDeque.java
 * Author: Wayne Snyder (waysnyder@gmail.com)
 * Data: Jul 29, 2020
 * Purpose: Example of Deque implemented by Doubly-Linked List
 */


public class DLLDeque {

    private class DNode {
        int item;
        DNode next, prev;
        public DNode(DNode p, int i, DNode n) {
            prev = p; item = i; next = n;
        }
    }

    private DNode front = null;
    private DNode rear = null;
    private int size = 0;

    public boolean isEmpty() {
        return front == null;
    }

    public int size() {
        return size;
    }

    public void enqueueRear(int i) {
        if (front == null) {    // DQ is empty
            front = rear = new DNode(null,i,null);
        } else {
            rear.next = new DNode(rear, i, null);
            rear = rear.next;
        }
        ++size;
    }


    public void enqueueFront(int i) {
        if (front == null) {    // DQ is empty
            front = rear = new DNode(null,i,null);
        } else {
            front.prev = new DNode(null, i, front);
            front = front.prev;
        }
        ++size;
    }

    public int dequeueRear() {
        int tmp = rear.item;
        rear = rear.prev;
        rear.next = null;
        --size;
        return tmp;
    }

    public int dequeueFront() {
        int tmp = front.item;
        front = front.next;
        front.prev = null;
        --size;
        return tmp;
    }

    public String toString() {
        String s = "front-> ";
        for(DNode p = front; p != null; p = p.next) {
            if (p.next == null) {  // last item
                s += p.item + " <-rear";
            } else {
                s += p.item + " <-> ";
            }
        }
        return s;
    }


    public static void main(String[] args) {

        DLLDeque DQ = new DLLDeque();
        DQ.enqueueFront(2);
        DQ.enqueueRear(3);
        DQ.enqueueFront(1);
        DQ.enqueueRear(4);
        DQ.enqueueRear(5);
        //   front -> 3 1  2  3  4  5 <- rear
        System.out.println();
        System.out.println(DQ);
        System.out.println("\nSize; Should print 5:");
        System.out.println(DQ.size());
        System.out.println("\nShould print 5 then 4:");
        System.out.println(DQ.dequeueRear());
        System.out.println(DQ.dequeueRear());
        System.out.println("\nShould print 1, then 2::");
        System.out.println(DQ.dequeueFront());
        System.out.println(DQ.dequeueFront());
        System.out.println();
        System.out.println(DQ);
        System.out.println("\nSize; Should print 1:");
        System.out.println(DQ.size());
        
    }
}