//***********************************************************************
#ifndef PRIQUEUE_H
#define PRIQUEUE_H
//***********************************************************************
#include "vertex.h"
//***********************************************************************
const int Q_Default_Size = 128;
//***********************************************************************
// Binary Heap class, makes a priority queue out of vertices and
// weighted edges, the weight being the key
class PriQueue
{
	private:
	   Vertex *head; 	// Pointer to array of vertices
	   int size; 		// Number of vertex's in allocated array
	   int max_size;	// Max number of vertices
	   int *mapper;		// Maps the index to the actual vertex ID

	   void Percolate_Up(int index);
	   void Percolate_Down(int index);
	   void Error(char *s);		// Error handling routine
	   int Is_Full( ) const    { return size == max_size; }
	   int Is_Empty( ) const    { return size == 0; }

	public:
	   // Constructor
	   PriQueue(int number = Q_Default_Size);
	   // Destructor
	   ~PriQueue();

	   // Insert a vertex into heap	   
	   void Insert(Vertex& add); 

	   // Remove the vertex with the smallest weight
	   Vertex Delete_Min(); 

    	   // Decrease the weight of vertname to amt and reassign parent
	   int Decrease_Key(int vertname,int amt,int newparent);

	   // Heapify the queue
 	   void Build_Heap(); 

	   // return current number of vertices present in the queue
	   int getSize() {return size;}; 

	   // Get the name of the vertex at the i'th location of queue
	   int getName(int index) {return head[index].name;};

	   // Check whether vertname is already present in the queue
	   int IsThere(int vertname) 
	   	{return (head[mapper[vertname]].name == vertname);};

	   // Get the weight of vertex at i'th location of the queue
	   int getWeight(int index) {return head[index].distance;};

	   // Get the weight of vertname if it there in the queue
	   int getWeightName(int vertname)
	   	{return head[mapper[vertname]].distance;};
};
//***********************************************************************
#endif
//***********************************************************************