The first attributes are localSpatialWidth and
localSpatialHeight, both integer powers of two in the range of to
. These two attributes define the
rectangular region the local spatial data structures can store. Recall that a local spatial map represents a PMQuadtree for a particular metropole. All local spatial maps will be bounded by the closed rectangle whose lower left corner is
and whose width and height are given by localSpatialWidth and localSpatialHeight.
The second two attributes are remoteSpatialWidth and remoteSpatialHeight, both integer powers of two in the range of 32 bit 2's complement integers. These two attributes define the rectangular region that the remote spatial data structure can store. This refers to the map of remote coordinates and represents coordinates of metropoles relative to other metropoles. The remote spatial map will be bounded by the rectangle whose lower left corner is , whose width and height are given by remoteSpatialWidth and remoteSpatialHeight, whose left and bottom boundaries are closed, and whose top and right boundaries are open.
Pay attention to the difference between the local and remote spatial map rectangular regions. Local spatial maps are closed on all four sides, as in a PM Quadtree. The remote spatial map is open on the top and right boundary, as in a PR Quadtree (you are encouraged to use one for globalRangeCities).
We will not be dealing with negative coordinates.
Observe that these four values have an impact on the success of
the <mapCity> and the <mapRoad> commands, but DO NOT affect the success of the
<createCity> command. Cities can be created in the data
dictionary with local or remote coordinates outside their boundaries. New for part 3, these four values will also have an impact on the success of the <mapAirport> command.
Additionally, the attribute pmOrder specifies which variant of the PM quadtree should be used. Possible values are 1 for PM1 quadtree and 3 for PM3 quadtree. If it is not specified, you may use either PM1 or PM3 quadtree.
Possible errors:
If there is any problem with the attributes in the <command> tag a <fatalError> tag is outputted without a <results> tag, and the program exits.
New for Part 3: city names cannot be the same as those of existing airports or terminals. Errors should be returned if trying to create a city with the same name as an existing airport (duplicateCityName).
Parameters: (In output order)
namePossible <output>:
localX
localY
remoteX
remoteY
radius
color
(none)Possible <error> types (In priority order):
duplicateCityCoordinates<success> Example:
duplicateCityName
<success> <command name="createCity" id="1"/> <parameters> <name value="Annapolis"/> <localX value="12"/> <localY value="14"/> <remoteX value="0"/> <remoteY value="0"/> <radius value="15"/> <color value="red"/> </parameters> <output/> </success>
Note also that unlike last time, a city may be deleted even if it
exists in some quadtree. In the case that it is mapped as a road,
you're required to print a roadUnmapped command that looks
the same as the one below, for all of the roads that have the
specified city as either the start or the end.
Sort the tags in descending asciibetical order by start, tie breaking by end, as usual.
Although other cities may incidentally be unmapped (if the last road
to them is removed), these will not be printed as that is a side effect. You do not need
to handle the case where a city deletion would cause a terminal to be unmapped.
Parameter:
namePossible <output>:
A list of roadUnmapped tags, with a single cityUnmapped tag before it, which follow the specifications below for unmapRoad or unmapCityPossible <error> types (In priority order):
cityDoesNotExist<success> Example:
<success> <command id="1" name="deleteCity"/> <parameters> <name value="Chicago"/> </parameters> <output> <cityUnmapped color="black" name="Chicago" radius="5" localX="133" localY="34" remoteX="1" remoteY="1"/> <roadUnmapped end="Zurich" start="Chicago"/> </output> </success>
(none)Possible <output>:
(none)Possible <error> types:
(none)<success> Example:
<success> <command name="clearAll" id="2"/> <parameters/> <output/> </success>
Note that airports, terminals, and metropoles are not cities and as such should not be included.
Parameter:
sortByPossible <output>:
A <cityList> tag will be contained in output and will contain 1 or more city tags of the form:Possible <error> types:
<city name="city1" localX="coordx" localY="coordy" remoteX="coordX" remoteY="coordY" color="color1" radius="radius1"/>
noCitiesToList<success> Example:
<success> <command name="listCities" id="3"/> <parameters> <sortBy value="name"/> </parameters> <output> <cityList> <city name="Derwood" localX="5" localY="5" remoteX="1" remoteY="2" color="blue" radius="90"/> <city name="Annapolis" localX="19" localY="20" remoteX="1" remoteY="1" color="red" radius="40"/> </cityList> </output> </success>
First, the new road should not intersect any road already mapped at a point other than a vertex of the road (this is a requirement of the PM quadtree family). Also, you must check that inserting this road into the PM quadtree will not cause the tree to be partitioned beyond the smallest size (that is, less than a 1 by 1 partition). This should produce a roadViolatesPMRules error.
For Part 3, a road is in bounds if and only if both cities have remote coordinates that are within the bounds of the remote spatial map, and the line segment connecting both cities' local coordinates intersects the local spatial region.
Parameter:
startPossible <output>:
end
The road mapped will cause a roadCreated tag in the <output> and will appear as such:Possible <error> types (In priority order):
<roadCreated/>
startPointDoesNotExist
endPointDoesNotExist
startEqualsEnd
roadNotInOneMetropole
roadOutOfBounds
roadAlreadyMapped
roadIntersectsAnotherRoad
roadViolatesPMRules
<success> Example:
<success> <command name="mapRoad" id="4"/> <parameters> <start value="Baltimore"/> <end value="Annapolis"/> </parameters> <output> <roadCreated start="Baltimore" end="Annapolis"/> </output> </success>
Parameters:
namePossible <output>:
localX
localY
remoteX
remoteY
terminalName
terminalX
terminalY
terminalCity
(none)Possible <error> types (In priority order):
duplicateAirportName<success> Example:
duplicateAirportCoordinates
airportOutOfBounds
duplicateTerminalName
duplicateTerminalCoordinates
terminalOutOfBounds
connectingCityDoesNotExist
connectingCityNotInSameMetropole
airportViolatesPMRules
connectingCityNotMapped
terminalViolatesPMRules
roadIntersectsAnotherRoad
<success> <command id="5" name="mapAirport"/> <parameters> <name value="AirportB"/> <localX value="2"/> <localY value="14"/> <remoteX value="1"/> <remoteY value="1"/> <terminalName value="TerminalBC"/> <terminalX value="6"/> <terminalY value="10"/> <terminalCity value="C"/> </parameters> <output/> </success>
Parameters:
namePossible <output>:
localX
localY
remoteX
remoteY
cityName
airportName
(none)Possible <error> types (In priority order):
duplicateTerminalName<success> Example:
duplicateTerminalCoordinates
terminalOutOfBounds
airportDoesNotExist
airportNotInSameMetropole
connectingCityDoesNotExist
connectingCityNotInSameMetropole
connectingCityNotMapped
terminalViolatesPMRules
roadIntersectsAnotherRoad
<success> <command id="5" name="mapTerminal"/> <parameters> <name value="terminalB"/> <localX value="2"/> <localY value="14"/> <remoteX value="1"/> <remoteY value="1"/> <cityName value="CityB"/> <airportName value="AirportB"/> </parameters> <output/> </success>
Parameter:
startPossible <output>:
end
The road unmapped will cause a roadDeleted tag in the <output> and will appear as such:Possible <error> types (In priority order):
<roadDeleted/>
startPointDoesNotExist<success> Example:
endPointDoesNotExist
startEqualsEnd
roadNotMapped
<success> <command name="unmapRoad" id="5"/> <parameters> <start value="Baltimore"/> <end value="Annapolis"/> </parameters> <output> <roadDeleted start="Baltimore" end="Annapolis"/> </output> </success>
Parameter:
namePossible <output>: Each terminal that corresponds to the airport will also be unmapped, producing a terminalUnmapped tag in the output and will appear as such:
airportDoesNotExist<success> Example:
<success> <command name="unmapAirport" id="5"/> <parameters> <name value="JFK"/> </parameters> <output> <terminalUnmapped name="T1"/> <output/> </success>
Parameter:
namePossible <output>: The airport associated with the terminal may be unmapped, producing an airprotUnmapped tag in the output and will appear as such:
terminalDoesNotExist<success> Example:
<success> <command name="unmapTerminal" id="5"/> <parameters> <name value="T1"/> </parameters> <output> <airportUnmapped name="A1"/> <output/> </success>
remoteXPossible <output>:
remoteY
name - filename to save the image to
Possible <error> types:
metropoleOutOfBounds<success> Example:
metropoleIsEmpty
<success> <command name="saveMap" id="6"/> <parameters> <remoteX value="1"/> <remoteY value="2"/> <name value="map_1"/> </parameters> <output/> </success>
remoteXPossible <output>:
remoteY
radius
The output will contain one <cityList> which will contain the list of cities. This is an example of a city tag:Possible <error> types:
<city name="city1" localX="coordx" localY="coordy" remoteX="coordX" remoteY="coordY" color="color1" radius="radius1"/>
The cities should be printed in descending asciibetical order of the names according to java.lang.String.compareTo().
noCitiesExistInRange<success> Example:
<success> <command name="globalRangeCities" id="7"/> <parameters> <remoteX value="3"/> <remoteY value="3"/> <radius value="100"/> </parameters> <output> <cityList> <city name="Derwood" localX="20" localY="40" remoteX="4" remoteY="4" color="blue" radius="23"/> <city name="Annapolis" localX="20" localY="30" remoteX="3" remoteY="3" color="red" radius="12"/> </cityList> </output> </success>
localXPossible <output>:
localY
remoteX
remoteY
The output will contain one city tag which is the nearest city. This is an example of a city tag:
<city name="city1" localX="coordx" localY="coordy" remoteX="coordX" remoteY="coordY" color="color1" radius="radius1"/>
Possible <error> types:
cityNotFound<success> Example:
<success> <command name="nearestCity" id="8"/> <parameters> <localX value="1"/> <localY value="2"/> <remoteX value="3"/> <remoteY value="3"/> </parameters> <output> <city name="Annapolis" localX="20" localY="30" remoteX="3" remoteY="3" color="red" radius="12"/> </output> </success>
The mst command takes a starting city, and outputs the tree produced. The root will be the starting vertex. Each element's children should appear in descending asciibetical order by name.
Note that you must use Prim's algorithm for this, otherwise it's possible that you produce a different minimum spanning tree.
Parameters: (In output order)
startPossible <output>:
A <mst> tag with attribute distanceSpanned will be contained in output. The value of distanceSpanned is the sum of all of the edges in the minimum spanning tree. The first and only child of the mst tag is a <node> tag with attribute name containing the name of the starting city. The rest of the tree is outputted as shown below - every <node> tag contains its children in reverse asciibettical order. Just like the root node, each of the children is represented by a <node> tag with attribute name containing the name of the city, terminal, or airport of the node in the minimum spanning tree.Possible <error> types (In priority order):
cityDoesNotExist<success> Example:
<success> <command name="mst" id="9"/> <parameters> <start value="B"/> </parameters> <output> <mst distanceSpanned="35.032"> <node name="B"> <node name="A"> <node name="TerminalAB"> <node name="AirportA"> </node> </node> </node> </node> </mst> </output> </success>