C++ Queues related Computer Science

profileshahanil436
Assignment11.zip
Home>Computer Science homework help>C++ Queues related Computer Science

Assignment 11/assg-11.cpp

Assignment 11/assg-11.cpp


#include   < cassert >
#include   < iostream >
#include   "Queue.hpp"
#include   "JobSimulator.hpp"

using   namespace  std ;


/** main 
 * The main entry point for this program.  Execution of this program
 * will begin with this main function.
 *
 *  @param  argc The command line argument count which is the number of
 *     command line arguments provided by user when they started
 *     the program.
 *  @param  argv The command line arguments, an array of character
 *     arrays.
 *
 *  @returns  An int value indicating program exit status.  Usually 0
 *     is returned to indicate normal exit and a non-zero value
 *     is returned to indicate an error condition.
 */
int  main ( int  argc ,   char **  argv )
{
   // -----------------------------------------------------------------------
  cout  <<   "--------------- testing basic Queue ----------------------------"   <<  endl ;
   LQueue < int >  aQueue ;

  aQueue . enqueue ( 5 );
  aQueue . enqueue ( 7 );
  aQueue . enqueue ( 9 );
  aQueue . enqueue ( 11 );
  cout  <<   "<LQueue> basic test of the base LQueue using linked list"   <<  endl ;
  cout  <<   "   "   <<  aQueue  <<  endl ;

   int  expectedInit1 [ 4 ]   =   { 5 ,   7 ,   9 ,   11 };
   AQueue < int >  expectedQueue1 ( expectedInit1 ,   4 );
  assert ( aQueue  ==  expectedQueue1 );
  cout  <<  endl ;


  
   // -----------------------------------------------------------------------
  cout  <<   "--------------- testing PriorityQueue<int> ----------------------"   <<  endl ;
   //PriorityQueue<int> priorityQueue;

  cout  <<   "<PriorityQueue<int> Test case 1 insertion into empty priority queue"   <<  endl ;
   //priorityQueue.enqueue(5);
   //cout << "   " << priorityQueue << endl << endl;
   //assert(priorityQueue.length() == 1);
   //assert(priorityQueue[0] == 5);
  
  cout  <<   "<PriorityQueue<int> Test case 2 new node is highest priority and needs to go on front"   <<  endl ;
   //priorityQueue.enqueue(10);
   //cout << "   " << priorityQueue << endl << endl;
   //assert(priorityQueue.length() == 2);
   //assert(priorityQueue[0] == 10);
  
  cout  <<   "<PriorityQueue<int> Test case new node is lowest priority and ends up on back "   <<  endl ;
   //priorityQueue.enqueue(2);
   //cout << "   " << priorityQueue << endl << endl;
   //assert(priorityQueue.length() == 3);
   //assert(priorityQueue[2] == 2);
  
  cout  <<   "<PriorityQueue<int> Test case new node is lowest priority and ends up on back "   <<  endl ;
   //priorityQueue.enqueue(1);
   //cout << "   " << priorityQueue << endl << endl;
   //assert(priorityQueue.length() == 4);
   //assert(priorityQueue[3] == 1);
  
  cout  <<   "<PriorityQueue<int> Test case 3 insertion in between "   <<  endl ;
   //priorityQueue.enqueue(3);
   //cout << "   " << priorityQueue << endl << endl;
   //assert(priorityQueue.length() == 5);
   //assert(priorityQueue[2] == 3);
  
  cout  <<   "<PriorityQueue<int> Test case 3 insertion of equal valued priority"   <<  endl
        <<   "   (can't see if correct or not with ints) "   <<  endl ;
   //priorityQueue.enqueue(2);
   //cout << "   " << priorityQueue << endl << endl;
   //assert(priorityQueue.length() == 6);
   //assert(priorityQueue[4] == 2);

  cout  <<  endl ;


  
  cout  <<   "--------------- testing PriorityQueue<Job> ----------------------"   <<  endl ;

   //PriorityQueue<Job> jobs;

  cout  <<   "<PriorityQueue<Job> Test case 1 insertion into empty priority queue"   <<  endl ;
   //jobs.enqueue(Job(5, 0, 0));
   //cout << "   " << jobs << endl << endl;
   //assert(jobs.length() == 1);
   //assert(jobs[0].getPriority() == 5);
    
  cout  <<   "<PriorityQueue<Job> Test case 2 new node is highest priority and needs to go on front"   <<  endl ;
   //jobs.enqueue(Job(10, 0, 0));
   //cout << "   " << jobs << endl << endl;
   //assert(jobs.length() == 2);
   //assert(jobs[0].getPriority() == 10);
  
  cout  <<   "<PriorityQueue<Job> Test case new node is lowest priority and ends up on back "   <<  endl ;
   //jobs.enqueue(Job(2, 0, 0));
   //cout << "   " << jobs << endl << endl;
   //assert(jobs.length() == 3);
   //assert(jobs[2].getPriority() == 2);
  
  cout  <<   "<PriorityQueue<Job> Test case new node is lowest priority and ends up on back "   <<  endl ;
   //jobs.enqueue(Job(1, 0, 0));
   //cout << "   " << jobs << endl << endl;
   //assert(jobs.length() == 4);
   //assert(jobs[3].getPriority() == 1);
  
  cout  <<   "<PriorityQueue<Job> Test case 3 insertion in between "   <<  endl ;
   //jobs.enqueue(Job(3, 0, 0));
   //cout << "   " << jobs << endl << endl;
   //assert(jobs.length() == 5);
   //assert(jobs[2].getPriority() == 3);
  
  cout  <<   "<PriorityQueue<Job> Test case 3 insertion of equal valued "   <<  endl ;
   //jobs.enqueue(Job(2, 0, 0));
   //cout << "   " << jobs << endl << endl;
   //assert(jobs.length() == 6);
   //assert(jobs[4].getPriority() == 2);
   // tests that the new item was inserted after the old item with same priority
   //assert(jobs[3].getPriority() == 2);
   //assert(jobs[3].getId() < jobs[4].getId());

  cout  <<  endl ;
  

  
  cout  <<   "----------- testing jobSchedulerSimulator() --------------------"
        <<  endl  <<  endl ;
   JobSchedulerSimulator  sim ;
  
   //srand(time(0));  // seed random number generator using current time
   LQueue < Job >  jobQueue ;
   int  seed  =   32 ;
  srand ( seed );
   //sim.runSimulation(jobQueue, "Normal (non-prioirity based) Queueing discipline");
  cout  <<  sim ;
  
  srand ( seed );
   //PriorityQueue<Job> jobPriorityQueue;
   //sim.runSimulation(jobPriorityQueue, "Priority Queueing discipline");
  cout  <<  sim ;
  
  
   // return 0 to indicate successful completion
   return   0 ;
}

Assignment 11/assg-11.pdf

Assg 11: Priority Queues and Queue Applications

COSC 2336 Spring 2019

March 13, 2019

Dates:

Due: Sunday March 31, by Midnight

Objectives

ˆ Extend queue ADT to add a priority queue type

ˆ Use queue ADT for a job scheduling simulation

ˆ Practice with manipulating linked list data structures

ˆ Practice with inheritance and class abstractions

ˆ Practice with operator overloading

ˆ Practice using queue data types for applications and simulations

ˆ Introduction to some concepts in scienti�c simulations an programming

Description

In this assignment, we will be building a simulation of a job scheduling and processing system. The purpose of the simulation is to be able to run simulations in order to compare their performance, when they use di�erent queuing disciplines in order to schedule and run jobs in the system as they arrive. We will only be building a simulator that will compare a basic queuing discipline (�rst-come-�rst-serve) with a priority queuing discipline. In the system being simulated, jobs will have a priority level assigned to them. It is more costly to keep high priority jobs waiting. Thus we will de�ne an execution cost of a job as

1

cost = priority× waitTime (1)

