Part 2 Command Specification

Part 2 of the project requires the implementation of a B+-tree for the data dictionary; use of the PR quadtree and an adjacency list in an application; and the addition of the required commands to the command decoder.

Note that for full credit on part 2, the functions listed below must replace any with the same command name, as we will be adding parameters and changing the underlying structures from those used in part 1.

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 is worth DOC points. Don't forget to check the BNF in section as well.

• 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. Your output should look like

  
  Error: B+ tree already initialized.  The current order is:<current-order>
  

• CLEAR_ALL() [DD 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. This also resets $j$ to 0. Print ``All structures cleared.'' after execution, even if this is the second 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 B+-tree with keys in the natural ASCII order ( 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. There used to be an assumption about the max number of cells which could be added. You may make no such assumption.

  As before, creating a cell that exists already is an error. However, there is no need to detect that two cells with different names have identical coordinates, and, there is no intention to put this specific error in the test data until Part 3.

• LIST_CELLS() [DD points] Output identical to part 1. 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. Print ``None'' if no cells have been created. For part2 Cells should now be printed with 3 digits past the decimal. This means most of your points will end in .000 See sample IO for details.

• PRINT_BPTREE() [DD points] Lists the B+ in a breadth first search order. If you used links between internal nodes this will be trivial, BFS will be a little more complicated. Check the web page for pseudo code(soon). Every level of the tree is enclosed in braces {}, every node is inclosed in parenthesis, every key within a node is separated by commas. Each level of the tree should appear on its own line and in order. A sample tree of order 3 is printed below:

  
  {(bar)}
  {(CELL3),(foo)}
  {(CELL1,CELL2),(CELL3),(bar),(foo)}
  

  Even at the leaves print only the key (the cellname). If the tree is empty, print "Tree is empty." Your tree is not expected to match mine exactly. Your grade will be based on your tree displaying the following properties(this does deviate somewhat from shaffer, you are required do what what is listed below): For our order m tree: The leaves contain between 1 and m-1 keys. They may not have m keys. Internal node internal nodes must have between ceiling(m/2) and m children. There must be one fewer guide than children (no 'extra' key on the far left should be printed, even if you used one in your implementation). Your tree, of course, must also contain the correct data at the leaves!

• INSERT_CELL($cell\_name$) [MAP points] inserts the specified cell into PR quadtree just as the coordinates are listed when they are inserted in the CREATE_CELL. An attempt to insert a cell already present in the PR quadtree should result in an error message(same error as part1).

  Note: At the same time that a cell is inserted in the PR quadtree, the EnviroBot (EBOT) net connecting existing cells is extended to include the additional cell. Details of EBOT net development are included here for your convenience. When a cell is inserted in the PR quadtree successfully, the cell must be added to the EBOT net by finding the cheapest edge between the existing cell and all other cells already in the net.

  The edge cost is computed according to the following algorithm for inserting the j-th cell into the path.

  If $j=1$ the cost is $0$. For $j > 1$, the edge cost between cells A and B having coordinates $x_A, y_A$ and $x_B, y_B$, respectively, is

  
  

  $${\rm cost}_{AB} = [(x_A) - (x_B)]^2 + [(y_A) - (y_B)]^2 + (\max(r_A,r_B))^j$$
  
  
  .

  where $r_A = {\it sqrt}(x_A^2 + y_A^2)$ and $r_B$ is defined similarly.

  So, if cell B is being inserted in the PR quadtree and there are already $j-1$ cells in the service path, an edge will be inserted from cell B to the existing cell A for which ${\rm cost}_{AB}$ is minimal. And, yes, that means the number of cells already in the EBOT net also contributes to the cost. However, once an edge has been inserted in the EBOT net, no attempt should be made to recompute the cost.

  Furthermore, as the cost increases, it may be more reasonable to keep the cost in two pieces--the portion that dominates, with the j-th power tucked in, and the portion from the difference in x and y coordinates...this will keep the need to use double precision to store humongous integers from introducing unneeded errors. Do what you think is right.

  Were this a REAL application, you might suggest that the developers consider using a disconnected EBOT net once the number of cells makes the cost prohibitively large-on the other hand, we really don't know the units of the cost function, now do we, so these values might be what the customer expects.

  Full credit will be given for brute force (meaning always compute all the distances to all cells in the net). However, up to 10 points extra credit may be given if your algorithm need not always check all known cells to find the closest-and sometimes, reasoning based on the size of a given portion of the cost function can allow you to prune the PR quadtree.

  If you do choose this option, make sure you describe your algorithm within your code, and explain your algorithm and why it is better than brute force in the README. p.s. The cost function doesn't have any particular rationale, but ya gotta live with it ;)

  Important: Last Minute Clarification of Ebot Net cost function

  Since the last term of the cost function blows up quickly, the client has agreed to accept the following modification. Floating point may be used as an approximation to the cost and double precision gives best results. The BNF now reflects this change, with <float> replacing <int> as needed.

  Furthermore, suppose you are adding cellname $D$ to the EBOT NET. When comparing cost $c_A$, the cost of a potential edge connecting $A$ to $D$, to cost $c_B$, the cost of a potential edge between $B$ and $D$, you find that the following is true:

  
  

  $$\frac{\vert c_A-c_B\vert}{\max (c_A,c_B)} < {10}^{-5}$$
  
  

  Then, you may continue as if the cost to connect $D$ to either $A$ or $B$ were identical, and use strcmp order of the cell name to discern which of $A$ or $B$ gets the connection. Please note that if you compute the function as written, you will have a loss of precision when $c_A$ and $c_B$ differ by only a few low order digits.

  So, you might want to consider the following alternative if you need to preserve the actual difference for some other reason. This method can be evaluated without the loss of precision caused by subtracting two nearly equal floating point numbers.

  If $c_A < c_B$, then the cost of the edge to A is treated as matching that to B whenever
  

  $$c_B (1-10^{-5}) < c_A$$
  
  
  Similarly, if $c_B \leq c_A$, then if
  
  $$c_A (1-10^{-5}) < c_B$$
  
  
  the edges should be treated as having equal cost.

  (Note that the previous discussion assumes that $c_A$ and $c_B$ are non-negative.)

• PRINT_PRTREE() [MAP points] prints the output of traversing the PR quadtree in preorder, just like in part 1.

• PRINT_EBOT_NET() [MAP points] prints the adjacency list corresponding to the minimal network eaten through the planet's interior by the EnviroBots in preparing the MacroCells for implantation of the MI's. This represents a minimal network connecting all the MacroCells activated thus far, as described above under the heading INSERT_CELL. Requirements for demonstrating which Cells you visited have been removed, as in order for me to verify that you haven't fudged your results I would have to examine your code anyway. Extra credit for cutting down the total number of comparisons will therefor be based on the description of your algorithm in your README. You will also never explicitly print the cost of the EBOT-NET (seems odd doesn't it, you should think about why I have done this). Simply print what the network is. Your network will be expected to match exactly unless pseudo cells are involved.

  The cells should be listed in strcmp order, with the nodes linked to each individual cell listed in strcmp order afterwards. (Ok, not too helpful.) Try:

  
  CELL1:   CELL2 CELL 3
  CELL2:   CELL1
  CELL3:   CELL1 CELL4
  CELL4:   CELL3
  

• RADIUS_CELL( $cell\_name, radius$) [AP points] identifies and prints all cells within the closed circle of the specified radius around the specified cell. You are expected to use the PR quadtree efficiently to guide your search process. For full credit, your output should also include the path that you follow during the search, as defined in part 1 for RECTANGLE_CELL. Programs that do not prune the search tree efficiently will be penalized up to half credit. Note that you are not required to find the best such algorithm; merely one that prunes the PR quadtree in some reasonable way. It is acceptable to use your original rectangle function to prune. As before, you must make sure that your tree behaves like that theoretical model- that is, even if you use NULL pointers for children you should still print out the relevant directions, or you will receive a giant 0 points. For instance on the following tree:

  
  NW
  NE Foo at (5.000,6.000)
  SW Bar at (1023.000,1023.000)
  SE
  

  the output of RADIUS_CELL(Foo,1000,1000) should be

  
  NW
  NE Foo at (5.000,6.000)
  SW 
  SE
  

  even though NW and SE may actually be NULL pointers. Please don't mess this up, I'll have no sympathy if you do.

• CREATE_PSEUDO_CELLS( $x\_coord$, $x\_range$, $y\_coord$, $y\_range$ ) [AP points] Ahh pseudo cells. Perhaps it is best to explain why these exist. 1. To get you to implement line intersection 2. To get you do do subdivision in your quadtree beyond the unit level. These are warm-ups for project three, and not directly related to p2. That said, read on... Identify pseudocells within rectangle determined by $x\_coord$ plus or minus $x\_range$, and $y\_coord$ plus or minus $y\_range$. Next, name the pseudo sites "+PSxxx" where xxx is the number of pseudo cells that have already been created +1. ie, the first pseudo cell should be called +PS001, the second pseudo cell should be +PS002 etc. Of course, I am limited in my ability to force which order your cells are added in, so outputs may not neccessarily match. The "+" will ensure that the user cannot enter such a name as a Cell name ahead of time, since + is not a valid character for the CREATE_CELL() command. Then, insert the site information into the B+tree and insert the site into the quadtree. If while inserting into the quadtree you find that for some point p already in the tree, |p.x-x|<.0001 and |p.y-y|<.0001 you must disregard the point. It should then have no effect on the PRTree or the BPTree or any other values. Contrary to what I(brian) posted, Pseudo cells have absolutely no effect on the EBOT_NET. PRINT_EBOT_NET should not display Pseudo Cells at all. The avoid a slew of error checking and make our lives easier, after CREATE_PSEUDO_CELLS is called for the first time, INSERT_CELL() *will not be called again* unless CLEAR_ALL() is called first. Any other function may still be called, including another call to CREATE_PSEUDO_CELLS(). As this command is processed you should print out the pseudo cells you create. See the sample io for proper formatting, but essentially it will look like either:

  
  *****
   ==> CREATE_PSEUDO_CELLS(...)
  New pseudo cells:
  +PS001 at (...,...)
  .
  .
  .
  
  or
  
  *****
   ==> CREATE_PSEUDO_CELLS(...)
  No new pseudo cells discovered in the specified region.
  

• DRAW_QTREE_MAP() [MAP points] Pending. If this isn't updated by friday night you are not responsible. Check back. Original description to give you an idea (you will definately be drawing in part3, so it won't hurt to play with even if this isn't updated): Draws the quadtree partitions, as well as cells in the PR tree and Ebot net edges included in the quadtree on an X-terminal screen. If this instruction appears after execution of a CREATE_PSEUDO_CELLS() command, then the pseudo cells should be included in the drawing. Similarly, the entire ebot net should be shown if more than one cell has been inserted in the map.

  Note that you will need either the C++ utilities on our 420 webpage, or SWING in Java. Please note that this ability will be very helpful for part 3. And, this function description will need to be updated, because the TA's have to decide how to grade this piece.

Web Accessibility