For this project you will make use of the 3rd coordinate for the first time since project 1. In order to map this third coordinate you will implement a skiplist of pm1 quadtrees. To test the skiplist the upper bound requirement on the z coordinate has been removed changed to max_signed_32bit_int (too lazy to figure out latex right now for the caret). If the upper bound is actually an issue don't worry, all the numbers used will certainly be below 100,000, but there is no reason why your program should not handle any integer value.
As an example of what I am describing, consider the set of commands:
CREATE_DOCK(A,4,6,2000)
CREATE_DOCK(B,20,1000,2000)
CREATE_FLIGHT(A,B)
Your first action will be to query the skiplist to see if there is already a PM1 quadtree with a height value of 2000. If there is, you will insert the flight into that tree. If there isn't, then you will initialize a new PM1 with that flight, and add it to the skiplist with the key 2000. The skiplist will of course be sorted by the height. If a PM1 ever becomes completely empty because all the docks inside of it are deleted, then that is the time that the entire PM1 level should be deleted from the skiplist.
For skiplist testing make sure that you at least can handle creating a PM1 with a single isolated dock, and deleting a single isolated dock from such a PM1. I will use this ability to try and check your skiplist functionality separately from the other parts of the project.
The other major aspect of this project is the implementation of PM1 delete. Moreso than with project3 I will try and make sure there are a fair amount of points for the 'basic' cases. Be aware if you have not thought about it that PM1 delete is more complicated than just collapsing subtrees because of the division rules involved. There is IO from last semester I will put up demonstrating this with postscript pictures (I am not sure I will have the IO perfectly tuned to the requirements of the current spec, but you'll get the idea).
As far as grading there will be 130 points available but the grade will only be based out of 100. For this project that will mean that you can skip PM1 delete or the nearest flight/dock commands and still get 100 points (which means neither will be worth more than 30 points). You may still do more to get extra credit. You may find it advantageous whatever you decide to get the basic cases of PM1 delete to work. You can roughly assume that the following groups will all be counted about equally:
1. Skiplist add
2. Skiplist delete (you'll need at least PM1 delete of a single point to work)
3. Nearest flight/nearest dock
4. PM1 delete
I did say 'about', so don't expect quite 30/30/30/30. There will also be some tests for intersection detection, which were unfortunately omitted from project3s testing. Note that There will not be any testing of B+ delete! If you never got it quite debugged, let it be. If you've done good work on it since the end of p3 and the posting of this spec because you weren't aware of this, talk to meesh or the TA[me]. This may have already been mentioned in class. If so, cool.
Ah, and the tests aimed at testing PM1 delete will only deal with z coordinates of 0 as as with p2 and p3, so you need not have a working skiplist to get PM1 delete credit. Since there are no more graph algorithms being run, you do not need to support the adjacency list if it is not convenient to do so (I won't call list_flights, that will be about the only change).