Difference between revisions of "Part 2"
From CMSC 420
m (put in a warning that summer 2007 and 2008 use b+ tree, not b tree.) |
|||
| (19 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
| − | * | + | * 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/ | + | * 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 [ | + | 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 ([[ | + | # Data Dictionary ([[AVLGTree.java |AVL-G tree]] for part 2) |
#* Related commands: | #* Related commands: | ||
#** [[createCity]] | #** [[createCity]] | ||
#** [[listCities]] | #** [[listCities]] | ||
#** [[clearAll]] | #** [[clearAll]] | ||
| − | #** [[ | + | #** [[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]] | ||
| − | |||
# 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. | ||
| − | * [[ | + | * [[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. | ||
| − | * [[ | + | * [[nearestIsolatedCity]]: This finds the nearest isolated city in the spatial map to a given point. |
| − | * [[ | + | * [[nearestRoad]]: This finds the nearest road in the spatial map to a given point. |
| − | * [[ | + | * [[nearestCityToRoad]]: This finds the nearest road in the spatial map to a given point. |
| − | |||
* [[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]. | ||
Latest revision as of 00:48, 6 February 2017
- All files for part 2 can be found here.
- The official spec is Draft 2.1.
- 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 AVL-G Tree that implements the 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 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 (AVL-G tree for part 2)
- Related commands:
- Spatial Map (PM3 Quadtree for part 2)
- 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.
- 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.
- 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.
- 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.
- nearestIsolatedCity: This finds the nearest isolated city in the spatial map to a given point.
- nearestRoad: This finds the nearest road in the spatial map to a given point.
- nearestCityToRoad: This finds the nearest road in the spatial map to a given point.
- shortestPath: Computes the shortest path between two cities. Optionally saves the path to an image file using CanvasPlus or generates an HTML file for the shortest path using XSLT.
