Part 3

• Not Current for Summer 2007 or 2008 (We use B+ tree, not B tree)
• The official spec is not up yet.
• As always, the spec will freeze 1 week prior to the due date.
• Test Files

Overview

For this part of the project, you will implement a B+ Tree that implements the SortedMap interface with insertion and deletion. The B+ tree will become the new data dictionary. Depending on the input, the spatial map will use a PM1Quadtree, PM2Quadtree, or PM3Quadtree to store both cities and roads. You will also be required to make a road adjacency list for use in finding the shortest path between two cities.

Data structures

1. Data Dictionary (B+ tree from part 2)
   • Related commands:
     • createCity
     • deleteCity
     • listCities
     • clearAll
     • printBPTree
     • nameRange
2. Spatial Map (PM3 Quadtree from part 2)
   • Related commands:
     • mapRoad
     • unmapRoad
     • printPMQuadtree
     • rangeCities
     • rangeRoads
     • nearestCity
     • nearestCityToRoad
     • nearestRoad
     • saveMap
     • clearAll
3. Road Adjacency List
   • Related commands:
     • shortestPath
     • clearAll

Commands

The operations you will need to implement are in the spec:

• createCity/deleteCity: You will need to be able to add/remove cities to the data dictionary. No two cities can have the same coordinates or name.
• mapRoad/unmapRoad: Map/unmap a road in the spatial map.
• listCities: Output a sorted (XML) list of cities in the data dictionary.
• rangeCities: This searches the spatial data structure for all cities within a given radius of a given point. Optionally save a visual representation of the command to an image file.
• rangeRoads
• nearestCity: This finds the nearest city to a given point in the spatial map.
• nearestCityToRoad
• nearestRoad
• printBPTree: This outputs an XML representation of the data dictionary.
• printPMQuadtree: This outputs an XML (textual) representation of the spatial map.
• saveMap: This outputs a visual representation (an image) of the spatial data structure. See CanvasPlus.
• clearAll: Clears all of the data structures, removing all elements.
• shortestPath: Computes the shortest path between two cities. Optionally saves the path to an image file or generates an HTML file for the shortest path.
• nameRange

Web Accessibility