Part 3: B+ tree delete, PM1 Quadtree and Adjacency Lists

In Part 3 we upgrade our data structures and add new commands to utilize these changes. You will be adding new functionality to SoftWar by accepting tracks and locations of interest, or loci in your spatial structure. To do this, the PR Quadtree will be upgraded or replaced (your design decision) with a shiny new PM1 Quadtree that is more appropriate than the PR when modeling graphs that can be interpreted as polygonal maps. The implementation of a PM1 quadtree (instead of, say a PM2 or PM3) will permit us to quickly identify the closest track to a given coordinate, with search time in $O(\log\;n)$, instead of the search time given by $O(n)$ of the PM2 and the PM3. Additionally, we will complete the B+ Tree from Part 2 by adding delete capabilities, and give extra credit to those of you who finish implementing the SortedMap interface as well.

You will also maintain adjacency lists corresponding to graphs of loci connected by tracks, which we shall call routes. We use this collective term because collections of tracks connecting different types of loci may have different roles than say, roads. However, road would not be an appropriate term for the set of edges between say, a weapon and its target.

In the Part 3 specification, we will attempt to repair the errors and inconsistencies that have plagued earlier specs. We will be removing punctuation at the end of error messages. This will improve the ease of quick visual checks for output correctness. Furthermore, since the complexity of Part 3 is about double that of Part 2, we are eliminating the separation of data dictionaries to make grading easier.

Any other changes of this nature will be added here.