- INIT_QUADTREE(size)
- Sets the size for the quadtree.
After
initialization the quadtree should hold points/lines that fall between [0,0] at the
southwest/lower left hand corner, and [
] in the northeast upper
right hand corner. If size is less than 2 or more than 30 print an error. For
simplicity your quadtrees should have a minimum partition size of 1x1. In
particular, this means that your trees cannot hold adjacent coordinates.
This command will always precede the first command which requires the quadtree. This
command is only valid the first time it is successfully called (out of range is
not a successful call). If an attempt is made to reinitialize the tree, print an
error.
Output summary:
<output>:=<success>|<error>
<success>:=Quadtree initialized.<nl>
<error>:=<OOR>|<INIT>
<OOR>:=Error: size out of range.<nl>
<INIT>:=Error: The Quadtree has already been initialized.<nl>
- MAP_SEGMENT(name1,name2)
- Adds a segment to the PM3. It is possible
that name1==name2,
this should not be an error. The PM3 should be able to know whether any given
point has a path to itself or not. There is one further error to detect. If the segment
intersects a segment already in the tree(except for shared endpoints),
print an error and leave the PM3 unchanged. If a subdivision smaller than 1x1
would be forced then this should also be treated as an intersection.
You may use this error even if the segment intersected is the same as the one you
are trying to insert(ie. trying to remap a segment that was already in the tree).
Output summary:
<output>:=<success>|<error>
<success>:=Mapped segment (name1,name2).<nl>
<error>:=<DNE>|<ID>
<ID>:=Error: Intersection detected.
- UNMAP_SEGMENT(name1,name2)
- Deletes a segment from the PM3. If the points do
not exist, or the segment does not exist, print an error. If after the operation
an endpoint would be left with no adjacent segments then it should also be completely
removed from the tree. The tree should be collapsed so that it is minimal- which
basically means that the tree should look as if the segment had never been in the
tree to begin with. (Some collapsing will need to be done). Remember that if
(A,A) is explicitly added to the tree via MAP_SEGMENT, then
(A,A) must be unmapped before A is removed. Likewise A should never be an
isolated point in the tree unless (A,A) was explicitly added.
Output summary:
<output>:=<success>|<error>
<success>:=Unmapped Segment (name1,name2).<nl>
<error>:=<DNE>|<SNF>
<SNF>:=Error: The specified segment was not found on the map.
- NEAREST_SEG_TO_POINT(x,y)
- Finds the Segment in the PM3 closest to the specified point, along
with the distance to the segment. If multiple
segments are the same distance from the point pick your favorite. If
the quadtree is empty print an error. Print the endpoints of the segment
in coordinate order.
Output summary:
<output>:=<success>|<error>
<success>:= Nearest segment: <segment>. Distance: <double>.<nl>
<segment>:= (<name1>,<name2>)
<error>:= Tree is empty.<nl>
- PRINT_QUADTREE()
- Prints out the PM3 Quadtree map.
When printing you must print in the following order: Northwest,
Northeast, Southwest, Southeast.
If you reach a leaf with a dot in it you should print the dot, followed
by all the segments in the quadrant in coordinate order (more detail below).
If a black leaf does not contain an
endpoint dot, just print the segments.
Output summary:
<output>:=<success>|<error>
<success>:= <pmtree><nl>
<pmtree>:=<black_node><nl>|<white_node><nl>|<nl><grey_node>
<grey_node>:= NW <pmtree> NE <pmtree> SW <pmtree> SE <pmtree>
<black_node>:=<dot>:<seglist>|<seglest>
<white_node>:=
<error>:= Tree is empty.<nl>
Clarifying the description above, for a black node you should first print the
endpoint in that segment if there is one, followed by a list of all the segments in the
quadrant. For each segment the dots corresponding to name1 and name2 should be
sorted in the coordinate order used in p2. The edges themselves in the seglist
should be sorted in
coordinate order based on the first endpoint (ties broken by the second endpoint),
even though it is the String name
that is printed.
- EXIT()
- ends the program. Your program shoudl also naturally terminate
(with no exit message) when end-of-file is reached. Print a goodbye message (as
specified below) and exit the command interpreter.
Output summary:
<success>:=Have a nice day!
- CREATE_DOT(name, x, y, radius, color)
- creates a 'dot' object with the
appropriate name, coordinates, radius, and color.
The dot will then be added to a SkipList sorted based on the name (the
data dictionary) and to one based on the coordinates. The latter structure is
used to check for duplicate coordinates.
Coordinates will be non-negative. This should be an O(logn) operation where n is
the number of dots already in the dictionary. The dots should be stored in an
asciibetically sorted SortedMap(SkipList for project 2).
If a dot with the same name already exists print an error. If a dot already exists
at the specified coordinates print an error.
Output summary:
<output>:=<success>|<error>
<success>:=Created dot <dot>.<nl>
<error>:=<AE>|<DC>
<AE>:=Error: Dot <name> already exists.<nl>
<DC>:=Error: Dot <other\_dot\_name> already exists at the specified coordinates.
- DELETE_DOT(name)
- Removes the dot with the given name from the data dictionary(and the coordinate checking dictionary).
If the dot does not exist print an error.
Delete should be O(logn).
Output summary:
<output>:=<success>|<error>
<success>:=Deleted dot <name>.<nl>
<error>:=<DNE>
- LIST_DOTS()
- Lists all dots in the data dictionary
in increasing asciibetical order. This function will be used as a measure of
success for the CREATE_DOT function.
(Hint: You should probably be using SortedMap.values().iterator() to implement this;)
Output summary:
<output>:=<success>|<error>
<success>:=<dotlist>
<error>:= Dictionary is empty.<nl>
- COLOR_DOT(name,color)
- Changes the color of the dot with the specified
name to the color given. The change should be reflected in the map, however the
PM3 itself should not be accessed for this operation.
Output summary:
<output>:=<success>|<error>
<success>:=Color of <name> changed from <oldcolor> to <color>.<nl>
<error>:=<DNE>
- COLOR_SEGMENTS(lx,ly,ux,uy,color)
- This function
will first locate all segments in PM3 which OVERLAP (inclusive) the specified
rectangular region(determined by (lx,ly),(lx,uy),(ux,ly),(ux,uy)).
Then it will change the color of the endpoints of those segments to the color
specified. The segment endpoints will not necessarily be within the rectangle.
Print the
number of unique segments matched.
Success can also be determined with the DRAW_MAP or LIST_DOTS commands
Output summary:
<output>:=<success>
<success>:=Update complete. Found <int> segments.
- SET_DRAW_MODE(mode, xsize, ysize, step)
- Changes the mode for all graphical output commands. The mode will be either
"TEXT", "DRAW", or "BOTH". If BOTH, then you should print text before drawing to
the screen. "TEXT" will be the mode used when grading, the others will
mostly be for your benefit in debugging and for impressing your friends. If
the input is invalid (I will not test this) stay in the current mode. To be safe
I will always call this function before using a drawing command, so you may use
whatever default you find handiest.
The parameters xsize and ysize will specify the size of the view window used on the map. When
drawing a frame the current coordinate should be treated as the center of
the view window, with ysize units above and below the center and xsize units to the left and
right so that the actual window is 2*xsize by 2*ysize. The step is only used
for animation commands and says how far
to move each frame in the current direction of travel(always east/right now).
If you are following
a particular line and the next step will cause you to pass the end of that line
then you should have a frame exactly at that endpoint instead.
- DRAW_FRAME(xpos,ypos)
- Processes the first frame only of the ANIMATE_HORIZONTAL_PATH command,
centered at (xpos,ypos). Equivalent to ANIMATE_HORIZONTAL_PATH(xpos,xpos,ypos).
Output summary:
<output>:=<optional textoutput><nl><success>
<success>:=Draw Frame Complete.<nl>
<optional textoutput>:=<frame>
- ANIMATE_HORIZONTAL_PATH(xmin,xmax,ypos)
- The first
frame should be centered at (xmin,ypos),
and then you should procede right moving 'step' units each frame (as defined
SET_DRAW_MODE)
till reaching a frame centered at (xmax, ypos).
There is no such thing as failure, and there are no bounding requirements for
xmin,xmax, and ypos (well, they will be non negative). If the
current mode is BOTH or TEXT then each frame should also have a textual version
printed according to the BNF.
For P3 the frame content will change to now be a list of segments rather than a list
of points, which overlap the rectangle corresponding to each frame (boundary edges inclusive)
and you will have to use the PM3 rather than the SkipList to select the points.
(You may need a skiplist to do a secondary sort to print the segments in the correct order).
Essentially, for each frame you will have to select a rectangle of lines from the PM3, sort
it appropriately, and print the lines. You will have to perform a similar rectangle search
for the COLOR_SEGMENTS command. For this reason I recommend you write a single
function that can get rectangles of lines and return them in a set of some kind to
be operated on :) Your search is expected to be as efficient as possible for a PM3.
Output summary:
<output>:=<optional textoutput><nl><success>
<success>:=Animation Complete.<nl>
<optional textoutput>:=<framelist>
if P1.x < P2.x or (P1.x==P2.x and P1.y<P2.y)
P1>P2
otherwise
Whenever a