Jump to content


 


Register a free account to unlock additional features at BleepingComputer.com
Welcome to BleepingComputer, a free community where people like yourself come together to discuss and learn how to use their computers. Using the site is easy and fun. As a guest, you can browse and view the various discussions in the forums, but can not create a new topic or reply to an existing one unless you are logged in. Other benefits of registering an account are subscribing to topics and forums, creating a blog, and having no ads shown anywhere on the site.


Click here to Register a free account now! or read our Welcome Guide to learn how to use this site.

Photo

C++ Queues


  • Please log in to reply
4 replies to this topic

#1 Iscariot

Iscariot

  • Members
  • 49 posts
  • OFFLINE
  •  
  • Local time:07:55 AM

Posted 23 November 2008 - 01:32 AM

I have an assignment where I need to schedule operating rooms based on the priority of the operation using a .txt file with data.
I need to utilize previously written code to create the program.
The code is:
=========================================================

ReadPatients.cpp
#include "PriQueue.h"
#include <fstream>
using namespace std;

struct patientItem
{
	char patientID[6];
	char operationCode[4];
	char doctorID[3];
	int priority;
	int hours;
};

int main()
{
	patientItem newItem;
	ifstream infile;

	infile.open("./patients.txt");
	if (infile.fail())
	{
	  cerr << "\nError opening file";
	  return 1;
	}

	newItem.patientID[5] = '\0';
	newItem.operationCode[3] = '\0';
	newItem.doctorID[2] = '\0';

	while (! infile.eof())
	{
		infile >> newItem.patientID >> newItem.operationCode
				>> newItem.doctorID >> newItem.priority
				>> newItem.hours;
		infile.get();  // remove return
		cout << newItem.patientID << ' '
			 << newItem.operationCode << ' '
			 << newItem.doctorID << ' '
			 << newItem.priority << ' '
			 << newItem.hours << endl;
	}
	infile.close();
	system ("Pause");
	return 0;
}

=========================================================

PRIQUEUE.H
#ifndef PriQueue_h
#define PriQueue_h
#include <iostream>
#define MaxQueues 5
using namespace std;

//Definition of the node
template <class Type>
struct nodeType
{
	Type info;
	nodeType<Type> *link;
};


template <class Type>
class priorityQueueType
{
public:

	bool isEmptyQueue() const;
	  //Function to determine whether all the queues are empty. 
	  //Postcondition: Returns false if one queue is not empty,
	  //			   otherwise returns true.

	bool isEmptyQueue(int priority) const;
	   //Function to determine whether the specific queue is empty. 
	  //Postcondition: Returns true if the queue is empty,
	  //			   otherwise returns false.

	bool isFullQueue() const;
	  //Function to determine whether the queue is full. 
	  //Postcondition: Returns true if the queue is full,
	  //			   otherwise returns false.

	Type front(int) const;
	  //Function to return the first element of the priority queue.
	  //Precondition: The queue exists and is not empty.
	  //Postcondition: If the queue is empty, the program 
	  //			   terminates; otherwise, the first 
	  //			   element of the queue is returned. 

	Type back(int) const;
	  //Function to return the last element of the priority queue.
	  //Precondition: The queue exists and is not empty.
	  //Postcondition: If the queue is empty, the program 
	  //			   terminates; otherwise, the last 
	  //			   element of the queue is returned.

	void addQueue(const Type& queueElement, int);
	  //Function to add queueElement to the priority queue.
	  //Precondition: The queue exists and is not full.
	  //Postcondition: The queue is changed and queueElement
	  //			   is added to the queue.

	void deleteQueue(Type&);
	  //Function  to remove the first element of the priority queue.
	  //Precondition: The queue exists and is not empty.
	  //Postcondition: The queue is changed and the first 
	  //			   element is removed from the queue.

	void list() const;
	  //Function to list all queue items
	  
	void list(int) const;
	  //Function to list all items in one queue
	  
