/* DequeReferenceBased.java */

/**
 * This is an implementation of a Queue that supports
 * queuing and dequeuing from both ends.
 * @see QueueReferenceBased for other available methods.
 *
 * @author Zach Tomaszewski
 * @date  27 Oct 2001
 */

public class DequeReferenceBased extends QueueReferenceBased
                                 implements DequeInterface{
   
/* In retrospect, it would have been much less work just
   to iterate through the list once on dequeBack than
   implement all the DoublyLinkedNodes.
   Also, probably could have called some super methods
   and just added on to that.  Oh well.    */

/**
 * Enqueues newItem on the front of the queue (similar to a push)
 * @param newItem - the object to be added to the front of the queue
 */
public void enqueueFront(Object newItem) throws QueueException{

  DoublyLinkedNode newNode = new DoublyLinkedNode(newItem);
  // insert the new node
   if (isEmpty()) {
  // insertion into empty queue
     newNode.setNext(newNode);
     newNode.setPrev(newNode);
     lastNode = newNode;
   }else {
  // insertion into nonempty queue
     newNode.setNext(lastNode.getNext());
     ((DoublyLinkedNode)lastNode.getNext()).setPrev(newNode);
     newNode.setPrev(lastNode);
     lastNode.setNext(newNode);
   }
}


/**
 * Removes and returns the last item on a queue (similar to pop).
 * This shortens the list by one item.
 * @return - the Object that was on the end of the queue
 * @throws QueueException if the queue is empty
 */
public Object dequeueBack() throws QueueException{
                   
  if (!isEmpty()) {
     Object item = lastNode.getItem();
     if (lastNode.getNext() == lastNode) { // special case?
       lastNode = null; // yes, one node in queue
     }else {
       ((DoublyLinkedNode)lastNode.getNext()).setPrev(
                          ((DoublyLinkedNode)lastNode).getPrev());
       ((DoublyLinkedNode)lastNode).getPrev().setNext(lastNode.getNext());
       lastNode = (DoublyLinkedNode)((DoublyLinkedNode)lastNode).getPrev();
     }
     return item;
  }else {
     throw new QueueException("QueueException on dequeueBack:"
                               + "queue empty");
  }
}



/* Overridding methods */

public void enqueue(Object newItem) {
  DoublyLinkedNode newNode = new DoublyLinkedNode(newItem);

  // insert the new node
   if (isEmpty()) {
  // insertion into empty queue
     newNode.setNext(newNode);
     newNode.setPrev(newNode);
   }else {
  // insertion into nonempty queue
     newNode.setNext(lastNode.getNext());
     ((DoublyLinkedNode)lastNode.getNext()).setPrev(newNode);
     newNode.setPrev(lastNode);
     lastNode.setNext(newNode);
   }// end if

lastNode = newNode;// new node is at back
}// end enqueue


public Object dequeue() throws QueueException {
  if (!isEmpty()) {
     // queue is not empty; remove front
     Node firstNode = lastNode.getNext();
     if (firstNode == lastNode) { // special case?
       lastNode = null; // yes, one node in queue
     }else {
       lastNode.setNext(firstNode.getNext());
       ((DoublyLinkedNode)firstNode.getNext()).setPrev(lastNode);
     }
     return firstNode.getItem();
  }else {
     throw new QueueException("QueueException on dequeue:"
                               + "queue empty");
  }// end if
}// end dequeue

}//end class