// pqueue.cpp: implementation of the pqueue class.
//
//////////////////////////////////////////////////////////////////////

#include "pqueue.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

pqueue::pqueue(int sz)
{
	queue = new event[sz];
	last = 0; // element 0 is not used.
	size = sz;
}

pqueue::~pqueue()
{

}

void pqueue::insert(int time, agent * ag)
{
	int	hole = last + 1;
	while (queue[hole/2].time > time) {
		queue[hole] = queue[hole/2];
		hole /=2;
	};
	queue[hole] =  event(time, ag);
	last++;
//	cout << "insert done. last=" << last << endl;
}

event pqueue::deleteMin()
{
	int child;
	if (last == 0) return event(-1,0);
	event minEvent = queue[1];
	event lastEvent = queue[last];
	for (int i=1; i *2 <=  last; i = child) {
		child = i*2;
		if (child != last)
				if (queue[child+1].time < queue[child].time)
					child++;
		if (lastEvent.time > queue[child].time)
			queue[i] = queue[child];
		else
			break;
	};
	queue[i] = lastEvent;
	last --;
//	cout << "deleteMin time=" << minEvent.time << " agent=" << minEvent.ag << endl;
	return minEvent;
}