Part 1 Command Specification

You will build a command decoder with a small set of commands(you may of course use the framework provided by the TA); 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 EXIT() is

*****
==> EXIT()
Have a nice day!

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 TreeMap 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(TreeMap for project 1). 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. If the dot does not exist print an error. If the dot was previously in the AdjacenctList remove it and all connecting edges from there as well. Delete should be O(logn) if that dot was not previously in the Adjacency list.

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

CREATE_PATH(name1, name2)

adds a unidirectional path from the first dots specified to the second in the Adjacency List. If one or both dots does not exist print the <DNE> for the first argument not found. If the path already exists print an error. If name1==name2 you may still print the success message, however no changes need to be made to the adjacency list. (All nodes are assumed to have a path to themselves of zero length).

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

DELETE_PATH(name1, name2)

Deletes a segment from the Adjacency list. If either endpoint does not exist, or the segment does not exist print an error.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Deleted Segment (name1,name2).<nl>
         
          <error>:=<DNE>|<SDNE>
          <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 path 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. The weight of an edge should be based on the Euclidean distance between the endpoints of the edge. ( $sqrt((x1-x2)^2 +(y1-y2)^2)$)

          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.