Commands for Part 3

commands

This is the root element of the XML tree for the input files. It contains attributes that will affect the behavior of your command interpreter.

The first attributes are localSpatialWidth and localSpatialHeight, both integer powers of two in the range of $2^1$ to $2^{25}$ . 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 $(0,0)$ 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 $(0,0)$ , 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. The integer attribute g specifies the g (the maximum imbalance) for the AVL-g.

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.

createCity

Creates a city (a vertex) with the specified name, local coordinates, radius, color, and remote coordinates. A city can be successfully created if its name is unique (i.e., there isn't already another city or airport or terminal with the same name), its coordinates are also unique (i.e., there isn't already another city or airport or terminal with the same local AND remote coordinates), and the coordinates are non-negative integers. Names are case-sensitive.

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)

name
localX
localY
remoteX
remoteY
radius
color

Possible <output>:

(none)

Possible <error> types (In priority order):

duplicateCityCoordinates
duplicateCityName

<success> Example:

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

deleteCity

Removes a city with the specified name from data dictionary and the adjacency list. The criteria for success here is simply that the city exists.

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:

name

Possible <output>:

A list of roadUnmapped tags, with a single cityUnmapped tag before it, which follow the specifications below for unmapRoad or unmapCity

Possible <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>

clearAll

Resets all of the structures including the PM Quadtrees, clearing them. This has the effect of removing every metropole, every city, every airport, every terminal, and every road. This command cannot fail, so it should unilaterally produce a <success> element in the output XML.

Parameter:

(none)

Possible <output>:

(none)

Possible <error> types:

(none)

<success> Example:

	<success>
	    <command name="clearAll" id="2"/>
	    <parameters/>
	    <output/>
	</success>

listCities

Prints all cities currently present in the dictionary. The order in which the attributes for the <city> tags are listed is unimportant. However, the city tags themselves must be listed in sorted order either by name or by coordinate, as per the sortBy attribute in the listCities command, whose two legal values are name and coordinate. The ordering by name is descending asciibetical according to the java.lang.String.compareTo() method, and the ordering by coordinate is similar to the one defined in the Part 1 spec, but is modified for Part 3. Coordinate ordering is done by comparing $remoteY$ values first; for cities with the same $remoteY$ value, one city is less than another city if its $remoteX$ value is less than the other. If $remoteX$ and $remoteY$ are identical, then you compare by $localY$ . If both cities have the same $localY$ , then you compare by $localX$ . This command is only successful if there is at least 1 (1 or more) cities in the dictionary.

Note that airports, terminals, and metropoles are not cities and as such should not be included.

Parameter:

sortBy

Possible <output>:

A <cityList> tag will be contained in output and will contain 1 or more city tags of the form:
<city name="city1" localX="coordx" localY="coordy" remoteX="coordX" remoteY="coordY" color="color1" radius="radius1"/>

Possible <error> types:

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>

printAvlTree

Prints the structure of your AVL-g tree as specified in General XML output. This takes no parameters, and airports should not be part of the AVL-g tree.

mapRoad

Inserts a road between the two cities (vertices) named by the start and end attributes in PM quadtree. The obvious error conditions follow: the start or end city does not exist; the start and end are the same; the start and end are not in the same metropole; the road from start to end already exists. However, there are two error conditions you must handle.

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:

start
end

Possible <output>:

The road mapped will cause a roadCreated tag in the <output> and will appear as such:
<roadCreated $start=''city_a''\;\;\;\; end=''city_b''$ />

Possible <error> types (In priority order):

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>

mapAirport

Creates an airport at the specified local and remote coordinates. Note that unlike the good old isolated cities, an airport doesn't get its data from a createCity. It has no color or radius, and you should not store airports in your city data dictionary. An airport cannot have the same name as any other airport, terminal, or city (mapped or unmapped). Furthermore, an airport cannot have the same coordinates in the same metropole as any other airport, terminal, or city (mapped or unmapped). An airport is out of bounds if either its remote coordinates are out of bounds of the remote map or its local coordinates are out of bounds of its local map. Corresponding errors should be returned when any of these errors happen. The command also maps a terminal with the same remote coordinates, specified local coordinates and name, and it maps the road between the terminal and its connecting city. The connecting city must already be mapped in the same metropole. Of course, mapping the terminal and the road may cause any of the error conditions of mapRoad.

Parameters:

name
localX
localY
remoteX
remoteY
terminalName
terminalX
terminalY
terminalCity

Possible <output>:

(none)

Possible <error> types (In priority order):

duplicateAirportName
duplicateAirportCoordinates
airportOutOfBounds
duplicateTerminalName
duplicateTerminalCoordinates
terminalOutOfBounds
connectingCityDoesNotExist
connectingCityNotInSameMetropole
airportViolatesPMRules
connectingCityNotMapped
terminalViolatesPMRules
roadIntersectsAnotherRoad

<success> Example:

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

mapTerminal

Creates a terminal at the specified local and remote coordinates, associated with the specified airport and connected to the specified city. Terminals may not share a name or local coordinates with any other terminal, city, or airport. The terminal must be lie in the remote and the local spatial maps; otherwise it is considered out of bounds. The road between the terminal and its connecting city must also be mapped and may throw errors as in mapRoad. The connecting city and airport must already be present in the spatial map for the command to succeed.

Parameters:

name
localX
localY
remoteX
remoteY
cityName
airportName

Possible <output>:

(none)

Possible <error> types (In priority order):

duplicateTerminalName
duplicateTerminalCoordinates
terminalOutOfBounds
airportDoesNotExist
airportNotInSameMetropole
connectingCityDoesNotExist
connectingCityNotInSameMetropole
connectingCityNotMapped
terminalViolatesPMRules
roadIntersectsAnotherRoad

