/* 
 *  File: queue-linked.cpp
 *        Member function implementations for a template class
 *        Queue ADT using a linked list representation
 *
 *  From Kruse&Ryba: _Data Structure and Program Design in C++_
 *
 *  Modified: spc
 *
 * Class Invariant
 *
 *   1) For an empty queue, front = back = NULL
 *   2) For a non-empty queue, front points to the least-recently 
 *      enqueued item and back points to the most-recently enqueued item
 *   3) The item in the node pointed to by front will be the next to
 *      be removed by a dequeue operation
 */

//#include "queue-linked.h"
#include <iostream>
#include "queue-rizki.h"
using namespace std;

template <class Queue_entry>
Queue<Queue_entry>::Queue()
{
   front = back = NULL;
}


template <class Queue_entry>
Queue<Queue_entry>::Queue(const Queue<Queue_entry>& copy)
{
	Node<Queue_entry> *copy_node = copy.front;
	front = back = NULL;
	while (copy_node != NULL) {
		enqueue(copy_node->entry);
		copy_node = copy_node->next;
	}
}

template <class Queue_entry>
Queue<Queue_entry>::~Queue()
{
	Queue_entry temp;   // to satisfy compiler ... we never use this object
	while (!empty())
		dequeue(temp);
}

template <class Queue_entry>
bool Queue<Queue_entry>::empty() const
{
	return (front == NULL);
}

template <class Queue_entry>
void Queue<Queue_entry>::enqueue(const Queue_entry &item)
{
   Node<Queue_entry> *new_back = new Node<Queue_entry>(item);
   if (new_back == NULL) throw string("out of memory");

   if (back == NULL) front = back = new_back;
   else {
      back->next = new_back;
      back = new_back;
   }
   return;
}

template <class Queue_entry>
void Queue<Queue_entry>::dequeue(Queue_entry &item)
{
   if (front == NULL) throw string("underflow");

   item = front->entry;
   Node<Queue_entry> *old_front = front;
   front = old_front->next;

   if (front == NULL) back = NULL;
   delete old_front;
   return;
}

template <class Queue_entry>
void Queue<Queue_entry>::getFront(Queue_entry &item)
{
   if (front == NULL) throw string("underflow");

   item = front->entry;
   return;
}

template <class Queue_entry>
Queue<Queue_entry>& Queue<Queue_entry>::operator=(const Queue<Queue_entry>& copy)
{
	Queue_entry temp;   // to satisfy compiler ... we never use this object

	// clear out any current queue items
	while (!empty())
		dequeue(temp);
	front = back = NULL;

	Node<Queue_entry> *copy_node = copy.front;
	while (copy_node != NULL) {
		enqueue(copy_node->entry);
		copy_node = copy_node->next;
	}
	return *this;
}

//#include "expqueue.h"
#include <string>
using namespace std;
template class Queue<int>;
template class Queue<string>;