In this simulation, higher numbers will represent higher priority jobs. Thus in the formula to compute cost, if a high priority job ends up having a long wait time before it is executed and �nishes, then the cost will be high. This is not so much of an issue if a low priority task ends up waiting a long time, or if a high priority task is executed immediately without waiting.

In general, we want to run simulations of jobs arriving, and being man- aged, dispatched and run, using di�erent queuing disciplines. As already mentioned, we will only compare a basic �rst-come-�rst-serve queue with a priority queue, but the basic framework you will create and see in this assignment is useful for many kinds of simulation system problems.

In this assignment, you are going to be given quite a bit of starting code. We will be using the basic Queue data type that was developed in the videos for this weeks content about Queues ("Queue.hpp" and "Queue.cpp"). You will also be given �les called "JobSimulator.[hpp|cpp]" which contain de�- nitions already for a Job class, and for a JobSchedulerSimulator class. A Job class/object represents a single job being managed and run in a sim- ulation. The basic characteristics of a Job for our assignment is that it is created or arrives in a system at some startTime. The simulator will simu- late the creation/arrival of new jobs. New jobs are also randomly assigned a priority level and a serviceTime upon arrival (again by the simulator). The serviceTime is the amount of system time that the Job needs in or- der to complete its work, or in other words it is the amount of resources or time that the system will need to allocate to and be busy with in order to complete the work of the Job.

The JobSchedulerSimulator runs a simulation of jobs arriving, being put on a waiting jobQueue, and being dispatched and run when the system is ready to run the next Job. Di�erent types of queues will e�ect the perfor- mance of the system and how well it does in reducing the overall and average cost of running jobs on the system. The simulator will simulate time using discrete time steps, starting at time 1, 2, . . . up to the simulationTime that is speci�ed as one of the simulation parameters. Other parameters of a simulation, besides the type of queuing discipline to use, is the min and max priority range to randomly assign when new jobs arrive, and the min and max amount of serviceTime that newly created jobs will need from the system.

You basically have to perform two di�erent parts to complete the sim- ulator you have been given. You have to implement a PriorityQueue

2

class (derived from the given LQueue linked list based queue class), in or- der to have a PriorityQueue we can use for the simulator. And the main runSimulation()method has not been implemented in the JobSchedulerSimulator class, you will need to create it according to the description below.

For this assignment you need to perform the following tasks.

1. Create a PriorityQueue class and implement a new enqueue()method to implement a priority queuing discipline. For e�ciency, priority queues are often implemented using a heap, so that both insertion and removal of items can be done in O(log n) time. However, we are going to use a simple naive method and simply insert new items into a link list that we keep sorted by priority. Doing this means that the insertion (enqueue()) operation becomes O(log n), but since for a pri- ority queue we always want the next item with the highest priority for a dequeue(), dequeue() is still O(1) constant time, since we will keep items order by priority and the highest priority item in the queue should always be at the front of the list.

This may sound like a lot, but there is really not too much to do to get a basic priority queue working. You need to perform the following steps

(a) Create a new class called PriorityQueue that inherits (using pub- lic inheritance) and derives from the LQueue class. This class still needs to be a template class, as it needs to be able to handle queues of di�erent types of objects. I have set the member vari- ables of the LQueue class to be protected, which means that your PriorityQueue class methods will be able to access and refer to the queueFront and queueBack member variables. You should insert your class de�nition for your PriorityQueue at the end of the "Queue.hpp" �le.

The only method you need to implement/override is the enqueue() method. All other methods should work correctly using the LQueue() implementations you will inherit. But since you are overriding enqueue() you do need to put a new declaration for this function in your PriorityQueue class declaration, but this will be the only function or variable (re)de�ned in the PriorityQueue.

(b) Once you have the declaration working, you will need to create your implementation of the enqueue()method for the PriorityQueue. As we already mentioned, instead of always just inserting the new

3

item/node at the back of the queue, you instead need to some some extra work and insert the new node into the linked list at the proper position so that the link list is ordered by priority. You can assume that the objects inserted into a PriorityQueue are over- loaded so that boolean comparisons (like operator<, operator<=, operator>, etc.) are de�ned to order object by their priority. The Job class that you will be managing with your PriorityQueue has had this operators de�ned to order jobs by their priority level. The pseudo-code for the algorithm your enqueue() function needs to perform is as follow:

0. Create a new Node dynamically, and assign the

newItem as its item. You may need to set link

to NULL and don't forget to update the numitems

variable of the LQueue parent as well.

1. Case 1, if the queue is empty, then the new node

becomes both the queueFront and the queueBack.

You don't have to do anything else, because a

list of only 1 item is already sorted.

2. Case 2, if the priority of the newItem is bigger

than the priority of the queueFront, then simply

make the newNode the new queueFront (and don't

forget to link the newNode back to the old front

item).

3. Case 3, if the newNode priority is less than or

equal to the front node, then it is going to end

up somewhere in the middle (or end) of the

linked list. Here you need a loop to search for

the correct position. You need to keep following

links until the current node is greater or equal

in priority to the newNode, and the node it links

to is smaller priority.

a. Once you have found that position, you need

to link the newNode between the two nodes, in

the correct position to keep the list sorted.

4

b. You may or may not need to do something special

to detect if you are linking as the last node,

so it becomes the new queueBack. For the

priority queue, you don't need the queueBack

pointer anymore, since you aren't inserting on

the end, so you can safely ignore the queueBack

member variable for your priority queue. But

you do need to make sure if your newNode ends up

being the last node, that its link is properly

NULL terminated.

You should try and implement the cases in order, and uncomment out the individual tests of the PriorityQueue given one by one to test them.

(c) Once you have your PriorityQueue working, and it is passing all of the tests given for it, you should then try and implement the runSimulation() class method. This is a member of the JobSchedulerSimulator class. You need to add the function prototype for this function in the "JobSimulator.hpp" �le, and add the implementation of the function at the end of the "Job- Simulator.cpp" �le.

There are 2 examples of how this function should be called in the tests give to you. The runSimulation() method takes a Queue<Job>, a queue class derived from the Queue base class, that is parameterized to hold objects of type Job, as its �rst pa- rameter. The second parameter to the function is a simple string description of the simulation type/queue that will be run, for display purposes. You should assign the class member variable this value of the passed in description as one of the things you din in the runSimulation() method.

We already brie�y described the runSimulation() method. Here is the pseudo-code of what you need to implement in this method:

for time in range 1..simulanTime

do

// 1. process new job creation, use jobArrived()

// to check this

if job arrived

do

- generate a random priority

5

(using generateRandomPriority() )

- generate a random serviceTime

(generateRandomServiceTime() )

- create a new instance of a Job

- enqueue the job on the job queue

passed in to this function

done

// 2. dispatch jobs to run on system

if no job is running and job queue is not empty

do

- dequeue the next job from the job queue

- set remaining time for this job to its service time

done

// 3. If job is currently running, update remaining time

if job running

do

- decrement the jobs remaining time

// handle when job has finished here

if job is now finished

do

- update stats on number of jobs completed

- update totalWaitTime

- update totalCost

done

done

done

The order of execution of the 3 steps is important in the simula- tion. If no job is running at the start of the time step, it should be possible for a new job to enter at that time step, it be immedi- ately dispatched, and it executes for 1 simulated time step. Thus you have to check the arrival, dispatch and update in that order.

After you main loop simulating the system time steps, you may have to do some more things to calculate your �nal statistics, which is not shown. For example, when a job completes, you

6

should keep track of the number of jobs that have completed so far, and keep track of the total wait time and total cost. You need these sums so you can calculate the average wait time and the average cost after the simulation ends. These averages should be calculated only for the jobs that successfully completed be- fore the simulation ended. There is also a parameter named numJobsUnfinished in the simulator, which is the number of jobs still on the job queue when the simulation ends that you should �ll in as well.

