CMSC 420 Data Structures, Fall 2003 History of Specification Changes Back to Main page DISCLAIMER This history has been compiled by diffing the previous version of the specification with the updated version. This history is NOT guaranteed to be complete. That is, if something in the spec changed between versions but was not listed in this history, you are still responsible for adhering to the specification! In short, the specification is final. This history is merely meant as a public service to highlight the major changes between versions. If you find something that should be on this list that is not, e-mail Kevin Conroy at kmconroy at wam. Version 4.01 (html) (pdf) (ps) to Version 4.02 (html) (pdf) (ps) on 12/5/03. Clarified CREATE_ROAD explaination to more accurately reflect the <SpatialIntersection> error. Clarified "*_WITH_MAP" commands; You should only draw a map on a <success> message. Added <LocationNotMapped> check to FIND_IN_CITY Fixed typo in FIND_IN_CITY: <CityDoesNotExist> -> <LocationDoesNotExist> Added "Point Breakdown" section for Part 4. Version 3.04 (html) (pdf) (ps) to Version 4.01 (html) (pdf) (ps) on 11/26/03. Added ANNOTATED_ROUTE, UNMAP_LOCATION, UNMAP_ROAD commands. Expanded explanation of Part 4 requirements to include details on ANNOTATED_ROUTE. Added unchanged commands from Part 3 to Part 4. Version 3.03 (html) (pdf) (ps) to Version 3.04 (html) (pdf) (ps) on 11/14/03. Changed second to last line in the long example in PRINT_MAP to accurately reflect <OneWayRoad> BNF. Added section "Point Breakdown" to Part 3. Added O(E*lgV) runtime requirement for shortest route/adjacency list to Part 4 Preview. Nov. 17: Changed due date to reflect part 3 extension. New due date is Mon. Nov 24, 2003 10pm. Version 3.02 (html) (pdf) (ps) to Version 3.03 (html) (pdf) (ps) on 11/7/03. Changed <black_node> in PRINT_MAP to use <Location> rather than <City> Clarified CREATE_CITY: Radius will be a non-negative integer (i.e. 0 is a valid radius). Changed <success> on CREATE_CITY to say "Created city" rather than "Created location" and changed from <Location> to <City> (just to clarify). Added BNF for <LocationType> Added a new Location type: Intersection. This should allow you to create data sets that have intersecting roads! Added "Please note that you should use a single B+ tree to store all Cities and Locations!" to CREATE_CITY, CREATE_LOCATION, DELETE_LOCATION, LIST_LOCATIONS, and PRINT_BPTREE. This rule applies to all commands, but those were the ones most directly affected. Changed CREATE_LOCATION to match the ordering of latitude/longitude of CREATE_CITY. Also change <GenericLocation> to reflect this. Noted that the FIND_IN_CITY command should use Euclidean geometry. Clarified that 20 levels means that the root is one level. (Let's make sure we get our definitions straight folks!) Clarified CREATE_ROAD command: You may only have one road with the same name connecting two cities. That is, you can't have two I95's connecting DC and Baltimore even if one is a TwoWay road and the other is a OneWay road. The name, startcity, and destinationcity are the unique key! Changed the <success> BNF for FIND_IN_CITY. You will now print the locations in sorted order based on the distance from the city center and should print this distance after the <Location>. Corrected <SpatialIntersection> typo. Version 3.01 (html) (pdf) (ps) to Version 3.02 (html) (pdf) (ps) on 10/31/03. Added command specification. Each commands notes if it has changed or not. The range for valid coordinates is now fully inclusive, [0, 1024]. Road objects now represented with OneWayRoad or TwoWayRoad City objects are now considered to be a Location. Other types of points are also Locations. See each command's description as numerous things have changed. Version 2.04 (html) (pdf) (ps) to Version 3.01 (html) (pdf) (ps) on 10/29/03. Added general requirements for part 3. This should be enough to allow anyone to start work on the project as you should spend at least several days planning your PM1 quadtree. Version 2.03 (html) (pdf) (ps) to Version 2.04 (html) (pdf) (ps) on 10/17/03. Added additional error checking to DELETE_ROAD. Be sure that you check to make sure that each city exists (otherwise print <CityDoesNotExist>). I am not including <StartAndDestinationSame> because I think it makes more sense to let CREATE_ROAD determine this policy. If CREATE_ROAD were changed to allow self-loops, then DELETE_ROAD would have to be changed as well. By not checking for this error we minimize the dependence of DELETE_ROAD on the behavior of CREATE_ROAD. Corrected spelling/grammar error in B+ tree requirements section. Added a paragraph to B+ tree requirements noting that we won't try to insert multiple types into your B+ tree at the same time. That is, your key will be a String and all objects in the leaves will have the same type. Added clarification to CLEAR_ALL: Should clear the data structures of their values but in the case of the B+ tree, it should not clear the order or the Comparator that was passed to the constructor. (You could still create a brand new B+ tree, but make sure that the new B+ tree has the same order and Comparator as the old tree.) Modified the behavior of MAP_CITY. Rather than checking to see if the specified city has already been mapped, you must look at the spatial data structure and determine if there is a city already mapped at the specified coordinates. It could be the same city or it could be city with a different name but the same coordinates. Regardless, a simple boolean flag on your city will no longer suffice to determine if there is already a city mapped. Changed the <CityAlreadyMapped> error message. Make sure that you match the new text. Added "Code Sharing Rules" subsection (under "Integrity Policy"). Make sure that you comply!!! Version 2.02 (html) (pdf) (ps) to Version 2.03 (html) (pdf) (ps) on 10/11/03. Modified <success> BNF of PRINT_MAP to correct a minor new line issue. Now should accurately reflect the fact that a grey node is the base case. Defined behavior of UNMAP_CITY command when the specified city has roads connected to it. Added a new error message to support this behavior: <CityInUse>. Added missing equal sign to <CityNotMapped> BNF definition. Added O(log n) runtime complexity restriction to MAP_CITY and UNMAP_CITY commands (see command description for details). Noted that the B+ tree does not have to support null key or value parameters. It is acceptable to throw a NullPointerException. See "B+ Tree Design Requirements" for more information. Spell checked the specification. INIT_BPTREE <success> now contains the correct spelling for "Initialized" as does the <BPTreeAlreadyInitialized> error message. Other highlights include "drasitically" and "seperately." Version 2.01 (html) (pdf) (ps) to Version 2.02 (html) (pdf) (ps) on 10/7/03. Removed “\” from string regular expression for input format specs. Fixed typo in “B+ Tree Design Requirements” Added clarification on requirements for SortedMap key/value parameter types to “B+ Tree Design Requirements” Added <InvalidBPTreeOrder> error message Added “inclusive” to guide/key value requirements. Updated wording of “B+ Tree Design Requirements” to reflect use of the terms “guide” and “key” in lecture. Added clarification to the <CityAlreadyExists> error message in CREATE_CITY. Updated B+ tree requirements in PRINT_BPTREE to match updated to INIT_BPTREE. Change instructions of UNMAP_CITY to suggest an implementation with a faster runtime. Added <CityNotMapped> to UNMAP_CITY Clarified <NoRouteExists> error message in SHORTEST_ROUTE command. Version 1.03 (html) (pdf) (ps) to Version 2.01 (html) (pdf) (ps) on 10/3/03. “Cought” and fixed minor typos/spelling errors throughout specification. Added “Interfaces” tutorial. Moved Part 1 BNF from “Output” to “Part 1 -> BNF” Added Part 2 specifications. Many of the error messages have changed slightly since Part 1. Double checked that all of your error messages follow the Part 2 BNF now! Doubles should ALWAYS be printed with 3 decimal places rather than 2. Integers should not have any decimal places. Neither doubles nor integers should have commas. Back to Main page