A few linked lists questions. Very confused...

[burzum619]

I guess the best way to start would be by providing the context of my program. I have already begun writing it, however, I'm very confused with a few things. Here is the full prompt given to my by my teacher:

In this assignment we are going to implement a task scheduler which assigns tasks to the computer’s CPU based on the priority of the task. Each task has a unique id and a priority tag associated with it. The scheduler has a buffer in which it stores the tasks in decreasing order of priority. Tasks are sent to the CPU (or removed from the buffer) in the order of their priority – i.e the task with the highest priority is sent to the CPU first. Note that the task with the highest priority is stored at the head of the buffer. When a new task arrives at the scheduler (with its id and priority tag), the scheduler inserts it into the appropriate location in the buffer. The task then waits its turn to be sent to the CPU.

In order to simulate this process, you will use a linked list which will act as the buffer. Every buffer has a finite capacity, hence we shall assume that the buffer cannot accommodate more than 15 tasks at any point in time. The minimum number of tasks can be zero. Think about the following design and implementation details:
1) How would you model a task with its id and priority tag?
2) How would the task insertion policy in the buffer be – how would you take care of tasks with similar priorities?
3) What is the task removal/deletion policy? Can deletions occur from any point in the buffer?

Here’s one idea to implement the scheduler. Create a class called “task” which has distinct fields like ID and PT(priority tag) and a pointer to the next task. Create another class called “Scheduler” which has a constructor, a destructor, a copy constructor, a display function, an insert and delete function and any other functions that you might think is appropriate to execute the task of the scheduler. The basic scheduler should comprise of a pointer to the first task, and a counter denoting the total number of tasks in the buffer. The MAX_TASK could be a global variable set to 15. However while putting a new task in the buffer you have to ensure that the buffer capacity is not exceeded.

Write a function that generates tasks. Begin by generating 10 tasks in the buffer. Anytime the buffer reaches its maximum capacity, have a warning message flash on screen – “BUFFER FULL”. If a new task arrives at the buffer when the buffer is full, discard the task and send an error message to the screen saying “Task Discraded. Buffer full”.

In addition have two functions : (1)one that overloads the “cout” operator so that you can print a buffer B1 by using a statement like cout<<B1 which will print out the contents of the buffer in the following manner: 231(6) 572(6) 453(3) 234(2) where the first number is the task ID and the number within the parenthesis is the priority of the task. Note that priority 6 is considered to have higher priority than a task having priority 3. Also note that the task ID has to be a unique ID – so think carefully while assigning it (NO duplicates allowed there).

Things I'm confused about:

1. How would I go about assigning a different ID to every element? Should I just use the rand function when inserting, and just do a check to make sure its not the same ID?
2. For my "first_task" value, what should I be returning? The Priority tag or the ID????
3. I have no idea how to implement the MAX_TASK stuff. Where would I do the check? Simply in my insert function?

Here's my current unfinished code. I have only started on the header and .cpp file for the class definitions, but here goes. I haven't done the insert or delete functions since I don't know how to organize it.

Scheduler.h

/*----scheduler.h-----------------------------------------------------

	This header file defines a Scheduler data type.
	Basic Operations include:
		constructor: Constructs a schedule
		empty: checks if there are no tasks scheduled
		display: Displays tasks in the schedule
		first: accesses first task
		copy constructor: copies the given schedule
		destructor: Deletes the schedule after execution of program
		insert: inserts a task into the schedule
		delete: deletes a task in the schedule
---------------------------------------------------------------------*/

#include <iostream>
using namespace std;

#ifndef SCHEDULER
#define SCHEDULER

typdef int Element

class Scheduler
{
public:
	//function members
	//constructor
	Scheduler();
	/*-------------------------------------------------------------------
	Constructs scheduler object. first_task initialized to a null pointer
	--------------------------------------------------------------------*/

	~Scheduler(); //Class Destructor
	/********Copy Constructor******/
	 Scheduler(const Schedule & origSched);

	 /******Assignment******/
	 const Schedule & operator=(const Scheduler & rightHandSide);