In this assignment you will only be given 5 �les in total. The "assg- 11.cpp" �le contains tests of the PriorityQueue you are to create, and exam- ples of creating a JobSchedulerSimulator, and how your runSimulation() method should be called. In addition, as mentioned, there are the "Queue.[hpp|cpp]" �les, that you will modify to add the PriorityQueue class implementa- tion. And the �les "JobSimulator.[hpp|cpp]" contain both the Job class and the JobSchedulerSimulator class. You need to only add the single runSimulation() member method to the JobSchedulerSimulator class in these �les.

Here is an example of the output you should get if your code is passing all of the tests and is able to run the simulation. You may not get the exact same statistics for the runSimulation() output, as the simulation is generating random numbers, but you should see similar values.

--------------- testing basic Queue ----------------------------

<LQueue> basic test of the base LQueue using linked list

Front: 5 7 9 11 :Back

--------------- testing PriorityQueue<int> ----------------------

<PriorityQueue<int> Test case 1 insertion into empty priority queue

Front: 5 :Back

<PriorityQueue<int> Test case 2 new node is highest priority and

needs to go on front

Front: 10 5 :Back

<PriorityQueue<int> Test case new node is lowest priority and

7

ends up on back

Front: 10 5 2 :Back

<PriorityQueue<int> Test case new node is lowest priority and

ends up on back

Front: 10 5 2 1 :Back

<PriorityQueue<int> Test case 3 insertion in between

Front: 10 5 3 2 1 :Back

<PriorityQueue<int> Test case 3 insertion of equal valued priority

(can't see if correct or not with ints)

Front: 10 5 3 2 2 1 :Back

--------------- testing PriorityQueue<Job> ----------------------

<PriorityQueue<Job> Test case 1 insertion into empty priority queue

Front: [id: 1 priority: 5] :Back

<PriorityQueue<Job> Test case 2 new node is highest priority and

needs to go on front

Front: [id: 2 priority: 10] [id: 1 priority: 5] :Back

<PriorityQueue<Job> Test case new node is lowest priority and ends

up on back

Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 3 priority: 2] :Back

<PriorityQueue<Job> Test case new node is lowest priority and ends

up on back

Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 3 priority: 2]

[id: 4 priority: 1] :Back

8

<PriorityQueue<Job> Test case 3 insertion in between

Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 5 priority: 3]

[id: 3 priority: 2] [id: 4 priority: 1] :Back

<PriorityQueue<Job> Test case 3 insertion of equal valued

Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 5 priority: 3]

[id: 3 priority: 2] [id: 6 priority: 2] [id: 4 priority: 1] :Back

----------- testing jobSchedulerSimulator() --------------------

Job Scheduler Simulation Results

--------------------------------

Simulation Parameters

--------------------------

Description : Normal (non-prioirity based) Queueing discipline

Simulation Time : 10000

Job Arrival Probability : 0.1

Priority (min,max) : (1, 10)

Service Time (min,max) : (5, 15)

Simulation Results

--------------------------

Number of jobs started : 990

Number of jobs completed : 956

Number of jobs unfinished: 33

Total Wait Time : 165051

Total Cost : 906378

Average Wait Time : 172.6475

Average Cost : 948.0941

Job Scheduler Simulation Results

--------------------------------

Simulation Parameters

--------------------------

Description : Priority Queueing discipline

Simulation Time : 10000

9

Job Arrival Probability : 0.1

Priority (min,max) : (1, 10)

Service Time (min,max) : (5, 15)

Simulation Results

--------------------------

Number of jobs started : 990

Number of jobs completed : 956

Number of jobs unfinished: 34

Total Wait Time : 113251

Total Cost : 204155

Average Wait Time : 118.4634

Average Cost : 213.5513

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed "Queue.[hpp|cpp]" and "JobSim- ulator.[hpp|cpp]" source �les to the submission folder to complete this as- signment. You do not need to submit your "assg-11.cpp" �le with test. But please only submit the asked for source code �les, I do not need your build projects, executables, project �les, etc.

Requirements and Grading Rubrics

Program Execution, Output and Functional Requirements

1. Your program must compile, run and produce some sort of output to be graded. 0 if not satis�ed.

2. (50 pts.) PriorityQueue is implemented correctly.

ˆ Correctly derived class from LQueue base class.

ˆ Class is still a template class

ˆ Correctly specify prototype to override enqueue() method of base class.

ˆ enqueue() implementation works for the empty list case

ˆ enqueue() works to insert node at front when it is highest priority

ˆ enqueue() works to insert node in list in correct order by priority

10

ˆ enqueue() works when inserting node with lowest priority at back of list

3. (50 pts.) runSimulation() function is implemented correctly.

ˆ Correctly creating new jobs and assigning random priority and service time on Poisson random arrival.

ˆ Correctly dispatching jobs from queue when no job is running

ˆ Correctly simulating job running, keeping track of remaining

ˆ Correctly update statistics when jobs �nish.

ˆ All simulation steps and statistics look correctly calculated.

Program Style

Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.

1. Most importantly, make sure you �gure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from �les, and only 2 spaces used for indentation.

2. A function header must be present for member functions you de�ne. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.

3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.

4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is speci�c to a single operating system, such as the system("pause") which is Microsoft Windows speci�c.

11

Assignment 11/JobSimulator.cpp

Assignment 11/JobSimulator.cpp

/** 

 *  @description  Assignment 11 Priority queues and scheduling
 *   simulation of jobs with priorities.
 */
#include   < climits >
#include   < cmath >
#include   < iomanip >
#include   < iostream >
#include   < string >
#include   < sstream >
#include   "JobSimulator.hpp"
#include   "Queue.hpp"

using   namespace  std ;



//-------------------------------------------------------------------------
/**
 * A constant for the Job class, used to keep track of
 * and assign unique id's for each job created.
 */
int   Job :: nextListId  =   1 ;


/** Job default constructor
 * Default constructor for Job, needed because some Queue types
 * create an empty array of Job objects, so they need to get filled
 * with empty jobs.  We simply initialize everything to 0, as 
 * Job objects created this way, without a priority or service time,
 * can't be used as real jobs in a simulation.
 */
Job :: Job ()
{
   this -> id  =   0 ;
   this -> priority  =   0 ;
   this -> serviceTime  =   0 ;
   this -> startTime  =   0 ;
   this -> endTime  =   0 ;
}


/** Job constructor
 * The actual constructor that needs to be used for Jobs in a simulation.
 * The job is assigned a priority, serviceTime and we record the startTime
 * when the job arrived and began waiting on the system queue for processing.
 * 
 *  @param  priority Each job in our simulations has a priority level.  In this
 *   Job object and simulation, the higher the number, the higher the priority
 *   of the Job.
 *  @param  serviceTime This is the time that the job needs to run, once it is
 *   selected/scheduled by the system dispatcher to be executed.  This represents
 *   the time the system is busy processing this Job once it starts running.
 *  @param  startTime The system time at which this jobs was created.  Also will be
 *   the system time this job was added to a job queue in the system and began
 *   waiting to be executed.
 */
Job :: Job ( int  priority ,   int  serviceTime ,   int  startTime )
{
   this -> id  =  nextListId ++ ;
   this -> priority  =  priority ;
   this -> serviceTime  =  serviceTime ;
   this -> startTime  =  startTime ;
   this -> endTime  =  startTime ;
}


/** endTime setter
 * Setter method to set the endTime of this Job.  This is actually the endTime
 * of when the job stoped waiting and began executing (not the time when the job
 * was finished).  The endTime - startTime gives the total waitTime this job
 * spent waiting.
 *
 *  @param  endTime The time when job stoped waiting on a queue and began executing.
 */
void   Job :: setEndTime ( int  endTime )
{
   this -> endTime  =  endTime ;
}


/** id getter
 * Getter method to return this Job's id.  Used for display purposes.
 *
 *  @returns  int The unique id of this Job is returned.
 */
int   Job :: getId ()   const
{
   return  id ;
}


