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:
* Not Current for Summer 2007 or 2008 ( no more btree---we use the b+ tree)
+
* 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 ([[BTree.java |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].

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]

  1. Data Dictionary (AVL-G 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.
  • 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.