<success> Example:

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

unmapRoad

Will remove a road and its associated endpoints from the map, unless the endpoint (city) is part of another mapped road. Note that you cannot unmap a road between a terminal and a city. This should throw one of the start or end does not exist errors.

Parameter:

start
end

Possible <output>:

The road unmapped will cause a roadDeleted tag in the <output> and will appear as such:
<roadDeleted $start=''city_a''\;\;\;\; end=''city_b''$ />

Possible <error> types (In priority order):

startPointDoesNotExist
endPointDoesNotExist
startEqualsEnd
roadNotMapped

<success> Example:

	<success>
	    <command name="unmapRoad" id="5"/>
	    <parameters>
	        <start value="Baltimore"/>
	        <end value="Annapolis"/>
	    </parameters>
	    <output>
	        <roadDeleted start="Baltimore" end="Annapolis"/>
	    </output>
	</success>

unmapAirport

Will remove an airport from the map. All terminals associated with the airport will also be unmapped. Of course, the roads connecting the terminals to their cities will also be unmapped.

Parameter:

name

Possible <output>: Each terminal that corresponds to the airport will also be unmapped, producing a terminalUnmapped tag in the output and will appear as such:
<terminalUnmapped name="terminalA"/>

Possible <error> types (In priority order):

airportDoesNotExist

<success> Example:

        <success>
            <command name="unmapAirport" id="5"/>
            <parameters>
                <name value="JFK"/>
            </parameters>

            <output>
                <terminalUnmapped name="T1"/>
            <output/>
        </success>

unmapTerminal

Will remove a terminal from the map. If the associated airport has no remaining mapped terminals, then the airport is also removed. Of course, the roads connecting the terminals to their cities will also be unmapped.

Parameter:

name

Possible <output>: The airport associated with the terminal may be unmapped, producing an airprotUnmapped tag in the output and will appear as such:
<airportUnmapped name="AiroprtA"/>

Possible <error> types (In priority order):

terminalDoesNotExist

<success> Example:

	<success>
	    <command name="unmapTerminal" id="5"/>
	    <parameters>
	        <name value="T1"/>
	    </parameters>
	    <output>
	        <airportUnmapped name="A1"/>
	    <output/>
	</success>

printPMQuadtree

Prints the PMQuadtree corresponding to the command parameter pmOrder, if given, as specified in the General XML output page. Because we have quadrants numbered as: (1) NW, (2) NE, (3) SW, (4) SE, the PM quadtrees are deterministic, you should use the output rules described in the previous section to assure that your XML matches ours.

saveMap

Saves the current map to a file. The image file should be saved with the correct name. It should match our image file: same dimensions, same cities, same colors, same partitions, etc. For part 3, a particular metropole is specified. There are two errors conditions: the remote coordinates are out of bounds of the remote spatial map, or the metropole at the specified remote coordinates is empty. Roads should be drawn as black (java.awt.Color.BLACK) line segments. Everything else from the last part will be the same (e.g. Cities and airports should be drawn as black (java.awt.Color.BLACK) named points) with one exception: To differentiate from Roads, quadtree partitions should now be gray (java.awt.Color.GRAY) crosses.

Parameters (In output order):

remoteX
remoteY
name - filename to save the image to

Possible <output>:

Possible <error> types:

metropoleOutOfBounds
metropoleIsEmpty

<success> Example:

<success>
    <command name="saveMap" id="6"/>
    <parameters>
	<remoteX value="1"/>
        <remoteY value="2"/>
        <name value="map_1"/>
    </parameters>
    <output/>
</success>

globalRangeCities

Lists all the cities present in any spatial map within a radius of a point x,y in the remote map. Any city whose remote coordinates are in range of the specified point is included. Cities on the boundary of the range are included, and x,y are integer coordinates. Only cities that are in the spatial structure, in this case, the PM quadtrees, are relevant to this commmand. Airports and terminals are not considered cities. Keep in mind also that the cities for this command can come from any metropole. Design your structure so that this is efficient; if you use a HashMap and you have to check every possible metropole within the radius , you will be unhappy. <success> will result from the existence of at least one <city> that satisfy the range check condition. If none do, then an <error> tag will be the result. If the radius is 0, but the query point coincides with the remote coordinates of any cities, a list of those cities should be returned. It should be noted that the radius attribute for a city does not factor into this calculation; all cities are considered points.
Parameters (Listed in output order):

remoteX
remoteY
radius

Possible <output>:

The output will contain one <cityList> which will contain the list of cities. This is an example of a city tag:
<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().

Possible <error> types:

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>

nearestCity

Will return the name and location of the closest city to the specified point in the spatial map at the specified metropole only, where the set of valid cities excludes airports and terminals (which are not cities). If the metropole is empty, has no cities, or the remote coordinates are out of bounds of the remote map, then you should return a cityNotFound error. Terminals are not considered airports. To do this correctly, you probably want to use a PriorityQueue-based algorithm-otherwise, you might not be fast enough. In the case of a tie (two cities equally far away from the point), choose the city with the asciibetically greatest name. The ordering by name is descending asciibetical according to the java.lang.String.compareTo() method.

Parameters (In output order):

localX
localY
remoteX
remoteY

Possible <output>:

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>

mst

You will have to construct a minimum spanning tree for all mapped objects using Prim's algorithm, starting at a specified city (not airport or terminal). City-city and city-terminal travel takes place on roads, terminal-airport travel is in a straight line from the terminal to the airport, and airport-airport travel is in a straight line from one metropole to the other (using remote coordinates). Every airport is connected to every other airport. When considering two edges with the same cost, break ties by choosing the one who appears first in reverse asciibetical order.

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)

start

Possible <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 in a similar fashion to the AVL tree - 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>