Part 2 Command Specification

You will build a command decoder with a small set of commands; you will expand it later to accommodate commands required for future parts.

The following is a list of commands you should support for part 2 and a description of the output you should give for each one. Note that for all functions, you should print ''*****\n'' followed by a '' ==> `` and an echo of the command given. For instance, the entire valid output to a hypothtical *wink wink* CLEAR_ALL() command would be:

*****
 ==> CLEAR_ALL()
All structures are cleared.

This is done to negate the effects of input redirection and to assist in grading. Note that although it is done in the samples that will appear later, you are not required to reformat the original command (fixing spacing, for instance) in any way.

The definitions below will use the following standard BNF definitions.

          <dotlist>:=<dot><nl><dotlist>|<dot><nl>
          <dot>:= <name> at (<int>,<int>) color:<color>
          <color>:= RED|GREEN|BLUE|BLACK|WHITE
          <DNE>:=Error: The specified dot does not exist.<nl>

Whenever a <double> appears, it means a floating point decimal number printed with exactly three digits after the decimal place (including trailing zeros as necessary). To do this in java check out the NumberFormat class.

Also, when looking at the list of errors, eg.

     <error>:= <DNE>|<NR>|<AI>|<DC>|<NZ>

the leftmost applicable error should always be the one printed.

INIT_QUADTREE(size)

Sets the upper bounds for the quadtree. After initialization the quadtree should hold points/lines that fall between [0,0] at the southwest/lower left hand corner, and [ $2^{size}, 2^{size}$] in the northeast upper right hand corner. If size is less than 2 or more than 30 print an error. 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>

CREATE_DOT(name, x, y, radius, color) UNCHANGED

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

If a dot with the same name already exists print an error. If a dock 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. If the dot does not exist print an error. If the given dot has already been added to the Adjacency List (via CREATE_PATH()) print an error and do not remove it from the dictionary. If it has already been added to the PM1 (via MAP_SEGMENT()) print an error. Delete from the skiplist should be O(logn). Some slowdown may occur from checks to the adjacency list and PM1 if either is non-empty. This command will likely be used to verify that you can search for points in those structures ;)

          Output summary:
          <output>:=<success>|<error>
          <success>:=Deleted dot <name>.<nl>
         
          <error>:=<DNE>|<AA>|<ZZ>
          <AA>:=Error: Dot <name> has already been added to the Adjacency List.
          <ZZ>:=Error: Dot <name> has already been added to the Quadtree.

LIST_DOTS() UNCHANGED

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.

          Output summary:
          <output>:=<success>|<error>

          <success>:=<dotlist>
          <error>:= Dictionary is empty.<nl>

COLOR_DOT(name,color) UNCHANGED

Changes the color of the dot with the specified name to the color given. The change should be reflected in the map, however only the skiplist should be accessed for this operation.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Color of <name> changed from <oldcolor> to <color>.<nl>
         
          <error>:=<DNE>

CREATE_PATH(name1, name2)

adds a bidirectional path between the dots named to the Adjacency List. If one or both dots does not exist print the <DNE> for the first argument not found. If the segment already exists print an error. This command is not related to the PM1.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Created segment (name1,name2).<nl>
          <error>:=<DNE>|<AI>
         
          <AI>:=Error: The specified segment already exists.

DELETE_PATH(name1, name2)

Deletes the edge between name1 and name2 from the Adjacency list. If either endpoint does not exist, or the edge does not exist print an error. This command is not related to the PM1.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Deleted Segment (name1,name2).<nl>
         
          <error>:=<DNE>|<SDNE>|<AM>
          <SDNE>:=Error: The specified segment does not exist.

SHORTEST_PATH(name1,name2)

Prints the shortest path from the first dot to the second dot based on the segments in the Adjacency List. If either name is not in the dictionary print an error. If there is no path between the two dots (possibly because one of the endpoints was never added to the adjacency list) then print an error. Otherwise print out the shortest path, followed by the total length of the path.

          Output summary:
          <output>:=<success>|<error>

          <success>:= <name1> -> <moredots> <nl>Total length:<double>.<nl>
          <moredots>:= <dotname> -> <moredots>| <name2>
          <error>:= <DNE>|<NP>
          <NP>:= Error: No path exists.

MAP_SEGMENT(name1,name2)

Adds a segment to the PM1.It is possible that name1==name2, this should not be an error. The PM1 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 PM1 unchanged. You may use this error even if the segment intersected is the same as the one you are trying to insert. Further discussion on interesection detection rules will appear on the newsgroup and later versions of the spec. This command is unrelated to the CREATE_PATH command.

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

          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.

COLOR_SEGMENTS(lx,ly,ux,uy,color)

A twist on the old version. This function will first locate all segments in PM1 which OVERLAP the specified inclusive 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 endpoints will not necessarily be in the tree. 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.

PRINT_QUADTREE()

Prints out the PM1 Quadtree map. Be sure to read the section on the PM1 to understand what its structure must be. 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's name, followed by all the dots it is adjacent to in some order. If a black leaf does not contain an endpoint dot, print the segment that passes through it. A tree with only one isolated point created by MAP_SEGMENT(A,A) should have output:

          A:A

IE., a one element tree should look like a leaf, even if not implemented that way.

          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>:=<name>:<namelist>|<segment><nl>
          <white_node>:= 
          <namelist>:= <name><namelist>|<name>
          <segment>:= (<name1>,<name2>)     

          <error>:= Tree is empty.<nl>

DRAW_MAP()

Draws all the points and segments of the pm1 map using the java canvas class. The points should be displayed as in part1, the lines can be plain solid black lines. (If you're good with java graphics you are not required to use the canvas class, but your output should be similar). Your program should stop running until the graphics window is closed(this is the default behavior of the canvas class).

          Output summary:
          <output>:=<success>
          <success>:=Drawing complete.

DRAW_QUADTREE()

Draws the internal partitions of the quadtree, as well as the segments inside it. Do not draw the pretty colorful dots, as they will just get in the way of debugging.

          Output summary:
          <output>:=<success>
          <success>:=Drawing complete.

Web Accessibility