Part 4 Command Specification

The definitions below will use the following standard BNF definitions. In addition, the echoing rule at the beginning of command spec 1 still holds;)

          <docklist>:=<dock><nl><docklist>|<dock><nl>
          <dock>:= <dockname> at (<int>,<int>,<int>) of type <docktype>
          <docktype>:=REMOTE | STANDARD
          <flight> := <dockname> <dockname>
          <DNE>:= Error: Dock <dockname> does not exist.<nl>

When printing a flight, the first dockname must always be alphabetically less than the second. In addition, whenever a <double> appears, 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. If multiple dock arguements cause the same error, then the dock given first should be the one for which an error is printed.

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.

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 second 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(PM1 quadtrees /skiplist).

          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,max_32bit_signed_int]. Note that the boundaries are closed for the PM1(although CREATE_DOCK does not interact with any structures besides the B+ tree). 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 CREATE_FLIGHT function.

For project 3 docks may have a specific type dependant on the first letter of their name (case insenstative). So far these will include only Remote Docks (which will begin with the letter 'R' or 'r') and Standard Docks (those beginning with any other valid character). Remote Docks will have the special property that flights cannot be created to them or between them.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Created Dock <dock>.<nl>
         
          <error>:=<BAD_COORD>|<AE>
          <AE>:=Error: Dock <dockname> already exists.<nl>
          <BAD_COORD>:= Error: Coordinates out of range.<nl>

REMOVE_DOCK(dockname)

NOT TESTED IN PROJECT 4. Deletes a dock from the B+ tree dictionary. If the dock has already been inserted in the PM1 via CREATE_FLIGHT or INSERT_REMOTE_DOCK then you should print an error message and leave the B+ tree unchanged. If the dock does not exist, print an error message. Otherwise print a message to say the dock has been successfully deleted.

My putting this statement here does not mean that this wasn't a requirement for P2, but to make this clear B+ delete must run in O(logn) time. (As must insert)

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

          <success>:=Deleted dock <dockname>.
          <error>:=<DNE>|<AI>
          <AI>:= Error: Dock <dockname> has already been inserted.<nl>

LIST_DOCKS(type)

If type is ALL, lists all dock. Otherwise lists only docks of the corresponding type (STANDARD or REMOTE). If the type specified is not one of the above 3 print an error. Output should always be in asciibetically increasing order. Note that the BNF specifies all infor for the dock should be printed, not just the names.

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

          <success>:=<docklist>
          <error>:= <BT>|<NM>
          <BT>:= Error: The specified type is invalid. 
          <NM>:= No matching docks found.<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>

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>

PRINT_PMTREE(LEVEL)

Prints out the PM1 Quadtree map for the z coordinate of LEVEL. If the level does not exist print the standard 'empty' error. The PM Tree should have the origin [0,0] at the lower left hand corner(SW Corner), with [1024,1024] at the upper right corner (NE corner). When printing you must print in the following order: Northwest, Northeast, Southwest, Southeast.

If you reach a leaf with a dock in it you do not need to worry about printing the list of flights associated with that leaf.

Our outputs should be identical regardless of implementation. A tree with one element should make the root appear to be a leaf- ie. Only the REMOTE dock would be printed out. (The only way a the root can be a leaf is is a REMOTE dock is added to an empty tree).

It's up there at the top, but remember that the docks in a fligth must be printed in increasing alphabetical order.

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

          <success>:= <pmtree><nl>
          <pmtree>:=<black_node><nl>|<white_node><nl>|<nl><grey_node>
          <grey_node>:= NW <pmtree> NE <pmtree> SW <pmtree> SE <pmtree> 
          <black_node>:=<dock><nl>| <flight><nl>
          <white_node>:= 

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

RANGE_DOCKS(dockname1, dockname2)

Lists all docks with names between dock_name1 and dock_name2. If dockname1 < dockname2 the docks must be listed in increasing strcmp order (endpoints included, neither dockname1 nor dockname2 need actually be in the dictionary). If dockname1 > dockname2 The docks must be listed in reverse strcmp order.

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

          <success>:=<docklist>
          <error>:= No matching docks found.<nl>

SHORTEST_PATH(dockname1, dockname2)

DONE, FINITO, NOT TESTED Prints the shortest path from dockname1 to dockname2. If either name is not in the dictionary print an error. Likewise if either has not been added to the PM1 print an error. Finally, if there is no path between the two docks then print an error. Otherwise print out the shortest path from dockname1 to dockname2, followed by the total length of the path. If either dock is a remote dock you can quickly jump to the "No path exists" error.

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

          <success>:= <dockname1> -> <moredocks> <nl>Total length:<double>.<nl>
          <moredocks>:= <dockname> -> <moredocks>| <dockname2>
          <error>:= <DNE>|<NF>|<NP>
          <NF>:= Error: Dock <dockname> has not been added to the map.
          <NP>:= Error: No path exists.

INSERT_REMOTE_DOCK(dock_name)

Adds a REMOTE dock as an isolated point to the PM1 correspoding to the z coordinate of the dock with name dock_name. You may think of this as an edge of zero length if you like. If the dock does not exist, or is not a REMOTE dock, then print an error. STANDARD docks may only be added via the CREATE_FLIGHT command. If the dock has already been inserted, print an error. If a different dock has already been inserted with the same coordinates print an error with the name of the conflicting dock.

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

          <success>:= Dock <dockname> has been inserted.<nl>

          <error>:= <NR>|<DNE>|<AI>|<DC>
          <NR>:= Error: Dock <dockname> is not a REMOTE dock.<nl>
          <AI>:= Error: REMOTE dock <dockname> has already been inserted.<nl>
          <DC>:= Error: Dock <other_dockname> already exists at the specified coordinates.

