PriorityQueue enqueue and dequeue functions

[d3sousa92]

I have a trying to create a list of patients sorted by their priority of ailments that have been added by the user.

I have several header files with different functions to determine priority score, to initialize a patient linkedlist etc. I am having trouble with enqueueing(and sorting them in order from lowest to highest [left to right]) and dequeueing patients(basically removing the patient with the highest priority from the list).

Below you will find what I have so far. I have started the enqueueing function but not sure where to start with the dequeueing function. Also how I am to add patients and their corresponding ailments.

  class Ailment
{
protected:
	std::string name;
	int sev;
	int time;
	int cont;
public:
	Ailment() = default;
	Ailment(const std::string& name, const int sev, const int time, const int cont);

	bool operator==(const Ailment& rhs) const;

	std::string get_name() const;

	int get_severity() const;

	int get_time_sensitivity() const;

	int get_contagiousness() const;
};

#include "Ailment.h"
#include "LinkedList.h"
#include <string>
#include <iostream>

class Patient
{
	std::string name_;
	LinkedList<Ailment> ailments_;

public:

	Patient(std::string name) : name_(std::move(name)) {}

	std::string get_name() const;

	void add_ailment(const Ailment& ailment);

	LinkedList<Ailment>& get_ailments();

	int get_score() const;

};

template <typename T>
class LinkedList
{
public:
	struct Node
	{
		Node* previous;
		Node* next;

		T data;
	};

protected:
	Node* begin_;
	Node* end_;

public:
	LinkedList() : begin_(nullptr), end_(nullptr) {}
	~LinkedList()
	{
		Node* node = begin();
		while(node)
		{
			Node* next = node->next;
			delete node;
			node = next;
		}
	}

	Node* begin() { return begin_; }
	Node const* cbegin() const { return begin_; }
	Node* end() { return end_; }

	void push_front(const T& item)
	{
		Node* node_front = new Node();
		node_front->data = item;

		//check if there is a node to link in-front of
		if (begin_ != nullptr)
		{
			begin_->previous = node_front;
			node_front->next = begin_;
		}
		else
		{
			end_ = node_front;
		}

		begin_ = node_front;
	}

	void push_back(const T& item)
	{
		Node* node_back = new Node();
		node_back->data = item;

		if (begin_ == nullptr && end_ == nullptr)
		{
			begin_ = node_back;
			end_ = node_back;
			return;
		}

		node_back->previous = end_;
		end_->next = node_back;

		end_ = node_back;
	}

	T pop_front()
	{
		if (begin_ == nullptr)
		{
			//todo: throw
			throw "";
		}

		Node* node = begin_;
		const T value = node->data;
		begin_ = node->next;

		return value;
	}

	T pop_back()
	{
		if (end_ == nullptr)
		{
			//todo: throw
			throw "";
		}

		Node* node = end_;
		const T value = node->data;
		end_ = node->previous;

		return value;
	}

	bool empty() const
	{
		return begin_ == nullptr;
	}

	size_t size() const
	{
		size_t counter = 0;

		Node* node = begin_;
		while (node != nullptr)
		{
			++counter;
			node = node->next;
		}

		return counter;
	}
};

template <typename T>
class PriorityQueue
{
	LinkedList<T> patients_;


	typename LinkedList<T>::Node* ptr;

public:
	PriorityQueue(): ptr(nullptr)
	{
	}

	int size();
	bool empty();

	void enqueue(const T& item)
	{
		typename LinkedList<T>::Node* node = new typename LinkedList<T>::Node();
		node->data = item;

		if(patients_.empty())
		{
			
		}

		typename LinkedList<T>::Node* left_node = patients_.begin();
		while(left_node && item < left_node->data)
		{
			left_node = left_node->next;
		}

		typename LinkedList<T>::Node* right_node = left_node->next;
		if(right_node)
		{
			right_node->previous = node;
		}
	}

	void dequeue(const T& item)
	{
		typename LinkedList<T>::Node* node = new typename LinkedList<T>::Node();

	}
};

template <typename T>
int PriorityQueue<T>::size()
{
	int counter = 0;

	typename LinkedList<T>::Node* node = new typename LinkedList<T>::Node();
	node = patients_.begin_;
	while (node != nullptr)
	{
		++counter;
		node = node->next;
	}

	return counter;
}

template <typename T>
bool PriorityQueue<T>::empty()
{
	return patients_.begin_ == nullptr;
}

#include "Patient.h"
#include "PriorityQueue.h"

#include<iostream>
#include<string>

PriorityQueue<Patient> queue;


void flush_buffer()
{
	while (getchar() != '\n');
}

