Description
Problem 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.