/** service time getter
 * Getter method to return this Job's service time.  Service time
 * is the amount of time this job needs from the system to complete
 * its task.
 *
 *  @returns  int The serviceTime for this Job is returned.
 */
int   Job :: getServiceTime ()   const
{
   return  serviceTime ;
}


/** priority getter
 * Getter method to return this Job's priority level.  Priority
 * is a measure of the job importance.  In this simulation, higher
 * priority means higher importance.
 *
 *  @returns  int The priority level for this Job is returned.
 */
int   Job :: getPriority ()   const
{
   return  priority ;
}


/** waitTime getter
 * Getter method to return this Job's waitTime.  Wait time is
 * the difference from the endTime when the job stoped waiting
 * (and began executing) and startTime when the job was created
 * and began waiting to get access to the system for execution.
 *
 *  @returns  int The wait time for this Job is returned.  Wait time
 *   is not valid until after the job as exited the wait queue, and
 *   its endTime has been set.
 */
int   Job :: getWaitTime ()   const
{
   return  endTime  -  startTime ;
}


/** cost getter
 * Getter method to return this Job's cost.  Cost is a measure of
 * used to evaluate how well a particular system performs in
 * processing jobs.  In this simulation, we want to minimize time
 * high priority jobs spend waiting, and maximize high priority
 * job throughput.  Thus cost is a combination of priority and how
 * long the job spent waiting to be processed.  Since higher numbers
 * are used to mean higher priorities, multiplying the wait time 
 * times the priority scales the cost so that high priority jobs
 * that have to wait for long periods have high costs.  In the
 * system, we want to minimize cost as a measure of performance.
 *
 *  @returns  int The cost for this Job is returned.  Cost is a measure
 *   of performance with regards to this parcitular jobs.  Cost is
 *   measured in this system as the job priority times the time the
 *   job was forced to wait before it could start executing.
 */
int   Job :: getCost ()   const
{
   return  priority  *  getWaitTime ();
}


/** overload boolean equal comparison
 * Overload boolean comparison between jobs.  The main purpose of
 * providing boolean comparisons between jobs in this simulation is
 * so that priority based schedulers can order the jobs based on
 * priority level, from lowest priority to highest priority.  Thus
 * for a Job, jobs are equal when they have equal priorities.
 *
 *  @param  rhs The Job object on the right hand side of the boolean
 *   comparison.
 *
 *  @returns  bool True if the two jobs have equal priority, false
 *   otherwise.
 */
bool   Job :: operator == ( const   Job &  rhs )   const
{
   return   this -> priority  ==  rhs . priority ;
}


/** overload boolean less than
 * Overload boolean less than comparison between jobs.  The main
 * purpose of providing boolean comparisons between jobs in this
 * simulation is so that priority based schedulers can order the jobs
 * based on priority level, from lowest priority to highest priority.
 * Thus for a Job, a job is less than another job if its priority
 * is smaller.
 *
 *  @param  rhs The Job object on the right hand side of the boolean
 *   comparison.
 *
 *  @returns  bool True if this job has lower priority than the rhs
 *   job, false otherwise.
 */
bool   Job :: operator < ( const   Job &  rhs )   const
{
   return   this -> priority  <  rhs . priority ;
}


/** overload boolean greater than
 * Overload boolean greater than comparison between jobs.  The main
 * purpose of providing boolean comparisons between jobs in this
 * simulation is so that priority based schedulers can order the jobs
 * based on priority level, from lowest priority to highest priority.
 * Thus for a Job, a job is greater than another job if its priority
 * is bigger.
 *
 *  @param  rhs The Job object on the right hand side of the boolean
 *   comparison.
 *
 *  @returns  bool True if this job has higher priority than the rhs
 *   job, false otherwise.
 */
bool   Job :: operator > ( const   Job &  rhs )   const
{
   return   this -> priority  >  rhs . priority ;
}


/** overload boolean <=
 * Overload boolean less than or equal comparison between jobs.  The
 * main purpose of providing boolean comparisons between jobs in this
 * simulation is so that priority based schedulers can order the jobs
 * based on priority level, from lowest priority to highest priority.
 * Thus for a Job, a job is less than or equal another job if its
 * priority is smaller or the same.
 *
 *  @param  rhs The Job object on the right hand side of the boolean
 *   comparison.
 *
 *  @returns  bool True if this job has lower or equal priority than the
 *   rhs job, false otherwise.
 */
bool   Job :: operator <= ( const   Job &  rhs )   const
{
   return   this -> priority  <=  rhs . priority ;
}


/** overload output stream operator 
 * Overload the output stream operator to provide a representation
 * of this Job suitable for display.  Mainly useful for displaying
 * queue contents and for debugging purposes.
 */
ostream &   operator << ( ostream &  out ,   const   Job &  aJob )
{
   // out << "[id: " << aJob.id
   //     << " priority: " << aJob.priority
   //     << " serviceTime: " << aJob.serviceTime
   //     << " startTime: " << aJob.startTime
   //     << " endTime: " << aJob.endTime
   //     << " waitTime: " << aJob.getWaitTime()
   //     << "]";
  out  <<   "[id: "   <<  aJob . id
       <<   " priority: "   <<  aJob . priority
       <<   "]" ;
   return  out ;
}



//-------------------------------------------------------------------------
/** random uniform
 * Return a random floating point value in the range of [0.0, 1.0] with
 * uniform probability of any value in the range being returned.
 * The algorithm is that rand() returns an int in range [0, RAND_MAX]
 * and doing floating point division on the random integer by 
 * RAND_MAX recasts the result into a floating point number in range
 * [0.0, 1.0].
 *
 *  @returns  double Returns a randomly generated double valued number
 *   with uniform probability in the range [0.0, 1.0]
 */
double   JobSchedulerSimulator :: randomUniform ()
{
   double  randValue  =   double ( rand ())   /   double ( RAND_MAX );
   return  randValue ;
}


/** random range
 * Generate a random ingeger number in the given range from [minValue to
 * maxValue].  We are given minValue and maxValue, a random integer is
 * generated (with uniform probability) that is between minValue and
 * maxValue (inclusive, so minValue or maxValue are valid results
 * that can be returned, or any integer in between).
 *
 *  @param  minValue The minimum value of the range of integers to generate.
 *  @param  maxValue The maximum of the range of integers to generate.
 *
 *  @returns  int Returns a random integer value in range [minValue,
 *   maxValue] inclusive of the end points.
 */
int   JobSchedulerSimulator :: randomRange ( int  minValue ,   int  maxValue )
{
   // the range is difference between desired max and min.  We need
   // this magnitude in order to correctly generate a random value in
   // the given range
   int  range  =  maxValue  -  minValue  +   1 ;

   // generate a random value in range 0 to range (inclusive)
   int  randValue  =  rand ()   %  range ;

   // shift the value so it is in range [minValue, maxValue]
  randValue  +=  minValue ;

   return  randValue ;
}


/** job arrived
 * Test if a job arrived.  We use a poisson distribution to generate
 * a boolean result of true, a new job arrived in this time period,
 * or false, a new job did not arrive.  A Poisson distribution is often
 * a good model of discrete arrivals of jobs or customers in a system.
 * See Malik Ch. 18, pg. 1233 for description of the poisson arrival
 * calculation here.
 *
 *  @param  none, but we use the class simulation parameter
 *   jobArrivalProbability to determine if a new job arrived
 *   using a Poisson distribution.  The jobArrivalProbability
 *   is the probability of an arrival during a time period (lambda).
 *
 *  @returns  bool True if a new job arrived according to random check,
 *   false otherwise. 
 */
bool   JobSchedulerSimulator :: jobArrived ()
{
   // if a random uniform value in range [0.0, 1.0] is greater than
   // e^(-arrivalProbability), then a job has arrived according to
   // the poisson distribution
   return  randomUniform ()   >  exp ( - jobArrivalProbability );
}