int main(int argc, char* argv[])
{
	int user_selection;
	std::string name;
	std::string ailment;
	int severity = 0;
	int time_criticality = 0;
	int contagiousness = 0;

	while (user_selection != 0)
	{
		std::cout << "\nPlease Make A Selection:" << std::endl;

		std::cout << "1 - Add Patient" << std::endl;
		std::cout << "2 - Process Next Patient In Queue" << std::endl;
		std::cout << "3 - Display Queue" << std::endl;
		std::cout << "4 - View Processed Patients History" << std::endl;
		std::cout << "5 - Load Queue" << std::endl;
		std::cout << "6 - Save Queue" << std::endl;
		std::cout << "0 - Exit" << std::endl;
		std::cout << "\nSelection: ";
		std::cin >> user_selection;

		flush_buffer();

		switch(user_selection)
		{
		case 1:
			std::cout << "Enter patient name: ";
			std::getline(std::cin, name);

			do
			{
				std::cout << "\tEnter ailment (leave blank when done): ";
				std::getline(std::cin, ailment);
				if (ailment.empty())
				{
					break;
				}

				std::cout << "\tEnter severity: ";
				std::cin >> severity;

				std::cout << "\tEnter time criticality: ";
				std::cin >> time_criticality;

				std::cout << "\tEnter contagiousness: ";
				std::cin >> contagiousness;

				flush_buffer();


			} while (!ailment.empty());

			break;

		case 2:
			std::cout << " moved to patient room!" << std::endl;
			// Process patient with highest priority
			break;

		case 3:
			std::cout << "Patients In Queue:" << std::endl;
			// Display patient queue
			break;

		case 4:
			std::cout << "History:" << std::endl;
			// Display history of processed patients
			break;
	
		case 5:
			std::cout << "Enter path to file: ";
			// Load a .csv file
			break;

		case 6:
			std::cout << "Enter path to file: ";
			// Save to .csv file
			break;

		default: 
			std::cout<<"Invalid input. Please choose from the list provided.";
			break;
		}
	}
}

[jonnin]

you use the push and pop methods. your object that the queue is made of should support a simple comparison function that orders the queue by that value or multiple values (eg this one, if equal, use that one, if equal, third one,..etc) or whatever.

you will have to dig around for an example with the comparison function as most examples are going to be queues of basic integers that already have a valid compare.

this is one of the containers I don't like very much. It may be better to roll your own if its for a much larger program. For example a vector or map etc of normal queues would avoid all the sorting and internal fuss that the PQ does for you at the cost of a few extra min to mince it all together.

[d3sousa92]

Hi jonnin,

Thank you for your response. I am still very new to priority queues and linked lists. All these pointers and nodes really confuse me. Pretty overwhelming to be honest.

So, for example if I want to add a Patient that has more than one ailment how would add all those values to the same patient name?

Lets say Patient: John Doe has 2 ailments

Ailment 1: Heart Attack
Severity: 8
Time Criticality: 10
Contagiousness: 0

Ailment2: Stroke
Severity: 9
Time Criticality: 10
Contagiousness: 0

How would I add all of those values to John Doe?

Sorry for asking I am just so lost as to how.

[jonnin]

add them to that patient's linked list member, which is ailments_

so it looks like you have a PQ of patients (which is for some weird reason a global variable, it should be created in main and passed off as needed).
you create a patient, who has a bunch of ailments, so you fill all that out, then add it to the PQ, ideally. If you scramble up order of allowed operations, so the patient is added to the PQ and then gets an ailment and then later another one, like he had a heart attack and then a stroke an hour later... you have a lot more to deal with. In that case, you have to make it so that adding to the ailments triggers a new priority in the queue.

now we get into why I don't like the PQ. How can you get at patient #11 to add a new ailment? You cannot, directly! You can get to its underlying container with some ugly hand waving, but you are trying at that point to get into the middle of a container that wants you to deal with only the next up item, and on top of that, if you DO get into the container, you have to re-sort it after a modification to the element there. And, I am not sure that re-sorting it communicates to the queue to grab a new top element!

So this is where you decide what exactly you need to do with the program, whether now or later you will ever need to support changing ailments on a patient who has been queued. In a real hospital, in a real world, you WOULD for sure, as one problem leads to another when a person is hurt badly.

In my world, I would solve these problems by not using the darn PQ of patients in the first place. If they were just in a normal vector, you can sort them as needed and peel of the last element easily (vector even has, yep, a pop-back!) while accessing all the elements at any time ... etc. Vector may or may not be the best choice, but its one way. If you still want the PQ .. I don't know what the answer is if the data in the PQ changed to get a new top to register.

[seeplus]

C++ provides std::priority_queue
https://en.cppreference.com/w/cpp/container/priority_queue

By default, this is based upon a std::vector (although you also use std::deque)

Also note that another class can be derived from std::priority_queue as the underlying container is protected and so can be accessed from a derived class.

PS For your linked list, it might be a little easier if you maintained a count of nodes. Also in PriorityQueue, why not just use .size() of the underlying linked list rather than re-coding this?

The LinkedList should also provide a copy constructor and operator= (assignment) as the default ones are not suitable when using dynamic memory as a shallow copy is done rather than the required deep-copy. If you don't need/want then you can disable these easily by in the class:

LinkedList(const LinkedList&) = delete;
LinkedList& operator=(const LinkedList&) = delete;

[AbstractionAnon]

You have two elements in Ailments: sev for severity and time for time-critical.
It's not clear which of these (or both) your PriorityQueue is based on.
Your LinkedList doesn't take either of these into consideration when it's inserting an element. I suggest that you do as others have suggested and use a std::vector<Ailment>. This allows you to sort the vector on either severity or time-critical (or a combination of both).

When you think about it, a collection of Ailments should be an attribute of a Patient.

Line 170: What's the point of the trailing underscore on patients_? Trailing underscores are legal, while leading underscores are reserved for the compiler.
IMO, a trailing underscore should be avoided. You've already made the variable name plural which is a good indicator the the variable is a collection.

Lines 280-301: You ask for the patient info possibly multiple times, but never save the info.