// *********************************************************
// Implementation file QueueP.cpp for the ADT queue.
// Pointer-based implementation.
// *********************************************************
using namespace std;
#include "QueueP.h" // header file
#include <cstddef>
#include <stdexcept>

Queue::Queue() : frontPtr(NULL), backPtr(NULL)
{
} // end default constructor

Queue::Queue(const Queue& aQueue)
  throw(runtime_error): frontPtr(NULL), backPtr(NULL)
{
  if (!aQueue.isEmpty()) 
  { 
    // copy first node 
    QueueNode *origCur = aQueue.frontPtr; // pt to first node 
    QueueNode *newHead = new QueueNode; 
    if(newHead == NULL)
      throw runtime_error("bad allocation in copy constructor");
    
    newHead->item = origCur->item; 
    newHead->next = newHead;
    frontPtr = newHead;
    backPtr = newHead;
    
    // copy rest of list 
    QueueNode *newCur = newHead; 
    
    while (origCur != aQueue.backPtr)
    {  
      origCur = origCur->next;
      newCur->next = new QueueNode;
      if(newCur == NULL)
        throw runtime_error("bad allocation in copy constructor");
      newCur = newCur->next;
      newCur->item = origCur->item;
      newCur->next = NULL;
      backPtr = newCur;
    }  // end while 
  }  // end if 
}  // end copy constructor

Queue::~Queue()
{
  while (!isEmpty())
    dequeue();
} // end destructor

bool Queue::isEmpty() const
{
   return backPtr == NULL;
} // end isEmpty

void Queue::enqueue(QueueItemType newItem)
  throw(runtime_error)
{
  QueueNode *newPtr = new QueueNode;
  if (newPtr == NULL) // check allocation
    throw runtime_error("enqueue cannot allocate memory");
  
  // allocation successful; set data portion of new node
  newPtr->item = newItem;
  newPtr->next = NULL;
  // insert the new node
  if (isEmpty())
    // insertion into empty queue
    frontPtr = newPtr;
  else
    // insertion into nonempty queue
    backPtr->next = newPtr;
  
  backPtr = newPtr; // new node is at back
} // end enqueue

void Queue::dequeue()
  throw (QueueException)
{
   if (isEmpty())
      throw QueueException("QueueException: empty queue, cannot dequeue");
   
   // queue is not empty; remove front
   QueueNode *tempPtr = frontPtr;
   if (frontPtr == backPtr) // special case?
   {  // yes, one node in queue
     frontPtr = NULL;
     backPtr = NULL;
   }
   else
     frontPtr = frontPtr->next;
   
   tempPtr->next = NULL; // defensive strategy
   delete tempPtr;
} // end dequeue

void Queue::dequeue(QueueItemType& queueFront)
  throw (QueueException)
{
   if (isEmpty())
   throw QueueException("QueueException: empty queue, cannot dequeue");
   
   // queue is not empty; retrieve front
   queueFront = frontPtr->item;
   dequeue(); // delete front
} // end dequeue

void Queue::getFront(QueueItemType& queueFront) const
  throw(QueueException)
{
   if (isEmpty())
     throw QueueException("QueueException: empty queue, cannot getFront");

   // queue is not empty; retrieve front
   queueFront = frontPtr->item;
} // end getFront