/**
  * Class Node Deque to implement the Deque interface using doubly linked list
  *
  * @author Roberto Tamassia
  * @author Michael Goodrich

  * @author Jack Han
  */

public class NodeDeque<E> implements Deque<E> {
 

  protected DLNode<E> header;  // sentinels
  protected int size;    // number of elements
 

 // initialize an empty deque

 public NodeDeque() { 
    header = new DLNode<E>();
    header.setNext(header);  // make header point to itself
    head.setPrev(header); 
    size = 0;
  }
 

// Returns the number of nodes

 public int size() {  
    return size;
  }
 

 // Test if empty

 public boolean isEmpty() {   
    if (size == 0)
      return true;
    return false;
  }

// Returns the first element

 public E getFirst() throws EmptyDequeException { 
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    return header.getNext().getElement();
  }
 

 // Returns the last element

public E getLast() throws EmptyDequeException { 
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    return header.getPrev().getElement();
  }

 // Adds a new element at the front

 public void addFirst(E o) { 
    DLNode<E> second = header.getNext();
    DLNode<E> first = new DLNode<E>(o, second, header);
    second.setPrev(first);
    header.setNext(first);
    size++;
  }
 

 // Adds a new node at the tail

 public void addLast(E o) { 
    DLNode<E> second = header.getPrev();
    DLNode<E> last = new DLNode<E>(o, header, second);
    second.setNext(last);
    header.setPrev(last);
    size++;
  }

 // Removes the first node

 public E removeFirst() throws EmptyDequeException {
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    DLNode<E> first = header.getNext();
    E o = first.getElement();
    DLNode<E> second = first.getNext();
    header.setNext(second);
    second.setPrev(header);
    size--;
    return o;
  }

 // Removes the last node

 public E removeLast() throws EmptyDequeException {
    if (isEmpty())
      throw new EmptyDequeException("Deque is empty.");
    DLNode<E> last = trailer.getPrev();
    E o = last.getElement();
    DLNode<E> secondtolast = last.getPrev();
    trailer.setPrev(secondtolast);
    secondtolast.setNext(trailer);
    size--;
    return o;
  }
}