Member Avatar for katzumi_r

hi, im new in programming and C++ and i have a homework and i need a little help on how to do it will u please just tell give me some suggestions on what i should do and ill try to do it myself

This is what i have to do
In this assignment you are to implement a priority queue using a dynamic array as its implementation. The class specification file, priorityQueue.h, is given and should be used as your guideline. You must add the implementation file, priorityQueue.cpp, and create the driver file p06.cpp.

Program Requirements
§ Implement the class methods.
§ Check if memory allocation was successful each time you allocate, but do not handle the case when allocation fails.
§ Be aware of memory leaks.


and i have a header file given and i am supposed to implement the classes and create the driver file

i have attached the files
priorityQueue.h - the header file given
p06.doc - the question
priorityQueue.cpp - my incomplete code for the implementation file

will some one please help me or tell me what to do in the next 12-13 hours so i can do that and get the program done by the due time tomorrow.

Thanks
:cheesy:

p06.doc (43.5 KB) 
#include "priorityQueue.h"
#include <iostream>
#include <string>

using namespace std;

namespace P06{
	//-----------------------------------------------------------------------
	// Class : ScheduleQueue
	//-----------------------------------------------------------------------

	//-----------------------------------------------------------------------
	// Inner Class : AthleteHeat
	//-----------------------------------------------------------------------

	ScheduleQueue::AthleteHeat::AthleteHeat(const string athlete, 
		const int number, const double time){
			// sets object to ("unassigned", 0, 0.0)

			
			
	}

	string ScheduleQueue::AthleteHeat::GetAthleteName() const{
		// returns the athlete name
		return(athleteName);
	}

	int ScheduleQueue::AthleteHeat::GetHeatNumber() const{
		// returns the heat number
		return(heatNumber);

	}

	double ScheduleQueue::AthleteHeat::GetHeatTime() const{
		// returns the head time 
		return(heatTime);
	}

	
	istream& operator >>(istream& inStream, AthleteHeat& heat){
	
	}

	ostream& operator <<(ostream& outStream, const AthleteHeat& Heat){

	}

	//--------------------------------------------------------------------------
	// end of inner class AthleticHeat
	//--------------------------------------------------------------------------

	int ScheduleQueue::NextItemIndex() const{
		// returns the index of the item with the next lowest time, -1 if 
		// there are no more items

		int minIndex = 0;

		for(int i = 0; i <= lastIndex; i; i++){
			if(*items[i] < *items[minIndex]){
				minIndex = i;
			}
		}
		return(minIndex);
	}

	ScheduleQueue::ScheduleQueue(){
		// sets items to NULL and lastIndex to -1
		items = NULL;	
		lastIndex = -1;

	}

	ScheduleQueue::ScheduleQueue(const ScheduleQueue& copy){
		// creates a copy of the parameter queue if not empty

	}

	ScheduleQueue::~ScheduleQueue(){
		// destroys the queue
		delete [] items;
	}

	bool ScheduleQueue::Add(const QueueItemType& item){
		// Increments array by 1 and adds the item to the end 
		// of the queue if possible.  Returns false if not added,
		// true if item was added succesfully

		success = false;

		lastIndex++;
		items = new int[lastIndex+1];
		
		items[lastIndex+1] = item;

		return(success);
	}

	QueueItemType ScheduleQueue::RemoveNext(){
		// removes the item with the next lowest time if present.  
		// If queue is empty it returns an empty item ("empty",0,0.0)

	}

	QueueItemType ScheduleQueue::NextItem() const{
		// returns the item with the next lowest time if present.  
		// If there are no more items it returns an empty item ("empty",0,0.0)

	}

	int ScheduleQueue::Count() const{
		// returns the number of items in the queue

	}

	ScheduleQueue operator =(const ScheduleQueue& rhs){
		// assigns the parameter queue to the current queue, by deep copying it
	
	}
	
}
#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
#include <string>
using namespace std;


//---------------------------------------------------------------------------------------------------------
// Class: ScheduleQueue
//---------------------------------------------------------------------------------------------------------
class ScheduleQueue {
public:
	//---------------------------------------------------------------------------------------------------------
	// Inner Class: AthleteHeat
	//---------------------------------------------------------------------------------------------------------
	class AthleteHeat {
		//friend class ScheduleQueue;
	private:
		friend istream& operator >>(istream& inStream, AthleteHeat& heat);
		friend ostream& operator <<(ostream& outStream, const AthleteHeat& Heat);

		string athleteName;
		int heatNumber;
		double heatTime;