	 /******Empty Function****/
	 bool empty() const; //checks if stack is empty. Returns true/false.

	 /*******Insert Function*****/
	void insert(const Element &value);

	/********First Function*******/
	Element first() const;

	/********Delete Function********/
	void 

	/*********Display Function*****/
	void display(ostream &out) const;

private:
	int counter;
	class Task
	{
	public:
		Element ID;
		Element PT;
		Task *next;
		//Task constructor
		Task(Element ID_val, Element PT_val, Task *link = 0);
		: ID(ID_val), PT(PT_val), next(link)
		{}
	};

	typedef Task *TaskPointer;

	//Data Members
	TaskPointer first_task; //points to first task

};
//------ Prototype of output operator
ostream & operator<< (ostream & out, const Schedule & aSchedule);

#endif 

Scheduler.cpp

//------Scheduler.cpp-----------------------------
#include <iostream>
using namespace std;
#include "scheduler.h"

//-----Definition of Scheduler Constructor
Scheduler::Scheduler()
	: first_task(0)
{}

//------Definition of Scheduler copy constructor
Scheduler(const Schedule & origSched);
{
	first_task = 0;
	if(!origSched.empty()){
		//Copy first task
		first_task = new Scheduler::Task(origSched.first());

		// Sets points to run through linked list
		Scheduler::TaskPointer lastPtr = first_task,
								origPtr = origSched.first->next;

		while (origPtr != 0)
		{
			lastPtr->next = new Scheduler::Task(origPtr->PT);
			lastPtr = lastPtr->next;
			origPtr = origPtr->next;
		}
	}
}

//----Definition of Stack Destructor
Scheduler::~Scheduler()
{
	// Sets pointers to run through the scheduler
	Scheduler::TaskPointer currPtr = first_task
							nextPtr;
	while(currPtr != 0)
	{
		nextPtr = currPtr->next;
		delete currPtr;
		currPtr = nextPtr;
	}
}

//------Definition of assignment operator
const Scheduler &Scheduler::operator=(const Scheduler &rightHandSide)
{
	if (this != &rightHandSide) 	//Checks to make sure both sides are not the same
	{
		this -> ~Scheduler();     //Destroys current schedule
		if(rightHandSide.empty())
			first_task = 0;
		else
		{
			//Copy first task
			first_task = new Scheduler::Task(rightHandSide.first());

			//Set points to run through scheduler
			Scheduler::TaskPointer lastPtr = myTop
									rhsPtr = rightHandSide.first->next;

			while (rhsPtr != 0)
			{
				lastPtr->next = new Stack::Node(rhsPtr->PT);
				lastPtr = lastPtr->next;
				rhsPtr = rhsPtr->next;
			}
		}
	}
	return *this;
}


//------- Definition of output operator
ostream & operator<< (ostream & out, const Scheduler & aScheduler)
{
   aScheduler.display(out);
   return out;
}

//----Definition of empty()
bool Scheduler::empty() const
{
	return (first_task == 0);
}

//----Definition of dipsplay()
void Scheduler::display(ostream &out) const
{
	Scheduler::TaskPointer ptr;
	for (ptr = first_task; ptr != 0; ptr = ptr->next)
		out << ptr -> ID << "("<<ptr -> PT <<")"<<endl;
}

//----Definition of first()
Element Scheduler::first() const
{
	if(!empty())
		return(first_task ->PT);
	else
	{
		cerr <<"The Stack is empty"<<endl;
		Element *temp = new(Element);
		Element garbage = *temp;
		delete temp;
		return garbage;
	}
}

[sammy34]

Wow, I wish my assignment specs at Uni gave so many hints...you should be overjoyed :)!

A very detailed post, but you're asking a lot. I won't comment on everything, but I will address the 'things you're most confused about':

1. How would I go about assigning a different ID to every element? Should I just use the rand function when inserting, and just do a check to make sure its not the same ID?
(sammy) You could simply have an integer counter (initialised to one might be appropriate) in the scheduler class, which increments each time a task is added to the buffer. This counter would be DIFFERENT to the counter that records the number of tasks in the buffer.

