Homework #7 -- Templates and Operator Overloading

Assigned: Thursday, April 19, 2001

Due: At the beginning of class, Wed, April 25

Worth: 30 points, Late papers will be docked 5 points per 24 hour period

Collaboration: As usual, you may discuss this homework with anyone in the class. For this assignment you may also work in groups of three or less. If you work in a group, please turn in just one copy of your assignment with all group members' names included. All group members will receive the same grade.

Turn In: A copy of BST2.h. In addition, create a directory in /submissions called BST2 and in it place a copy of BST2.h.

Objective: Templates and operator overloading are intermediate C++ topics with which you should be familiar. This assignment gives you the chance to practice implementing them. Plus they are just cool!

What to do:

1. Get a copy of BST2.h from ~vanbusum/public. You will be modifying this file to turn in. (If you would prefer to modify your own BST class, that is fine, but my file is set up specifically for these directions, and you may run into trouble if your implementation is different.) Note: Most compilers will not allow the declarations for a templated class to be in the .h file and the implementations to be in the .cpp file. I will discuss how this is typically handled in class, but for this assignment, put your code and declarations both in the .h file.

2. Get a copy of BST2drv.cpp from ~vanbusum/public. Modify this code to test your BST class. You will not turn the driver in.

3. Template the BST class. Be sure you are familiar with the template reading distributed in class. You will need to make the following changes in BST2.h to make it templated:

Right before class BST in your .h file add: template <class T>

In your struct, value should be of type T

Before each function implementation, add: template <class T>

In each function implementation change (for example):

nodeptr BST::find(…) to

BST<T>::nodeptr

BST<T>::find(…)

4. Test this with your driver.

5. Overload the following operators: ==, <, >

We are defining these operators as follows:

Tree1 == Tree2 iff (the sum of the values in Tree1 == the sum of the values in Tree2)

(So, if Tree1 has nodes 2, 3, and 5, and Tree2 has just node 10, Tree1==Tree2)

Tree1 < Tree2 iff (the sum of the values in Tree1 < the sum of the values in Tree2)

Tree1 > Tree2 iff (the sum of the values in Tree1 > the sum of the values in Tree2)

I have already implemented the overloaded functions themselves in BST2.h. Make sure you are familiar with how these functions work. Your job is to implement

void calcsum(nodeptr thenode, int& sum);

//This function should be private (although you can make it public for testing).

//It should take a pointer to the root of a tree and return the sum of all of its values. If the //tree is empty, the sum should return 10,000. (We are calling this INFINITY.)

//Hint: You need to traverse the tree… Your function should be similar to another

//traversal routine, such as inorder().

6. Test overloading with your driver.

7. When everything works, go out and celebrate. You have finished you last homework for this class!