Required Part 3 Commands

You are required to attempt the following commands.

INIT_BPTREE(order)

This command takes one parameter: the order of the B+ tree to be created, which is an integer that is greater than or equal to three (3). All B+ trees that are created during a given execution of your code must have this order. If the B+ tree order has not been initialized, this command will initialize the B+ trees to have the specified order and print the <success> message. If the parameter order is less than three (3), print the <error> message <InvalidBPTreeOrder> If the B+ tree order has already been initialized, then you should print the <error> message <BPTreeOrderAlreadyInitialized>.

If any other command involving the B+ tree is attempted before the B+ tree order has been initialized, then print the <error> message <BPTreeOrderNotYetInitialized>. Although this error message is a "user-level" exception thrown by several other commands, we mention it here because consideration of how to deal with it might have an impact on this command as well.

Output summary:
<output>:=<success>|<error>
<success>:=Initialized B+ trees to order <order><nl>
<error>:=<BPTreeOrderAlreadyInitialized>|<InvalidBPTreeOrder>

EXIT()

This is the simplest command. It should end the program. Print mission complete and exit the program. Your program should also naturally terminate (with no exit message) when the end-of-file is reached.

Output summary:
<output>:=mission complete<nl>

CLEAR_ALL()

This command takes no parameters. This command should delete all entries from the dictionary, spatial data structure, adjacency lists, and inventory heap. (Hint: You don't actually have to perform any delete operations on any of these objects.) The confirmation message structures cleared should be printed.

Output summary:
<output>:=structures cleared<nl>

CREATE_LOCUS(LocusName, longitude, latitude, radius)

This command takes four (4) parameters: the name of the locus as a case insensitive string; the longitude (which represents the x coordinate) as an integer; and the latitude (which represents the y coordinate) as an integer; and the radius as a non-negative integer. Unless otherwise stated, the radius of a locus is zero (0).

Both longitude and latitude should be integers in the range [0, 1024]. Your Mediator should parse this information and store it in a Locus object. If the dictionary does not already contain a locus by the same name or same coordinates, you should add the Locus to the dictionary and print the <success> message. If there is a Locus in the dictionary with the same name or coordinates, you should print the <LocusAlreadyExists> error message using the Locus that is currently in the data dictionary, NOT the locus specified in the command parameters. Note that loci should be sorted asciibetically by their case insensitive name.

Sites are a distinguished subclass of Loci having a non-zero radius. For the purposes of Part 3, a Loci is a Site iff (if and only if) the radius is positive. And, the radii of all Loci are non-negative (meaning either zero or positive).

Since the type of loci is encoded in the naming conventions, you should check for type mismatches between the LocusName, and the radius and print the corresponding error message. For example, if someone where to try to add a junction with a radius$>0$, you should print the <NotSitePosRadius> error. Likewise, if someone tried to add military base with the radius equal to zero, you should print the <SiteWithZeroRadius> error. And, finally, detection of coordinates already present in the specific data dictionary, using, perhaps, the TreeMap used for spatial structures in Part 1. All of these operations should be in O(log n), and we will test this!.

This command functions almost identically to CREATE_SITE except it creates a generic Locus rather than a Site.

First Character	Encoded LocusType
A	Air Unit Site
B	military Base Site
C	Civilian territory Site
E, F	Reserved-illegal locus name
G	Ground unit Site
H	Hospital Site
I	Interesting Places
J	Junction
M	MASH Unit
P	Pantry and Supplies
S	Shelter
W	Weapons
other	Unassigned

Output summary:
<output>:= <success>|<error>
<success>:=Created locus <LocusName><nl>
<error>:=<BPTreeOrderNotYetInitialized>|<InvalidLocusType>|
         <LocusAlreadyExists>|<SiteWithZeroRadius>|<NotSitePosRadius>>

DELETE_LOCUS(LocusName)

This command takes in one parameter: the name of the site or locus as a case insensitive string. Your Mediator should search the dictionary dictname for a locus with the specified name. If you find a locus with that case insensitive name and the locus has not been added to the spatial data structure, remove it from the dictionary and print the <success> message. If the locus is in the dictionary but has already been added to the spatial data structure, then print the <UnableToDeleteLocus> error message. If the locus cannot be found in the dictionary, print the <LocusDoesNotExist> error. This should be an O(log n) operation.

Output summary:
<output>:=<success>|<error>
<success>:=Deleted locus <LocusName><nl>
<error>:=<BPTreeOrderNotYetInitialized>|<LocusDoesNotExist>|<UnableToDeleteLocus>

LIST_LOCI()

This command takes no parameters. This command should print out a list of all of the loci in the dictionary in asciibetically sorted order. If the dictionary is empty, print the <NoLociEntered> message. If there are loci in the dictionary, print them as described below. Note that locus names are case insensitive.

Please note that the error message has changed for this command.

Output summary:
<output>:=<success>|<error>
<success>:=<LocusList>
<error>:=<BPTreeoOrderNotYetInitialized>|<NoLociEntered>

PRINT_BPTREE()

The purpose of this command is to print out the structure of the B+ tree used as a data dictionary by doing a breadth first search. However, if you used links between internal nodes you can produce the same results as BFS with much cleaner code.

The output is formatted so that each level of the tree is enclosed in braces {}; each node is enclosed in parentheses; guide values in each internal node are separated by spaces; key values within leaf nodes are separated spaces. Each level of the tree should appear on its own line and in order. Thus, a tree of order three (3) with five keys (names of sites) might look like this:

{(BOWIE)}
{(BALTIMORE) (COLLEGE PARK)}
{(ANNAPOLIS) (BALTIMORE) (BOWIE) (COLLEGEPARK HOLYCROSS)}

Note that by convention, the leaf containing the key "COLLEGEPARK" (the key of the object of type "civilian territory" with site name "COLLEGEPARK") is a right child of the internal node containing the guide value " COLLEGEPARK". That is, we have a rule for dealing with equal guide and key values.

Even at the leaves print only the key (the locus name). If the data dictionary is empty, print the <NoSitesEntered> message. Your tree is not expected to match ours exactly. Your grade will be based on your tree displaying the properties described below.

For our order m tree in Part 3, the leaves wil contain between ceiling(m/2) and m keys, inclusive. Internal node must have between ceiling(m/2) and m children, inclusive. For each internal node, the number of guide values printed must be one less than the number of child nodes, meaning that (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>:=<LocusName>
<error>:=<BPTreeOrderNotYetInitialized>|<NoLociEntered>

INPUT_LOCUS(LocusName):

This command annulled. Will disappear in the next version of the specification.

INSERT_SITE(SiteName):

This command takes one parameter, the name of the site to add to the map as an isolated site. If the string <SiteName> does not satisfy the naming conventions for a site, print the <SiteNameNotASite> If site <SiteName> is not in the data dictionary, you should print the <SiteDoesNotExist> error. If site <SiteName> does exist, attempt to add it to the spatial map. If an intersetion is detected, you should print the <SpatialIntersection> error, otherwise, success.

output summary:
<output>:=<success>|<error>
<success>:=Inserted Site <SiteName><nl>
<error>:=<BPTreeNotYetInitialized>|<SiteNameIsLocus><SiteDoesNotExist>|<SpatialIntersection>

INPUT_TRACK(name, startLocus, destinationLocus, weight, two-way)

This command has been annulled.

INSERT_TRACK(startLocus, destinationLocus, weight, two-way)

This command takes four (4) parameters: the name of the track as a case insensitive string, the name of the start and destination loci as a case insensitive strings, the weight (cost) of the track connecting these loci as a double, and the type of track to input (1 for a OneWayTrack, 2 for a TwoWayTrack). Consider creating an abstract Track and a concrete OneWayTrack and TwoWayTrack.

You are permitted to assume that when grading, we will enter values greater than or equal to zero for the weights (even though you'd really be silly to assume this for debugging purposes, or in case your user makes a mistake). Similarly, you can assume that the parameter <two-way> will be a valid integer equal to 1 or 2, with the obvious definitions.

If startLocus and destinationLocus are the same, print the <StartAndDestinationSame> error message. If either locus has not been added to the dictionary, print the <LocusDoesNotExist> error message. (The <LocusDoesNotExist> message for startLocus takes precedence over destinationLocus.) If either of the loci has not been added to the map, print the <LocusNotMapped> error message. (Again, startLocus takes precedence over destinationLocus.) If a track by the same case insensitive name connecting the same loci already exists, then you should print the <TrackAlreadyExists> error message. If either the start or destination locus is of type Site, then you should print the <LocusIsSite> error message.

If the loci are different, are not sites, exist in the dictionary, have been added to the map (the spatial data structure), and if no-other track connecting the same two sites (either one way or two way) exists already insert a Track object of the appropriate type (one (1) or two (2) way) starting at startLocus and going to destinationLocus. Attempt to add the Track to the spatial data structure. If you detect an intersection while attempting to insert the Track into the spatial data structure, print the <SpatialIntersection> error message. If there is no intersection (i.e. the Track was successfully inserted into the spatial data structure), add the Track to the adjacency list(s), and print the <success> message. Please remember to handle OneWayTrack and TwoWayTrack objects properly in the adjacency list.

Note: One way tracks are directed edges going from startLocus to destinationLocus. Two-way tracks are undirected edges connecting startLocus and destinationLocus. It is not possible to have two or more tracks with the same name, nor is it possible to have two or more tracks connecting the same two sites because we are not using names to distinguish among them. Thus, the startLocus, and destinationLocus are the unique key for the track

Output summary:
<output>:=<success>|<error>
<success>:=Inserted track <Track><nl>
<error>:=<BPTreeOrderNotYetInitialized>|<LocusIsSite>
         |<StartAndDestinationSame>|<LocusDoesNotExist>
         |<LocusNotMapped>| <TrackAlreadyExists>|<SpatialIntersection>

PRINT_TRACK_GRAPH:

TBD. This will be used to output the adjacency list corresponding to the graph of tracks connecting loci only. Since sites are isolated points, there is no reason for them to be contained in a structure associated with nearest neighbors of loci.

Would someone kindly write a BNF for this. Not pb:: He's off for a few days to recover his strength.

REMOVE_TRACK(startLocus,destinationLocus)

Delete track will be an optional command. If you have not implemented this portion the PM1 delete, then any attempt to use REMOVE_TRACK in Part 3 should result in the <InvalidCommand> error message. Otherwise, implement the command as described below in Section 8.8.

REMOVE_SITE(SiteName)

this is an optional command. If you have not implemented this portion of the PM1 delete, then any attempt to use REMOVE_SITE in Part 3 should result in the <InvalidCommand> error message. Otherwise, implement the command as described below in Section 8.8.

FIND_IN_SITE(SiteName,LocusType)

This command takes in two parameters: the name of the site in which you are searching as a case insensitive string, and the LocusType indicates the loci for which your are searching. This command finds all of the loci of a the specified type that fall within the limits of the specified site.

If the LocusType does not fall within the set of valid locus names, print the <InvalidLocusType> error message. Search the data dictionary to see if the Site exists. If the site could not be found, print the <SiteDoesNotExist> error message. Search the spatial structure for the site to ensure that it is mapped. If it is not, print the <SiteNotMapped> error message. If the site is found you, search the spatial data structure for all loci of LocusType that reside within the site limits, which is the circle determined by the radius and center of the Site, and all points inside that circle.

Please note that you should just use simple Euclidean geometry to determine the distance. That is, pretend that the world is flat. ;)

The <FindInSiteLocusList> should be printed in order from the closest point to the farthest point. You should break ties using the asciibetically ordering of the Locus's name. You should also print the distance from the Site's coordinates (the circle center) as a double.

Output summary:
<output>:=<success>|<error>
<success>:=<FindInSiteLocusList>
<error>:=<InvalidLocusType>|<SiteDoesNotExist>|<SiteNotMapped>|<NoLociEntered>

PRINT_MAP()

This command takes no parameters. This command prints the spatial data structure (in part 3, a PM1 quadtree) in the order (NW, NE, SW, SE). Before going in any direction, you should print out the direction you are about to go. Only one direction should appear on a line. You should also indent 2 spaces for each level of depth in the treee.

There are two types of output for a black node: If the black node contains a point and any number of q-edges, print the locus corresponding to that poiot on the same line as the last direction printed. If the black node containsa a single q-edge without it's endpoints, print the track corresponding to that q-edge on the same line as the last dirction printed.

For instance, a tree containing the Wawa (WAWA, 0, 1000), Lasicks (LASICKS, 1000,0) and two-way track Route 1 (RT1, WAWA, LASICKS, 5) would print as:

           NW weapons: WAWA at (0,1000)
           NE
           SW RT1 (WAWA <=> LASICKS)
           SE unassigned: LASICKS at (1000,0)

If Mandalay (MANDALAY, 500,600) were added, the output would look like:

           NW
             NW weapons: WAWA at (0,1000)
             NE
             SW
             SE
               NW RT1 (WAWA <=> LASICKS)
               NE
               SW RT1 (WAWA <=> LASICKS)
               SE
                 NW RT1 (WAWA <=> LASICKS)
                 NE MASH unit: MANDALAY at (500,600)
                 SW RT1 (WAWA <=> LASICKS)
                 SE RT1 (WAWA <=> LASICKS)
           NE
           SW RT1 (WAWA <=> LASICKS)
           SE unassigned: LASICKS at (1000,0)

Output summary:
<output>:=<success>|<error>
<success>:=<black_node>|<grey_node>
<grey_node>:=<nl>NW <pm_tree>NE <pm_tree>SW <pm_tree>SE <pm_tree>
<pm_tree>:=<black_node>|<white_node>|<grey_node>
<black_node>:=<Locus><nl>|<Track><nl>
<white_node>:=<nl>
<error>:=<success>:=<LocusName>|
<error>:=<InvalidLocusType>|<SiteDoesNotExist>|<SiteNotMapped>|<NoLociEntered>

DRAW_MAP()

This command takes no parameters. This command will draw a graphical map by examining the quadtree and drawing the partitions, the points in the quadtree, and all of the tracks that are in the adjacency list and print the <success> message. Although you are welcome to make use of any drawing mechanisms in JAVA, we recommend that you use the CanvasPlus drawing package on the class web page which was written specifically to support this feature.

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 only be eye-balling your drawing during grading; so, as long as you have a picture that represents the mapped sites and the roads somewhat correctly we'll be happy.

Note that this function is primarily to help *you* debug your code. It will be very helpful in Part 2 to help you determine if your UNMAP_SITE function is working correctly and it will become an invaluable debugging tool for your PM1 quadtree in Parts 3 and 4.

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