	public:
		AthleteHeat(const string athlete = "unassigned", const int number = 0, const double time = 0.0);
			// sets object to ("unassigned", 0, 0.0)
		string GetAthleteName() const;
			// returns the athlete name
		int GetHeatNumber() const;
			// returns the heat number
		double GetHeatTime() const;
			// returns the head time
	};

private:
	typedef AthleteHeat QueueItemType;
	typedef QueueItemType* QueuePtr;

	int NextItemIndex() const;
		// returns the index of the item with the next lowest time, -1 if there are no more items
	QueuePtr items;
	int lastIndex;				// index of last item in the queue

public:
	ScheduleQueue();
		// sets items to NULL and lastIndex to -1

	ScheduleQueue(const ScheduleQueue& copy);
		// creates a copy of the parameter queue if not empty

	~ScheduleQueue();
		// destroys the queue

	bool Add(const QueueItemType& item);
		// Increments array by 1 and adds the item to the end of the queue if possible.  Returns false if not added,
		// true if item was added succesfully

	QueueItemType RemoveNext();
		// removes the item with the next lowest time if present.  If queue is empty it returns
		// an empty item ("empty",0,0.0)

	QueueItemType NextItem() const;
		// returns the item with the next lowest time if present.  If there are no more items it returns
		// an empty item ("empty",0,0.0)

	int Count() const;
		// returns the number of items in the queue

	ScheduleQueue operator =(const ScheduleQueue& rhs);
		// assigns the parameter queue to the current queue, by deep copying it
};
#endif
  • 2 Contributors
  • 11 Replies
  • 150 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by vijayan121

Recommended Answers

All 11 Replies

Member Avatar for vijayan121

if performance is not of great concern, you could do one of the following:
a. when you add an item to the array,
1. add it as the last element.
2. compare it with the element just ahead of it; if it has a higher priority,
swap the two.
3. repeat step two till either i. you find that the element just ahead has
a higher priority or ii. you have reached the front of the array.
now to remove/return the item with the highest priority, you know
that it is at the front of the array.
b. when you add an element add it at the back, as the last item.
to find the element with the highest priority, do a linear search.
with either of these approaches, the time taken to start with an empty
priority queue, add N elements and then remove N elements would be
O(N*N) - ie quadratic time.

to get a more efficient implementation ( O( N*log(N) ) ), you would
need to use a heap data structure; i am certain, it would be there
in one of your your text books.

i would suggest that you start of by implementing a dynamically
resizeable array first. make sure that it is working. and then
implement the priority queue on top of it.

Member Avatar for katzumi_r

im sorry but, i dont really get u

Member Avatar for vijayan121

for suggestion a
let us say your queue (numbers are priorities, lower numbers indicate higher priority) looks like this:
2 5 8 11 16 23 32
and you want to add 14.
add it at the end to get 2 5 8 11 16 23 32 14
compare 14 with 32, priority is higher, so swap them to get 2 5 8 11 16 23 14 32
compare 14 with 23, priority is higher, so swap them to get 2 5 8 11 16 14 23 32
compare 14 with 16, priority is higher, so swap them to get 2 5 8 11 14 16 23 32
compare 14 with 11, priority is lower, so let things beso after add, you get a sequence sorted on priorities.
one with the highest priority is right in front.

Member Avatar for katzumi_r

hmm, do i have to swap them, im just supposed to find the index of the smallest time after the one im adding.

Member Avatar for katzumi_r

and the array is supposed to remain random i guess

Member Avatar for katzumi_r

will u please help me on what i should do in the ScheduleQueue(const ScheduleQueue& copy) thing, i dont really get what im supposed to copy and where

Member Avatar for katzumi_r

sorry about the last minute questions but ive been trying to do this program for the whole week and i have to submit it today and my friends are clueless about it too and i found out about this site yesterday night, wish i knew about it earlier.

Member Avatar for katzumi_r

this is how far ive gotten till now, some one please tell me what else i have to do and whats wrong there. there seems to be something wrong and i get a lot of errors and im not sure what else i have to do there either.

//   File: p06.cpp
//   Name: Resha Puri
//   Date: 03/29/06
// Course: CS 150 - Introduction to Computing II
//   Desc: the main file
//


#include "priorityQueue.h"
#include <iostream>
#include <string>
using namespace std;


void main(void) {
	char choice;
	ScheduleQueue queue;
	ScheduleQueue::AthleteHeat heat;
	
	
	do{
		cout << "Enter athlete's downhill heat info (heat#, last name, heat time[mm.ss]): ";
		cin >> heat;
		cout << "Enter choice (y/n)? ";
		cin >> choice;

	}while(choice = 'y' || choice == 'Y');

	cout << heat;


}
#include "priorityQueue.h"
#include <fstream>
#include <iostream>
#include<iomanip>
#include <cstdlib>

