- All files for part 2 can be found here.
- The official spec is Draft 2.1.
- As always, the spec will freeze 1 week prior to the due date.
- Test Files
For this part of the project, you will implement a AVL-G Tree that implements the SortedMap interface. However, you do not need to implement deletion operations until Part 3. The AVL-G tree will become the new data dictionary. The spatial map will now use a PM3 Quadtree 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 Dictionary (AVL-G tree for part 2)
- Spatial Map (PM3 Quadtree for part 2)
- Road Adjacency List
The operations you will need to implement are in the spec:
- createCity: You will need to be able to add cities to the data dictionary. No two cities can have the same coordinates or name.
- clearAll: Clears all of the data structures, removing all elements.
- listCities: Output a sorted (XML) list of cities in the data dictionary.
- printAvlTree: Prints the structure of your AVL-G Tree using rules from Section 7 of the spec.
- mapRoad: Map a road in the spatial map.
- 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.
- 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: This searches the spatial data structure for all roads within a given radius of a given point.
- nearestCity: This finds the nearest city in the spatial map to a given point.
- nearestIsolatedCity: This finds the nearest isolated city in the spatial map to a given point.
- nearestRoad: This finds the nearest road in the spatial map to a given point.
- nearestCityToRoad: This finds the nearest road in the spatial map to a given point.
- shortestPath: Computes the shortest path between two cities. Optionally saves the path to an image file using CanvasPlus or generates an HTML file for the shortest path using XSLT.