CMSC-341 Fall 2004
Project 4
Assigned |
10 Nov 2004 |
Due |
23 Nov 2004 at 11:59PM |
Description
In this project you will implement a bottom-up Splay Tree based on
existing Binary Search Tree code.
Here are your tasks:
- Obtain the files SplayTree.h, SplayTree.cpp, and
dsexceptions.h from the following location:
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj4/
The first two of these files are identical to BinarySearchTree.h and
BinarySearchTree.cpp. The only difference is that they have been
renamed, and the strings BinarySearchTree and BinaryNode in the code
have been replaced with SplayTree and SplayNode, respectively.
- The code in SplayTree.h and SplayTree.cpp implements a Binary
Search Tree. Modify this code to support bottom-up insert, remove,
and find Splay Tree operations.
- Write Proj4.cpp and any supporting files required to process
command files.
- Answer the questions posed in 341-Fall04-proj4_questions.txt. Copy
the file
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/Proj4/341-Fall04-p4_questions.txt
to your own directory and edit it to provide your answers to the questions.
Don't forget to submit the edited file; it's 10% of this project's
grade.
Definition of the ADT
In this project you will convert BST code to bottom-up Splay Tree
code, and write code to read and process commands from a file that
will exercise the Splay Tree code. Recall that BST and Splay
operations are similar:
- To insert a value into a bottom-up Splay tree, you insert the
value as if inserting into a BST and then splay the new node to the
root of the tree.
- To find a value in a bottom-up Splay tree, you find the value as
if finding in a BST and then splay the node containing the value to
the root. If the value is not found, then you splay the last node on
the failed search path.
- To remove a value from a splay tree, you find it, splay it to the
root, detach the left and right subtrees of the root node, delete
the root node, splay the largest (smallest) value in the left (right)
sub-tree and make other sub-tree the right (left) sub-tree of the
node just splayed.
Your primary task is to implement a bottom-up splay routine. Your
secondary task is to modify the insert, remove, and find routines
provided so that they use this splay routine as appropriate.
You may modify the provided code in any way you see fit. Clearly, you
must modify the insert, remove, and find routines. If other routines
will work for you as they are, or if you don't need them to process
commands (see below) you don't need to modify them.
The Command Line
Project 4 will be invoked with a command line that consists of one
argument - the name of a file that contains a set of operations that
must be performed. The format of this file is described in the command file section below.
Note that you must check command line arguments to ensure that they
are valid, e.g. that the command file can be opened, and print an
appropriate message if an error is found.
The Command File
Commands in the file specify operations to be performed. Each line in
the file represents one command. Blank lines may appear anywhere in
the file and should be ignored. Otherwise, you can assume that any
line containing a command is syntactically well-formed. We make this
assumption so you don't have to spend lots of time making the command
file parser bullet proof.
Each command should be applied to a single Splay Tree that is
allocated by your program.
Echo each command as it is read.
The command file format follows:
- INSERT N V1 V2 ... VN - This command asks you to insert N integer
values (V1 through VN) into the Splay Tree. The value -1 will never
be inserted into the tree via this command.
- REMOVE V - This command asks you to remove the specified value (V)
from the splay tree. If the value exists in the tree, remove it and
print a message indicating success. If the value does not exist in
the tree, print a message saying so.
- FIND V - This command asks you to find the specified value (V) in
the tree. Print a message indicating whether or not the value was
found.
- PRINT - Print the contents of the tree in level order.
Sample Output
The following input file:
INSERT 5 10 20 30 40 50
FIND 20
REMOVE 20
FIND 20
creates the following output:
Command: INSERT 5 10 20 30 40 50
Command: FIND 20
20 was found
Command: REMOVE 20
20 was successfully removed
Command: FIND 20
20 was not found
Files To Be Submitted
Submit all files required to build an executable named Proj4 by
running make.
Submit the files using the procedure given to you for your section of
the course.
If your makefile is set up correctly, you should be able to execute
the command make submit.
Submit Tools
There are a number of tools available to you to check on your submittal.
It is your responsibility to ensure that the submittal is correct and will
result in a successful
compilation of your project. Do not wait till the last minute to submit
your files. Give yourself enough time to check that your submittal is correct.
If you don't submit a project correctly, you will not get credit
for it. Why throw away all that hard work you did to write the project?
Check your
submittals. Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/.
One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.
Additionally, there are two programs for use only by CMSC-341 students
(not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/o/a/oates/pub/CMSC341/ and are
named submitmake and submitrun. You can
use these programs to
make or run your submitted projects.
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj4
This makes the project, and shows you the report from the make utility.
It cleans up the directory after making the project (removes .o and ii_files),
but leaves the
executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341Proj1 checkers checkfile.dat
This runs the project, assuming there is an executable (i.e. submitmake
was run successfully).
Grading and Academic Integrity
Your project will be tested using a variety of command lines, some of which
will be invalid.
Your project will also be tested using a variety of command files which
will test various conditions which your code should handle.
Project grading is described in the Project
Policy handout.
Your answers to 341-Fall04-proj1_questions.txt
are worth 10% of your project grade.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for
this course.
Remember, the due date is firm. Submittals made after midnight of the
due date will not be accepted. Do not submit any files after that time.