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.