	priorityQueueType(); 
	  //Default constructor
	priorityQueueType(const priorityQueueType<Type>&);
	  //Copy constructor 

	~priorityQueueType(); 
	  //Destructor

private:
	nodeType<Type> *queueFront[MaxQueues]; //pointer to the front of 
								//the queue
	nodeType<Type> *queueRear[MaxQueues];  //pointer to the rear of 
								//the queue
};

	//Default constructor
template<class Type>
priorityQueueType<Type>::priorityQueueType() 
{
	for (int i=0; i < MaxQueues; ++i)
	  queueFront[i] = queueRear[i] = NULL;
} //end default constructor

template<class Type>
bool priorityQueueType<Type>::isEmptyQueue() const
{
	for (int i = 0; i < MaxQueues; i++)
	   if (queueFront[i] != NULL)
		   return false;
	return true;
} //end 

template <class Type>
bool priorityQueueType<Type>:: isEmptyQueue(int priority) const
{
	if (queueFront[priority-1] != NULL)
	   return false;
	else
	   return true;
}

template<class Type>
bool priorityQueueType<Type>::isFullQueue() const
{
	return false;
} //end isFullQueue


template <class Type>
void priorityQueueType<Type>::addQueue(const Type& newElement, int priority)
{
	if (priority < 1 || priority > MaxQueues)
		throw string("Priority out of range");

	nodeType<Type> *newNode;
	newNode = new nodeType<Type>;   //create the node

	if (newNode == NULL)
		throw string("No memory allocated");

	newNode->info = newElement; //store the info
	newNode->link = NULL;  //initialize the link field to NULL
 
	if (isEmptyQueue(priority))
	{
		queueFront[priority-1] = newNode;
		queueRear[priority-1] = newNode;
}
	else
	{
		queueRear[priority-1]->link = newNode;
		queueRear[priority-1] = queueRear[priority-1]->link;
	}   //These 2 statements are equivalent
}  //end addQueue

template <class Type>
Type priorityQueueType<Type>::front(int priority) const
{
	if (priority < 1 || priority > MaxQueues)
		throw string ("Priority out of range");
	if (queueFront[priority-1] == NULL)
		throw string ("Queue empty - no front");
	return queueFront[priority-1]->info; 
} //end front

template <class Type>
Type priorityQueueType<Type>::back(int priority) const
{
	 if (priority < 1 || priority > MaxQueues)
		throw string ("Priority out of range");
	 if (queueRear[priority-1] == NULL)
		throw string ("Queue empty - no rear");
	return queueRear[priority-1]->info; 
} //end back

template <class Type>
void priorityQueueType<Type>::deleteQueue(Type & item)
{
	nodeType<Type> *temp;
	bool found = false;
   
	for (int i=0; i<MaxQueues && !found; ++i)
	   if (!isEmptyQueue(i+1))
	   {
		   temp = queueFront[i];  //make temp point to the 
							//first node
		   item = temp->info;
		   queueFront[i] = queueFront[i]->link; //advance queueFront 
	   
		   delete temp;	//delete the first node

		   if (queueFront[i] == NULL) //if after deletion the 
								//queue is empty
			   queueRear[i] = NULL;   //set queueRear to NULL
			   
		   found = true;
	   }
	if (! found)
		throw string ("Cannot remove from an empty queue");
}//end deleteQueue


	//Destructor
template <class Type>
priorityQueueType<Type>::~priorityQueueType() 
{
	Type item;
	for (int i=1; i <=MaxQueues; ++ i)
		while (!isEmptyQueue(i))
		   deleteQueue(item);
} //end destructor

template <class Type>
void priorityQueueType<Type>:: list(int priority) const
{
	if (priority < 1 || priority > MaxQueues)
		throw string ("Priority out of range");

	if (isEmptyQueue(priority))
		throw string ("Queue empty");

	nodeType<Type> *current; //pointer to traverse the list 
	
	for (current = queueFront[priority-1]; current != NULL; current = current->link)
		cout << current->info << endl;
}

