Changes

* Due Date: April/May ? (+ epsilon)

* Not Current for Summer 2007 or 2008 (We use B+ tree, not B tree)

* The official spec is not up yet.

* The official spec is not up yet.

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

== 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 with insertion and deletion. The B-tree will become the new data dictionary. Depending on the input, the spatial map will use a [[PM Quadtree#PM1 Quadtree | PM1Quadtree]], [[PM Quadtree#PM2 Quadtree | PM2Quadtree]], or [[PM Quadtree#PM3 Quadtree | PM3Quadtree]] 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 [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 with insertion and deletion. The B+ tree will become the new data dictionary. Depending on the input, the spatial map will use a [[PM Quadtree#PM1 Quadtree | PM1Quadtree]], [[PM Quadtree#PM2 Quadtree | PM2Quadtree]], or [[PM Quadtree#PM3 Quadtree | PM3Quadtree]] 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 (B-tree for part 2)

# Data Dictionary (B+ tree from part 2)

#* Related commands:

#* Related commands:

#** [[createCity]]

#** [[createCity]]

#** [[listCities]]

#** [[listCities]]

#** [[clearAll]]

#** [[clearAll]]

#** [[printBTree]]

#** [[printBPTree]]

#** [[nameRange]]

#** [[nameRange]]

# Spatial Map (PM3 Quadtree for part 2)

# Spatial Map (PM3 Quadtree from part 2)

#* Related commands:

#* Related commands:

#** [[mapRoad]]

#** [[mapRoad]]

* [[nearestCityToRoad]]

* [[nearestCityToRoad]]

* [[nearestRoad]]

* [[nearestRoad]]

* [[printBTree]]: This outputs an XML representation of the data dictionary.

* [[printBPTree]]: This outputs an XML representation of the data dictionary.

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