editor
32
edits
Changes
no edit summary
* 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/users/meesh/420/part2/p21/ Draft 2.1].
* All files for part 2 (Summer 2010) can be found [http://www.cs.umd.edu/users/meesh/420/part2/ here].
* 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%2B_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 ([[BPTree.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]]
#** [[printNonaTrie]]
#** [[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:
* [[clearAll]]: Clears all of the data structures, removing all elements.
* [[clearAll]]: Clears all of the data structures, removing all elements.
* [[listCities]]: Output a sorted (XML) list of cities in the data dictionary.
* [[listCities]]: Output a sorted (XML) list of cities in the data dictionary.
* [[printHeptaTrie]]: Prints the structure of your HeptaTrie using rules from Section 7 of the spec.
* [[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.
* [[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].