Part 1 Command Specification

You will also build a command decoder with a minimal set of commands; you will expand it appropriately later to accommodate commands required for future parts. Each command spans exactly one line; commands will be uppercase, and reasonably sloppy syntax is to be supported (spaces and empty lines are allowed). Documentation and conformance to the rules is worth 10 points for part 1. The clear all function is worth 5 points. The data dictionary development (DD points) is worth 15 points. There are 30 points for developing the map (PR points). And, 40 points are alloted to the rectangle search (AP points).

The following is a list of commands you should support and a description of the output you should give for each one. Note that for all functions, you should print "*****\n" followed by an " ==> " 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 you are not required to reformat the orginial command (fixing spacing, for instance) in any way.

• CLEAR_ALL() [5 points] initializes all data structures used in your program. This is always the first command, but can also appear anywhere after the first command, and should then cause deletion of all currently defined cells and routes. Print ``All structures cleared.'' after execution, even if this is the first command in the data file.

• CREATE_CELL( $cell\_name,x, y$) [DD points] adds the name of the cell along with its coordinate position into the data dictionary. The data dictionary should be implemented as a binary search tree (BST) with keys in the natural ASCII order (ie. strcmp() order- henceforth asciibetical order) of the cell names. In the case of duplicate keys, we assume that `less than' values are to be inserted into the left subtree and `greater than or equal to' values are inserted into the right subtree. Cell names will be composed of up to 6 characters that are _ or alphanumeric. Coordinates will be in the range [0, 1024).

  The mapping between cell names and coordinates is one-to-one, meaning that you can't have two instances of the same coordinates inserted having different cell names and vice versa.

  While creating a cell that exists already is an error, at this stage we are only trying to catch duplicate names. That is, while two cells with different names are forbidden to have the same coordinates there is no intention to put this specific error in the test data until Part 3, and you are not required to catch that error NOW for reasons that should be obvious if you try to think of an efficient way to check for that condition.

  On success you should print:

  
  Created cell <cell\_name>.
  

  The following are possible error messages:

  
  Error: Cell <cellname> already exists.
  

• LIST_CELLS() [DD points] Lists the cell names and their coordinates in increasing alphabetical (strcmp) order of the cellnames. This function will be used as a measure of success for the CREATE_CELL function.

  If there are no created cells simply print "None." Otherwise output the cells one on each line in increasing asciibetical order in the format

  
  <cellname> at (<x-coordinate>,<y-coordinate>)
  ...
  <cellname> at (<x-coordinate>,<y-coordinate>)
  

  followed by

  
  End of list.
  

  Note, contrary to the original description and my original samples, "End of list." is not printed if there is no list printed. Just print "None."

• INSERT_CELL($cell\_name$) [PR points] inserts the specified cell into PR quadtree. The cell to be inserted should have been created earlier using CREATE_CELL command.

  On success you should print:

  
  Cell <cellname> has been inserted.
  

  The following are possible error messages:

  
  Error: Cell <cellname> is not the name of a created cell.
  Error: Cell <cellname> is already inserted.
  

  Note that for part one no two Cells will have the same coordinates so you are not required to check this condition.

• PRINT_PRTREE() [PR points] prints the output of traversing the PR tree in preorder. You will be required to print out the path you take for your benefit and ours. For the most clear explanation see the samples that are posted. Basically, before examining any child you should output the direction you are about to go. When you hit a leaf node print either the Cell (in the form "<cellname> at (<x-coord>,<y-coord>)", or the word EMPTY for an empty leaf. ie. A tree with 1 Cell (Foo,20,73) would print as:

  
  Inserted Cells:
  Foo at (20,73)
  

  since there are no directions to look (the root is a leaf). If you added (Bar, 800,800) you would end up with 4 children from the root and print the following:

  
  Inserted Cells:
  NW EMPTY
  NE Bar at (800,800)
  SW Foo at (20,73)
  SE EMPTY
  

  and if you added one more point (Hello,520,520) you would print

  
  Inserted Cells:
  NW EMPTY
  NE 
    NW EMPTY
    NE Bar at (800,800)
    SW Hello at (520,520)
    SE EMPTY
  SW Foo at (20,73)
  SE EMPTY
  

  If the tree is empty you should print:

  
  Tree is empty.
  

  (Note this is a change from earlier versions. Don't say "Inserted Cells:" if there aren't any)

• RECTANGLE_CELL($c\_x$, $c\_y$,$x\_h$,$y\_h$) [AP points] Identifies and prints the names of all cells in the PR quadtree whose location on the planet is within the closed rectangle determined by set of four points:

  
  

  $$\{(c\_x + x\_h , c\_y + y\_h)\;\;\; (c\_x + x\_h , c\_y - y\_... ...c\_x - x\_h , c\_y + y\_h)\;\;\; (c\_x - x\_h , c\_y - y\_h) \}$$
  
  

  You must use the PR quadtree efficiently (as described below) to prune your search in order to get full credit[You will need to match the TA's code exactly].

  With this simple rectangle there is an exact amount of pruning that can be done- namely, you need only follow a child if the rectangle overlaps the child's region at at least one point. You will be required to print in the same format as in PRINT_PRTREE, except for the following:

  1. When you reach an an empty leaf you will not print EMPTY.
  2. When you reach a leaf with a point that is outside the rectangle, do not print the cell name.
  3. Do not print directions that you did need to search.

  After printing the search path you took, you are to list the cells in NW-NE-SW-SE order in a list similar to the output of LIST_CELLS(). If you only accomplish this second part you will no more than one half of the possible points for this function. For example, in the tree above the output to RECTANGLE_CELL(800,700,20,120) would look like:

  
  NE 
    NE Bar at (800,800)
    SE 
  
  Cells within rectangle:
  BAR at (800,800)
  

  Explanation: Starting from the root, the NorthWest quadrant from

  $x=[0,512) y=[512, 1024)$ does not overlap the rectangle $x=[780,780] y=[580, 820]$, so you don't go NW, etcetera... Think of the output as representing all the quadrants that a point in the rectangle might have been in... Longer examples are in the sample online.

  If there are no points in the given rectangle, then after printing the search path you should print only:

  
  No cells within the specified region.
  

  This is also a change from earlier specification.

Note: Although you have all doubtlessy implemented your quadtrees in different ways, the PRINT_PRTREE and RECTANGLE_CELLS commands should behave as if they were working with the theoretical model of a quadtree- ie. each node is either a leaf or has four children. Just because you use a NULL pointer to represent an empty leaf, for instance, does not mean that you can skip printing out that direction in your traversal. For this reason your output must match the ta's exactly for these functions to be considered correct. You will be given test files to help ensure that you are formatting correctly.

Note2: You may adopt anyone's BST, so long as it is properly attributed in your documentation. This includes your own BST from 214 (!). The BST need not be balanced; however, no deduction will be made for a correctly working balanced BST. If you are truly ambitious, you can build the B+-tree early. The functions in part one will should give the same result for a BST, a B+-tree, or even an AVL tree, because we aren't checking the dynamic (run time) code size, or the execution time. However, there is no need to do so. You are required to write your own command decoder and PR, but the PR quadtree can be built by extending an existing BST ADT, for example. Or, you can build it from scratch.

Web Accessibility