// file:    DLDeque.java
// author:  Robert Keller
// purpose: Implement the Deque interface using bi-directional linked lists.

/**
 * DLDeque is an implementation of Deque, a repository for Objects. 
 * that maintains insertion order.  
 * Objects can be inserted and removed from either in.
 * Objects are inserted using enqueue and removed using dequeue. 
 * A doubly-linked list is used to maintain the Deque.
 */

class DLDeque implements Deque
{
/**
 * the Dcell at the front
 */

Dcell front;


/**
 * the Dcell at the back
 */

Dcell back;


/**
 * Construct an empty DLDeque.
 */

public DLDeque()
  {
  front = back = null;
  }


/**
 * Insert an Object at the back of the Deque.
 *
 * @param item the Object to be inserted
 */

public void enqueueBack(Object item)
  {
  if( front == null )
    {
    // The Deque was empty, so make its only Dcell contain the item.

    back = front = new Dcell(item, null, null);
    }
  else
    {
    // The Deque was not empty, so make the last Dcell contain the item.

    back = back.Next = new Dcell(item, null, back);
    }
  }


/**
 * Remove an Object from the front of the Deque.
 *
 * @return the Object removed
 * @exception EmptyQueueException if the Queue is empty
 */

public Object dequeueFront() throws EmptyQueueException
  {
  if( isEmpty() )
    {
    throw new EmptyQueueException();
    }

  Object result = front.Data;
  front = front.Next;           // Remove the first Dcell.

  if( front != null )
    {
    front.Previous = null;      // Indicate that there are no preceding Dcells.
    }
  return result;
  }


/**
 * Insert an Object at the front of the Deque.
 *
 * @param item the Object to be inserted
 */

public void enqueueFront(Object item)
  {
  if( front == null )
    {
    // The Deque was empty, so make its only Dcell contain the item.

    front = back = new Dcell(item, null, null);
    }
  else
    {
    // The Deque was non-empty, so make the first Dcell contain the item.

    front = front.Previous = new Dcell(item, front, null);
    }
  }


/**
 * Remove an Object from the back of the Deque.
 *
 * @return the Object removed
 * @exception EmptyQueueException if the Queue is empty
 */

public Object dequeueBack() throws EmptyQueueException
  {
  if( isEmpty() )
    {
    throw new EmptyQueueException();
    }

  Object result = back.Data;

  back = back.Previous; // Remove the last Dcell.
  if( back == null )
    {
    front = null;       // Indicate that the Deque is now empty.
    }
  else
    {
    back.Next = null;   // Indicate that there are no following Dcells.
    }
  return result;
  }


/**
 * Indicate whether or not the Deque is empty
 *
 * @return boolean indicating whether or not the Deque is empty
 */

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


/**
 * A Dcell stores one Object in the Queue and points to the immediately
 * following and preceding Dcells, if any.
 */

class Dcell
  {
  /**
   * the data in this Dcell
   */

  Object Data;


  /**
   * reference to the next Dcell in the sequence
   */

  Dcell Next;  


  /**
   * reference to the previous Dcell in the sequence
   */

  Dcell Previous;


  /**
   * construct a Dcell referencing the next and previous Dcell and
   * containing specified data
   *
   * @param _Data the data in this Dcell
   * @param _Next the next Dcell in the sequence
   * @param _Previous the previous Dcell in the sequence
   */

  Dcell(Object _Data, Dcell _Next, Dcell _Previous)
    {
    Data     = _Data;
    Next     = _Next;
    Previous = _Previous;
    }
  }
}