Difference between revisions of "Part 3"

From CMSC 420
m (→‎Data structures: more btree to bptree changes)
 
(4 intermediate revisions by the same user not shown)
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.
Line 5: Line 5:
  
 
== 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 14: 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 44: 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].

Latest revision as of 19:35, 10 June 2008

  • Not Current for Summer 2007 or 2008 (We use B+ tree, not B tree)
  • The official spec is not up yet.
  • As always, the spec will freeze 1 week prior to the due date.
  • Test Files

Overview[edit]

For this part of the project, you will implement a B+ Tree that implements the 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 PM1Quadtree, PM2Quadtree, or 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[edit]

  1. Data Dictionary (B+ tree from part 2)
  2. Spatial Map (PM3 Quadtree from part 2)
  3. Road Adjacency List

Commands[edit]

The operations you will need to implement are in the spec:

  • createCity/deleteCity: You will need to be able to add/remove cities to the data dictionary. No two cities can have the same coordinates or name.
  • mapRoad/unmapRoad: Map/unmap a road in the spatial map.
  • listCities: Output a sorted (XML) list of cities in the data dictionary.
  • rangeCities: This searches the spatial data structure for all cities within a given radius of a given point. Optionally save a visual representation of the command to an image file.
  • rangeRoads
  • nearestCity: This finds the nearest city to a given point in the spatial map.
  • nearestCityToRoad
  • nearestRoad
  • printBPTree: This outputs an XML representation of the data dictionary.
  • 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 CanvasPlus.
  • clearAll: Clears all of the data structures, removing all elements.
  • shortestPath: Computes the shortest path between two cities. Optionally saves the path to an image file or generates an HTML file for the shortest path.
  • nameRange