/** generate priority
 * Generate a random priority within the given range of the
 * simulation parameters [minPriority, maxPriority] inclusive.
 *
 *  @param  none, but minPriority and maxPriority simulation
 *   parameters are used in this function to randomly select
 *   a priority for a Job in the given range.
 *
 *  @returns  int A random priority in the range [minPriority, maxPriority]
 *   using the current settings of the simulation parameters.
 */
int   JobSchedulerSimulator :: generateRandomPriority ()
{
   return  randomRange ( minPriority ,  maxPriority );
}


/** generate service time
 * Generate a random job service time within the given range of the
 * simulation parameters [minServiceTime, maxServiceTime] inclusive.
 *
 *  @param  none, but minServiceTime and maxServiceTime simulation
 *   parameters are used in this function to randomly select a
 *   service time for a Job in the given range.
 *
 *  @returns  int A random serviceTime in the range [minServiceTime,
 *   maxServiceTime] using the current settings of the simulation
 *   parameters.
 */
int   JobSchedulerSimulator :: generateRandomServiceTime ()
{
   return  randomRange ( minServiceTime ,  maxServiceTime );
}


/** simulator constructor
 * Mostly just a constructor to allow all of the simulation parameters
 * to be set to initial values when a simulation is created.  All of these
 * simulation parameters have default values specified for a standard
 * job simulation.  All simulation result member values are initialized
 * to 0 or null values in preparation for a simulation run.
 */
JobSchedulerSimulator :: JobSchedulerSimulator ( int  simulationTime ,
                          double  jobArrivalProbability ,
                          int  minPriority ,
                          int  maxPriority ,
                          int  minServiceTime ,
                          int  maxServiceTime )
{
   // initialize/remember the simulation parameters
   this -> simulationTime  =  simulationTime ;
   this -> jobArrivalProbability  =  jobArrivalProbability ;
   this -> minPriority  =  minPriority ;
   this -> maxPriority  =  maxPriority ;
   this -> minServiceTime  =  minServiceTime ;
   this -> maxServiceTime =  maxServiceTime ;

   // initialize simulation results to 0, ready to be calculated
   this -> description  =   "" ;
   this -> numJobsStarted  =   0 ;
   this -> numJobsCompleted  =   0 ;
   this -> numJobsUnfinished  =   0 ;
   this -> totalWaitTime  =   0 ;
   this -> totalCost  =   0 ;
   this -> averageWaitTime  =   0.0 ;
   this -> averageCost  =   0.0 ;
}


/** summary results
 * Convenience methods for creating a string for display listing
 * all of the simulation parameters, and all of the simulation
 * results.  Mostly useful after a simulation has just completed,
 * to get a summary of the simulation results for the given
 * simulation parameters.
 *
 *  @returns  string This method constructs and returns a string
 *   with a summary of the current simulation parameter settings
 *   and a summary of the simulation results.
 */
string  JobSchedulerSimulator :: summaryResultString ()
{
  ostringstream out ;

  out  <<   "Job Scheduler Simulation Results"   <<  endl
       <<   "--------------------------------"   <<  endl
       <<   "Simulation Parameters"   <<  endl
       <<   "--------------------------"   <<  endl
       <<   "Description              : "   <<  description  <<  endl
       <<   "Simulation Time          : "   <<  simulationTime  <<  endl
       <<   "Job Arrival Probability  : "   <<  jobArrivalProbability  <<  endl
       <<   "Priority (min,max)       : ("   <<  minPriority  <<   ", "   <<  maxPriority  <<   ")"   <<  endl
       <<   "Service Time (min,max)   : ("   <<  minServiceTime  <<   ", "   <<  maxServiceTime  <<   ")"   <<  endl  <<  endl
       <<   "Simulation Results"   <<  endl
       <<   "--------------------------"   <<  endl
       <<   "Number of jobs started   : "   <<  numJobsStarted  <<  endl
       <<   "Number of jobs completed : "   <<  numJobsCompleted  <<  endl
       <<   "Number of jobs unfinished: "   <<  numJobsUnfinished  <<  endl
       <<   "Total Wait Time          : "   <<  totalWaitTime  <<  endl
       <<   "Total Cost               : "   <<  totalCost  <<  endl
       <<   "Average Wait Time        : "   <<  setprecision ( 4 )   <<  fixed  <<  averageWaitTime  <<  endl
       <<   "Average Cost             : "   <<  setprecision ( 4 )   <<  fixed  <<  averageCost  <<  endl
       <<  endl  <<  endl ;

     return  out . str ();
}


/** csv results
 * A method for outputing the simulation results as a string of
 * comma separated values (csv).  This method is useful for generating
 * data about large numbers of simulations for later analysis.
 *
 *  @returns  string This method constructs and returns a string
 *   of comma separated values (csv) of current simulation results,
 *   suitable for constructing a x.csv file for data analysis.
 */
string  JobSchedulerSimulator :: csvResultString ()
{
  ostringstream out ;
  out  <<  numJobsStarted  <<   ","
       <<  numJobsCompleted  <<   ","
       <<  numJobsUnfinished  <<   ","
       <<  totalWaitTime  <<   ","
       <<  totalCost  <<   ","
       <<  setprecision ( 4 )   <<  fixed  <<  averageWaitTime  <<   ","
       <<  setprecision ( 4 )   <<  fixed  <<  averageCost  <<  endl ;
   return  out . str ();
}


/** overload output stream operator
 * Overload the output stream operator for convenience so we can
 * output a simulation object directly to an output stream.
 *
 *  @param  out A reference to the output stream we are sending our
 *   output to.
 *  @param  sim The JobSchedulerSimulator object we are outputing 
 *   the values of.  This is a friend funciton of the class, so
 *   the object is given as second parameter of this binary operator.
 *
 *  @returns  ostream Returns the given output stream object, but after
 *   we have inserted the output representation of the sim into it.
 */
ostream &   operator << ( ostream &  out ,   JobSchedulerSimulator &  sim )
{
  out  <<  sim . summaryResultString ();
   return  out ;
}


// Assignment 11
// You need to add the implementation of your runSimulation()
// method, as described in the assignment, here.

Assignment 11/JobSimulator.hpp

