// Implementation file for Queue ADT; class specification in file queuell.h.
// Class is templated.
// Uses linked list of items with a pointer to the head and one to the tail.

//------------------------------------------------------------------------------------
// NodeType for nodes in linked list
//------------------------------------------------------------------------------------

template <class ItemType>
struct NodeType
{
    ItemType info;
    NodeType* next;
};

//------------------------------------------------------------------------------------
// Queue Constructor - Initializes an empty queue
//------------------------------------------------------------------------------------

template <class ItemType>
QueueType<ItemType>::QueueType()
{
    qFront = NULL;
    qRear = NULL;
}

//------------------------------------------------------------------------------------
// Queue Destructor - releases memory used by nodes
//------------------------------------------------------------------------------------

template <class ItemType>
QueueType<ItemType>::~QueueType()
{
    NodeType<ItemType>* tempPtr;

    while (qFront != NULL)
    {
        tempPtr = qFront;
        qFront = qFront->next;
        delete tempPtr;
    }
    qRear = NULL;
}

//------------------------------------------------------------------------------------
// IsEmpty - tests for empty queue
//------------------------------------------------------------------------------------
// Returns true if the queue is empty; false otherwise
//------------------------------------------------------------------------------------

template <class ItemType>
bool QueueType<ItemType>::IsEmpty() const
// Returns true if there are no elements on the queue; false otherwise.
{
    return (qFront == NULL);
}

//------------------------------------------------------------------------------------
// IsQueue - tests for full queue  (linked implementation "never" full!)
//------------------------------------------------------------------------------------

template <class ItemType>
bool QueueType<ItemType>::IsFull() const
{
    return false;
}

//------------------------------------------------------------------------------------
// Enqueue - adds item to rear of the queue
//------------------------------------------------------------------------------------
// Accepts:  item to be added
//------------------------------------------------------------------------------------

template <class ItemType>
void QueueType<ItemType>::Enqueue(ItemType newItem)
{
    NodeType<ItemType>* newNode;

    newNode = new NodeType<ItemType>;
    newNode->info = newItem;
    newNode->next = NULL;
    if (qRear == NULL)
        qFront = newNode;
    else
        qRear->next = newNode;
    qRear = newNode;
}

//------------------------------------------------------------------------------------
// Dequeue - removes item at front of queue
//------------------------------------------------------------------------------------
// Returns:  copy of item removed
//------------------------------------------------------------------------------------

template <class ItemType>
void QueueType<ItemType>::Dequeue(ItemType& item)
{
    NodeType<ItemType>* tempPtr;

    if (!IsEmpty())
    {
        tempPtr = qFront;
        item = qFront->info;
        qFront = qFront->next;
        if (qFront == NULL)
            qRear = NULL;
        delete tempPtr;
    }
    else
        cout << "\nError - attempting to remove item from empty queue";
}

//------------------------------------------------------------------------------------
//Copy
//------------------------------------------------------------------------------------

template<class ItemType>
void QueueType<ItemType>::CopyNth(int N, ItemType& copyitem)
{
   NodeType<ItemType>* ptr;
   int count = 1;
   bool found = false;
   ptr = qFront;
   if(!IsEmpty())
   {      
     while(count < N+1 && ptr != NULL && found == false)
     {
        if(count == N)
        {
           copyitem = ptr->info;
           found = true;
        }
        else
        {  
           ptr = ptr->next;
           count++; 
        }         
     }
   }
}