The first attributes are spatialWidth and
spatialHeight, both Unrestricted Integers, but in the range of
to
). These two attributes define the
rectangular region the spatial data structure can store. Note that
the lower left corner of this region is always
, 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
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 for PM1 quadtree and
for PM3 quadtree. For Part 2, you can safely assume that the pmOrder is always 3.
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.
Parameters: (In output order)
namePossible <output>:
x
y
radius
color
(none)Possible <error> types (In priority order):
duplicateCityCoordinates<success> Example:
duplicateCityName
<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>
(none)Possible <output>:
(none)Possible <error> types:
(none)<success> Example:
<success> <command name=''clearAll'' id=''2''/> <parameters/> <output/> </success>
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'' x=''coordx'' y=''coordy'' color=''color1'' radius=''radius1''/>
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>
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:
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
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>
namePossible <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>
name - filename to save the image toPossible <output>:
(none)Possible <error> types:
(none)<success> Example:
<success> <command name=''saveMap'' id=''6''/> <parameters> <name value=''map_1''/> </parameters> <output/> </success>
xPossible <output>:
y
radius
saveMap (optional) - image filename
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'' 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().
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>
xPossible <output>:
y
radius
saveMap (optional) - image filename
The output will contain one <roadList> tag, which will have one or more <road> child elements. The <road> element will appear as such;Possible <error> types:
<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.
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>
Parameters (In output order):
xPossible <output>:
y
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>
xPossible <output>:
y
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>
xPossible <output>:
y
The output will contain one road tag which is the nearest road. This is an example of a road tag:Possible <error> types:
<road start=''city1'' end=''city2''/>
roadNotFound<success> Example:
<success> <command name=''nearestRoad''/> <parameters> <x value=''1''/> <y value=''2''/> </parameters> <output> <road start=''Annapolis'' end=''Derwood''/> </output> </success>
startPossible <output>:
end
The output will contain one city tag which is the nearest city (isolated or not). This is an example of a city tag:Possible <error> types:
<city name=''city1'' x=''coordx'' y=''coordy'' color=''color1'' radius=''radius1''/>
roadIsNotMapped<success> Example:
noOtherCitiesMapped
<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>
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
precision10 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.
startPossible <output>:
end
saveMap (optional)
saveHTML (optional)
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:Possible <error> types (In priority order):
<road start=''road1'' end=''road2''/>
nonExistentStart<success> Example:
nonExistentEnd
noPathExists
<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.
MM Hugue 2018-06-11