Code States #3 - Linked Array Based Priority Queue Implementation

Priority Queue

They are the most important aspect, which must be known by any roboticist. Priority queue are used in path planning algorithms in general and shortes path algorithm like Dijkstra's algorithm. There are three types of Priority Queue implementation

1. Using Linked list 
2. Using Linked array representation
3. Priority matrix representation - Space taxing as a lot of elements might be empty

In the next set of Path planning algorithms, I will be making extensive use of Priority Queue. So that we all are on the same page, and you have the prerequisite, I am posting the code for Priority Queue implementation using Linked array representation. Please look into the theory of Priority Queue for implementation of (1) and (2)

DISCLAIMER - 

Though I have taken enough care that no bug is in introduced, I have written it in half an hour. Though I have checked the correctness on run-time, there might be some insidious bug. Please comment them on the blog, so that I can correct them and publish the revised version.

Cheers

Harshal

Edit - The codes below get creepy due to parsing issues that i am yet to figure out. Alternatively, you can fork me on github repository
harpribotics.blogspot
Do Fork me if you like it. :)

//// Array based Priority Queue implementation - Harshal Priyadarshi
#include
#include

using namespace std;
 
void assignRandomLinks(int* link,int* info, int* prn, int & avail, int & start, int size){
 avail = 0;                              //means that avail points to the very first array location
 start = size + 1;                       // means that start does not point anywhere
 
 for(int i = 0; i< size; i++){
  *(link + i) = i+1;
  *(info + i) = 0;
  *(prn + i) = 0;
 }
}
// Note To the readers
// link = size + 1 -> start is not initialized
// link = size     -> that the end point of either the occupied or avail list has reached
void priorityInsert(int *info, int* prn, int* link, int & avail, int & start, int num, int numPr, int size)
{
 //**** search for the suitable place where prn is just greater than numPr. ****\\
 //**** insert the number before that array ****\\
 
 //// check if the queue is full 
 if(avail == size)                       // means that their is no available place
 {
  printf("No place left. Kindly delete some information\n");
  
 }
 else{
 
  //// check if this is the first number to be inserted
  if(start == size + 1) 
  {
   start = avail;
   avail = *(link + avail);
   *(link + start) = size; 
   *(info + start) = num;
   *(prn + start) = numPr;
   
  }
  
  else{
  
   int counter = start;            // initialize the counter to start
   int prevlink = start;
   
   //// run till the pointer is just greater than numPr or till endpoint is reached
   while(numPr >= *(prn + counter) && counter != size)
   {
    prevlink = counter;         // maintains info of before link
    counter = *(link + counter);// maintains info of after link       
   }
   //// this handles all cases 
   int temp2 = *(link + prevlink);
   *(link + prevlink) = avail;     // the before link points to the first available position
   *(info + avail) = num;          // the info of 1st available position is set to num
   *(prn + avail) = numPr;         // the prn of 1st available position is set to numPr
   int temp = *(link + avail);
   *(link + avail) = temp2;        // the avail array points to the after link
   avail = temp;                   // the avail pointer is set to next available location
  }
 }
}

void priorityDelete(int *info, int* prn, int* link, int & avail, int & start,int size )
{
 if(start == size + 1)                   //means that no element was inserted before
 {
  printf("There was no entry in the system. Please feed in values\n");
 }
 else{
  if(*(link + start) == size)         //if the deletion will lead to an empty queue
  {
   int temp = avail;               // the present avail pointer is stored
   avail = start;                  // the start pointer is recovered
   *(info + avail) = 0;            // the values for priority and info is initialized
   *(prn + avail) = 0;   
   *(link + avail) = temp;         // the avail -> next = previous avail
   start = size + 1;               // the start pointer points to some value not representative in the link . We chose (size + 1)
  }
  
  else{
   int temp = avail;               // the present avail pointer is stored
   avail = start;                  // the start pointer is recovered
   *(info + avail) = 0;            // the values for priority and info is initialized
   *(prn + avail) = 0;
   start = *(link + start);   
   *(link + avail) = temp;         // the avail -> next = previous avail
   
  }
 }
}

int main(){
 int size = 10;
 int info[size], prn[size], link[size];
 int * INFO = info;                      // pointer to info
 int * PRN = prn;                        // pointer to priority prn
 int * LINK = link;                      // pointer to link
 int  start;                             // start or head location 
 int  avail;                             // first place available location
 int num = 0;                            // number to insert
 int numPr = 0;                          // priority of number to be inserted
 int choice;                             // choice of deletion or insertion

 //// initialize links randomly and assign the suitable start and avail list
 assignRandomLinks(LINK,INFO,PRN ,avail, start, size);
 
 //// make your choice now
 printf("Press 1 for Priority insert and press 2 for Priority delete ");
 scanf("%d",& choice);
 
 while(num != 99)                        // insert 99 to end the loop
 {                       
  
  if(choice == 1)                     // priority insert
  {                                   
   printf("Insert the number \n");
   cin>>num;
   printf("Insert the priority of number %d \n",num);
   cin>>numPr;
   priorityInsert(INFO, PRN, LINK, avail, start, num, numPr,size);
  }
  
  if(choice == 2)                     // priority delete
  {
   priorityDelete(INFO, PRN, LINK, avail, start, size);
  }
  
  //// print the three arrays
  for(int i = 0; i< size; i++)
  {
   printf("%d %d %d\n",info[i],prn[i],link[i]); 
  }
  
 //// make the choice within the loop
 printf("Press 1 for Priority insert and press 2 for Priority delete ");
 scanf("%d",& choice);
 }
}