Commands for Part 2

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 spatialWidth and spatialHeight, both Unrestricted Integers, but in the range of $2^{1}$ to $2^{25}$). These two attributes define the rectangular region the spatial data structure can store. Note that the lower left corner of this region is always $(0,0)$, the origin, as we will not be dealing with negative city coordinates in this project. Thus, the spatial structure's bounding volume is the rectangle whose lower left corner is $(0,0)$ and whose width and height are given by these two parameters. You must setup your spatial structure to be centered accordingly. Note that although all of our coordinates will be given as integers, you may need to center your spatial structure around a coordinate that is not an integer; so, make sure you plan accordingly.

Observe that these two 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 coordinates outside the boundaries of this range, on the boundary as well as inside this range. For Part 2 and Part 3, Cities on the top and right boundaries of this range can also be ``mapped'' or inserted into the PM quadtree.

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. For Part 2, you can safely assume that the pmOrder is always 3.

The attribute leafOrder specifies the order of the leaves in your DodekaTrie. See the DodekaTrie section for more detail.

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, coordinates, radius, and color (the last two attributes will be used in later project parts). A city can be successfully created if its name is unique (i.e., there isn't already another city with the same name) and its coordinates are also unique (i.e., there isn't already another city with the same $(x,y)$ coordinate), and the coordinates are non-negative integers. Names are case-sensitive.

Parameters: (In output order)

name
x
y
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''/>
                        <x value=''12''/>
                                <y value=''14''/>
                                        <radius value=''15''/>
                                                <color value=''red''/>
                                                    </parameters>
    <output/>
</success>

clearAll

Resets all of the structures including the PM Quadtree, clearing them. This has the effect of removing every city 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 ordered 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 name according to the java.lang.String.compareTo() method, and the ordering by coordinate is discussed in the Part 1 spec. To reiterate, coordinate ordering is done by comparing $y$ values first; for cities with the same $y$ value, one city is less than another city if its $x$ value is less than the other. This command is only successful if there is at least 1 (1 or more) cities in the dictionary.

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'' x=''coordx'' y=''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'' x=''5'' y=''5'' color=''blue'' radius=''90''/>
                                                        <city name=''Annapolis'' x=''19'' y=''20'' color=''red'' radius=''40''/>
                                                                </cityList>
                                                                    </output>
                                                                    </success>

printDodekaTrie

Takes no arguments, and merely prints the structure of your DodekaTrie using the rules from Section 7. This function is used to serialize your DodekaTrie tree so that its correctness can be checked.

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 or are the same; the start or end vertex is an isolated city (see below); the road from start to end already exists; the road is outside of the spatial area defined by (0,0) and spatialWidth/spatialHeight. Note that it is possible for (part of) a road to be within the spatial area, but not its endpoints. However, there are two other potential error conditions you must handle when adding a road to the spatial map, but not until part 3.

Note: THIS IS FOR Part 3: 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. We would prefer to have you implement this correctly the first time; but, experience has shown that not everyone will be comfortable doing this the first time through. Thus, the correct functionality is included in the spec, but will not be fully tested until Part 3.

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
startOrEndIsIsolated
roadAlreadyMapped
roadOutOfBounds

<success> Example:

    <success>
        <command name=''mapRoad'' id=''4''/>
            <parameters>
                    <start value=''Baltimore''/>
                            <end value=''Annapolis''/>
                                </parameters>
    <output>
        <roadCreated start=''Baltimore'' end=''Annapolis''/>
            </output>
            </success>

mapCity

maps an isolated city that is not an endpoint of any roads, i.e., the city is not connected to any roads. An isolated city cannot be turned into a normal city and vice versa without being unmapped from the spatial structure first. Thus, when trying to map an isolated city to the endpoints of a road, cityAlreadyMapped error should be returned. Parameter:

name

Possible <output>:

(none)

Possible <error> types (In priority order):

nameNotInDictionary
cityAlreadyMapped
cityOutOfBounds

