COSC 072/503 Project 5

COSC 072/503: Computer Science II

Project 5
Spring 2009

Due: Mon, Apr 27 @ 10 PM
10 points

For this project, we are going to implement a tree of trees. To be more precise, we are going to implement a binary search tree and use it to store information about trees (real ones).

A real tree has five data members: scientific name, common name, alternate name, family, height, and diameter. The input format for a tree is as follows:

"Magnolia acuminata" "Cucumbertree" "Cucumber Magnolia" "Magnolia" 80 2

Additional examples of trees are in the file trees.dta. I derived this data set from eNature.com. Do not change the input format of the trees. You can get a copy trees.dta on seva with the command:

seva% cp ~maloofm/cosc072/trees.dta ./

To make things (really) simple, do not worry about implementing a full set of set and get methods, and do not worry about range checking. You can assume that all of the input will be complete and accurate. Implement a default constructor, a print method, and a read method that reads values for the private data members from an istream.

We will use the scientific name as the unique key for trees, so in addition to the previous methods, the Tree class must implement the method getKey, which for the Tree class, will return the object's scientific name. This method will be useful for implementing the find method for the binary search tree.

Also implement Tree::operator<, Tree::operator>, and Tree::operator==. These methods return true if the scientific name of one tree is less than, greater than, or equal to the scientific name of a second tree. These methods will be useful for implementing the insert method for the binary search tree.

Morph Node<T> from p3 into TreeNode<T> by changing prev to left and next to right, as we discussed in lecture.

Design and implement the class BST<T,K> for a binary search tree. The template variable T refers to type of the objects stored in the binary search tree. The template variable K refers to the type of the key. This class is an extension of the class BST<T>, which we have been developing in lecture.

For this project, since we'll be using the Tree class, the type of the key (i.e., the scientific name) is string. Thus, in main, we can instantiate the BST class by writing:

BST<Tree, string> bst;

To insert a Tree into the binary search tree, we can write:

BST<Tree, string> bst;
Tree tree;
tree.read( cin );
try {
  bst.insert( tree );
  ...
} // try
catch ( DuplicateKey &e ) {
  ...
} // catch

To find a tree in the binary search tree, we can write:

string key;
getline( cin, key );
try {
  Tree &tree = bst.find( key );
  ...
} // try
catch ( KeyNotFound &e ) {
  ...
} // catch

In addition to the obvious required methods (constructors, destructor, insert, and find), implement a print method that prints to cout the preorder traversal of the tree. You do not need to implement methods for printing other traversals. You do not need to implement methods for removing elements from the tree.

It is important for the BST<T,K> to be completely generic with respect to the Tree class. That is, BST<T,K> must work for any class T that implements operator<, operator>, operator==, and K T::getKey(), where K is the type of the key,.

The main function should take a file name passed in from the command line and process the commands therein. There are four commands: C for clear, P for print, I for insert, and F for find. The I command will be followed by the object to be inserted. The F command will be followed by the object's key to be found.

Assume that the file t0.in contains the sample input:

I "Acer pseudoplatanus" "Planetree Maple" "Sycamore Maple" "Maple" 60 2
I "Acer ginnala" "Amur Maple" "N/A" "Maple" 20 0
I "Liriodendron tulipifera" "Yellow Poplar" "Tulip Tree" "Magnolia" 120 3
F Acer pseudoplatanus
F Liriodendron tulipifera
P

which might produce the output:

seva% a.out t0.in
Inserting Acer pseudoplatanus...

Inserting Acer ginnala...

Inserting Liriodendron tulipifera...

Finding Acer pseudoplatanus...found
Scientific Name: Acer pseudoplatanus
Common Name: Planetree Maple
Alternate Name: Sycamore Maple
Family: Maple
Height: 60
Diameter: 2

Finding Magnolia virginiana...not found

Printing:
Scientific Name: Acer pseudoplatanus
Common Name: Planetree Maple
Alternate Name: Sycamore Maple
Family: Maple
Height: 60
Diameter: 2
---
Scientific Name: Acer ginnala
Common Name: Amur Maple
Alternate Name: N/A
Family: Maple
Diameter: 20
Height: 0
---
Scientific Name: Liriodendron tulipifera
Common Name: Yellow Poplar
Alternate Name: Tulip Tree
Family: Magnolia
Height: 120
Diameter: 3
seva%

You will be graded on how well your implementation passes our tests, the completeness of your design, and the quality of your implementation. You do not need to document the class.

Instructions for Electronic Submission

At the top of the file main.cc (or the file containing the main function), place the following header comment, with the appropriate substitutions:

/*
 * COSC 072 Project 5
 * Name: <your name>
 * ID: <GoCard ID>
 * E-mail: <e-mail address>
 * Instructor: Maloof
 * TA: <TA's name>
 *
 * In accordance with the class policies and Georgetown's Honor Code,
 * I certify that, with the exceptions of the class resources and those
 * items noted below, I have neither given nor received any assistance
 * on this project.
 */

Instructions for Electronic Submission

If you need to include a message to your TA about your submission, then place the message in a file named README. Place the README file in the project's directory.

Assuming all of your code is in the subdirectory p5, directory, this directory and the submit program should be in the same directory:

seva% ls
p5/ submit.jar

To reduce the size of the zip file, before submitting, remove all object and executable files:

seva% cd p5
seva% make clean

If you need to include a message to your TA or me about your submission, then place the message in a file named README. Place the README file in the project's directory.

To move from the p5 directory to the parent directory, type

seva% cd ..

At this point, you should be above the p5 directory:

seva% ls
p5/ submit.jar

(Additional useful Unix commands)

When you are ready to submit, change the name of the directory to your netid. For example, if your netid is maloofm, then rename the directory p5 by typing

seva% mv p5 maloofm

Create a zip file of the directory and its contents by typing

seva% zip -r p5.zip maloofm/*

This command creates a zip file named p5.zip by recursively (-r) copying all of the files (*) from the directory maloofm/.

To submit the zip file type

seva% java -jar submit.jar -a p5 -f p5.zip

p5 is the name of the assignment (-a) and p5.zip is the file (-f) to be submitted for that assignment.

If the program submits the file successfully, you will receive a receipt by e-mail at the address <netid>@georgetown.edu.

Submit your project only once.

Once you've submitted your project, it is important to keep an electronic copy on a university machine (e.g., seva) that preserves the modification date and time. If we lose your project or the submission system breaks, then we will need to look at the modification date and time of your project to ensure that you submitted it before it was due.

You can also change the directory's name back to the original name. For example,

seva% mv maloofm p5

Note that changing the name of the directory does not change the dates of the files in the directory. You can also remove the zip file from your directory:

seva% rm p5.zip

The TA who will be grading your projects this semester is listed on the main page. You must submit your project before 5 PM on the due date.

Plan B

Submit is pretty reliable, but it is software. If you're running submit correctly and you see an error message labeled as SEVERE, then it's time to execute Plan B by using mail to submit your project.

To accomplish this, assuming the file you want to submit p5.zip, type at the seva prompt

seva% uuencode p5.zip p5.zip | mail cosc072@cush.georgetown.edu

Briefly, uuencode encodes the binary file p5.zip as an ASCII file that can be transmitted as mail. This form of the uuencode command pipes the ASCII-encoded file through standard input and into (|) the mail command.

When we receive you mail, we will save it to a file and use uudecode to translate the ASCII-encoded file back to the original binary file. Virtually all mail clients automatically encode binary files in this way.

Please don't use this account for communication. We don't check it regularly.