Changes

== 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 ==

#** [[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]]

#** [[printPMQuadtree]]

#** [[printPMQuadtree]]

#** [[rangeCities]]

#** [[rangeCities]]

#** [[nearestCity]]

#** [[nearestCity]]

#** [[saveMap]]

#** [[nearestIsolatedCity]]

#** [[nearestCityToRoad]]

#** [[clearAll]]

#** [[clearAll]]

# Road Adjacency List

# Road Adjacency List

* [[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.