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. Each command spans exactly one line; commands will be uppercase, and reasonably sloppy syntax is to be supported (spaces and empty lines are allowed).

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.

SET_BPTREE_ORDER(btree_order)

will indicate the order of the B+ tree used in the data set. It will always be the first command. 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.

The order will never be less than 3(here or for any future parts- this covers internal node size only, in part 3 or 4 you will have to allow for an independant leaf size, which may be as small as 1) . You should check for this condition to avoid crashing horribly on a bad input, but I won't add a specific error for this part.

Note that the following rules apply to B+ tree nodes:

Internal: must always contain between floor( $(btree\_order-1)/2$) and $btree\_order-1$ keys, with exactly one more child than the number of keys at all times. (this implies between ceiling( $btree\_order/2$) and $btree\_order$ children per node, inclusive).

Leaf: must always contain between ceiling( $(btree\_order-1)/2$) and $btree\_order-1$ keys, inclusive. Must not contain $btree\_order$ keys!

Remember the root is an exception, in that it never has a lower bound on the number of keys it contains.

Also, whenever a value is equal to a key it must go to that key's RIGHT child. This is mandatory, meaning no credit will be given for the B+ tree if this rule is not observed.

Even if you do not implement the b+ tree you must still implement this function! Default to printing the correct <success> message. Because this is always the first command and diff is used in grading, if you skip this function your project will fail every test!

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

          <success>:= Order set to <btree_order>.<nl>
          <error>:=Error: B+ tree already initialized.<nl>

CLEAR_ALL()

initializes all data structures used in your program. This is always the first command in the test data, but can also appear anywhere after the first command, and should delete all information from the dictionary(B+ tree), and map(k-d tree and adjacency list).

          Output summary:
          <output>:=<success>

          <success>:=All structures cleared.<nl>

CREATE_DOCK(dock_name, x, y, z)

creates a flight dock at the three-dimensional point ($x, y, z$) and assigns name dock_name to it. Names will be limited to 10 characters in length and will be alphanumeric or `_'; $x$ and $y$ coordinates will be in range [0, 1024). The $z$ coordinate will be in the range [0,64). You should store the dock internally in an asciibetically ordered B+ tree. Dock names are case sensitive. You should not check for coordinate conflict with an existing dock in this function, however you will in the INSERT_DOCK function.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Created Dock <dock>.<nl>
         
          <dock>:= <dockname> at (<int>,<int>,<int>)

          <error>:=<nameErr>
          <nameErr>:=Error: Dock <dockname> already exists.<nl>

INSERT_DOCK(dockname)

inserts the specified dock into k-d tree map. The dock to be inserted should have been created earlier using CREATE_DOCK command. If the dock does not exist print an error message. The k-d tree is expected to be constructed in standard fashion, which means that your tree should be exactly the same as the TA's.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Dock <dockname> has been inserted.<nl>

          <error>:=<NE>|<AI>
          <NE>:=Error: Dock <dockname> does not exist.
          <AI>:=Error: Dock <dockname> has already been inserted.

CREATE_FLIGHT(dockname1, dockname2)

approves flight between two flight docks. Both dock names should be valid (ie. created beforehand with CREATE_DOCK command); otherwise, output an error message. Flights are bi-directional. (In terms of underlying graph this command creates an undirected edge; the length of this edge is just Euclidean distance between given docks). Print a confirmation message on success. Note that flights are to be stored as adjacency lists. Flights can only be approved between docks inserted into the k-d tree map. If either dock has not been inserted print an error. The TA will not attempt to create flight from a dock to itself, but you should handle this case gracefully.

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

          <success>:= Flight approved.<nl>

          <error>:= <NE>|<AE>|<NI>
          <NE>:= Error: Dock <whichdock> does not exist.<nl>
          <NI>:= Error: Dock <whichdock> has not been inserted.<nl>
          <whichdock>:= <dock_name1> | <dock_name2>
          <AE>:= The specified flight has already been approved.<nl>

A note on <NE> and <NI>- the first dock that fails(based on the order the docks are given to the function) should be the one printed. The <NE> error should supercede the <NI> error. At most one error should ever be printed.

LIST_DOCKS()

Lists the dock names and their coordinates in increasing alphabetical (strcmp) order of the dock names. This function will be used as a measure of success for the CREATE_DOCK function.

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

          <success>:=<docklist>
          <docklist>:=<dock><nl><docklist>|<dock><nl>
          <dock>:= <dockname> at (<int>,<int>,<int>)

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

LIST_FLIGHTS()

lists all approved flights along with their lengths. The docks should be listed in increasing strcmp order, with the docks linked to each individual dock listed in strcmp order afterwards. For instance, if approved flights are (D1, 0,0,0)-> (D2, 0,0,1), and (D1, 0,0,0)-> (D3, 0,1,0), then the output would appear as:

          D1: D2(1.000) D3(1.000)
          D2: D1(1.000)
          D3: D1(1.000)

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

          <success>:= <adj-list>
          <adj-list>:=<adj-row><adj-list>|<adj-row>
          <adj-row>:=<dockname>:  <adjEdges><nl>
          <adjEdges>:= <adjEdge>(<double>) <adjEdges> | <adjEdge>(<double>)
          <adjEdge>:= <dockname>
          <error>:= No flights have been approved.<nl>

CUBE_DOCK(lx,ly,lz, ux,uy,uz)

identifies and prints the docks in the map whose location on the planet is within the closed cube determined by set of eight points: (lx,ly,lz),(lx,uy,lz),(ux,ly,lz),(ux,uy,lz), (lx,ly,uz),(lx,uy,uz),(ux,ly,uz),(ux,uy,uz) Your program should be as efficient as possible- your project may be tested on *very* large inputs that should be able to finish in a reasonable amount of time(based on trials with the TA's project). The docks must be printed in pre-order (self, left child, right child) with respect to the k-d tree(which should be identical to the TA's). The output format is similar to that of the LIST_DOCKS command.

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

          <success>:=<docklist>
          <docklist>:=<dock><nl><docklist>|<dock><nl>
          <dock>:= <dockname> at (<int>,<int>,<int>)

          <error>:= No docks found within the specified region.<nl>

PRINT_KD_TREE()

prints the output of traversing the k-d tree in preorder. Your output is expected to match the TA's exactly. The output format is identical to that of LIST_DOCKS, except for the order that the docks are printed and the error message for an empty tree.

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

          <success>:=<docklist>
          <docklist>:=<dock><nl><docklist>|<dock><nl>
          <dock>:= <dockname> at (<int>,<int>,<int>)

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

PRINT_BPTREE()

requires you to list the B+ in a breadth first search order. If you used links between internal nodes this will be easier, BFS is more complicated. Every level of the tree is enclosed in braces {}, every node is enclosed 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)}
          {(DOCK3),(foo)}
          {(DOCK1,DOCK2),(DOCK3),(bar),(foo)}

Note the leaf DOCK3 is to the RIGHT of the key DOCK3:)

Even at the leaves print only the key (the dockname). 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 properties described above in the SET_BPTREE_ORDER command.

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

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

          <success>:=<b+rows><nl>
          <b+rows>:=<b+row><nl><b+rows>|<b+row>
          <b+row>:={<nodes>}
          <nodes>:=<node>,<nodes>|<node>
          <node>:=(<keys>)
          <keys>:=<key>,<keys>|<key>
          <key>:=<dockname>

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

Web Accessibility