REMOVE_REMOTE_DOCK(dock_name)

Removes a REMOTE dock from the appropriate PM1with name dock_name. If the dock does not exist, is not a remote dock, or is not in the PM1, then print an error. STANDARD docks may only be removed via the DELETE_FLIGHT command. If a PM1 becomes empty because of this command, then that PM1 should be removed from the skiplist (This is very important if you want skiplist delete credit, regardless of PM1 delete).

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

          <success>:= Dock removed.<nl>

          <error>:= <NR>|<DNE>|<NAI>|<DC>
          <NR>:=  Error: Dock <dockname> is not a REMOTE dock.<nl>
          <NAI>:= Error: Dock has not yet been inserted.<nl>

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. The flights must be stored in the PM1. (adjacency list is still an option) There is a restriction that flights cannot be approved to, from, or between REMOTE docks. The docks will be inserted in the PM1 associated with the z coordinate of both docks (the docks must have the same z coordinate, if not print an error).

If an attempt is made to create a flight between a dock and itself, (ie. dockname1==dockname2) report an error.

Right now there is no support for intersecting edges in the PM1, so if the flight intersects an existing flight print an error. In this case the PM1 should not be modified. The error should include the flight that is intersected. If multiple flights are intersected you may chose one arbitrarily. For simplicity the TA will not add a flight which intersects a REMOTE point, but you should still handle this gracefully for your own peace of mind. Note that if an endpoint of the flight is at the same coordinates a different dock which is already in the PM1, then this will be handled as an intersection error.

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

          <success>:= Flight approved.<nl>

          <error>:= <DS>|<RD>|<DNE>|<LD>|<ID>|<AA>
          <DS>:= Error: Docknames must be distinct.<nl>
          <RD>:= Error: Flights cannot be created to REMOTE docks.<nl>
          <LD>:= Error: Docks must have the same z coordinate. 
          <ID>:= Error: Intersection detected with flight: <flight>.
          <AA>:= The specified flight has already been approved.<nl>

Note that the flight is the flight intersected, and follows the same alphabetical ordering rules as flights everywhere else.

DELETE_FLIGHT(dockname1, dockname2)

removes a flight from the PM1. If a non-remote dock in a PM1 is left with no adjacent flights after this command then the dock should also be removed from the PM1. If the relevant PM1 becomes empty then it should also be removed from the skiplist.

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

          <success>:= Flight deleted.<nl>

          <error>:= <DNE>|<NFE>
          <NFE>:= Error: The specified flight does not exist.<nl>

NEAREST_FLIGHT(x,y,z)

Finds the flight closest to the coordinate x,y,z. REMOTE docks must be ignored. For simplicity any flight found must have the same z coordinate as the one given (you only need to work in one PM1). The only possible error is that no flights exist at that z coordinate. On success print the nearest flight along with the shortest distance between the flight and the point (x,y,z).

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

          <success>:= Nearest flight: <flight>. Distance: <double>.<nl>
          <error>:= Error: No flights exist on this level.

NEAREST_DOCK(dockname1, dockname2)

Finds the REMOTE_DOCK closest to the Flight specified. non-REMOTE docks must be ignored. For simplicity any dock found must have the same z coordinate as the one given (you only need to work in one PM1). There are two possible errors: 1. the flight does not exist. 2.No remote docks exist at that z coordinate. On success print the nearest flight along with the shortest distance between the flight and the point (x,y,z).

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

          <success>:= Nearest dock: <dockname>. Distance: <double>.<nl>
          <error>:= <NF>|<NRE>
          <NF>:= Error: The specified flight does not exist.
          <NRE>:= Error: No REMOTE docks exist on this level.

PRINT_SKIPLIST()

prints out the nodes of the skiplist in order. Each line will contain they key of the node (the height of its corresponding PM1). So, if I had PM1s at z coordinates/height of 3 5 and 7 the output would just be

              3
              5
              7

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

          <success>:=<skipnodes>
          <skipnodes>:=<skipnode><nl><skipnodes>|<skipnode><nl>
          <skipnode>:= <int>

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

DRAW_MAP(LEVEL, outfile)

will not be tested, but has a suggested change Draws the quadtree partitions, the points in the quadtree, and the graph of approved flights for the level specified. (superimposed on the quadtree). You have two options for implementing this:

1. If you are using java you can use the canvas class on the web page (or any other java drawing utils that you prefer, but I hear that the canvas class is quite nice). If you choose this method you can ignore the outfile parameter.

2. If you are using c++ (or java with a few modifications) you can make use of the printquad/showquad also on the web page. Also quite easy to use. My recommendation is to the psdraw.h file I provided to output drawing commands to a file. When grading I will then manually run printquad program to produce a postscript file. $outfile$ should be the name of the file you produce. If you wish to produce a postscript file directly, its name should be '$outfile$.ps'. Like the java project, if you can display the image directly to an x-term window using the showquad package or any other means you may do so.

Please use common sense in rendering your picture to a size that fits on an average size screen(1024x768 max). It is understood the small quadrants will be difficult to see in the picture, this is ok. We will just be eyeballing pictures, as long as your output looks correct we will be happy.

DRAW_MAP() is primarily for *you*. As stated, drawing is very easy to do, The goal is that by forcing you to draw your output you will have an easier time debugging, especially later projects.

          Output summary:
          <output>:=<success>
          <success>:= Drawing complete.<nl>

Web Accessibility