Part 3 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.

The following is a list of commands you should support for part 2 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 a hypothtical *wink wink* CLEAR_ALL() command would be:

*****
 ==> CLEAR_ALL()
All structures are cleared.

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.

The definitions below will use the following standard BNF definitions.

          <dotlist>:=<dot><nl><dotlist>|<dot><nl>
          <dot>:= <name> at (<int>,<int>) color:<color>
          <color>:= RED|GREEN|BLUE|BLACK|WHITE
          <DNE>:=Error: The specified dot does not exist.<nl> 
          
          <framelist>:<frame>|<frame><framelist>
          <frame>:Frame <int><nl><seglist>
          <seglist>:<segment><nl>|<segment><nl><seglist>
          <segment>:= (<name1>,<name2>)

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). To do this in java check out the NumberFormat class.

This <int> in a frame is the 0 based frame number for teh current drawing command. For instance, if you are drawing the 300th frame of ANIMATE_PATH, then the int should be 299. In the <segment> the names should be in increasing alphabetical order. The segments of the segment list. when printed, should be printed in increasing alphabetical order as well based on the alphabetically lowest endpoint of each segment. Break ties with the second endpoint. For instance:

      Frame 7:
      (a,b)
      (a,c)
      (a,d)
      (b,d)
      (c,d)

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.

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. 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! This is to force consistency between our projects so that I have some chance of grading. 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>

USE_HAPPY_FUN_BP()

As discussed in the newsgroup, if used at all this is guaranteed to be the first line of input. If it does appear then it is guaranteed that SET_BPTREE_ORDER will not. This command indicates that you should use a version of your B+ tree that tries to preserve memory locality within a node rather than using naive pointer reassignment. Exact implementation details are up to you. You should hard code an order of your chosing that is tuned to the detective cluster machines, with the guarantee that dot names will be at most 10 characters (your unerlying implementation should probably make use of new StringBuffer(10) as a key type). You should print what that order is :) To get credit for this function you will have to turn in an extra file called HAPPYFUN, whose contents are described on the newsgroup. IF YOU DO NOT IMPLEMENT THIS FUNCTION, you can still get a few points just for gracefully exiting with System.exit(0); when this function is encountered after printing the "not implemented" message specified. It would be better for all if I don't have to run your project on a 30 minute test if you're not getting any points for it anyway.

Full information is in the newsgroup, but to be clear- when this function is used the only other commands tested will be CREATE_DOT, COLOR_DOT< and PRINT_QUADTREE. There will be no delete, or any other functions tested.

When you print the order in the output, just print whichever order you selected. Remember, "Not Implemented
n" + System.exit(0); is worth a few points here.

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

          <success>:= Order set to <btree_order>.<nl>
          <error>:=Not Implemented.<nl>

RANGE_DOTS(name1, name2)

Lists all dots with names between name1 and name2. If name1 < name2 the dots must be listed in increasing strcmp order (endpoints included, neither name1 nor name2 need actually be in the dictionary). If name1 > name2 The dots must be listed in reverse strcmp (String.compareTo()) order. Show off that B+ range search ;)

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

          <success>:=<dotlist>
          <error>:= No matching dots found.<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)}
          {(DOT3),(foo)}
          {(DOT1,DOT2),(DOT3),(bar),(foo)}

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

Even at the leaves print only the key (the dotname). 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.

See SET_BPTREE_ORDER for rules on the number of keys in a node. Remember that 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>:=<dotname>

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

SET_DRAW_MODE(mode, xsize, ysize, step)

Changes the mode for all graphical output commands. The mode will be either "TEXT", "DRAW", or "BOTH". If BOTH, then you should print text before drawing to the screen. "TEXT" will be the mode primarily used when grading, the others will mostly be for your benefit in debugging and for impressing your friends. If the input is invalid (I will not test this) stay in the current mode. To be safe I will always call this function before using a drawing command, so you may use whatever default you find handiest.

