Lab : Priority Queues Solution

Information




In-class labs are meant to introduce you to a new topic and provide some practice with that new topic.




Topics: Priority Queue




Solo work: Labs should be worked on by each individual student, though asking others for help is permitted. Do not copy code from other sources, and do not give your code to other students. Students who commit or aid in plagiarism will receive a 0% on the assignment and be reported.










Building and running: If you are using Visual Studio, make sure to run with debugging. Do not run without debugging!




Using the debugger will help you nd errors.




To prevent a program exit, use this before return 0;







cin.ignore(); cin.get();







Turn in: Once you're ready to turn in your code, prepare the les by




doing the following: (1) Make a copy of your project folder and name it




LASTNAME-FIRSTNAME-LABNAME. (Example: HOPPER-GRACE-LAB-UNIT-TESTS)




Make sure that all source les (.cpp, .hpp, and/or .h les) and the Makefile les are all present. (3) Remove all Visual Studio les - I only want the source les and Make les. (4) Zip your project folder as LASTNAME-FIRSTNAME-LABNAME.zip



Never turn in Visual Studio les!




Starter les: Download from GitHub.




Grading: Grading is based on completion, if the program functions as intended, and absense of errors. Programs that don't build will receive 0%. Besides build errors, runtime errors, logic errors, memory leaks, and ugly code will reduce your score.




Contents










1.1
About . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3


1.1.1
Priority Queues . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Lab speci cations . . . . . . . . . . . . . . . . . . . . . . . . .
3


1.2.1
Job . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3


1.2.2
Priority Queue . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Example output . . . . . . . . . . . . . . . . . . . . . . . . . .
6


1.3.1
Running the program . . . . . . . . . . . . . . . . . . .
6


1.3.2
result.txt . . . . . . . . . . . . . . . . . . . . . . . . . .
7


1.1 About




1.1.1 Priority Queues




A priority queue is a queue where items are added in so that higher prior-ity items are ahead of the lower priority items. This requires some form of sorting on the Push function to make sure that items are added in the right order.




We will learn more about heaps later on, which are another way we can implement a priority queue. For now, we are going to implement the priority queue in this lab with a simple array.













1.2 Lab speci cations




In this lab, a series of homework assignments are generated, each with a due date, and an amount of work associated with it. The homework assignments will be added into a PriorityQueue and then processed based on the priority (in this case, what assignment is due sooner.)




In this assignment, the Processor/Work functions are already implemented and you just have to focus on the Priority Queue functionality.













1.2.1 Job




In this lab, the Job class looks like this:







struct Job



2
{
3
Job () ;
4
void Work () ;







void S e t F i n i s h D a y ( int day ) ;



6
void
Update ( int ti me st am p ) ;
7




8
int
id ;
9
string a s s i g n m e n t ;
10
bool
done , overdue ;
11








12
int dueOnDay , timeRemaining , d a y F i n i s h e d ;
13
};















In the Processor, it will keep track of the \day", starting from 0. In the Job, dueOnDay corresponds to this day.




The timeRemaining variable is the amount of \days" of work remaining for the assignment.




The dayFinished is logged as which day the work remaining hit 0.













1.2.2 Priority Queue




The PriorityQueue class declaration looks like this:







const int MAX_SIZE = 1000;






2




3 class P r i o r i t y Q u e u e







{



5
public :
6
P r i o r i t y Q u e u e () ;
7
void
Push ( Job * task ) ;
8
void
Pop () ;









Job * Front () ;



10
int
Size () ;
11
void
Display () ;
12




13
private :
14
void
S h i f t R i g h t ( int atIndex ) ;









void Sh if tL ef t ( int atIndex ) ;






16


17
Job * m_arr [ MAX_SIZE ];
18
int m _ i t e m C o u n t ;
19
};













void PriorityQueue::Push( Job* task )




Error check: If the internal array m arr is full, throw a runtime error that additional items cannot be added.







Locate the index where the new item task should be inserted at. Use the Job's dueOnDay eld to compare to what is already in the array.




In other words, iterate through the array. Once you nd an item with a lower priority (the due date is greater) than the new task, insert the new





task at this position.




You can access the dueOnDay like this:




In the array: m arr[insertAt]-dueOnDay







The new task: task-dueOnDay




Once you nd the proper location to add the new item, call ShiftRight at that index to make room for the new item. Afterwards, set




m arr[insertAt] = task;







and increment the item count.




void PriorityQueue::Pop()




Remove the front-most item from the queue, and push everything forward by one slot. Decrement the item count. You can use the ShiftLeft function.




Job* PriorityQueue::Front()




Return the front-most item.




1.3 Example output




1.3.1 Running the program







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




| Homework P r i o r i t i z e r |




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










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




How many tasks ? ( More than 10)







10










Creating homework ...







Filling queues ...







P r o c e s s i n g with FCFS ...







DONE























1.3.2 result.txt







Doing my homework !







- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - DAY : 0







P r o c e s s i n g task 2...







ID
DUE ON
R EM AI NI NG
FINISHED DAY
OVERDUE
0
15
6




1
37
2




2
13
4






<<






3
13
1




4
39
15




5
17
5




6
24
9




7
29
11




8
18
5




9
18
7













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




DAY :
1






P r o c e s s i n g task 2...




ID
DUE ON
R EM AI NI NG
FINISHED DAY
OVERDUE
0
15
6




1
37
2




2
13
3




<<






3
13
1




4
39
15




5
17
5




6
24
9




7
29
11




8
18
5




9
18
7




( etc )














- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - DAY : 64







P r o c e s s i n g task 4...







ID DUE ON R EM AI NI NG FINISHED DAY OVERDUE











CS 250,


Lab : Priority Queues


















15
0
11




0




1
37
0
50
overdue


2
13
0
4




3
13
0
5




4
39
1


overdue


<<










5
17
0
16




6
24
0
37
overdue


7
29
0
48
overdue


8
18
0
21
overdue


9
18
0
28
overdue


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




DAY :
65










P r o c e s s i n g task 4... done !








ID
DUE ON
R EM AI NI NG
FINISHED DAY
OVERDUE


0
15
0
11




1
37
0
50
overdue


2
13
0
4




3
13
0
5




4
39
0
65
overdue


<<










5
17
0
16




6
24
0
37
overdue


7
29
0
48
overdue


8
18
0
21
overdue


9
18
0
28
overdue