/**
   The LinkedDeque class implements the Deque interface by means of
   a doubly linked list.
 
   @author      Franck van Breugel
   @version     1.3    May 15, 2000
   @see DLNode
*/
public class LinkedDeque implements Deque
{
    DLNode header;  // dummy node at the beginning
    DLNode trailer; // dummy node at the end
    int size;       // size of this deque

    /** Constructs an empty deque. **/
    public LinkedDeque() 
    {
        header = new DLNode();
        trailer = new DLNode();
        header.setNext(trailer);
        trailer.setPrev(header);
        size = 0;
    }

    public int size() 
    {
        return size;
    }

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

    public Object first() throws DequeEmptyException 
    {
        if (isEmpty()) 
        {
            throw new DequeEmptyException("Deque is empty.");
        }
        DLNode first = header.getNext();
        return first.getElement();
    }

    public Object last() throws DequeEmptyException 
    {
        if (isEmpty()) 
        {
            throw new DequeEmptyException("Deque is empty.");
        }
        DLNode last = trailer.getPrev();
        return last.getElement();
    }

    public void insertFirst(Object element) 
    {
        DLNode second = header.getNext();
        DLNode first = new DLNode(element, header, second);
        second.setPrev(first);
        header.setNext(first);
        size++;
    }

    public void insertLast(Object element) 
    {
        DLNode secondToLast = trailer.getPrev();
        DLNode last = new DLNode(element, secondToLast, trailer);
        secondToLast.setNext(last);
        trailer.setPrev(last);
        size++;
    }

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

    public Object removeLast() throws DequeEmptyException 
    {
        if (isEmpty()) 
	{
            throw new DequeEmptyException("Deque is empty.");
        }
        DLNode last = trailer.getPrev();
        DLNode secondToLast = last.getPrev();
        trailer.setPrev(secondToLast);
        secondToLast.setNext(trailer);
        size--;
        return last.getElement();
    }

    /**
       Returns a string representation of this deque.
       
       @return A string representation of this deque.
    */
    public String toString() 
    {
        String rep = "";
        DLNode pointer = header.getNext();
        while (pointer != trailer) 
	{
            rep += pointer.getElement().toString();
            rep += "\t";
            pointer = pointer.getNext();
        }
        return rep;
    }
}