CSE 222 Lab #3

Objectives

Familiarity with writing a concrete template class for a new type and its kernel operations (Partial_Map layered on Array of Queue of Records, using hashing).
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 Array_Kernel, Queue_Kernel, and Record. The algorithmic approach is to use hashing to immediately narrow every search to a much smaller Queue than would otherwise be encountered.

Method

Here's what to do:

Copy the initial lab #3 files to your own working directory and get into that directory:
```
cp -R /class/sce/now/222/labs/lab03/Lab03/ .
```
```
cd Lab03
```
Get into an emacs window and visit your Lab03 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_Hash_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, to create and debug a test script for regression testing.
Complete the skeleton kernel body file CT/Partial_Map/Kernel_2.h (which initially contains empty bodies for the operations to be implemented) by supplying code for the bodies of the public interface operations Define, Undefine, Undefine_Any, the accessor, Is_Defined, and Size, and the private operations Initialize and Move_To_Front.
When you are satisfied that your program works, get into your Lab03 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?? lab3 CT/Partial_Map/Kernel_2.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.

The Initialize operation is a new one. Its purpose is to construct the representation for an initial value of a Partial_Map object (which is an empty set). Initialize is an operation that you never call explicitly; all calls to it are inserted automatically by the C++ compiler at the appropriate places. But for this case, unlike previous examples of kernel implementations, you do have to write a body for it. The reason is that before Initialize executes, C++ has automatically initialized, to their respective initial values, the fields of the Representation record. If automatic initialization of these fields happens to result in the representation of an initial value of the type being implemented then you don't need to write any code for Initialize. That has been the situation in the previous implementation examples you've done. But here, the representation of an empty Partial_Map object must have the bounds of the Array field (called hash_table) set to 0 and hash_table_size-1, respectively; by default they are initially 1 and 0. Therefore, you need to put (only) the following code into the body of Initialize:

self[hash_table].Set_Bounds (0, hash_table_size-1);

Possible Maintenance Activities

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

Modify the test driver program, or create a new program from scratch, so you can estimate the execution times for the various Partial_Map_Kernel operations. Use it to find out, on the average, about how much improvement arises for the accessor operation when you have a hash table size of 10. Hint: Use the Timer component family.
Explain why the automated regression testing approach used in the closed lab does not work, i.e., is not fully automated, for testing Partial_Map_Kernel operations. Explain how you could modify the regression testing approach to overcome this obstacle and make fully automated regression testing possible here, too.

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