template <class Type>
void priorityQueueType<Type>:: list() const
{
	nodeType<Type> *current; //pointer to traverse the list
	for (int i = 0; i < MaxQueues; ++ i)
	{
	   cout << "\nPriority queue " << i+1 << endl;
	   for (current = queueFront[i]; current != NULL; current = current->link)
		 cout << current->info << endl;
	}
}

template<class Type>
priorityQueueType<Type>::priorityQueueType(
							const priorityQueueType<Type>& otherQueue) 
{
	nodeType<Type> *newNode; //pointer to create a node
	nodeType<Type> *current; //pointer to traverse the list

	for (int i=0; i< MaxQueues; ++ i)
	{
		if (otherQueue.queueFront[i] == NULL) //otherList is empty
		{
			queueFront[i] = NULL;
			queueRear[i] = NULL;
		}
		else
		{
			current = otherQueue.queueFront[i];	//current points to the 
											//list to be copied

			//copy the first node
			queueFront[i] = new nodeType<Type>;  //create the node
			queueFront[i]->info = current->info; //copy the info
			queueFront[i]->link = NULL;	//set the link field of 
									//the node to null
			queueRear[i] = queueFront[i];	 //make rear point to the 
									//front node
			current = current->link;	//make current point to the 
									//next node

			//copy the remaining list
			while (current != NULL)
			{
				newNode = new nodeType<Type>;   //create a node
				newNode->info = current->info;  //copy the info
				newNode->link = NULL;	   //set the link of 
										//newNode to null
				queueRear[i]->link = newNode;  //attach newNode after rear
				queueRear[i] = newNode;	//make rear point to
									//the actual rear node
				current = current->link;   //make current point to
										//the next node
			}//end while
		}//end else
	}// end for
}//end copy constructor

#endif

=========================================================

The .txt file:
02321 122 30 8 5
02322 122 20 1 5
14545 120 12 7 4
15923 120 15 4 3
16934 122 25 1 4
21143 100 10 5 3
39814 130 22 4 4
42101 135 40 5 6
43001 110 45 6 3
49202 110 52 9 2
Data is: Patient ID (5 characters), Operation code (3 characters), Doctor ID (2 characters), Operation Priority (integer 1-10 where 1 is the highest priority and 10 is the lowest priority), length of operation (integer hours) – includes setup and cleanup of operating room.

=========================================================
What I want to do is sort the information by the priority, so I should get something like:

16934 122 25 1 4
02322 122 20 1 5
15923 120 15 4 3
39814 130 22 4 4
21143 100 10 5 3
42101 135 40 5 6
43001 110 45 6 3
14545 120 12 7 4
02321 122 30 8 5
49202 110 52 9 2
=========================================================

Then it would add the items to the queue in the following order:
Queue 1: 16934 122 25 1 4
Queue 2: 02322 122 20 1 5
Queue 3: 15923 120 15 4 3

Remaining patients:
39814 130 22 4 4
21143 100 10 5 3
42101 135 40 5 6
43001 110 45 6 3
14545 120 12 7 4
02321 122 30 8 5
49202 110 52 9 2

After 3 hours, Queue 3 opens, so I can add the next patient (Time is 11 AM)
Queue 1: 16934 122 25 1 4 (1 remaining)
Queue 2: 02322 122 20 1 5 (2 remaining)
Queue 3: 39814 130 22 4 4

After 1 hour, Queue 1 opens, so I can add the next patient (Time is 12 PM)
Queue 1: 21143 100 10 5 3
Queue 2: 02322 122 20 1 5 (1 remaining)
Queue 3: 39814 130 22 4 4 (3 remaining)

Remaining patients:
42101 135 40 5 6
43001 110 45 6 3
14545 120 12 7 4
02321 122 30 8 5
49202 110 52 9 2

