#pragma once

#include <list>
#include <iostream>
#include <sstream>

using namespace std;

template <typename T>
class PriorityQueue
{

private:
	// Nested class.
	class PriorityItem
	{
	private:
		int priority;
		T item;

	public:
		PriorityItem(T item_, int priority_)
			: item(item_),
			  priority(priority_)
		{
			cout << "PriorityItem ctor!" <<endl;
		}

		~PriorityItem()
		{
			cout << "PriorityItem dtor!" <<endl;
		}
		
		int GetPriority() const;
		PriorityItem GetItem() const;
		string ToString() const;
		void DisplayPriorityItem() const;

		bool operator<(const PriorityItem& other_) const;
	};


private:
	// State.
	list<PriorityItem> queue;
	void SortAccordingToPriority();
	

public:
	// Public interface.
	PriorityQueue();
	~PriorityQueue();

	void AddItem(T item_, int priority_);
	void RemoveItem();
	void DisplayQueue() const;
};


template <typename T>
PriorityQueue<T>::PriorityQueue()
{
	cout << "PriorityQueue ctor!" << endl;
}


template <typename T>
PriorityQueue<T>::~PriorityQueue()
{
	cout << "PriorityQueue dtor!" << endl;
}


template <typename T>
void PriorityQueue<T>::SortAccordingToPriority()
{
	queue.sort();
}


template <typename T>
void PriorityQueue<T>::AddItem(T item_, int priority_)
{
	queue.push_back(PriorityItem(item_,priority_));
	SortAccordingToPriority();  // You have to overload PriorityItem::operator< for this to work...
}


template <typename T>
void PriorityQueue<T>::RemoveItem()
{
	SortAccordingToPriority();
	typename list<PriorityItem>::iterator iter = queue.begin();
	queue.erase(iter);
}


template <typename T>
void PriorityQueue<T>::DisplayQueue() const
{
	typename list<PriorityItem>::const_iterator iter;
	for (iter = queue.begin(); iter != queue.end(); iter++)
	{
		cout << iter->ToString();
	}
}


// PriorityQueue<T>::PriorityItem methods

template <typename T>
string PriorityQueue<T>::PriorityItem::ToString() const
{
	stringstream stm;
	stm << item << " " << priority <<endl;
	return stm.str();
}

template <typename T>
void PriorityQueue<T>::PriorityItem::DisplayPriorityItem() const
{
	cout << ToString();
}

template <typename T>
int PriorityQueue<T>::PriorityItem::GetPriority() const
{
	return priority;
}

template <typename T>
bool PriorityQueue<T>::PriorityItem::operator<(const PriorityItem& other_) const
{
	return this->GetPriority() < other_.GetPriority();
}