<success> Example:

<success>
    <command name=''mapCity'' id=''4''/>
        <parameters>
                <name value=''Baltimore''/>
                    </parameters>
                        <output/>
                        </success>

printPMQuadtree

prints the PMQuadtree corresponding to the command parameter pmOrder. 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 established in Section 7 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. 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 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):

name - filename to save the image to

Possible <output>:

(none)

Possible <error> types:

(none)

<success> Example:

  <success>
      <command name=''saveMap'' id=''6''/>
          <parameters>
                  <name value=''map_1''/>
                      </parameters>
                          <output/>
                          </success>

rangeCities

Lists all the cities present in the spatial map within a radius of a point x,y in the spatial map. Cities on the boundary of the circle are included, and x,y are integer coordinates. That is, only cities that are in the spatial structure, in this case, the PM quadtree, are relevant to this commmand. <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. In the special case where the radius is 0 and there is a city at the range point, this city should be listed. It should be noted that the radius attribute for a city does not factor into this calculation; all cities are considered points.
If the saveMap attribute is present, the current map will be saved to an image file (see saveMap). The image file should be saved with the correct name. It should match our image file: same dimensions, same cities, etc. How to keep track of your graphic map is discussed in saveMap. Printing it out is discussed there too. The main difference with saveMap is that the image file should have a blue (java.awt.Color.BLUE) unfilled circle centered at the (x,y) values passed in with the radius passed in. Because CanvasPlus does not behave well when shapes exceed the bounds of the spatial map, the saveMap attribute will only be present when an entire range circle lies inclusively within the bounds of the spatial map.

Parameters (Listed in output order):

x
y
radius
saveMap (optional) - image filename

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'' x=''coordx'' y=''coordy'' color=''color1'' radius=''radius1''/>
The <city> tag is used for both isolated cities and non-isolated ones. 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=''rangeCities'' id=''7''/>
        <parameters>
                <x value=''1''/>
                        <y value=''1''/>
                                <radius value=''100''/>
                                    </parameters>
                                        <output>
                                                <cityList>
                                                            <city name=''Derwood'' x=''20'' y=''40'' color=''blue'' radius=''23''/>
                                                                        <city name=''Annapolis'' x=''20'' y=''30'' color=''red'' radius=''12''/>
                                                                                </cityList>
                                                                                    </output>
                                                                                    </success>

rangeRoads

Lists all the roads present in the spatial map that intersect the circle defined by the given radius and point (x, y). Roads which are tangent to the circle are considered in the range, i.e. intersection can occur at just one point. x and y are integer coordinates. <success> will result from the existence of at least one <road> that satisfies the range check condition. If none do, then an <error> tag will be the result. If the radius is 0 and there is a city at the range point, roads emanating from (or terminating at) that city will be listed. If the saveMap attribute is present, the current map will be saved to an image file (see saveMap), with features looking exactly like those of rangeCity.

Parameters (In output order):

x
y
radius
saveMap (optional) - image filename

Possible <output>:

The output will contain one <roadList> tag, which will have one or more <road> child elements. The <road> element will appear as such;
<road start=''city_a'' end=''city_b''/>
The roads should be printed in descending asciibetical order of the names according to java.lang.String.compareTo(), with the rule that roads should be compared first by the names of their start points. For two roads with the same starting city, an road is less than another road if its endpoint is asciibetically greater than the endpoint of the other road.
If the saveMap attribute is present, the current map will be saved to an image file (see saveMap) just like in rangeCities.

Possible <error> types:

noRoadsExistInRange

<success> Example:

        <success>
            <command id=''18'' name=''rangeRoads''/>
            <parameters>
                <x value=''512''/>
                <y value=''512''/>
                <radius value=''300''/>
            </parameters>
            <output>
                <roadList>
                    <road end=''City6'' start=''City5''/>
                    <road end=''City6'' start=''City3''/>
                    <road end=''City5'' start=''City3''/>
                </roadList>
            </output>
        </success>

