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.
For this assignment you are writing a subsystem for a large scale parallel collisional simulation. The way the system works, different objects in the simulation can collide or interact with one another at different times. Thankfully, you don't have to write the code for figuring out when and where things interact, your subsection simply deals with keeping track of what should interact next. Because it is in parallel, you will have a number of different queues, each with a unique ID. Your code will be handed interaction events for the queue. Each interaction event will have two ints for the two objects interacting and a double for the time the interaction begins (and as far as you are concerned, ends). When you are handed an event, you will also be told which queue it should go on. You will be told every so often to process all events on all queues up to a certain time. Basically you will pull everything off all queues that has a time equal to or less than the given time.
The trick comes in with the fact that things are in parallel. This is on a massive shared memory machine with many cores. There are also other loads going on. When the load gets too high, you will be told to scale back the number of queues that are processing. You will do this by merging the given queues together. If the load goes down you will be told to create a new queue with a specific ID. The details of the input are listed below. One other complication is that the user can select whether your queues should be binary heaps or binomial heaps. The first line of the input will tell you which type to use for everything else.
The final complication comes from the fact that occasionally objects will be removed from the system by one of the events. When that happens, all queue elements in all queues that refer to that object must be removed.
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 or BINOMIAL 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).
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.
REMOVE obj
All events involving that object should be removed from all queues.
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 is sample input and sample output. If you want to try a bigger file here are samples for that (in, out). I made the first line read BINARY. You can change it to BINOMIAL when you are ready to test that.