xsize and ysize will specify the size of the view window used on the map. When animating the path along a line, the line should always be at the center of the view window, xsize units above and below the center and ysize units to the left and right, so that the actual window is 2*xsize by 2*ysize. The step says how far to move each frame in the current direction of travel(always east now). If you are following a particular line and the next step will cause you to pass the end of that line then you should have a frame exactly at that endpoint (don't try to advance some fractional step into the next line segment you might be drawing). Some discourse on the use of parametric representations of lines will probably be necessary if we stick with this.

          Output summary:
          <output>:=<success>
          <success>:=Drawing mode changed to <mode>.<nl>

ANIMATE_HORIZONTAL_PATH(x,y,dist)

This will be the only drawing test and will be worth a fair amount of points. The only hope is that even if you didn't get the PM1 implemented you still see some use in it. The first frame should be centered at (x,y), and then you should procede right for the distance specified by dist incrementing each frame by the step specified in SET_DRAW_MODE.

There is no such thing as failure (I promise (x,y) will be in bounds). If the current mode is BOTH or TEXT then each frame should also have a textual version printed according to the BNF and explanatory side comments ;)

          Output summary:
          <output>:=<optional textoutput><nl><success>
          <success>:=Animation Complete.<nl>
          <optional textoutput>:=<framelist>

CREATE_DOT(name, x, y, radius, color)

Creates a 'dot' object with the appropriate name, coordinates, radius, and color. The dot will then be added to a B+ Tree sorted based on the name (the data dictionary) and to one based on the coordinates. The latter structure is used to check for duplicate coordinates.

Coordinates will be non-negative. This should be an O(logn) operation where n is the number of dots already in the dictionary. The dots should be stored in an asciibetically sorted B+ Tree.

If a dot with the same name already exists print an error. If a dot already exists at the specified coordinates print an error.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Created dot <dot>.<nl>
         
          <error>:=<AE>|<DC>
          <AE>:=Error: Dot <name> already exists.<nl>
          <DC>:=Error: Dot <other\_dot\_name> already exists at the specified coordinates.

DELETE_DOT(name)

Removes the dot with the given name from the data dictionary. If the dot does not exist print an error. If the given dot has already been added to the Adjacency List (via CREATE_SEGMENT()) print an error and do not remove it from the dictionary. If it has already been added to the PM1 (via MAP_SEGMENT()) print an error. Delete from the B+ should be O(logn). Some slowdown may occur from checks to the PM1 if either is non-empty.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Deleted dot <name>.<nl>
         
          <error>:=<DNE>|<ZZ>
          <ZZ>:=Error: Dot <name> has already been added to the Quadtree.

INIT_QUADTREE(size, maxdepth, isect_dist) UNCHANGED

Sets a number of parameters for the quadtree.

size

gives the upper bounds for the quadtree. After initialization the quadtree should hold points/lines that fall between [0,0] at the southwest/lower left hand corner, and [ $2^{size}, 2^{size}$] in the northeast upper right hand corner. If size is less than 2 or more than 30 print an error.

maxdepth

gives the maximum recursion depth in the tree before an intersection error should be reported. A maxdepth of 0 indicates that the root would not be allowed to split- ie. the tree could hold a single edge (A,A). A maxdepth of 1 would allow the tree to be split once into four quadrants. The value given will never be 0 or 1, I only state them explicitly so that we all agree on indexing ;)

isect_dist

specifies the minimum distance between two segments before the are considered intersecting. This number will be an integer as with size, however it may be negative. The actual minimum distance should be $2^{isect\_dist}$. A value of 0 would indicate that two lines one unit apart should be treated as intersecting. For concreteness this number should be inclusive, so that in the case of 0, (1,1) and (1,2) would be considered as intersecting. This detail is mostly irrelevant, since in floating point arithmetic 'inclusive' and 'exclusive' have very little meaning.

This command will always precede the first command which requires the quadtree. This command is only valid the first time it is successfully called (out of range is not a successful call). If an attempt is made to reinitialize the tree, print an error.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Quadtree initialized.<nl>
         
          <error>:=<OOR>|<INIT>
          <OOR>:=Error: size out of range.<nl>
          <INIT>:=Error: The Quadtree has already been initialized.<nl>

LIST_DOTS()

Lists all dots in the data dictionary in increasing asciibetical order. This function will be used as a measure of success for the CREATE_DOT function.

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

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

COLOR_DOT(name,color)

Changes the color of the dot with the specified name to the color given. The change should be reflected in the map, however only the B+ Tree should be accessed for this operation. Technically this changes since it uses the B+ and not the skiplist, but if you have a clean implementation this will not require a code change.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Color of <name> changed from <oldcolor> to <color>.<nl>
         
          <error>:=<DNE>

CREATE_PATH(name1, name2)

adds a bidirectional path between the dots named to the Adjacency List. If one or both dots does not exist print the <DNE> for the first argument not found. If the segment already exists print an error. This command is not related to the PM1.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Created segment (name1,name2).<nl>
          <error>:=<DNE>|<AI>
         
          <AI>:=Error: The specified segment already exists.

MAP_SEGMENT(name1,name2) UNCHANGED