/** * * @description Assignment 11 Priority queues and scheduling * simulation of jobs with priorities. */ #include "Queue.hpp" #ifndef JOBSIMULATOR_HPP #define JOBSIMULATOR_HPP /** Job class * Class for job scheduling simulation. A Job enters a system * at random intervals (determined by the JobSchedulerSimulator on * a random Poisson basis). A job has a priority level and a serviceTime * which is the amount of system time it needs in order to complete * it task. The main property to keep track of for jobs in a * simulation is how long they have to wait before they are selected * to be processed/run by the system. Jobs keep track of their cost, * which can be used to measure a particular system's performance * (lower costs mean the system performed well, higher costs mean the * system performed more poorly). For systems with priority based jobs, * the measure of the cost is determined of the function a job spent * waiting, and how high of a priority the job had. We use the * simple calculation of cost = priority * waitTime to calculate * the cost for a job once it completes. * * @var nextListId A static int variable, used to assign unique ids * when processes are created, for identification purposes. * @var id The actual unique id assigned to a job object. * @var priority This jobs priority level. Higher numbers mean higher * priority jobs in this simulation. * @var serviceTime The amount of system time this job needs in order to * complete its task. * @var startTime The time when the job was created. Also the time * when the job began waiting in a queue to be selected to run. * @var endTime The time when the job finished waiting (when it was * finally selected by the system to begin execution). The difference * between endTime - startTime determines the total waitTime for this * process (calculated by getWaitTime() accessor method). */ class Job { private: static int nextListId; int id; int priority; int serviceTime; int startTime; int endTime; public: Job(); Job(int priority, int serviceTime, int startTime); void setEndTime(int endTime); int getId() const; int getServiceTime() const; int getPriority() const; int getWaitTime() const; int getCost() const; bool operator==(const Job& rhs) const; bool operator<(const Job& rhs) const; bool operator>(const Job& rhs) const; bool operator<=(const Job& rhs) const; friend ostream& operator<<(ostream& out, const Job& aJob); }; /** JobSchedulerSimulator * This class organizes and executes simulations of job scheduling, using * different scheduling methods. The simulations are goverend by a number * of system parameters, that are specified when a simulation is created. * When a simulation is run, various data is gathered that describes the * results of the simulation. In general, the job scheduling being * simulated is simple. The system runs for discrete time steps (total * number of which is goverened by simulationTime parameter). At each step * we check for and simulate new job arrivals. When jobs arrive, they * are placed on a single job queue. We then check if the processor/executor * is busy or not, and if not and if the job queue has some jobs on it, we * simulate dispatching a job. Differences in how jobs are organized on * a queue, and their effects on system performance (as a function of * total or average cost) can be explored with this simulator. * * These are parameters of the simulation, they govern properties of * job arrivals and characteristics when a simulation is run: * * @var simulatTime The total number of time steps a simulation will * run. Time steps will run from 1..simulationTime number of * discrete steps. * @var jobArrivalProbability The Poisson probability that a job will * arrive any any given discrete time interval. This governs how * often new jobs arrive and are created in the simulation. * @var [minPriority, maxPriority] The range of Job priority levels * for jobs that arrive. This simulation generates priorities for * the jobs randomly with uniform probability within this range, and * assigns them to new jobs that arrive. * @var [minServiceTime, maxServiceTime] The range of Job serviceTimes * for jobs that arrive in the system simulation. Service times are how * long a job needs to execute, once it is selected to be processed. * Service times are generated with uniform probability in this * given range when new jobs arrive. * * These are resulting statistics of a simultion. While a simulation is * being run, data is gathered about various performance characteristics, like * wait times and costs. At the end of a simulation, these statistical results * are available for analysis of the system preformance. * * @var description A description of the dispatching/queueing method used. * @var numJobsStarted The new number of jobs that entered and were * started during the most recent simulation run. * @var numJobsCompleted The number of jobs that were successfully run during * a simulation. * @var numJobsUnfinished The number of jobs left in the waiting queues when * a simulation finished. * @var totalWaitTime The total amount of time spent waiting by jobs * that completed in the simulation. Mainly useful for calculating * the averageWaitTime. * @var totalCost The total cost of all jobs that completed in the simulation. * Also mainly useful for calculating averageCost statistic. * @var averageWaitTime The average waiting time for completed jobs of the * most recent simulation. * @var averageCost The average system cost for completed jobs of the most * recent simulation. */ struct JobSchedulerSimulator { private: // simulation parameters int simulationTime; double jobArrivalProbability; int minPriority; int maxPriority; int minServiceTime; int maxServiceTime; // simulation results string description; int numJobsStarted; int numJobsCompleted; int numJobsUnfinished; int totalWaitTime; int totalCost; double averageWaitTime; double averageCost; // private functions to support runSimulation(), mostly // for generating random times, priorities and poisson arrivals double randomUniform(); int randomRange(int minValue, int maxValue); bool jobArrived(); int generateRandomPriority(); int generateRandomServiceTime(); public: JobSchedulerSimulator(int simulationTime = 10000, double jobArrivalProbability = 0.1, int minPriority = 1, int maxPriority = 10, int minServiceTime = 5, int maxServiceTime = 15); string summaryResultString(); string csvResultString(); // Assignment 11 // You need to add a new method to the class definition of the // JobSchedulerSimulator named runSimulation() here. friend ostream& operator<<(ostream& out, JobSchedulerSimulator& sim); }; #endif

Assignment 11/Queue.cpp

Assignment 11/Queue.cpp

/**

 *  @description  A Queue ADT with two concrete impelementation
 *   examples: an array based queue implementaiton (AQueue), and
 *   a linked list based implementation (LQueue).
 */



//-------------------------------------------------------------------------
/** Queue equivalence
 * Compare two given queues to determine if they are equal or not.
 * stacks are equal if they are both of the same size, and each
 * corresponding item on each stack is equal at the same position on the
 * stack.  This function relies on overloaded operator[] to access
 * items on stack by index for the comparison.
 *
 *  @param  rhs The stack on the right hand side of the boolean comparison
 *   expression to compare this stack against to check for equivalence.
 *
 *  @returns  bool Returns true if the stacks are equal, and false otherwise.
 */
template   < class  T >
bool   Queue < T >:: operator == ( const   Queue &  rhs )   const
{
   // if number of items on the stacks don't match, then they can't
   // be equivalent
   if   ( this -> length ()   !=  rhs . length ())
   {
     return   false ;
   }

   // otherwise need to check each item individually
   for   ( int  index  =   0 ;  index  <   this -> length ();  index ++ )
   {
     if   (( * this )[ index ]   !=  rhs [ index ])
     {
       return   false ;
     }
   }

   // if we get to this point, all itmes checked were equivalent, so
   // we are done and the answer is yes the stacks are equal
   return   true ;
}


/** Queue output stream operator
 * Friend function for Queue ADT, overload output stream operator to allow
 * easy output of queue representation to an output stream.
 */
template   < typename  U >
ostream &   operator << ( ostream &  out ,   const   Queue < U >&  aQueue )
{
  out  <<  aQueue . tostring ();
   return  out ;
}



//-------------------------------------------------------------------------
/** queue (array) constructor
 * Constructor for queue.  Default to enough room for 100 items
 * NOTE: the front pointer points directly to the index of the front item, but
 * the backIndex pointer points to the index-1 of the item where next insertion
 * will happen.  
 * NOTE: we treat the items array as a circular buffer, so all increments of
 * indexes must be modulo current allocSize, to wrap backIndex around to beginning.
 *
 *  @param  initialAlloc Initial space to allocate for queue, defaults to
 *   100.
 */
template   < class  T >
AQueue < T >:: AQueue ( int  initialAlloc )
{
  allocSize  =  initialAlloc ;
  numitems  =   0 ;
  frontIndex  =   0 ;
  backIndex  =  allocSize  -   1 ;   // back points to (x-1) % allocSize index
  items  =   new  T [ allocSize ];
}


/** queue (array) constructor
 * Constructor for queue using an array initializer.
 * NOTE: the front pointer points directly to the index of the front item, but
 * the backIndex pointer points to the index-1 of the item where next insertion
 * will happen.  
 * NOTE: we treat the items array as a circular buffer, so all increments of
 * indexes must be modulo current allocSize, to wrap backIndex around to beginning.
 *
 *  @param  initialAlloc Initial space to allocate for queue, defaults to
 *   100.
 */
template   < class  T >
AQueue < T >:: AQueue ( int  initItems [],   int  numitems )
{
   this -> allocSize  =  numitems ;
   this -> numitems  =  numitems ;
  frontIndex  =   0 ;
  items  =   new  T [ allocSize ];

   // copy the initialize items into this queue
   for   ( int  index  =   0 ;  index  <  numitems ;  index ++ )
   {
    items [ index ]   =  initItems [ index ];
   }

   // set up the back index
  backIndex  =  numitems  -   1 ;
}


/** queue (array) destructor
 */
template   < class  T >
AQueue < T >::~ AQueue ()
{
   // free up currently allocated memory
   delete   []  items ;
}


/** queue (array) clear
 * Function to initialize the queue back to an empty state.
 * Postcondition: frontIndex = 0; backIndex = allocSize-1; numitems=0; isEmpty() == true
 */
template   < class  T >
void   AQueue < T >:: clear ()
{
  frontIndex  =   0 ;
  backIndex  =  allocSize  -   1 ;
  numitems  =   0 ;
}


/** queue (array) isEmpty
 * Determine whether queue is currently empty or not.
 *
 *  @returns  returns true if the queue is empty, otherwise
 *   returns false.
 */
template   < class  T >
bool   AQueue < T >:: isEmpty ()   const
{
   return  numitems  ==   0 ;
}