nearestCity

Will return the name and location of the closest city to the specified point in the spatial map, where the set of valid cities excludes isolated cities. To do this correctly, you may want to use the PriorityQueue from part 1-otherwise, you might not be fast enough. The ordering by name is asciibetical according to the java.lang.String.compareTo() method. So, to repeat, case of a tie (two cities equally far away from the point), choose the city with the asciibetically greatest name.

Parameters (In output order):

x
y

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'' x=''coordx'' y=''coordy'' color=''color1'' radius=''radius1''/>

Possible <error> types:

cityNotFound

<success> Example:

<success>
    <command name=''nearestCity'' id=''8''/>
        <parameters>
                <x value=''1''/>
                        <y value=''2''/>
                            </parameters>
                                <output>
                                        <city name=''Annapolis'' x=''20'' y=''30'' color=''red'' radius=''12''/>
                                            </output>
                                            </success>

nearestIsolatedCity

Will return the name and location of the closest isolated city to the specified point in the spatial map. To do this correctly, you may want to use the PriorityQueue from part 1-otherwise, you might not be fast enough for large data sets. 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 asciibetical according to the java.lang.String.compareTo() method.

Parameters (In output order):

x
y

Possible <output>:

The output will contain one city tag which is the nearest city. This is an example of a city tag:
<isolatedCity name=''city1'' x=''coordx'' y=''coordy'' color=''color1'' radius=''radius1''/>

Possible <error> types:

cityNotFound

<success> Example:

<success>
    <command name=''nearestIsolatedCity'' id=''8''/>
        <parameters>
                <x value=''1''/>
                        <y value=''2''/>
                            </parameters>
    <output>
        <isolatedCity name=''Annapolis'' x=''20'' y=''30'' color=''red'' radius=''12''/>
            </output>
            </success>

nearestRoad

Will output the nearest road to the specified point in the spatial map. Ties will be broken by applying the descending asciibetical rule to the start city names, then end city names. Again, this is done using thejava.lang.String.compareTo() method.



Parameters (In output order):

x
y

Possible <output>:

The output will contain one road tag which is the nearest road. This is an example of a road tag:
<road start=''city1'' end=''city2''/>

Possible <error> types:

roadNotFound

<success> Example:

<success>
    <command name=''nearestRoad''/>
        <parameters>
                <x value=''1''/>
                        <y value=''2''/>
                            </parameters>
                                <output>
                                        <road start=''Annapolis'' end=''Derwood''/>
                                            </output>
                                            </success>

nearestCityToRoad

Will return the name and location of the closest city in the spatial map to the specified road in the spatial map. The road is specified by the start and end cities. Since roads are undirected, specifying [start=A,end=B] is identical to specifying [start=B,end=A]. Obviously the city will not be one of the endpoints of the road or this command would be trivial. Ties broken by the city with the asciibetically greater name.

Parameters (In output order):

start
end

Possible <output>:

The output will contain one city tag which is the nearest city (isolated or not). This is an example of a city tag:
<city name=''city1'' x=''coordx'' y=''coordy'' color=''color1'' radius=''radius1''/>

Possible <error> types:

roadIsNotMapped
noOtherCitiesMapped

<success> Example:

<success>
    <command name=''nearestCityToRoad''/>
        <parameters>
                <start value=''Annapolis''/>
                        <end value=''Derwood''/>
                            </parameters>
                                <output>
                                        <city name=''CollegePark'' x=''20'' y=''30'' color=''red'' radius=''12''/>
                                            </output>
                                            </success>

shortestPath

Prints the shortest path and direction traveled (from the perspective of someone driving down the current road) between the cities named by the start and end attributes, where the length of the road is the Euclidean distance between the cities. Should a tie be encountered when constructing the shortest path, the vertex with the smaller asciibetical city name will be selected as appropriate using the java.lang.String.compareTo() method.

Success is reported if such a path exists. We have no plans to test this on unconnected graphs, and will restore any points lost should this happen by accident.

