#pragma once

template<typename T>
class CPriorItem
{
public:
	CPriorItem(T node, int nKey) : m_Node(node), m_nKey(nKey) {}
	CPriorItem() {}
	~CPriorItem() {}
	int GetKey() { return m_nKey; }
	T GetNode() { return m_Node; }
private:
public:
private:
	int m_nKey;
	T m_Node;
};

template<typename T>
class CPriorQueue : public CList<CPriorItem<T>, CPriorItem<T>>
{
public:
	CPriorQueue() {}
	~CPriorQueue() {}
	void Add(T node, int nKey);
	void AddFront(T node, int nKey);
private:
	void Insert(T node, int nKey, POSITION posStart, int nSize);
public:
private:
};

template<typename T>
void CPriorQueue<T>::Add(T node, int nKey)
{
	POSITION pos = GetHeadPosition();
	if(pos){
		Insert(node, nKey, pos, (int)GetSize());
	} else {
		AddFront(node,nKey);
	}
}

template<typename T>
void CPriorQueue<T>::AddFront(T node, int nKey)
{
	AddHead(CPriorItem<T>(node, nKey));
}

template<typename T>
void CPriorQueue<T>::Insert(T node, int nKey, POSITION posStart, int nSize)
{
	int nHalf = nSize/2;
	POSITION pos = posStart;
	if(nHalf > 0){
		for(int i=0; i<nHalf; i++){
			GetNext(pos);
		}
		if(nKey > this->GetAt(pos).GetKey()){
			Insert(node,nKey,pos,nSize-nHalf);
		}
		else{
			Insert(node,nKey,posStart,nHalf);
		}
	} else {
		if(nKey > this->GetAt(pos).GetKey()){
			InsertAfter(pos,CPriorItem<T>(node,nKey));
		}
		else{
			InsertBefore(pos,CPriorItem<T>(node,nKey));
		}
	}
}