Difference between revisions of "Part 3"
From CMSC 420
m (added warning that B tree information not current for summer 2007, 2008) |
m (→Data structures: more btree to bptree changes) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
== Overview == | == Overview == | ||
| − | For this part of the project, you will implement a [http://en.wikipedia.org/wiki/B | + | For this part of the project, you will implement a [http://en.wikipedia.org/wiki/B%2B_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 structures == | ||
| − | # Data Dictionary (B | + | # Data Dictionary (B+ tree from part 2) |
#* Related commands: | #* Related commands: | ||
#** [[createCity]] | #** [[createCity]] | ||
| Line 14: | Line 14: | ||
#** [[listCities]] | #** [[listCities]] | ||
#** [[clearAll]] | #** [[clearAll]] | ||
| − | #** [[ | + | #** [[printBPTree]] |
#** [[nameRange]] | #** [[nameRange]] | ||
| − | # Spatial Map (PM3 Quadtree | + | # Spatial Map (PM3 Quadtree from part 2) |
#* Related commands: | #* Related commands: | ||
#** [[mapRoad]] | #** [[mapRoad]] | ||
| Line 44: | Line 44: | ||
* [[nearestCityToRoad]] | * [[nearestCityToRoad]] | ||
* [[nearestRoad]] | * [[nearestRoad]] | ||
| − | * [[ | + | * [[printBPTree]]: 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 [http://wam.umd.edu/~bzoller/cmsc420/doc/cmsc420/drawing/CanvasPlus.html CanvasPlus]. | * [[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]. | ||
Latest revision as of 19:35, 10 June 2008
- 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[edit]
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[edit]
- Data Dictionary (B+ tree from part 2)
- Related commands:
- Spatial Map (PM3 Quadtree from part 2)
- Related commands:
- Road Adjacency List
- Related commands:
Commands[edit]
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
