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

/**
 * MyDeque is an implementation of Deque, a repository for Objects. 
 * Objects are inserted using enqueue and removed using dequeue. 
 * Objects are removed in the same order in which they are inserted.
 * A linked list is used to maintain the Deque.
 */

class MyDeque implements Deque
{
/**
 * the DCell at the front
 */

DCell head;


/**
 * the DCell at the back
 */

DCell tail;


/**
 * Construct an empty MyDeque.
 */

public MyDeque()
  {
  head = tail = null;
  }


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

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

    tail = head = new DCell(item, null, null);
    }
  else
    {
    // The Deque was not empty, so make the last DCell contain the item.

    tail = tail.Next = new DCell(item, null, tail);
    }
  }


/**
 * 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 = head.Data;
  head = head.Next;             // Remove the first DCell.

  if( head != null )
    {
    head.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( head == null )
    {
    // The Deque was empty, so make its only DCell contain the item.

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

    head = head.Previous = new DCell(item, head, 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 = tail.Data;

  tail = tail.Previous; // Remove the last DCell.
  if( tail == null )
    {
    head = null;        // Indicate that the Deque is now empty.
    }
  else
    {
    tail.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 head == 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;
    }
  }
}