/*      File Name:      queuell.cpp
        Author:         R.P. Patillo
        Instructor:     Dr. Ames
        Due Date:       Oct. 23, 2008
        Complilation:   g++ queueclient.cpp -o queueclient.out
        Execution:      ./queueclient.out
*/

// 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";
}

//----------------------------------------------------------------------------
// CopyNth - returns a copy of the item located in the Nth position of a stack
//----------------------------------------------------------------------------
// Returns:   copy of Nth item
//---------------------------------------------------------------------------

template<class ItemType>
void QueueType<ItemType> :: CopyNth(int N, ItemType& copyitem)
{
    NodeType <ItemType>* tempPtr = qFront;

    for(int i=0; i<N-1; i++)		// moves down the queue desired N times (which is N-1 times)
        tempPtr = tempPtr->next;
    copyitem = tempPtr->info;
}