// 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: looks at the Nth element without disturbing the original structure
//----------------------------------------------------------------------------------


template <class ItemType>
void QueueType<ItemType> ::CopyNth(int N, ItemType& copyitem)
{
    NodeType<ItemType>* tempPtr;
    int i=1;
    
    if (!IsEmpty())   
    {
        tempPtr = qFront;
        while(i < N && tempPtr != NULL)
        {
	    tempPtr = tempPtr->next;
	
	    i++;
	}
	copyitem = tempPtr->info;
    }
    else
        cout << "\nError - attempting to copy an item from an empty queue";
}