The <success> element in response to this command is empty and has no message attribute. It has one child element, <path>, which itself has a sequence of road and direction elements (<right/>, <left/>, and <straight/>) as children. The <path> element has two attributes which must be set: length which reports the double precision¹¹ length of the total path, rounded to 3 decimal places, and hops which indicates the number of unique edges traveled to get from the start to the end.

To make things more fun, we are going to use CanvasPlus sometimes when calling shortestPath. If a saveMap attribute is present, you need to create a new CanvasPlus object containing the shortestPath and save it to an image file with the value of the saveMap attribute. Here's what the shortest path should look like: You should include a black rectangle for the bounds of the spatial map just like in saveMap. All cities and roads contained by the path should be in this visual map. The start point should be green (java.awt.Color.GREEN). The end point should be red (java.awt.Color.RED). All cities in between and all connecting roads should be blue (java.awt.Color.BLUE). Since the customer doesn't care about how the spatial map is stored, we don't need to see the rest of the spatial map (partitions and other cities and roads). To reiterate, to keep it simple, just create a new CanvasPlus object and include on the cities and roads on the path. Lastly, remember to dispose of the CanvasPlus object when you are done with it.

Finally, to make things even make things even more fun, we are going to turn your shortestPath output into readable HTML. If a saveHTML attribute is present, you follow the same steps you did with the saveMap attribute instructions, but now name it the value of the saveHTML attribute. You need to do this because the HTML document will need your shortestPath image and your success node. But don't worry about any extra work here, it's all pretty much been done for you. First of all we need to make a new Document object and make a copy of our success node since it belongs to our results document. Then we just need to transform the XML using an XSLT (eXtensible Stylesheet Language Transformations-don't worry if you've never heard of this) file that I wrote into a pretty HTML document. Since Java's XML outputter prints attributes in alphabetical order it can be confusing to read them so hopefully this will make it easier for you to test your Dijkstra classes. The code for you to do this is below (and the XSLT file should be in the newest iteration of the JAR file):

org.w3c.dom.Document shortestPathDoc = XmlUtility.getDocumentBuilder().newDocument();
org.w3c.dom.Node spNode = shortestPathDoc.importNode(successNode, true);
shortestPathDoc.appendChild(spNode);
XmlUtility.transform(shortestPathDoc, new File(``shortestPath.xsl''), new File(saveHTMLName + ``.html''));

Note that both saveMap and saveHTML attributes could be present without a conflict, instead, two image files and an HTML file would be produced. As always, examples will be provided.

Parameters: (In output order)

start
end
saveMap (optional)
saveHTML (optional)

Possible <output>:

A <path> tag with attributes length, hops will be contained in output and will contain 1 <road> tag, followed by zero or more sequences of a direction element followed by a road element. These should be in the order of the path taken and will appear as follows:
<road start=''road1'' end=''road2''/>

Possible <error> types (In priority order):

nonExistentStart
nonExistentEnd
noPathExists

<success> Example:

  <success>
      <command name=''shortestPath'' id=''9''/>
          <parameters>
                  <start value=''Annapolis''/>
                          <end value=''Derwood''/>
                              </parameters>
                                  <output>
                                          <path length=''12.000'' hops=''4''>
                                                      <road start=''Annapolis'' end=''Bowie''/>
                                                                  <left/>
                                                                              <road start=''Bowie'' end=''Washington''/>
                                                                                          <right/>
                                                                                                      <road start=''Washington'' end=''Bethesda''/>
                                                                                                                  <straight/>
                                                                                                                              <road start=''Bethesda'' end=''Derwood''/>
                                                                                                                                      </path>
                                                                                                                                          </output>
                                                                                                                                          </success>

Do note: except for one input set per project part, we will provide syntactically error-free XML, which means that we will only test your error checking on one set of test inputs. However, we will check the syntactic validity of every output file you provide; so make sure that your output XML can be validated against the schema we provide for each part, or you risk losing substantial credit.