CSC 271
Homework 8 in C++

Assigned Nov 22, due Dec 6

A common abstract data type in computer science is the "dictionary", a collection of key/value pairs. It should be possible to look up a given key in a dictionary, find out whether it's there at all, find what value is associated with it, etc. For example, an ordinary dictionary is a "dictionary" in the computer science sense, with words as the keys and definitions as the values. A telephone book is a "dictionary" with names as the keys and phone numbers as the values. A reverse telephone book is a "dictionary" with phone numbers as the keys and names as the values. And so on. We'll implement one in C++.

1. Define a BST class that represents a binary search tree with integer keys and string values. That is, the tree is ordered by the integer keys, and each integer key has a string associated with it. It should have the following public methods:

   • a zero-argument constructor that produces an empty BST
   • a containsKey method that takes in an integer and tells whether or not that integer appears as a key in the tree
   • a lookup method that takes in an integer and returns the string associated with that integer. It should throw an exception if that integer doesn't appear as a key in the tree
   • an insert method that takes in an integer and a string, and inserts that key/value pair into the BST. It should throw an exception if there's already an entry with that key in the BST.
   • a modify method that takes in an integer and a string, and replaces the value associated with that integer with the given string. It should throw an exception if there isn't already an entry with that key in the BST.
   • a set method that combines insert and modify: if the key is already there, it modifies the entry, and if not, it inserts a new entry. It should never throw an exception.
   • an overridden << operator so it's easy to print out a BST. It should print the entries in the dictionary, showing the tree structure: for example,

      [[[[3:"hello"], 4:"goodbye", [7:"this is a test"]], 9:"huh?", [57:"isn't this fun?"]]]
     

     would represent a tree whose root had key 9 and value "huh?", its right subtree was the single node with key 57 and value "isn't this fun?", and its left subtree had key 4, value "goodbye", and children (3:"hello") and (7:"this is a test") on left and right respectively.
   • a copy constructor, which should produce a deep copy of the BST so that modifications made later to one copy don't affect the other one
   • an overridden assignment operator, ditto (but be sure to avoid memory leaks if the assignment target already contains a BST!)
   • a destructor that deallocates any memory that was allocated in order to build the BST

   As usual, there should be a test function that runs a bunch of test cases on the BST class and reports which test cases failed (or at least prints out both the actual answer and the right answer).

   You may do this with a null-terminated data structure, as you saw in CSC 172, or with a polymorphic data structure (an abstract class Tree with two concrete subclasses Leaf and Node). In either case, you may want the BST class to be just a "front end", using one or more other classes internally to actually represent the tree.

   The various methods must take advantage of the binary-search-tree structure: they should each search only either the left subtree or the right subtree, depending on whether the key being searched for is less than or greater than the key in the node at hand.

2. Generalize your BST class to a template with two parameters KeyType and ValueType. The above version would then be BST<int,string>; one should also be able to build easily a BST<float,string> with float keys and string values, or a BST<string,Employee> with string keys and Employee values, etc.

3. Once we've implemented a BST that can keep integer, float, or string keys in increasing order, it should be (almost) equally easy to build a BST with integer keys in decreasing order, or integer keys sorted by the number of prime factors, or string keys sorted by length rather than alphabetically, or Employee keys sorted by their id fields, etc. So let's modify the BST class so its constructor takes in a Comparator object, and the tree-traversing methods all use this Comparator to decide whether to go left or right.

   What is a comparator? If you were writing in Scheme, it would be just a function with contract KeyType KeyType -> boolean. In C++, it's difficult (though not impossible) to pass functions as arguments to other functions, so what we do instead is define a class with (usually) no data fields and one method, an overridden () operator that takes in two KeyType parameters. Suppose you had an instance of such a class, and you happened to store it in a variable named less. If obj1 and obj2 were both variables of type KeyType, then you could compare them by writing

   if (less(obj1, obj2)) { ... }
   

   So far that sounds like just a gee-whiz syntax hack. But suppose you had an abstract class Comparator with no data fields and a pure-virtual overridden () operator. You could define several subclasses of it -- class IncreasingIntOrder, class DecreasingIntOrder, class StringsByDecreasingLength, etc. -- each with its own definition of the () operator, and then you could create several differently-ordered BST's as follows:

   BST<int,string> tree1(IncreasingIntOrder());
   BST<int,string> tree2(DecreasingIntOrder());
   BST<string,string> tree3(StringsByDecreasingLength());
   

   The constructor for BST would take in an object of (abstract) type Comparator (presumably parameterized to the correct KeyType), memorize it in an instance variable, and use it subsequently to decide whether to go left or right in a tree.

   It probably makes sense for the constructor argument to default to a < comparison, so BST<int,string>() produces a BST with int keys, string values, with the keys sorted in increasing integer order.

   You can do a Web search for ideas on this; a few relevant hits are here and here.