Adds a segment to the PM1.It is possible that name1==name2, this should not be an error. The PM1 should be able to know whether any given point has a path to itself or not. There is one further error to detect. If the segment intersects a segment already in the tree(except for shared endpoints), print an error and leave the PM1 unchanged. You may use this error even if the segment intersected is the same as the one you are trying to insert. Further discussion on interesection detection rules will appear on the newsgroup and later versions of the spec.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Mapped segment (name1,name2).<nl>
          <error>:=<DNE>|<ID>
         
          <ID>:=Error: Intersection detected.

UNMAP_SEGMENT(name1,name2) UNCHANGED and TESTED

Deletes a segment from the PM1. If the points do not exist, or the segment does not exist, print an error. If after the operation an endpoint would be left with no adjacent segments then it should also be completely removed from the tree. The tree should be collapsed so that it is minimal- which basically means that the tree should look as if the segment had never been in the tree to begin with. (Some collapsing will need to be done). Remember that if (A,A) is explicitly added to the tree via MAP_SEGMENT, then (A,A) must be unmapped before A is removed.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Unmapped Segment (name1,name2).<nl>

          <error>:=<DNE>|<SNF>
          <SNF>:=Error: The specified segment was not found on the map.

PRINT_QUADTREE()UNCHANGED

Prints out the PM1 Quadtree map. Be sure to read the section on the PM1 to understand what its structure must be. When printing you must print in the following order: Northwest, Northeast, Southwest, Southeast. If you reach a leaf with a dot in it you should print the dot's name, followed by all the dots it is adjacent to in some order. If a black leaf does not contain an endpoint dot, print the segment that passes through it. A tree with only one isolated point created by MAP_SEGMENT(A,A) should have output:

          A:A

IE., a one element tree should look like a leaf, even if not implemented that way.

          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>:=<name>:<namelist>|<segment><nl>
          <white_node>:= 
          <namelist>:= <name><namelist>|<name>
          <segment>:= (<name1>,<name2>)     

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

DRAW_MAP()UNCHANGED

Draws all the points and segments of the pm1 map using the java canvas class. The points should be displayed as in part1, the lines can be plain solid black lines. (If you're good with java graphics you are not required to use the canvas class, but your output should be similar). Your program should stop running until the graphics window is closed(this is the default behavior of the canvas class).

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

DRAW_QUADTREE()UNCHANGED

Draws the internal partitions of the quadtree, as well as the segments inside it. Do not draw the pretty colorful dots, as they will just get in the way of debugging.

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

NEAREST_SEG_TO_POINT(x,y) NOT TESTED

Finds the Segment in the PM1 closest to the specified point, along with the distance to the segment. If multiple segments are the same distance from the point pick your favorite. If the quadtree is empty print an error. Print the endpoints of the segment in asciibetical order.

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

          <success>:= Nearest segment: <segment>. Distance: <double>.<nl>
          <segment>:= (<name1>,<name2>)     
          <error>:= Tree is empty.<nl>

COLOR_SEGMENTS(lx,ly,ux,uy,color) NOT TESTED

A twist on the old version. This function will first locate all segments in PM1 which OVERLAP the specified inclusive rectangular region(determined by (lx,ly),(lx,uy),(ux,ly),(ux,uy)). Then it will change the color of the endpoints of those segments to the color specified. The segment endpoints will not necessarily be within the rectangle. Print the number of unique segments matched. Success can also be determined with the DRAW_MAP or LIST_DOTS commands

          Output summary:
          <output>:=<success>
          <success>:=Update complete.  Found <int> segments.

DELETE_PATH(name1, name2) NOT TESTED

Deletes a segment from the Adjacency list. If either endpoint does not exist, or the segment does not exist print an error. This command is not related to the PM1.

          Output summary:
          <output>:=<success>|<error>
          <success>:=Deleted Segment (name1,name2).<nl>
         
          <error>:=<DNE>|<SDNE>|<AM>
          <SDNE>:=Error: The specified segment does not exist.

SHORTEST_PATH(name1,name2) NOT TESTED

Prints the shortest path from the first dot to the second dot based on the segments in the Adjacency List. If either name is not in the dictionary print an error. If there is no path between the two dots (possibly because one of the endpoints was never added to the adjacency list) then print an error. Otherwise print out the shortest path, followed by the total length of the path.

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

          <success>:= <name1> -> <moredots> <nl>Total length:<double>.<nl>
          <moredots>:= <dotname> -> <moredots>| <name2>
          <error>:= <DNE>|<NP>
          <NP>:= Error: No path exists.

Web Accessibility