Commands

Input will be provided via input redirection. In other words, input files will be passed to your program via the standard input stream (System.in).

The basic structure of the input XML will be a document whose root tag is <commands>. <commands> will contain, as its children, any series of the other commands. All commands (for Part 1 at least) will be single empty elements (recall that an empty element is one that has no children) which contain zero or more attributes. Input values that are numeric will always be integers. The schema and sample inputs will probably be sufficient in describing the input format. If the schema does not match the input a <fatalError> tag is printed without a <results> tag. Of most interest is the success and error conditions for each command and the corresponding messages each should provide. Here's the list:

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 attributes are spatialWidth and spatialHeight, both powers of 2, but in the range of 32 bit 2's complement integers. 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> command, butDO 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. However, only cities on the left and bottom boundaries of this range can be ``mapped'' or inserted into the PR 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.

createCity

Creates a city (a vertex) with the specified name, coordinates, radius, and color. 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).

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

deleteCity

Removes a city with the specified name from data dictionary. The criteria for success here is simply that the city exists. Note that if the city has been mapped, then it must be removed from the PR quadtree first, and then deleted.

Parameter:

name

Possible <output>:

If the city is in the spatial data structure, a cityUnmapped tag will appear as:

   <cityUnmapped name=``city1'' x=``coordx'' y=``coordy'' color=``color1'' radius=``radius1''/>

Possible <error> types (In priority order):

cityDoesNotExist

<success> Example:

<success>
    <command name=``deleteCity''/>
    <parameters>
        <name value=``Annapolis''/>
    </parameters>
    <output/>
</success>

clearAll

Resets all of the structures including the PR Quadtree, clearing them. This has the effect of removing every city. 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''/>
    <parameters/>
    <output/>
</success>

listCities

Prints all cities currently present in the dictionary. The sortBy attribute in the listCities command indicates that the city tags will be listed according to either the name or the coordinates of the city. When given a sortBy parameter of name, the city tags are sorted asciibetically, according to the java.lang.String.compareTo() method and listed in descending order. When the sortBy paremeter is coordinate, the city tags should be sorted using the comparator discussed in Section 6.1 and output in ascending order. That is, 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. The order in which the attributes for the <city> tags are listed is unimportant. 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''/>
    <parameters>
        <sortBy value=``name''/>
    </parameters>
    <output>
        <cityList>
            <city name=``Derwood'' x=``19'' y=``20'' color=``red'' radius=``40''/>
            <city name=``Annapolis'' x=``5'' y=``5'' color=``blue'' radius=``90''/>
        </cityList>
    </output>
</success>

mapCity

Inserts the named city into the spatial map.

Parameter:

name

Possible <output>:

(none)

Possible <error> types:

nameNotInDictionary
cityAlreadyMapped
cityOutOfBounds

<success> Example:

<success>
    <command name=``mapCity''/>
    <parameters>
        <name value=``Annapolis''/>
    </parameters>
    <output/>
</success>

unmapCity

Removes the named city from the spatial map.

Parameter:

name

Possible <output>:

(none)

Possible <error> types:

nameNotInDictionary
cityNotMapped

<success> Example:

<success>
    <command name=``unmapCity''/>
    <parameters>
        <name value=``Annapolis''/>
    </parameters>
    <output/>
</success>

printPRQuadtree

Prints the PR quadtree. Since PR quadtrees are deterministic, your XML should match exactly the primary input/output.

Parameter:

(none)

Possible <output>:

A <quadtree> tag will be contained within output and will contain several <gray> <white> and <black> nodes.
The first node in the quadtree will be the root node, this node can be gray or black, then the rest of the PR Quadtree follows. Remember, the exact structure of the quadtree will be represented by the XML output.

<gray>

Nodes will contain 4 children nodes with ordering decided by the order of the nodes within the actual gray node in your PR Quad Tree.<gray> nodes will have the attributes x and y, which are integers corresponding to the center point of that gray and identify the location of the gray node. They will appear as such:

<gray x=``72'' y=``40''>
    ...
</gray>

<black>

Nodes represent a mapped city in your PR Quadtree, they have the attributes name, x and y. These will identify the city name and location of the city in the black node, and will appear as such:
<black name=``Chicago'' x=``81'' y=``47''/>

<white>

Nodes represent an empty node in your PR Quadtree and will appear as such;
<white/>

Possible <error> types:

mapIsEmpty

<success> Example:

<success>
    <command name=``printPRQuadtree''/>
    <parameters/>
    <output>
        <quadtree>
            <gray x=``64'' y=``64''>
                <white/>
                <white/>
                <white/>
                <gray x=``96'' y=``32''>
                    <gray x=``80'' y=``48''>
                        <white/>
                        <white/>
                        <gray x=``72'' y=``40''>
                            <black name=``Boston'' x=``71'' y=``42''/>
                            <white/>
                            <white/>
                            <black name=``Baltimore'' x=``76'' y=``39''/>
                        </gray>
                        <gray x=``88'' y=``40''>
                            <black name=``Chicago'' x=``81'' y=``47''/>
                            <white/>
                            <black name=``Atlanta'' x=``84'' y=``33''/>
                            <white/>
                        </gray>
                    </gray>
                    <black name=``Los_Angeles'' x=``118'' y=``33''/>
                    <black name=``Miami'' x=``80'' y=``25''/>
                    <white/>
                </gray>
            </gray>
        </quadtree>
    </output>
</success>

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. How to keep track of your graphic map is discussed in the previous section. Printing it out is discussed there too.

Parameters (In output order):

name - filename to save the image to

Possible <output>:

(none)

Possible <error> types:

(none)

<success> Example:

<success>
    <command name=``saveMap''/>
    <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 PR quadtree, are relevant to this commmand.

<success> will result from the existence of at least one <city> that satisfies the range check condition. If none does, then an <error> tag will be the result. If the radius is 0 and no city occupies the point x,y, then <error> tag is the result.

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 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 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''/>
    <parameters>
        <x value=``1''/>
        <y value=``1''/>
        <radius value=``100''/>
    </parameters>
    <output>
        <cityList>
            <city name=``Derwood'' x=``20'' y=``30'' color=``red'' radius=``12''/>
            <city name=``Annapolis'' x=``20'' y=``40'' color=``blue'' radius=``23''/>
        </cityList>
    </output>
</success>

nearestCity

Will return the name and location of the closest city in the spatial map to the specified point in space. To do this correctly, you may want to use an algorithm using a PriorityQueue, such as www.cs.umd.edu/users/meesh/cmsc420/ContentBook/FormalNotes/neighbornotes/incnear.pdf or

www.cs.umd.edu/users/meesh/cmsc420/ContentBook/FormalNotes/neighbornotes/incnear2.pdf-otherwise, you might not be fast enough. If two or more cities are equidistant from the specified point in space, then output the city with the larger name in asciibetical order. That is, if city dark1 and city duck1 are the same distance from the specified point, then the duck1 would be given as the nearest city.

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:

mapIsEmpty

<success> Example:

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

The the XML specification appears in www.cs.umd.edu/users/meesh/cmsc420/ProjectBook/part1/part1in.xsd. Do note: except for one set of tests per project, 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 produced from your code.