Part 3 Command Specification

As before, 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.

• SET_BPTREE_ORDER($btree\_order$) (DD points) will indicate the size of the $B^+$-tree used in the data set. It will always be the first command in the data set. Don't bother checking to see if some OTHER command is the first. We won't do that. However, you should detect that the B+ tree order has already been set if the command appears again.

• CLEAR_ALL() [DOC points] initializes all data structures used in your program. This is always the second command in the test data, 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 second command in the data file.

• CREATE_CELL( $cell\_name,r, x, y$) [DD points] adds the name of the cell along with its distance from the planet's surface and coordinate position into the data dictionary. The data dictionary should be implemented as a skiplist with keys in the natural ASCII order (ie. strcmp() order) of the cell names. Cell names will be composed of 6 characters that are _ or alphanumeric. Coordinates will be in the range [0, 1024). Print a confirmation message if this command is processed successfully. You may assume that no more that 1024 cells will ever be inserted in the data dictionary.

  As before, creating a cell that exists already is an error. However, because the number of Sametists accessing the database has increased, the likelihood of input errors has increased. So, the input to the skip-list must be checked to make sure that (X , Y) coordinates are not replicated. That is, distinct cell names must imply distinct (X,Y) values, and brute force search across the leaves isn't fast enough.

  You should print a list of the cell coordinates examined in attempting to insert a new cell name to demonstrate that you did not use brute force to make this check, as described in section 1.3.2. And, you are welcomed to store the coordinates in a 2- or 3- dimensional k-d tree. I don't care which. We aren't looking for the fastest method, merely NOT brute force.

  Please note that there are several distinct Hanan-o-bot types: Alpha, Gamma, and Sigma The type of Hanan-o-bot will be encoded in the first letter of the cell name. Type Alpha Hanan-o-bots begin with the letters A-F inclusive; Type Gamma Hanan-o-bots begin with the letters G-J inclusive; Type Sigma cells begin with the letter S-V Other cell-types might make use of the remaining letters; so, please don't assume that no letter higher than N in strcmp will be used. That is, we can use any first letter we want for a cell name; so, you are not required to examine the first letter of the cell name when creating the entry in the data dictionary.

• LIST_CELLS($cell\_type$) [DD points] Lists the cell names of the Hanan-o-bot type specified, and their coordinates in increasing alphabetical (strcmp) order of the cellnames. The parameter $cell\_type$ is any one of ALPHA, GAMMA, SIGMA, or OMEGA. The parameter OMEGA means that all cells, regardless of type, should be listed. This function will be used as a measure of success for the CREATE_CELL function.

• PRINT_SKIPLIST() [DD points] Lists the skiplist as shown in the BNF, giving the cell name, followed by the number of links in its tower. This function will be used as a measure of success for having constructed a skip list.

• INSERT_CELL($cell\_name$) [SS points] inserts the specified cell into the point-region quadtree at positions determined by the (X,Y) coordinates of the cell as stored in the data dictionary.

  The cell to be inserted should have been created earlier using CREATE_CELL command. If the cell is not present in the data dictionary, output an error message. Print confirmation message if the command is processed successfully. If the cell exists in the point-region quadtree already, output an error message.

  Please note that the coordinate system in use for the project has [0,0] at the lower left corner and (1024,1024) at the upper right corner. Order of the subtrees should be: 1 (NE) ,2 (NW), 3 (SW), 4 (SE). Traversals of the PR tree should list the path through the PRtree by number.

• PRINT_QTREE() [SS points] should be a preorder traversal of the point-region quadtree that lists the names of all cells that have been inserted in the tree.

• RECTANGLE_CELLS($x\_coord$, $y\_coord$, $x\_range$, $y\_range$) [U points] identifies and prints all cells present in the point region quadtree within the specified closed rectangle. Cells should be printed in increasing strcmp order. You are expected to use the point-region quad tree efficiently to guide your search process. For full credit, you need to print the coordinates of any leaves (black nodes) you examine in the process. Programs that do not prune the search tree efficiently will be penalized up to half credit for this function.

• DRAW_QTREE_MAP() [AP points] Draws the quadtree partitions, as well as cells and edges included in the quadtree on an X-terminal screen using the resources on the class webpage. Two forms are acceptable: DRAW_QTREE_MAP(outfile, scale), and DRAW_QTREE_MAP(). We will check for both when grading.

• MAP_FEASIBLE_NET($cell1$,$cell2$) [AP points] Creates an edge between distinct cells, cell1 and cell2, in the support network to facilitate the spread of Hanan-o-bots, where cell1 and cell2 must be of the same type. Furthermore, both cells must have been inserted into the quadtree already. If they are not the same type, or are not both in the quadtree, then do not insert the edge, and print an appropriate error message.

• PRINT_FEASIBLE_NET($type$) [AP points] Lists feasible paths in adjacency list format.

• BUILD_SUPPORT_NET($type$) [AP points] Generates an MST from all cells of type either ALPHA, GAMMA, or SIGMA. Please note that if the graph of cells of a give type is not connected, you will need to restart the MST algorithm. The edges making up the MST for each type will be inserted in the quadtree.

  That is, the quadtree nodes containing the vertices of each segment of the path should include information that permits the presence of an edge intersecting that partition to be recognized quickly, as well as allowing several edges emanating from the same vertex to be distinguished. The edge cost is given by the Euclidean distance between the vertices.

• PRINT_SUPPORT_NET($type$) [AP points] Prints minimimum spanning tree (MST) cost and net in the adjacency list format, where $type$ is one of: ALPHA, GAMMA, SIGMA. Any other parameter should be identified with an error message because of the BAD ARGUMENT.

Web Accessibility