2. For my "first_task" value, what should I be returning? The Priority tag or the ID????
(sammy) I would return a pointer to the task object, rather than an attribute of that task.

3. I have no idea how to implement the MAX_TASK stuff. Where would I do the check? Simply in my insert function?
(sammy) You have a counter that records the number of tasks currently in the buffer. In the insert function, simply check first that inserting another Task wouldn't exceed this limit.

One other quick comment for now: 'Task' should not be a nested class in my opinion. Let it stand on it's own proverbial feet. Perhaps others can correct me if I'm wrong, but I don't think tasks in the general sense have to be handled by a scheduler (e.g. a simple microcontroller might be capable of executing only one task, and hence doesn't use a scheduler).

[burzum619]

Shouldnt task be acting as a node in a way? I just got that impression from the prompt provided.

Yeah, I've got most of the right ideas, I'm just having a hard time implementing.

Thanks for the help! I hate asking for help in programming because I always feel like I'm asking people to do my work for me - not my intentions at all. But thanks for the help. I'm going to try to work on it a little bit more on my own and do some reading when I get some time tonight.

[sammy34]

"Shouldnt task be acting as a node in a way?" - I don't understand what you mean by this. What prompt?...Can you explain it another way?

A task is best represented as a class 'Task' (with the attributes mentioned) which can be instantiated many times to represent as many specific tasks as you want. From what you've done I think you know that already...

[burzum619]

Basically this assignment is testing our understanding of linked lists. In a linked list, there is a class within the stack(or list)'s which is the node, which links to other nodes which contain the data.

So, from what I understand from the information given by my prof, the task is similar to a node in a linked list that points to the next node (or task) on the list. The difference being that i actually have to figure out how to organize all those nodes in this case.

Sorry if it was a little confusing. But this is all from my current understanding. However, you probably have a lot of knowledge on the subject, so please tell me if I'm wrong.

and by prompt I meant the sheet that the teacher gave us describing the program.

[sammy34]

Ok now I understand what you mean by node, thanks :). The way I see it, your Scheduler object will keep an array (of constant size MAX_TASK). This is the data structure which stores your linked list.

Imagine that at a particular time you have three elements in your list. Each element will be an instance of Task.

First task pointer: element 1
list...
Element 1: ID = 5, PT = 6, Points to element 2
Element 2: ID = 3, PT = 4, Points to element 3
Element 3: ID = 4, PT = 4, null pointer (last element)

Note that both elements 2 and 3 both have the same priority, so they're ordered based on a 'first come first served' (I think this would be appropriate in your case) - that is, based on ID.

Now let's imagine someone calls insert on your scheduler object. Let's say this new task has a priority of 5. In the insert, you give it an ID and put the new task at element 4 in your array, update the count of tasks, and adjust the pointers (i.e. element 1 now needs to point to element 4, element 4 now needs to point to element 2).

If someone wants to then delete element 2, you have to shuffle your array down so that the gap is closed and update your pointers considering the loss of element 2. Of course you'd also need to update the count of tasks in this case...

I have to say that I'm no expert with linked lists. In fact, I had to look it up to refresh my memory, but I've enjoyed helping you. Take what I've said sceptically. Perhaps somebody else would be so kind as to comment on this problem...

[sammy34]

Hmmm...actually, looking at the example list I gave you above, I don't think that was well done. Judging by what I said, tasks with higher IDs would be stored at higher indexes in the array, so it should have been something more like this:

first task pointer: points to element 3
Element 1: ID = 3, PT = 4, Points to element 2
Element 2: ID = 4, PT = 4, null pointer (last element)
Element 3: ID = 5, PT = 6, Points to element 1

I think that's better...does that make sense to you?

[burzum619]

Here's a copy of what I sent my cousin's husband, who's going to try and help me with this:



I worked on the program a bit more tonight. Pretty much the only thing I haven't really completed in the program is the insert and delete functions. I'll include some attachments with my header file and definition file.

