Sale!

EECS 268:  Laboratory 9

$30.00

Category:
Rate this product

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.

Scroll to Top