Changes

117 bytes added ,  17:27, 30 September 2013
no edit summary
Line 6: Line 6:     
== 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 ==
Line 14: Line 14:  
#** [[listCities]]
 
#** [[listCities]]
 
#** [[clearAll]]
 
#** [[clearAll]]
#** [[printNonaTrie]]
+
#** [[printAVLGTree]]
 
# 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:
 
#** [[mapRoad]]
 
#** [[mapRoad]]
 +
#** [[mapCity]]
 
#** [[printPMQuadtree]]
 
#** [[printPMQuadtree]]
 +
#** [[saveMap]]
 
#** [[rangeCities]]
 
#** [[rangeCities]]
 +
#** [[rangeRoads]]
 
#** [[nearestCity]]
 
#** [[nearestCity]]
#** [[saveMap]]
+
#** [[nearestIsolatedCity]]
 +
#** [[nearestRoad]]
 +
#** [[nearestCityToRoad]]
 
#** [[clearAll]]
 
#** [[clearAll]]
 
# Road Adjacency List
 
# Road Adjacency List
Line 34: Line 39:  
* [[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.
+
* [[printAVLGTree]]: 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.
 
* [[mapCity]]: Map a city in the spatial map.
 
* [[mapCity]]: Map a city in the spatial map.
editor
68

edits