Difference between revisions of "Part 2"
From CMSC 420
Ben Zoller (talk | contribs) (→Data structures: added command) |
Ben Zoller (talk | contribs) (added command) |
||
| Line 26: | Line 26: | ||
== Commands == | == Commands == | ||
| − | The operations you will need to | + | 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. | * [[createCity]]: You will need to be able to add cities to the data dictionary. No two cities can have the same coordinates or name. | ||
| Line 33: | Line 33: | ||
* [[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. | * [[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. | ||
* [[nearestCity]]: This finds the nearest city to a given point in the spatial map. | * [[nearestCity]]: This finds the nearest city to a given point in the spatial map. | ||
| + | * [[printBTree]]: This outputs an XML representation of the data dictionary. | ||
* [[printPMQuadtree]]: This outputs an XML (textual) representation of 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]]. | * [[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. | * [[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. | * [[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. | ||
Revision as of 23:51, 18 March 2007
- Due Date: April ? (+ epsilon)
- The official spec is not up yet.
- As always, the spec will freeze 1 week prior to the due date.
Overview[edit]
For this part of the project, you will implement a B-Tree that implements the SortedMap interface. However, you do not need to implement deletion operations until Part 3. The B-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 structures[edit]
- Data Dictionary (B-tree for part 2)
- Related commands:
- Spatial Map (PM3 Quadtree for part 2)
- Related commands:
- Road Adjacency List
- Related commands:
Commands[edit]
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.
- mapRoad: Map 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.
- nearestCity: This finds the nearest city to a given point in the spatial map.
- printBTree: 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.
