//***********************************************************************
#include <iostream.h>
#include <limits.h>
#include "vertex.h"
#include "priqueue.h"
//***********************************************************************
PriQueue::PriQueue(int number) // Constructor
{
if (number > 0)
	{
	 max_size = number;
	 head = new Vertex[max_size+1];
	 mapper = new int[max_size+1];
	 if (!head || !mapper)
		Error("Out of space in PriQueue !!");
	 head[0].distance = INT_MAX;
	 for (int i=0;i<=max_size;i++) 
	 	mapper[i] = 0;
	}
size = 0;
}	
//***********************************************************************
PriQueue::~PriQueue() // Destructor
{
delete [] head;
delete [] mapper;
}
//***********************************************************************
void PriQueue::Insert(Vertex& add) // Inserts a new vertex in correct place
{
if (Is_Full())
	Error( "Insert(): Priority queue is full !!" );

int i = ++size;
while (i > 1 && head[i/2] > add)	// Search for correct place
	{
	 head[i] = head[i/2];
	 mapper[head[i/2].name] = i;
	 i /= 2;
	}
head[i] = add;
mapper[add.name] = i;	// Map vertex name to the actual local index used
}
//***********************************************************************
Vertex PriQueue::Delete_Min() 	// Returns a vertex with minimum weight
{
if (Is_Empty())
	Error("Delete_Min(): Priority queue is empty !!");

Vertex root = head[1];		// Saves root 	
mapper[head[1].name] = 0; 	// deleted vertex, hence maps to 0
head[1] = head[size];		// Sets last vertex in array as root 
mapper[head[size].name] = 1;
size--;				// and decreases size
Percolate_Down(1); 		// Re-heapifies
return root;			// Returns saved root
}
//***********************************************************************
// Decreases the weight at index in array to amt, and reassigns 
// parent to newparent.  Returns 1 if succesfull, 0 if not.
int PriQueue::Decrease_Key(int vertname,int amt,int newParent)
{
if (Is_Empty())
	 Error("Decrease_Key(): Priority queue is empty !!");

int index = mapper[vertname];		// maps vertex name to local index
head[index].setDistance(amt);
head[index].setParent(newParent);
Percolate_Up(index);			// Re-heapifies
return 1;
}
//***********************************************************************
void PriQueue::Build_Heap()	// Heapifies the queue
{
for (int i=size/2;i>0;i--)
	Percolate_Down(i);
}
//***********************************************************************
void PriQueue::Percolate_Up(int index) // Up-heapifies starting at index
{
int i=index,parent;

Vertex Child = head[i];
for (;i>=2;i=parent)
	{
	 parent = i/2;
	 if (head[parent] > Child)	// If parent is bigger than child
	 	{
		 head[i] = head[parent];	// Swap it
		 mapper[head[parent].name] = i;
		}
	 else
		break;
	}
head[i] = Child;
mapper[Child.name] = i;
}
//***********************************************************************
void PriQueue::Percolate_Down(int index) // Down-heapifies starting at index
{
int i=index,child;

Vertex Parent = head[i];
for (;i*2<=size;i=child)
	{
	 child = i*2;
	 if (child < size && head[child+1] < head[child]) 
	 	child++;
	 if (Parent > head[child])  // if Parent is bigger than smaller child
	 	{
	 	 head[i] = head[child];	// Swap it
		 mapper[head[child].name] = i;
		}
	 else
		break;
	}
head[i] = Parent;
mapper[Parent.name] = i;
}
//***********************************************************************
void PriQueue::Error(char *s) 	// Error handling routine
{
cerr << "Error: " << s << endl;
cerr << "Exiting......." << endl;
exit(-1);
}
//***********************************************************************