Here's a few insecurities with the program that I am having:
1. in my copy constructor - is this line correct?
lastPtr->next = new Scheduler::Task(origPtr->PT);

should it be pointing to PT?

2. With the afterme function, what I'm trying to do is return a pointer to point to the location where the new task should be inserted, but the problem is I haven't figured out how to correctly implement this. I'm assuming I need to have some sort of if statement or while loop that will cycle through each task, until it finds one who's nextlink is pointing to a value with a lower PT, and then the insert function should insert the new task wherever afterme is pointing to. I think my logic is okay, but I still haven't figured this one out, I'll try to work on it tomorrow.

3. I'm sort of concerned about my counter and whether i'm using the increment functions correctly.

//----Definition of incCounter()
void Scheduler::incCounter()
{
counter++;
}

//-----Definition of decCounter()
void Scheduler::decCounter()
{
counter--;
}

since counter is a private member, am I allowed to mess with it like this?

Also, I haven't implemented anything for ID yet, but what the plan is is to just start with 1 as the ID for the first task, and just increase it by 1 and set that ID to the task as I keep inserting tasks. It wouldn't be the same as counter because the ID wouldn't be decremented at any point, only assigned a new ID that is 1 greater than the last task that was created.

Another thing I'm not too sure about - with the way I'm writing this program so far, it seems as though I wouldn't be able to place a new task at the beginning of the list? Another little nuissance I probably have to take care of.

I originally told you it was a doubly linked list, but upon some consideration I decided it might be easier to keep it singly linked for now. Maybe if I get some of the other functionalities working, I can use some time and make it doubly linked.

Please let me know if you spot any inconsistencies or weird shit in my code. I'm pretty new to classes so I wouldn't be surprised if I did something incorrectly syntactically or logically.

I also haven't started the driver program to test out all the functions. I figure I'll wait till I have the scheduler atleast somewhat functional before I start testing it.

scheduler.h

/*----scheduler.h-----------------------------------------------------

	This header file defines a Scheduler data type.
	Basic Operations include:
		constructor: Constructs a schedule
		empty: checks if there are no tasks scheduled
		display: Displays tasks in the schedule
		first: accesses first task
		copy constructor: copies the given schedule
		destructor: Deletes the schedule after execution of program
		insert: inserts a task into the schedule
		delete: deletes a task in the schedule
---------------------------------------------------------------------*/

#include <iostream>
using namespace std;

#ifndef SCHEDULER
#define SCHEDULER

typdef int Element

class Scheduler
{
public:
	//function members
	//constructor
	Scheduler();
	/*-------------------------------------------------------------------
	Constructs scheduler object. first_task initialized to a null pointer
	--------------------------------------------------------------------*/

	~Scheduler(); //Class Destructor
	/********Copy Constructor******/
	 Scheduler(const Schedule & origSched);

	 /******Assignment******/
	 const Schedule & operator=(const Scheduler & rightHandSide);

	 /******Empty Function****/
	 bool empty() const; //checks if stack is empty. Returns true/false.

	 /*******Insert Function*****/
	void insert(Task afterme, const Element &value_ID, const Element &value_PT);

	/********First Function*******/
	Element first() const;

	/********Delete Function********/
	void 

	/*********Display Function*****/
	void display(ostream &out) const;

	/***********Accessor Function****/
	int getCounter() const;

	/***********Mutator Function*****/
	void incCounter(); //increments counter by 1 when adding a task
	void decCounter(); //decrements counter by 1 when removing a task

	
	TaskPointer afterme(TaskpPointer first_task, int target); //Will locate where to place new task based on PT




private:
	int counter = 0; // Counts the number of tasks in the Scheduler

	class Task
	{
	public:
			/**********Accessor Functions*****/
		int getID() const{
			return ID;}

		int getPT() const{
			return PT;}

		Task* getLink() const {
			return next;}

		//Task constructor
		Task(Element ID_val, Element PT_val, Task *nextLink = 0);
		: ID(ID_val), PT(PT_val), next(nextLink) 
		{}

		void setNextTask(Task *pointer){
			nextLink = pointer;
		}


