For this assignment you are going to do some code with the heaps that have been discussed in class. As with all the assignments, you can write this in whatever language you want, but I have to be able to compile and run it under Linux on the lab machines. What you turn in will be graded for correctness and speed. It might also be used in a future assignment so keep that in mind and try to build flexible and robust data structures. You will use this data structure to solve the following problem. You might also use some other data structures to go along with it, but you don't have to write those if you can find a good library for them. You are required to write any heaps or priority queues that you use for this assignment.
This assignment is going to be very similar to the last assignment, but with a slight variation in that there will not be a remove command and instead, removes will happen automatically during processing. In addition, you will write a Fibonacci heap so that the program can be run with binary, binomial, or Fibonacci heaps.
Like the last assignment, this program will keep track of a number of different queues as a subsystem of a parallel simulation. The primary change from the last assignment is that when you pull events off during the process, you will do a remove on the two objects that were part of that event. So if you process an event with objects 5 and 20 you will then remove all remaining events that include either 5 or 20. All the other commands stay the same. If you are doing things well you should also be able to easily add in code that could use Fibonacci heaps for the previous assignment.
The interface for this program will be all text. You will read from standard input and write to standard output. Each line of input will have a command that you have to process. The meaning of each command and what you must print for it, if anything, is given below.
As mentioned above, the first line of the input is either going to be BINARY, BINOMIAL, or FIBONACCI to tell you which type of heap to use (so you might want your heaps to adhere to the same interface). Each line after that will have one of the following commands:
BUILD queueID
This tells you that the load has gotten smaller and you need to produce a new queue with the given ID.
ADD queueID time obj1 obj2
Place an event with the given time (double) and the specified ojects (ints) on the given queue (String).
PROCESS time
Process all events up to the given time (inclusive).
As each event is processed you remove all the remaining events that include either object from the processed event.
MERGE queueID1 queueID2
The two queues need to be merged and all the items will be on the first queue. The second one becomes inactive and nothing will be placed on it until another BUILD is issued.
DUMP
Print out a list of the active queues. The dump should start with the time that you have processed up to (0 if you haven't gotten a PROCESS call yet). After that you should have one line for each currently active queue with the following format: "queueID num firstTime firstObj1 firstObj2". The num is how many things are on the queue and the other values are those associated with the first object in that queue. The queues should be printed out in sorted order by queueID. If the queue is empty don't print anything for the last three values.
Here are the inputs and outputs.