Line 1: |
Line 1: |
− | * Due Date: April ? (+ epsilon) | + | * All files for part 2 can be found [http://www.cs.umd.edu/users/meesh/420/part2/ here]. |
− | * The official spec is [http://www.cs.umd.edu/~meesh/cmsc420/spr07/part2/p21/ Draft 2.1]. | + | * The official spec is [http://www.cs.umd.edu/users/meesh/420/part2/p21/ Draft 2.1]. |
| * As always, the spec will freeze 1 week prior to the due date. | | * As always, the spec will freeze 1 week prior to the due date. |
| * [[Part 2 Test Files | Test Files]] | | * [[Part 2 Test Files | Test Files]] |
| | | |
| == Overview == | | == 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. 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 [[PM Quadtree#PM3 Quadtree | 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. | + | For this part of the project, you will implement a [https://en.wikipedia.org/wiki/AVL_tree AVL-G Tree] that implements the [http://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html 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 [[PM Quadtree#PM3 Quadtree | 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 == | | == Data structures == |
− | # Data Dictionary (B-tree for part 2) | + | # Data Dictionary ([[AVLGTree.java |AVL-G tree]] for part 2) |
| #* Related commands: | | #* Related commands: |
| #** [[createCity]] | | #** [[createCity]] |
| #** [[listCities]] | | #** [[listCities]] |
| #** [[clearAll]] | | #** [[clearAll]] |
− | #** [[printBTree]] | + | #** [[deleteCities]] |
| + | #** [[printAvlTree]] |
| # Spatial Map ([[PM Quadtree#PM3 Quadtree |PM3 Quadtree]] for part 2) | | # Spatial Map ([[PM Quadtree#PM3 Quadtree |PM3 Quadtree]] for part 2) |
| #* Related commands: | | #* Related commands: |
| + | #** [[mapCity]] |
| + | #** [[unmapCity]] |
| #** [[mapRoad]] | | #** [[mapRoad]] |
| #** [[printPMQuadtree]] | | #** [[printPMQuadtree]] |
| + | #** [[saveMap]] |
| #** [[rangeCities]] | | #** [[rangeCities]] |
| + | #** [[rangeRoads]] |
| #** [[nearestCity]] | | #** [[nearestCity]] |
| + | #** [[nearestIsolatedCity]] |
| + | #** [[nearestRoad]] |
| + | #** [[nearestCityToRoad]] |
| + | #** [[clearAll]] |
| + | #** [[printPRQuadtree]] |
| #** [[saveMap]] | | #** [[saveMap]] |
− | #** [[clearAll]]
| |
| # Road Adjacency List | | # Road Adjacency List |
| #* Related commands: | | #* Related commands: |
Line 31: |
Line 40: |
| | | |
| * [[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. |
| + | * [[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. | | * [[mapRoad]]: Map a road in the spatial map. |
− | * [[listCities]]: Output a sorted (XML) list of cities in 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]. |
| * [[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. |
| + | * [[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. | | * [[nearestCity]]: This finds the nearest city in the spatial map to a given point. |
− | * [[printBTree]]: This outputs an XML representation of the data dictionary. | + | * [[nearestIsolatedCity]]: This finds the nearest isolated city in the spatial map to a given point. |
− | * [[printPMQuadtree]]: This outputs an XML (textual) representation of the spatial map. | + | * [[nearestRoad]]: This finds the nearest road in the spatial map to a given point. |
− | * [[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]. | + | * [[nearestCityToRoad]]: This finds the nearest road in the spatial map to a given point. |
− | * [[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 using [http://wam.umd.edu/~bzoller/cmsc420/doc/cmsc420/drawing/CanvasPlus.html CanvasPlus] or generates an HTML file for the shortest path using [http://en.wikipedia.org/wiki/XSLT XSLT]. | | * [[shortestPath]]: Computes the shortest path between two cities. Optionally saves the path to an image file using [http://wam.umd.edu/~bzoller/cmsc420/doc/cmsc420/drawing/CanvasPlus.html CanvasPlus] or generates an HTML file for the shortest path using [http://en.wikipedia.org/wiki/XSLT XSLT]. |