- 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(
)
and
keys, with exactly one more child than the number of keys
at all times. (this implies between ceiling(
)
and 
children per node, inclusive).
Leaf: must always contain between ceiling(
)
and
keys, inclusive. Must not contain 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_BPTREE. 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 [
] 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
. 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.
