//  Queue.h        Dave Reed        9/10/02
//
//  A templated Queue class, implemented using linked lists.
////////////////////////////////////////////////////////////////

#ifndef _QUEUE_
#define _QUEUE_

template <class Type>
class Node                          // class for storing some item
{                                   // in a linked list
  public:
    Type item;
    Node * next;
};

template <class Type>
class Queue
{
  public:
    Queue();                        // constructor
    Queue(const Queue<Type> & q);   // copy constructor
    ~Queue();                       // destructor
    Queue<Type> & operator=(const Queue<Type> & q);

    bool IsEmpty() const;           // returns if queue is empty
    void Enter(const Type & item);  // enters item at rear of queue
    void Remove();                  // removes item at front of queue
    Type & Front();	                // returns item at front of queue

  private:
    Node<Type> * myFront;           // pointers to linked list of items
    Node<Type> * myRear;
    Node<Type> * CopyList(const Node<Type> * ptr);
};

//////////////////////////////////////////////////////////////////////////

template <class Type>
Queue<Type>::Queue()
// Constructor: initializes queue to be empty (myFront = myRear = NULL)
{
    myFront = NULL;
    myRear = NULL;
}

template <class Type>
Node<Type> * Queue<Type>::CopyList(const Node<Type> * ptr)
// private member function to recursively copy a linked list
{
    if (ptr == NULL) {
        return NULL;
	}
    else {
        Node<Type> * copyFront = new Node<Type>;
        copyFront->item = ptr->item;
        copyFront->next = CopyList(ptr->next);
        return copyFront;
	}
}

template <class Type>
Queue<Type>::Queue(const Queue<Type> & q)
// Constructor: initializes queue to be empty (myFront = myRear = NULL)
{
    myFront = CopyList(q.myFront);
    myRear = myFront;
    while (myRear != NULL && myRear->next != NULL) {
        myRear = myRear->next;
	}
}

template <class Type>
Queue<Type> & Queue<Type>::operator=(const Queue<Type> & q)
// Assignment operator
{
    if (this != &q) {
        while (!IsEmpty()) {
            Remove();
        }
        myFront = CopyList(q.myFront);
        myRear = myFront;
        while (myRear != NULL && myRear->next != NULL) {
            myRear = myRear->next;
		}
	}
    return *this;
}

template <class Type>
Queue<Type>::~Queue()
// Destructor: deallocates nodes in the linked list
{
    while (!IsEmpty()) {
        Remove();
    }
}

template <class Type>
bool Queue<Type>::IsEmpty() const
// Returns: true if empty queue, else false
{
    return (myFront == NULL);
}

template <class Type>
void Queue<Type>::Enter(const Type & toBeEntered)
// Results: enters toBeEntered at rear of queue
{
    Node<Type> * temp = new Node<Type>;
    temp->item = toBeEntered;
    temp->next = NULL;
    
    if (myRear == NULL) {
        myRear = temp;
        myFront = temp;
	}
    else {
        myRear->next = temp;
        myRear = temp;
	}
}

template <class Type>
void Queue<Type>::Remove()
// Assumes: queue is not empty
// Results: removes an item from the front of the queue
{
    Node<Type> * temp = myFront;
    myFront = myFront->next;
    delete temp;

    if (myFront == NULL) {
        myRear = NULL;
	}
}

template <class Type>
Type & Queue<Type>::Front() 
// Assumes: queue is not empty
// Returns: reference to item at the front of the queue
{
    return myFront->item;
}

#endif