Line 1: |
Line 1: |
− | * 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. |
| + | * [[Part 3 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 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]] |
Line 13: |
Line 14: |
| #** [[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]] |
Line 43: |
Line 44: |
| * [[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]. |