// Chap 7, pp 314 - 315
// Rename this file as QueueP.cpp

// *********************************************************
// Implementation file QueueP.cpp for the ADT queue.
// Pointer-based implementation.
// *********************************************************
#include "QueueP.h"  // header file
#include <stddef.h>  // for NULL

// The queue is implemented as a circular linked list
// with one external pointer to the rear of the queue.
struct queueNode
{  queueItemType Item;
   ptrType       Next;
};  // end struct

queueClass::queueClass() : Rear(NULL)
{
}  // end constructor

queueClass::queueClass(const queueClass& Q)
{  // Implementation left as an exercise (Exercise 5).
}  // end copy constructor

queueClass::~queueClass()
{
   boolean Success;

   while (!QueueIsEmpty())
      QueueRemove(Success);
  // Assertion: Rear == NULL
}  // end destructor

boolean queueClass::QueueIsEmpty()
{
   return boolean(Rear == NULL);
}  // end QueueIsEmpty

void queueClass::QueueAdd(queueItemType NewItem,
                          boolean& Success)
{
   // create a new node
   ptrType NewFrontPtr = new queueNode;

   Success = boolean(NewFrontPtr != NULL);
   if (Success)
   {  // allocation successful; set data portion of new node
      NewFrontPtr->Item = NewItem;

      // insert the new node
      if (QueueIsEmpty())
         // insertion into empty queue
         NewFrontPtr->Next = NewFrontPtr;

      else
      {  // insertion into nonempty queue
         NewFrontPtr->Next = Rear->Next;
         Rear->Next = NewFrontPtr;
      }  // end if

      Rear = NewFrontPtr;  // new node is at rear
   }  // end if
}  // end QueueAdd

void queueClass::QueueRemove(boolean& Success)
{
   Success = boolean(!QueueIsEmpty());

   if (Success)
   {  // queue is not empty; remove front
      ptrType FrontPtr = Rear->Next;
      if (FrontPtr == Rear)   // special case?
         Rear = NULL;         // yes, one node in queue
      else
         Rear->Next = FrontPtr->Next;

      FrontPtr->Next = NULL;  // defensive strategy
      delete FrontPtr;
   }  // end if
}  // end QueueRemove

void queueClass::GetQueueFront(queueItemType& QueueFront, 
                               boolean& Success)
{
   Success = boolean(!QueueIsEmpty());

   if (Success)
      // queue is not empty; retrieve front
      QueueFront = Rear->Next->Item;
}  // end GetQueueFront
// End of implementation file.