## Description

In this homework, you are asked to implement an event-scheduler as a MIN-HEAP. A file keeps

a list of events with the following format:

EVENT-NAME START-TIME END-TIME

where EVENT-NAME is the name of the event, START-TIME is the scheduling time of the

event and END-TIME is the finishing time of the event. Following is an example events.txt file

which consists of three events: EVENT-A which starts at time 2 and ends at time 4, EVENT-B

which starts at time 5 and ends at time 7, and EVENT-C which starts at time 4 and ends at

time 5.

EVENT-A 2 4

EVENT-B 5 7

EVENT-C 4 5

events.txt

The event scheduler starts by reading the list of events from an event file whose name is

supplied as a command line parameter, as mentioned in homework policy section. Event

scheduler creates an event MIN-HEAP using the firing times of the events as keys. Note that,

each listed event in the events file produces two events: (1) an event at the start time and (2)

an event at the end time. Therefore, the heap nodes must store event type, either start or end,

as well as the event name. An event MIN-HEAP for the given example file is as follows:

2

EVENT-A

START

4

EVENT-A

END

5

EVENT-B

START

7

EVENT-B

END

4

EVENT-C

START

5

EVENT-C

END

There is a virtual clock in the system which starts from 0 and ticks by 1 time unit. At each clock

tick, event scheduler checks the top event in MIN-HEAP to see whether there is a scheduled

event at that time or not:

• If there is no scheduled event for that time, the program prints out:

TIME T: NO EVENT

where T is the current time.

• If there is a START event for the scheduled time, then the program prints out:

TIME T: EVENT-NAME STARTED

where T is the current time and EVENT-NAME is the name of the event. Afterwards,

the event is removed from the event MIN-HEAP.

• If there is an END event for the scheduled time, then the program prints out:

TIME T: EVENT-NAME ENDED

where T is the current time and EVENT-NAME is the name of the event. Afterwards,

the event is removed from the event MIN-HEAP.

Please note that, there may be more than one events scheduled for the same time (e.g., both

EVENT-A END and EVENT-C START events are scheduled for time 4 in the example above).

Therefore, you have to check heap till the scheduling time on top of the event MIN-HEAP

becomes larger than the current time.

Program Run and Output for The Given Example

At time T = 1, there is no scheduled event. Therefore, the program prints out:

TIME 1: NO EVENT

The clock ticks and at time T=2, there is a scheduled START event on the top of the event

MIN-HEAP. Therefore, the program prints out:

TIME 2: EVENT-A STARTED

Then, the node is removed from the heap and heap becomes:

4

EVENT-A

END

4

EVENT-C

START

5

EVENT-B

START

7

EVENT-B

END

5

EVENT-C

END

The top element has a scheduled time 4, which is larger than the current time T=2. Therefore,

the clock ticks to the next time, i.e., T=3.

At time T=3, there is no scheduled event. Therefore, the program prints out:

TIME 3: NO EVENT

The clock ticks and at time T=4, there is a scheduled END event on the top of the MIN-HEAP.

Therefore, the program prints out:

TIME 4: EVENT-A ENDED

Then, the node is removed from the heap and heap becomes:

4

EVENT-C

START

5

EVENT-C

END

5

EVENT-B

START

7

EVENT-B

END

The top element has a scheduled time 4, which is equal to the current time T=4. Therefore,

the program prints out:

TIME 4: EVENT-C STARTED

Then, the node is removed from the heap and heap becomes:

5

EVENT-C

END

7

EVENT-B

END

5

EVENT-B

START

The top element has a scheduled time 5, which is larger than the current time T=4. Therefore,

the clock ticks to the next time, i.e., T=5.

At time T=5, the top element has a scheduled time 5, which is equal to the current time.

Therefore, the program prints out:

TIME 5: EVENT-C ENDED

Then, the node is removed from the heap and heap becomes:

5

EVENT-B

START

7

EVENT-B

END

The top element has a scheduled time 5, which is equal to the current time T=5. Therefore,

the program prints out:

TIME 5: EVENT-B STARTED

Then, the node is removed from the heap and heap becomes:

7

EVENT-B

END

The top element has a scheduled time 7, which is larger than the current time T=5. Therefore,

the clock ticks to the next time, i.e., T=6.

At time T=6, there is no scheduled event. Therefore, the program prints out:

TIME 6: NO EVENT

The clock ticks and at time T=7, there is a scheduled END event on the top of the MIN-HEAP.

Therefore, the program prints out:

TIME 7: EVENT-B ENDED

Then, the node is removed from the heap and heap becomes empty.

Since the MIN-HEAP is empty, all the events are scheduled. The program prints out:

TIME 7: NO MORE EVENTS, SCHEDULER EXITS

Afterwards, the program exits gracefully since there is no more events and the user is informed!

Submission

Submit your homework files through Ninova. Please zip and upload all your files. You are

going to submit the following files:

(a) All your .h (if any) and .cpp files

(b) A .pdf file as your report. Your report should be clear and detailed. Otherwise, it may

result in a grade loss for you.

(c) A .txt file explaining how to compile and run your code (in a 1 or 2 line)

Use your student ID as file names. That is, your_student_id.zip for the .zip file,

your_student_id.cpp for the main C++ source file and your_student_id.pdf for the report.