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

#ifndef _PRIORITY_QUEUE_
#define _PRIORITY_QUEUE_

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


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

	bool IsEmpty() const;                   // returns if queue is empty
    void Enter(const Type & item, int pri); // enters item in queue
    void Remove();                          // removes item at front of queue
    Type & Front();							// returns item at front of queue
	int FrontPriority();                    // returns priority of front item

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

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

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

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

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

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

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

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

template <class Type>
void PriorityQueue<Type>::Enter(const Type & toBeEntered, int pri)
// Results: enters toBeEntered at rear of queue
{
    PriorityNode<Type> * temp = new PriorityNode<Type>;
    temp->item = toBeEntered;
    temp->priority = pri;
    temp->next = NULL;
    
    if (myFront == NULL || temp->priority < myFront->priority) {
        temp->next = myFront;
        myFront = temp;
	}
    else {
        PriorityNode<Type> * trailer = myFront;
        while (trailer->next != NULL && trailer->next->priority <= temp->priority) {
            trailer = trailer->next;
		}
        temp->next = trailer->next;
        trailer->next = temp;
	}
}

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

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

template <class Type>
int PriorityQueue<Type>::FrontPriority() 
// Assumes: queue is not empty
// Returns: priority of item at the front of the queue
{
    return myFront->priority;
}
#endif