/** queue (array) isFull
 * Determine whether queue is currently full or not.
 *
 *  @returns  returns true if the queue is full, otherwise
 *   returns false.
 */
template   < class  T >
bool   AQueue < T >:: isFull ()   const
{
   return  numitems  ==  allocSize ;
}


/** queue (array) enqueue
 * Add newItem to the back of the queue.
 * Preconditon: The queue exists
 * Postcondition: The queue is changed and newItem is added to the back
 *   of the queue.
 *  @param  newItem The new item to add to the frontIndex of this queue.
 */
template   < class  T >
void   AQueue < T >:: enqueue ( const  T &  newItem )
{
   // if queue is full, grow it
   if   ( isFull ())
   {
     // double the current size
     int  newAllocSize  =   2   *  allocSize ;

     // alloc the new space
    T *  newItems  =   new  T [ newAllocSize ];

     // and copy the queue to the new storage space
     // since we are copying anyway, we shift the items from the old
     // frontIndex back to index 0
     int  oldIndex  =  frontIndex ;
     for   ( int  index  =   0 ;  index  <  numitems ;  index ++ )
     {
      newItems [ index ]   =  items [ oldIndex ];
      oldIndex  =   ( oldIndex  +   1 )   %  allocSize ;
     }
    frontIndex  =   0 ;
    backIndex  =  numitems - 1 ;

     // free up the old space, start using the new space
     delete   []  items ;
    items  =  newItems ;
    allocSize  =  newAllocSize ;
   }

   // add the item, and increment our top
  backIndex  =   ( backIndex  +   1 )   %  allocSize ;
  numitems ++ ;
  items [ backIndex ]   =  newItem ;
}


/** queue (array) front
 * Peek at and return the front element of the queue.
 * Preconditon: The queue exists and is not empty
 * Postcondition: If the queue is empty, we throw QueueEmpty 
 *   exception; otherwise, the front element of the queue is
 *   returned
 *  @returns  T The item of type T currently on the front of this
 *   queue.
 */
template   < class  T >
T  AQueue < T >:: front ()   const
{
   //assert(topIndex != 0);
   if   ( isEmpty ())
   {
     throw   EmptyQueueException ( "AQueue<T>::front()" );
   }
   else
   {
     return  items [ frontIndex ];
   }
}


/** queue (array) dequeue
 * Remove the front element from the queue.  Some ADT combine dequeue
 * and front.  We have two separate operations in this ADT.
 * Preconditon: The queue exists and is not empty.
 * Postcondition: If the queue is empty, we throw QueueEmpty
 *   exception; otherwise the front element of the queue is removed
 *   from the queue.
 */
template   < class  T >
void   AQueue < T >:: dequeue ()
{
   // assert(topIndex != 0);
   if   ( isEmpty ())
   {
     throw   EmptyQueueException ( "Aqueue<T>::dequeue()" );
   }
   else
   {
    numitems -- ;
    frontIndex  =   ( frontIndex  +   1 )   %  allocSize ;
   }
}


/** queue (array) length
 * Getter method to access the current queue length.
 *
 *  @returns  length Returns the current queue length.
 */
template   < class  T >
int   AQueue < T >:: length ()   const
{
   return  numitems ;
}


/** queue (array) tostring
 * Represent this queue as a string.
 *
 *  @returns  string Returns the contents of queue as a string.
 */
template   < class  T >
string  AQueue < T >:: tostring ()   const
{
  ostringstream out ;
  
  out  <<   "Front: " ;
   int  index  =  frontIndex ;
   while   ( index  !=   ( backIndex  +   1 )   %  allocSize )
   {
    out  <<  items [ index ]   <<   " " ;
    index ++ ;
   }
  out  <<   ":Back"   <<  endl ;
  
   return  out . str ();
}


/** Queue (array) indexing operator
 * Access internel elements of queue using indexing operator[].
 * This is not a normal queue operation, we use mainly for testing
 * so that we can compare if two queues are equal at each internal
 * element of the queue.  For this reason, this operator should 
 * probably be private to the Queue class.
 *
 *  @param  index The index of the item on the queue we want to access
 *   and return, where index 0 represents the front of the queue and
 *   index == numitems-1 is the back.
 * 
 *  @returns  T Returns the item at "index" on the queue.
 */
template   < class  T >
const  T &   AQueue < T >:: operator []( int  index )   const
{
   // bounds checking, we will throw our stack exception if fails
   if   ( index  <   0   ||  index  >=  numitems )
   {
     throw   InvalidIndexQueueException ( "AQueue<T>::operator[]" );
   }
   // otherwise we can directly access the asked for item from our items array
   // our memory buffer is being treated as a circular buffer, so we
   // have to calculated the indicated index by hand
   else
   {
     return  items [( frontIndex  +  index )   %  allocSize ];
   }
}



//-------------------------------------------------------------------------
/** queue (list) constructor
 * Constructor for linked list version of queue.
 * An empty queue is indicated by both front and back
 * pointers pointing to null.
 */
template   < class  T >
LQueue < T >:: LQueue ()
{
  queueFront  =  NULL ;
  queueBack  =  NULL ;
  numitems  =   0 ;
}


/** queue (list) destructor
 * Destructor for linked list version of queue.
 */
template   < class  T >
LQueue < T >::~ LQueue ()
{
  clear ();
}


/** queue (list) clear
 * This will empty out the queue.  This method frees up all of the
 * dynamically allocated memory being used by the queue linked list
 * nodes.
 */
template   < class  T >
void   LQueue < T >:: clear ()
{
   Node < T >*  temp ;

   // iterate through Nodes in queue, freeing them up
   // as we visit them
   while   ( queueFront  !=  NULL )
   {
    temp  =  queueFront ;
    queueFront  =  queueFront -> link ;

     // dellocate this Node memory
     delete  temp ;
   }

   // make sure all private members are cleard correctly
  queueBack  =  NULL ;
  numitems  =   0 ;
}


/** queue (list) isEmpty
 * Check if queue is empty or not.
 * 
 *  @returns  true if the queue is currently empty, or
 *   false otherwise.
 */
template   < class  T >
bool   LQueue < T >:: isEmpty ()   const
{
   return  queueFront  ==  NULL ;
   // return numitems == 0;
}


/** queue (list) enqueue
 * Add the indicated item onto the back of the queue.
 *
 *  @param  newItem The new item we will add to the back of
 *   this queue.
 */
template   < class  T >
void   LQueue < T >:: enqueue ( const  T &  newItem )
{
   // dynamically allocate space for the new Node to hold
   // this newItem
   Node < T >*  newNode  =   new   Node < T > ;

   // initialize the node
  newNode -> item  =  newItem ;
  newNode -> link  =  NULL ;

   // if the queue is empty, then this new node is the
   // front and back node
   if   ( queueFront  ==  NULL )
   {
    queueFront  =  newNode ;
   }
   // otherwise, it gets added onto the back
   else
   {
    queueBack -> link  =  newNode ;
   }

   // the new node added is now the new back of the queue
  queueBack  =  newNode ;
  numitems ++ ;
}


/** queue (list) front
 * Return the front item from the queue.
 *
 *  @returns  T Returns the item currently at the front of
 *   this queue.
 */
template   < class  T >
T  LQueue < T >:: front ()   const
{
   //assert(queueFront != NULL)
   if   ( isEmpty ())
   {
     throw   EmptyQueueException ( "LQueue<T>::front()" );
   }
   else
   {
     return  queueFront -> item ;
   }
}


/** queue (list) dequeue
 * This function actually removes the item at the front of the queue from
 * the queue.  It is undefined what happens if you try and dequeue() from
 * an empty queue.  This method throws an exception if dequeue is attempted
 * from an empty queue.
 */
