Question:
Discuss about the Programming Implementation.
Answer:
#ifndef _PR_QUEUE_H
#define _PR_QUEUE_H
/*
* Some headers that may be useful.
* The utility header is included for the
* std::pair<X,Y> class, used below.
*/
#include <vector>
#include <list>
#include <utility>
#include <iostream>
/*
* This class implements a priority queue ADT
* with priorities specified in ints.
* Lower priority values precede higher values in
* the ordering.
* The template type E is the element type.
* See the tests for examples.
*/
template <typename E>
class PriorityQueue {
/* data members here. */
private:
int queueSize; // stores the number of elements in a priority queue
std::vector<std::pair<int,E> > queue; // priority queue is stored in a vector container
public:
/* default constructor*/
PriorityQueue()
{
queueSize = 0; // initialize the queue to be empty
}
/*
* This function adds a new element “element” to the queue
* with priorioty “priority”.
*/
void insert(int priority, E element) {
typename std:: pair<int, E> newnode; // newnode is pair type of container that contains the element value and its priority
newnode.first = priority; // first value of pair is priority and second is element value
newnode.second = element;
if(priority < 0 ) return ; // negative priority element won’t be added into the queue.
else if(queue.empty()== true) // if queue is empty then first element is added.
{ queue.push_back(newnode);
}
else{ // if queue has some element already then insert the element accorging to the priority increment order.
typename std::vector< std::pair <int,E> >::iterator it; // iterator declaration
it = queue.begin(); //
if (priority < it->first) // if new element’s priority is smallest then insert it in front.
queue.insert(it,newnode);
else // else insert the bnewnode in between or at the end of queue according to priority order.
{
while ( (it!= queue.end() ) && it->first <= priority)
it++;
queue.insert(it,newnode);
}
}
queueSize = queue.size(); // after inserting the element update the size of queue
}
/*
* Similar to insert, but takes a whole vector of new things to
* add.
*/
void insert_all(std::vector<std::pair<int,E> > new_elements) {
typename std:: pair<int, E> newnode;
for(int i=0;i< new_elements.size();i++)
{
newnode.first = new_elements[i].first; // same logic implementation for the input vector as in insert() function.
newnode.second = new_elements[i].second;
if(new_elements[i].first< 0)
continue;
else if(queue.empty()== true)
queue.push_back(newnode);
else{
typename std::vector< std::pair <int,E> >::iterator it;
it = queue.begin();
if(newnode.first < it->first)
queue.insert(it,newnode);
else
{
while ( (it!= queue.end() ) && it->first <= newnode.first)
it++;
queue.insert(it,newnode);
}
}
}
queueSize = queue.size(); // update the size of the queue
}
/*
* Takes the lowest priority value element off the queue,
* and returns it.
*/
E remove_front() {
E element ;
if(queue.size()==0) // if queue is empty then no element can’t be removed so it returns nullptr.
return 0;
element = queue.begin()->second; // otherwise returns the element value and erases it from the queue
queue.erase(queue.begin());
queueSize = queue.size();
return element;
}
/*
* Returns the lowest priority value element in the queue, but leaves
* it in the queue.
*/
E peek() {
E element ;
element = queue.begin()->second;
return element;
}
/*
* Returns a vector containing all the elements in the queue.
*/
std::vector<E> get_all_elements() { // from queue it inserts the value of elements in a vector and return it
typename std::vector<E> elements;
for(int i=0;i<queue.size();i++)
{
elements.push_back(queue[i].second) ;
}
return elements;
}
/*
* Returns true if the queue contains element “element”, false
* otherwise.
*/
bool contains(E element){
if (queueSize==0) // if no element then return false
return false;
for(int i=0; i< queue.size(); i++)
{
if(queue[i].second == element)
return true;
}
return false;
}
/*
* Returns the priority of the element that matches
* “element”. If there is more than one, return it returns
* the lowest priority value.
* If no element matches, return -1.
*/
int get_priority(E element){
for(int i=0;i< queue.size();i++)
{
if(queue[i].second == element)
return queue[i].first ;
}
return -1;
}
/*
* Returns a vector containing all the priorities.
* The ordering of the vector should match that of the
* return from get_all_elements().
* That is, the priority of the element
* get_all_elements()[i] should be get_all_prriorities()[i].
*/
std::vector<int> get_all_priorities(){
std::vector<int> priorities;
for(int i=0;i< queue.size();i++) // priority is included in the first data member of a pair struct based node element
{
priorities.push_back(queue[i].first);
}
return priorities;
}
/*
* Finds the first (in priority order) element that matches
* “element”, and changes its priority to “new_priority”.
*/
void change_priority(E element, int new_priority) {
if(queue.size()==0) // checks whether queue is empty. if, do nothing
return ;
else { int found =0; // found keeps the track whether element is found or not.
for(int i=0;i< queue.size() && found==0;i++) // if found then create one node consisting element and new_priority value and insert
{ // it according to the priority order int the queue.
if(queue[i].second == element)
{ found =1;
typename std::pair<int,E> newnode;
newnode.first = new_priority;
newnode.second = element;
queue.erase(queue.begin()+i);
if(new_priority < 0 ) return ;
else if(queue.empty()== true)
queue.push_back(newnode);
else{
typename std::vector< std::pair <int,E> >::iterator it;
it = queue.begin();
if (new_priority < it->first)
{
queue.insert(it,newnode);
}
else
{
while ( (it!= queue.end() ) && it->first <= new_priority)
it++;
queue.insert(it,newnode);
}
}
queueSize = queue.size();
}
}
}
}
/*
* Returns the number of elements in the queue.
*/
int size() {
return queue.size(); // the size of the p_queue vector will be the size of priority queue.
}
/*
* Returns true if the queue has no elements, false otherwise.
*/
bool empty() {
if(queueSize==0)
return true;
else
return false;
}
};
#endif
Code explanation:
PriorityQueue.h header file consists of priorityqueue implementation class. Which has element typename E. For data type of elements it has used template class.
The testing is done by other file named Assignment2Test.h which generates a Assignment2Test.cpp file after running the cxxtestgen command.
Data members: The class has 2 data member.
- queueSize: the number of the element in the queue at a point of time.
- Vector queue which consists the elements in a queue. The vector container is used rather than array for dynamic memory allocation. The vector stores an element in the form of a pair. An element has priority as int data type and the value of the element which can be of any type like int, float, string etc. So the typename is implemented using template class E.
Member Functions:
- PriorityQueue() : It is a default constructor. It initializes the size of the queue which is 0 initially.
- void insert(int priority, E element) : It declares one variable newnode which takes the value of element and priority. If the priority of the element is negative then this element is not added into the queue. If queue is empty then this newly formed element node is inserted into the queue. But if queue is not empty, priority of new element is compared to the priorities of the existing elements in the queue and if the new element’s priority is lesser than the priority of the existing element then it is inserted just before that element. The queueSize is updated then.
- void insert_all(std::vector<std::pair<int,E> > new_elements): It has the same logic as the insert() function has. But the logic is repeatedly applied for the vector of new_elements.
- E remove_front(): If queueSize is 0 then no element can be removed but if queue has even a single element then store the front element value in a variable, erase the front element from the queue , update the size of the queue and finally return the value of front element stored in the variable.
- E peek(): it will return the front element which is the lowest priority value.
- std::vector<E> get_all_elements(): It stores all the elements value in one vector and return the vector.
- Bool contains(E element): if queueSize is 0 then queue can’t contain the element so return false. Otherwise, it checks for the element value in the queue if value is found , returns true. If not found returns false.
- int get_priority(E element): If the element is in queue it return the priority of that particular element. If not present then returns -1.
- std::vector<int> get_all_priorities(): It stores the priority value of each element present in the queue into a vector and return the vector finally.
- void change_priority(E element, int new_priority): if queue is empty then it simply returns . We keep track of the element found or not by using variable found. Then we check for the element in the queue and if it is found then we create a newnode which has the value element and new_priority is priority. Then we erase the element which we found in the queue, from the queue and insert the newnode in the queue to maintain the correct priority order as it was done in insert() function. Thus the minheap implementation of the code remains correct. If element is not found then return simply from the queue.
- Int size(): it returns the size of the queue.
- Bool empty(): if there is no element in the queue , returns true otherwise false.
