103
edits
Changes
From CMSC 420
new part 3 page
* Due Date: April/May ? (+ epsilon)
* The official spec is not up yet.
* As always, the spec will freeze 1 week prior to the due date.
== Overview ==
For this part of the project, you will implement a [http://en.wikipedia.org/wiki/B-tree B-Tree] that implements the [http://java.sun.com/j2se/1.5.0/docs/api/java/util/SortedMap.html 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 [[PM Quadtree#PM1 Quadtree | PM1Quadtree]], [[PM Quadtree#PM2 Quadtree | PM2Quadtree]], or [[PM Quadtree#PM3 Quadtree | 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 ==
# Data Dictionary (B-tree for part 2)
#* Related commands:
#** [[createCity]]
#** [[deleteCity]]
#** [[listCities]]
#** [[clearAll]]
#** [[printBTree]]
#** [[nameRange]]
# Spatial Map (PM3 Quadtree for part 2)
#* Related commands:
#** [[mapRoad]]
#** [[unmapRoad]]
#** [[printPMQuadtree]]
#** [[rangeCities]]
#** [[rangeRoads]]
#** [[nearestCity]]
#** [[nearestCityToRoad]]
#** [[nearestRoad]]
#** [[saveMap]]
#** [[clearAll]]
# 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]]
* [[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 [http://wam.umd.edu/~bzoller/cmsc420/doc/cmsc420/drawing/CanvasPlus.html 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]]
* The official spec is not up yet.
* As always, the spec will freeze 1 week prior to the due date.
== Overview ==
For this part of the project, you will implement a [http://en.wikipedia.org/wiki/B-tree B-Tree] that implements the [http://java.sun.com/j2se/1.5.0/docs/api/java/util/SortedMap.html 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 [[PM Quadtree#PM1 Quadtree | PM1Quadtree]], [[PM Quadtree#PM2 Quadtree | PM2Quadtree]], or [[PM Quadtree#PM3 Quadtree | 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 ==
# Data Dictionary (B-tree for part 2)
#* Related commands:
#** [[createCity]]
#** [[deleteCity]]
#** [[listCities]]
#** [[clearAll]]
#** [[printBTree]]
#** [[nameRange]]
# Spatial Map (PM3 Quadtree for part 2)
#* Related commands:
#** [[mapRoad]]
#** [[unmapRoad]]
#** [[printPMQuadtree]]
#** [[rangeCities]]
#** [[rangeRoads]]
#** [[nearestCity]]
#** [[nearestCityToRoad]]
#** [[nearestRoad]]
#** [[saveMap]]
#** [[clearAll]]
# 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]]
* [[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 [http://wam.umd.edu/~bzoller/cmsc420/doc/cmsc420/drawing/CanvasPlus.html 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]]
