Difference between revisions of "Part 2"

From CMSC 420
(→‎Data structures: added command)
(added command)
Line 26: Line 26:
  
 
== Commands ==
 
== Commands ==
The operations you will need to support can be gleaned from the spec:
+
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]

  1. Data Dictionary (B-tree for part 2)
  2. Spatial Map (PM3 Quadtree for part 2)
  3. Road Adjacency List

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.