		Element ID;
		Element PT;
		Task *next;
		Task *previous;
		
	};

	typedef Task *TaskPointer;
	
	//Data Members
	TaskPointer first_task; //points to first task

};
//------ Prototype of output operator
ostream & operator<< (ostream & out, const Schedule & aSchedule);

#endif 

scheduler.cpp

//------Scheduler.cpp-----------------------------
#include <iostream>
using namespace std;
#include "scheduler.h"
#define MAX_TASK 15

//-----Definition of Scheduler Constructor
Scheduler::Scheduler()
	: first_task(0)
{}

//------Definition of Scheduler copy constructor
Scheduler(const Schedule & origSched);
{
	first_task = 0;
	if(!origSched.empty()){
		//Copy first task
		first_task = new Scheduler::Task(origSched.first());

		// Sets points to run through linked list
		Scheduler::TaskPointer lastPtr = first_task,
								origPtr = origSched.first->next;

		while (origPtr != 0)
		{
			lastPtr->next = new Scheduler::Task(origPtr->PT);
			lastPtr = lastPtr->next;
			origPtr = origPtr->next;
		}
	}
}

//----Definition of Stack Destructor
Scheduler::~Scheduler()
{
	// Sets pointers to run through the scheduler
	Scheduler::TaskPointer currPtr = first_task
							nextPtr;
	while(currPtr != 0)
	{
		nextPtr = currPtr->next;
		delete currPtr;
		currPtr = nextPtr;
	}
}

//------- Definition of afterme function
TaskPointer afterme(TaskPointer first_task, target)
{
	
	TaskPointer here = first_task;
	if(here == NULL) //if empty list
	{
		return NULL;
	}
	else
	{
		while(here->getPT() != target && here->getLink() != NULL)
			here = here->getLink();
				
		if(here->getPT() == target)
			return here;
		else
			return NULL;
	}
}

//---------Definition of insert function
void insert(TaskPointer afterme, int thePT)
{
	if(counter == MAX_TASK)
		cerr >> "Cannot add another task. Maximum task limit reached."<<endl;
	else
	{
		afterme->setNextTask(new Task(thePT, afterme->getLink()))
	}
}



//------Definition of assignment operator
const Scheduler &Scheduler::operator=(const Scheduler &rightHandSide)
{
	if (this != &rightHandSide) 	//Checks to make sure both sides are not the same
	{
		this -> ~Scheduler();     //Destroys current schedule
		if(rightHandSide.empty())
			first_task = 0;
		else
		{
			//Copy first task
			first_task = new Scheduler::Task(rightHandSide.first());

			//Set points to run through scheduler
			Scheduler::TaskPointer lastPtr = myTop
									rhsPtr = rightHandSide.first->next;

			while (rhsPtr != 0)
			{
				lastPtr->next = new Stack::Node(rhsPtr->PT);
				lastPtr = lastPtr->next;
				rhsPtr = rhsPtr->next;
			}
		}
	}
	return *this;
}


//------- Definition of output operator
ostream & operator<< (ostream & out, const Scheduler & aScheduler)
{
   aScheduler.display(out);
   return out;
}
//----Definition of getCounter()
int Scheduler::getCounter() const
{
	return counter;
}

//----Definition of incCounter()
void Scheduler::incCounter()
{
	counter++;
}

//-----Definition of decCounter()
void Scheduler::decCounter()
{
	counter--;
}

//----Definition of empty()
bool Scheduler::empty() const
{
	return (first_task == 0);
}

//----Definition of display()
void Scheduler::display(ostream &out) const
{
	Scheduler::TaskPointer ptr;
	for (ptr = first_task; ptr != 0; ptr = ptr->next)
		out << ptr -> ID << "("<<ptr -> PT <<")"<<endl;
}


//----Definition of first()
Element Scheduler::first() const
{
	if(!empty())
		return(first_task ->PT);
	else
	{
		cerr <<"The Stack is empty"<<endl;
		Element *temp = new(Element);
		Element garbage = *temp;
		delete temp;
		return garbage;
	}
}