using namespace std;


	//-----------------------------------------------------------------------
	// Class : ScheduleQueue
	//-----------------------------------------------------------------------

	//-----------------------------------------------------------------------
	// Inner Class : AthleteHeat
	//-----------------------------------------------------------------------

	ScheduleQueue::AthleteHeat::AthleteHeat(const string athlete, 
		const int number, const double time){
			// sets object to ("unassigned", 0, 0.0)

			
			
	}

	string ScheduleQueue::AthleteHeat::GetAthleteName() const{
		// returns the athlete name
		return(athleteName);
	}

	int ScheduleQueue::AthleteHeat::GetHeatNumber() const{
		// returns the heat number
		return(heatNumber);

	}

	double ScheduleQueue::AthleteHeat::GetHeatTime() const{
		// returns the head time 
		return(heatTime);
	}

	
	istream& operator >>(istream& inStream, ScheduleQueue::AthleteHeat& heat){
		inStream >> heat.GetHeatNumber() >> heat.GetAthleteName()
			>> heat.GetHeatTime();
		return(inStream);
	
	}

	ostream& operator <<(ostream& outStream, const ScheduleQueue::AthleteHeat& Heat){
		
		outStream << "Heat number: " << Heat.GetHeatNumber()
				<< "Athlete: " << Heat.GetAthleteName()
				<< "Heat Time: " << Heat.GetHeatTime();
		return(outStream);
	}

	//--------------------------------------------------------------------------
	// end of inner class AthleticHeat
	//--------------------------------------------------------------------------

	int ScheduleQueue::NextItemIndex() const{
		// returns the index of the item with the next lowest time, -1 if 
		// there are no more items

		int minIndex = -1;

		for(int i = 0; i <= lastIndex; i; i++){
			if(items[i]->GetHeatTime() < items[minIndex]->GetHeatTime()){
				minIndex = i;
			}
		}
		return(minIndex);
	}

	ScheduleQueue::ScheduleQueue(){
		// sets items to NULL and lastIndex to -1
		items = NULL;	
		lastIndex = -1;

	}

	ScheduleQueue::ScheduleQueue(const ScheduleQueue& copy){
		// creates a copy of the parameter queue if not empty
		if(lastIndex > -1){
			items = copy;
		}

	}

	ScheduleQueue::~ScheduleQueue(){
		// destroys the queue
		delete [] items;
	}

	bool ScheduleQueue::Add(const QueueItemType& item){
		// Increments array by 1 and adds the item to the end 
		// of the queue if possible.  Returns false if not added,
		// true if item was added succesfully

		success = false;

		lastIndex++;
		items = new int[lastIndex+1];
		
		items[lastIndex+1] = item;

		return(success);
	}

	QueueItemType ScheduleQueue::RemoveNext(){
		// removes the item with the next lowest time if present.  
		// If queue is empty it returns an empty item ("empty",0,0.0)

	}

	QueueItemType ScheduleQueue::NextItem() const{
		// returns the item with the next lowest time if present.  
		// If there are no more items it returns an empty item ("empty",0,0.0)
		int i = NextItemIndex();


	}

	int ScheduleQueue::Count() const{
		// returns the number of items in the queue
		int count = 0;
		count++;
		return(count);

	}

	ScheduleQueue operator =(const ScheduleQueue& rhs){
		// assigns the parameter queue to the current queue, by deep copying it
	
	}
Member Avatar for vijayan121

please post
a. what are the errors you get
b. what do you think is wrong?

Member Avatar for katzumi_r

i did this,

int ScheduleQueue::NextItemIndex() const{
// returns the index of the item with the next lowest time, -1 if
// there are no more items

int minIndex = -1;

for(int i = 0; i <= lastIndex; i++){
if(items.GetHeatTime() < items[minIndex].GetHeatTime()){
minIndex = i;
}
}
return(minIndex);
}

there were no errors around that area so i think it works.

But i dont know what to do with the copy thing ,


ScheduleQueue::ScheduleQueue(const ScheduleQueue& copy){
        // creates a copy of the parameter queue if not empty
       

    }

and this,

ScheduleQueue operator =(const ScheduleQueue& rhs){
        // assigns the parameter queue to the current queue, by deep copying it
    
    }
Member Avatar for vijayan121

these two functions are the copy constructor and the overloaded assignment operator.
these would be explained in every C++ beginner's book, including your text book.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.