Part 1 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 1 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 CLEAR_ALL() is

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

The sample output should make this clear. 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(not in this part, but it will come up later), it means a floating point decimal number printed with exactly three digits after the decimal place (including trailing zeros as necessary).

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.

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 SkipList. (If you don't complete a working skiplist you should use a TreeMap here instead to get some credit).

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 kd tree map print an error and do not remove it from the dictionary. Delete from the dictionary should be O(logn), checking for existence in the kd tree will be dependent on the structure of the tree.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Delete dot <name>.<nl>
         
          <error>:=<DNE>|<AA>
          <AA>:=Error: Dot <name> has already been mapped and cannot be deleted.

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.

          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 kd tree 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>

MAP_DOT(name)

inserts the specified dock into kd tree map. If the dot does not exist in the dictionary print an error message. The kd tree is expected to be constructed in standard fashion, which means that your tree should be exactly the same as the TA's (so long as the map_all function is never called).

          Output summary:
          <output>:=<success>|<error>
          <success>:=Dot <name> has been added to the map.<nl>

          <error>:=<DNE>|<AI>
          <AI>:=Error: The specified dot has already been added to the map.

MAP_ALL()

This function will build an ideal (log n depth) kd tree from all the dots currently in the dictionary. In practice kd trees are often built to analyze data that already exists, rather than being constructed point by point. A kd tree of order 2 built this way has guaranteed theta(logn) depth and O(sqrt(n)) rectangle query search time. The first part of this operation should be to remove any dots which are currently in the kd tree. The run time of this function should be O(nlogn) expected.

          Output summary:
          <output>:=<success>|<error>
          <success>:=All dots have been added to the map.<nl>

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

COUNT_RECTANGLE(lx,ly, ux,uy)

prints the number of dots on the map whose coordinates are within the closed rectangle determined by the four points: (lx,ly),(lx,uy),(ux,ly),(ux,uy). Your program should be as efficient as possible, in particular it is not necessary to visit every point in order to get a correct count. If the kd tree is built using the MAP_ALL command then this should run in O(sqrt(n)) time.

          Output summary:
          <output>:=<success>
          <success>:=Total count: <int>.<nl>

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

This function locates all dots in the kd tree map whose coordinates are contained within the closed region determined by the four points: (lx,ly),(lx,uy),(ux,ly),(ux,uy) and sets their color to the one specified. Success can be determined with the DRAW_MAP or LIST_DOTS commands

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

PRINT_KD_TREE()

prints the output of traversing the kd tree in preorder. If the MAP_ALL function as not been called then your output should match the TA's exactly. The output format is identical to that of LIST_DOTS, except for the order that the dots are printed and the error message for an empty tree.

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

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

DRAW_MAP()

Draws all the points of the map using the java canvas class. (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_KD_TREE()

Same as the DRAW_MAP function, except that the partitions of the kd tree are also displayed. Examples will be provided.

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

Web Accessibility