CSE 222 Lab #4

Objectives

Familiarity with writing a concrete template class for a new type and its kernel operations (Partial_Map layered on Binary_Tree of Records, using a binary search tree).
Familiarity with developing and using specification-based test plans.

The Problem

The problem is to complete and carefully test implementations of all the operations of abstract template Partial_Map_Kernel, building the data structure representing a Partial_Map object by layering it on top of abstract templates Binary_Tree_Kernel and Record. The algorithmic approach is to use a binary search tree to reduce search time from linear (as in Partial_Map_Kernel_1) to logarithmic in the number of pairs in the map; at least, there is this reduction in execution time "on average", though not in the worst case.

Method

Here's what to do:

Copy the initial lab #4 files to your own working directory and get into that directory:
```
cp -R /class/sce/now/222/labs/lab04/Lab04/ .
```
```
cd Lab04
```
Get into an emacs window and visit your Lab04 directory. You should see a file called Partial_Map_Test.cpp, a test driver you can use for testing. Please look at this file, especially the first portion that creates the required utility class Natural_Are_In_Order_1 and that lists the concrete instances it uses; but you shouldn't have to edit this file before building it because it already contains the code to instantiate your Partial_Map_Kernel implementation with D_Item bound to Natural_Number_1_C and R_Item bound to Integer. The executable file Partial_Map_Test_Sample has been compiled from this test driver with a correct implementation of Partial_Map_Kernel, and can be used, as in recent closed labs and the last lab, to create and debug a test script for regression testing. In fact, you can use or even embellish your test script from the previous lab.
Complete the skeleton kernel body file CT/Partial_Map/Kernel_6.h (which initially contains empty bodies for the operations to be implemented) by supplying code for the bodies of the public interface operations Undefine, Undefine_Any, Is_Defined, the accessor, and Size, and the private operations Remove_Pair_From_Tree, Remove_Smallest_Pair_From_Tree, and Is_In_Tree. By the way, as you are reading the specifications for the local (private) operations that manipulate binary search trees, notice the extra and separate formal comment "decreases". The "decreases" clause is something every recursive procedure or function body should have to make a convincing argument that the recursion will terminate. It does not mean that the net effect of the operation is to decrease the size of the tree!
When you are satisfied that your program works, get into your Lab04 directory in an xterm window and use the submit command to submit your solution as follows (noting that you will need to use the appropriate suffix in place of ?? in this command, as posted next to your instructor's name on the CSE 222 Home Page):
```
submit c222?? lab4 CT/Partial_Map/Kernel_6.h
```
If you get an error message rather than a confirmation of success, please read the message; it contains useful information! Do not just run the same command again. Save the e-mail you get as a receipt of submission, just in case.

Possible Maintenance Activities

Here are some questions about possible maintenance activities involving this program:

Record actual execution times of the public operations, comparing them to those for the previous lab's hashing implementation of Partial_Map_Kernel.
Devise some other approach to using the "cached" pair (e.g., keeping a boolean flag to tell whether the cache is "occupied" rather than always keeping it occupied when possible), and update the convention and correspondence as well as the code to reflect this different approach.
Find a balanced tree scheme, i.e., one that keeps the binary search tree balanced so its depth is always logarithmic in the number of pairs stored, and modify your code to incorporate it. (If you decide to try this, please contact your instructor first for some advice!)
Record actual execution times of the public operations with a balanced tree scheme in place, comparing them to those without balancing and to those for the hashing implementation of Partial_Map_Kernel.

Any extra work is strictly optional, for your own benefit, and will not directly affect your grade.