template   < class  T >
void   LQueue < T >:: dequeue ()
{
   //assert(queueTop != NULL)
   if   ( isEmpty ())
   {
     throw   EmptyQueueException ( "LQueue<T>::dequeue()" );
   }
   else
   {
     // keep track of the current front, so we can deallocate
     Node < T >*  temp ;
    temp  =  queueFront ;

     // remove the front item from the queue
     // if queue becomes empty, make sure both front and back
     // are NULL
    queueFront  =  queueFront -> link ;
     if   ( queueFront  ==  NULL )
     {
      queueBack  =  NULL ;
     }
    numitems -- ;
    
     // deallocate the old top now
     delete  temp ;
   }
}


/** queue (array) length
 * Accessor method to return the current length of this queue.
 *
 *  @returns  int The current queue length
 */
template   < class  T >
int   LQueue < T >:: length ()   const
{
   return  numitems ;
}


/** queue (array) tostring
 * Represent this queue as a string.
 *
 *  @returns  string Returns the contents of queue as a string.
 */
template   < class  T >
string  LQueue < T >:: tostring ()   const
{
  ostringstream out ;
   Node < T >*  temp  =  queueFront ;
  
  out  <<   "Front: " ;
   while   ( temp  !=  NULL )
   {
    out  <<  temp -> item  <<   " " ;
    temp  =  temp -> link ;
   }
  out  <<   ":Back"   <<  endl ;

   return  out . str ();
}


/** Queue (list) indexing operator
 * Access internel elements of queue using indexing operator[].
 * This is not a normal queue operation, we use mainly for testing
 * so that we can compare if two queues are equal at each internal
 * element of the queue.  For this reason, this operator should 
 * probably be private to the Queue class.
 *
 *  @param  index The index of the item on the queue we want to access
 *   and return, where index 0 represents the front of the queue and
 *   index == length-1 is the back.
 * 
 *  @returns  T Returns the item at "index" on the queue.
 */
template   < class  T >
const  T &   LQueue < T >:: operator []( int  index )   const
{
   // bounds checking, we will throw our stack exception if fails
   if   ( index  <   0   ||  index  >=  numitems )
   {
     throw   InvalidIndexQueueException ( "LQueue<T>::operator[]" );
   }
   // otherwise we will have to search our list for the desired item
   // we will search from the queue front, which is considered
   // index 0
   else
   {
     int  currentIndex  =   0 ;
     Node < T >*  currentNode  =  queueFront ;
    
     while   ( currentIndex  !=  index )
     {
      currentIndex ++ ;
      currentNode  =  currentNode -> link ;
     }

     return  currentNode -> item ;
   }
}



//-------------------------------------------------------------------------

// Assignment 11
// You should add the implemenation of your PriorityQueue
// enqueue() method here.

Assignment 11/Queue.hpp

/** * @description A Queue ADT with two concrete impelementation * examples: an array based queue implementaiton (AQueue), and * a linked list based implementation (LQueue). */ #include <iostream> #include <string> #include <sstream> using namespace std; #ifndef QUEUE_HPP #define QUEUE_HPP //------------------------------------------------------------------------- /** queue (base class) * The basic definition of the Queue Abstract Data Type (ADT) * and queue operations. All declared functions here are * virtual, they must be implemented by concrete derived * classes. */ template <class T> class Queue { public: /** clear * Method to clear out or empty any items on queue, * put queue back to empty state. * Postcondition: Queue is empty. */ virtual void clear() = 0; /** isEmpty * Function to determine whether the queue is empty. Needed * because it is undefined to remove from empty queue. This * function will not change the state of the queue (const). * * @returns bool true if queue is empty, false otherwise. */ virtual bool isEmpty() const = 0; /** enqueue * Add a new item onto back of queue. * * @param newItem The item of template type T to add on back of * the current queue. */ virtual void enqueue(const T& newItem) = 0; /** front * Return the front item from the queue. Note in this ADT, peeking * at the front item does not remove the front item. Some ADT combine * front() and dequeue() as one operation. It is undefined to try and * peek at the front item of an empty queue. Derived classes should * throw an exception if this is attempted. * * @returns T Returns the front item from queue. */ virtual T front() const = 0; /** dequeue * Remove the item from the front of the queue. It is undefined what * it means to try and dequeue from an empty queue. Derived classes should * throw an exception if dequeue() from empty is attempted. */ virtual void dequeue() = 0; /** length * Return the current length or number of item son the queue. * * @returns int The current length of this queue. */ virtual int length() const = 0; /** tostring * Represent queue as a string */ virtual string tostring() const = 0; // overload operators, mostly to support boolean comparison betwen // two queues for testing bool operator==(const Queue<T>& rhs) const; virtual const T& operator[](int index) const = 0; // overload output stream operator for all queues using tostring() template <typename U> friend ostream& operator<<(ostream& out, const Queue<U>& aQueue); }; //------------------------------------------------------------------------- /** Empty queue exception * Class for empty queue exceptions */ class EmptyQueueException { private: string message; public: EmptyQueueException() { message = "Error: operation on empty queue"; } EmptyQueueException(string str) { message = "Error: " + str + " attempted on emtpy queue"; } string what() { return message; } }; /** InvalidIndex queue exception * Class to be thrown when an invalid index is asked for when indexing * into a queue object. */ class InvalidIndexQueueException { private: string message; public: InvalidIndexQueueException() { message = "Error: invalid index request for queue"; } InvalidIndexQueueException(string str) { message = "Error: " + str + " invalid index request for queue"; } string what() { return message; } }; //------------------------------------------------------------------------- /** queue (array implementation) * Implementation of the queue ADT as a fixed array. This * implementation combines a circular buffer implementation, to make * sure that both enqueue() and dequeue() operations are O(1) constant * time. However, it also uses dynamic memory allocation, and * demonstrates doubling the size of the allocated space as needed to * grow queue if/when the queue becomes full. * * @var allocSize The amount of memory currently allocated for this queue. * @var numitems The current length or number of items on the queue. * @var front A pointer to the index of the front item on the queue. * @var back A pointer to the back or last item on the queu. * @var items The items on the queue. This is a dynamically allocated array that * can grow if needed when queue exceeds current allocation. */ template <class T> class AQueue : public Queue<T> { private: int allocSize; // amount of memory allocated int numitems; // The current length of the queue int frontIndex; // index of the front item of the queue int backIndex; // index of the last or rear item of the queue T* items; public: AQueue(int initialAlloc = 100); // constructor AQueue(int initItems[], int numitems); ~AQueue(); // destructor void clear(); bool isEmpty() const; bool isFull() const; void enqueue(const T& newItem); T front() const; void dequeue(); int length() const; string tostring() const; const T& operator[](int index) const; }; //------------------------------------------------------------------------- /** Node * A basic node contaning an item and a link to the next node in * the linked list. */ template <class T> struct Node { T item; Node<T>* link; }; //------------------------------------------------------------------------- /** queue (linked list implementation) * Implementation of the queue ADT as a dynamic linked list. This implementation * uses link nodes and grows (and shrinks) the nodes as items enqueued and dequeued * onto queue. * * @var queueFront a pointer to the node holding the front item of the queue. * @var queueBack a pointer to the node holding the back item of the queue. * @var numitems The length or number of items currently on the queue. */ template <class T> class LQueue : public Queue<T> { protected: Node<T>* queueFront; Node<T>* queueBack; int numitems; // the queue length public: LQueue(); // default constructor ~LQueue(); // destructor void clear(); bool isEmpty() const; void enqueue(const T& newItem); T front() const; void dequeue(); int length() const; string tostring() const; const T& operator[](int index) const; }; //------------------------------------------------------------------------- // Assignment 11 // You should add your PriorityQueue definition here. You class should // be derived from the LQueue<T> class (using public inheritance). // You only need to override and implement 1 method in your PriorityQueue // class, the enqueue() method, which should insert new items into the // linked list ordered by priority, rather than inserting at the end // of the queue as is done by the basic enqueue() // include the implementaiton of the class templates #include "Queue.cpp" #endif