EECS 268: Laboratory 9

EECS 268:
Laboratory 9
Due: This lab is due before the start of your lab that would meet the week of December 3. (Labs will not actually meet that week, but your lab is due at that time. Note also that labs will not meet the week of November 19.)
Introduction
In this lab, you will implement several methods of the BinarySearchTree class, using the BinaryNode data structure for the nodes in the tree. You are not allowed to add to, remove from, or modify the public interface to either of these classes. In addition, you must implement each method in the public interface, whether you think it will be used in this project or not.
Project Requirements
Begin by implementing all public methods of the BST class as specified in the header file linked above. Be sure to carefully read the comments in the header file for important requirements of the BST as well as of the instantiating ItemType. Among other things, this will give you insight into how to implement various BST methods. Note also that you will have to define the various exceptions declared in the BinarySearchTree header file. You will need to create the header files for those exceptions that are referenced and put your exception definitions in those files.
You will be developing a task management application. Tasks are given unique integer task IDs, and these IDs will be the KeyType for the BST. A task record will be the ItemType and will have the following fields, all of which must be stored in private instance variables:
•    int taskID
•    string taskName
•    int estimatedTimeToComplete
•    int timeAddedToBST
•    int timeStarted
Note that in addition to the ordinary methods you will need for this Task class, certain relational operators will also be needed as described in the BST header file whose link is above. Be sure you implement those.
The simulation will proceed by reading a file that describes task arrivals, departures, and other queries and transactions. Your Executive will keep track of time by incrementing the current time by 1 each time it reads a new transaction from the file. The first transaction happens at time 1; the second at time 2; etc. The complete list of transactions is:
Transaction    parameters    Example    Notes
add    id name estimatedTime    add 38297 Drive_Home 10    If the task already exists, report an error and ignore this transaction. Otherwise initialize "timeAddedToBST" to the current time; initialize "timeStarted" to -1 (the task doesn't start until the "start" directive is processed). Report that the task has been added.
finish    id    finish 31077    If the task does not exist, or if it has not yet started, report a suitable error and ignore the transaction. Otherwise remove the task from the BST and report its statistics. Report also the time at which it is finishing.
started    id    started 21867    Report whether the task has started or not; if the task is not in your BST, report that instead.
start    id    start 38553    locate the indicated task. If not found, report an error. If found and it has already started, report an error. If found and it has not already started, start it by recording its start time as the current time. Print a message saying it has started, and print its statistics.
taskPresent    id    taskPresent 44623    If the task is present, print its statistics. If not, print a suitable message.
height         height    Get the height of the BST and report it to the console.
numberNodes         numberNodes    Get the number of nodes in the BST and report that to the console.
flush         flush    Using an appropriate traversal scheme (be sure to pick the correct one, because only one will work!!!), traverse the tree and do the following on (the ID in) each node in the traversal order: (i) if it has not yet started, do a "start" on the ID; (ii) do a "finish" on the ID.
By "report a task's statistics", I mean produce a well-formatted display that labels and prints all the fields of the Task. If the task has not yet started, report that instead of something like "timeStarted = -1". From a design perspective, making the printing of statistics a method of the Task class would be a really good idea.
Sample Data Set
1.txt
Grading Criteria
As usual, we may test your code using different data files, so be sure your reading and parsing is robust. Grades will be assigned according to the following criteria:
•    50%: Correct implementation of the BST methods. Breakdown:
•    10%: isEmpty, getHeight, getNumberNodes
•    10%: add
•    15%: remove
•    15%: getEntry, contains, setEntry
•    30%: Good implementations of the Task and Executive classes. Breakdown:
•    10%: Parsing and processing commands
•    10%: Output formatting and clarity
•    10%: Modularity and Design (don't copy and paste code; break the implementation down into nice reusable modules)
•    10%: Comments and documentaton
@author, @file, @date, @brief (the author, file name, current date, and a brief description of a file) at the top of every file!
@pre, @post, @return, (Pre conditions, Post conditions, Return descriptions) in header files.
•    10%: No memory leaks
Submission
Create a tarball with your source code in the usual way.
Email this tarball to your TA. The email subject line must look like "[EECS 268] Submission Name" as follows:
[EECS 268] Lab 09
Note that the subject should be exactly like the line above. Do not leave out any of the spaces, or the bracket characters ("[" and "]"). In the body of your email, include your name and student ID.