After 1 hour, Queue 2 opens, so I can add the next patient (Time is 1 PM)
The next priority patient needs 6 hours to operate, not enough time (4PM, 3 hours remain)
Need to goto another priority, adding patient 43001
Queue 1: 21143 100 10 5 3 (2 remaining)
Queue 2: 43001 110 45 6 3
Queue 3: 39814 130 22 4 4 (2 remaining)


After 2 hours, Queues 1 and 3 open, so I can add patients (Time is 3 PM)
No operations take only 1 hour, so the hospital closes.

Should tell me that the following patients couldn't be scheduled:

42101 135 40 5 6
14545 120 12 7 4
02321 122 30 8 5
49202 110 52 9 2

=========================================================

In short, what I want to do is sort the information in the text file by priority (4th item)
I then want to read the patients into the queues using the data
When an operation ends, I want to add the next patient
In case there is not enough time to schedule a patient, I want to take a lower priority patient who has short enough time to be operated on.

At the moment I just really need help on the sort and I should be able to finish from there.
Help appreciated.

BC AdBot (Login to Remove)

 


#2 groovicus

groovicus

  • Security Colleague
  • 9,963 posts
  • OFFLINE
  •  
  • Gender:Male
  • Location:Centerville, SD
  • Local time:06:55 AM

Posted 23 November 2008 - 09:37 AM

By any chance, have you been studying greedy algorithms? Something like Prim's perhaps?

#3 Iscariot

Iscariot
  • Topic Starter

  • Members
  • 49 posts
  • OFFLINE
  •  
  • Local time:07:55 AM

Posted 23 November 2008 - 06:07 PM

By any chance, have you been studying greedy algorithms? Something like Prim's perhaps?

I haven't heard either of those terms so I'm gonna say I haven't

#4 groovicus

groovicus

  • Security Colleague
  • 9,963 posts
  • OFFLINE
  •  
  • Gender:Male
  • Location:Centerville, SD
  • Local time:06:55 AM

Posted 23 November 2008 - 06:45 PM

It still isn't clear to me whether or not you are trying to find an optimal solution, or just any solution.

All you need to do is sort based on priority, and then time. Judging by the assignment, this must be for an algorithms class, so I don't want to help too much, but you can do it one of two ways. Sort by priority, then add as many to the queue as you have time for, or sort by time, then take them by priority. Have you been studying any algorithms at all? I would be quite surprised if you were just given a problem like this without some sort of an introduction. There are a few ways to tackle this problem, but I am only going to confuse you if I don't know where you are coming fom.

#5 Iscariot

Iscariot
  • Topic Starter

  • Members
  • 49 posts
  • OFFLINE
  •  
  • Local time:07:55 AM

Posted 23 November 2008 - 06:49 PM

We're currently studying queues. The assignment is to read the text file and add patients to 1 of 3 operating rooms based on priority. Example, a person with a priority of 1 would be scheduled before a person with a priority of 5. If the next person to be added to the queue has an operating time that would exceed the closing time (4PM), then I would search the list for the first lower priority that can be scheduled.
This is the actual problem definition:

Linked List Representation of Priority Queues with Dynamic Memory Allocation

Hospital has 3 operating rooms.
Read Patient file (“Patients.txt”):
Patient ID (5 characters), Operation code (3 characters, Doctor ID (2 characters), Operation Priority (integer 1-10 where 1 is the highest priority and 10 is the lowest priority), length of operation (integer hours) – includes setup and cleanup of operating room.

Schedule the three operating rooms from (8:00 AM to 4:00 PM) i.e. 8 hours

Rules:
1. Schedule the operating rooms based on the priority of the operation
2. Equal operation priorities are based on FIFO
3. An operation can not be scheduled if it can’t end by 4:00 PM
4. Keep all operating rooms as busy as possible (i.e. take a lower priority operation if there is no higher priority operation that could finish by 4:00 PM

Output:
1. The schedule for each operating room (include hour and all the information in the file)
2. List of Patients (all information in file) remaining in the queues who could not be scheduled for an operating room


Edited by Iscariot, 23 November 2008 - 06:49 PM.





0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users