CSE 222 Lab #5

Please turn in whatever you have by the deadline, as no late submissions will be accepted for this lab assignment.

Objectives

Familiarity with developing and using specification-based test plans.
Familiarity with writing a "raw C++" implementation of a component, using pointers.

The Problem

The problem is to complete and carefully test implementations of all the operations of abstract template List_Retreat, by building a representation that involves a doubly-linked list of nodes using "raw C++" pointers. List_Retreat extends List_Kernel with one more operation, Retreat, which has the following specification:

procedure Retreat () is_abstract;
/*!
    requires
        self.left /= empty_string
    ensures
        self.left * self.right = #self.left * #self.right and
        |self.left| = |#self.left| - 1
!*/

This additional operation gives the client the ability to move backward one position at a time. The original List_Kernel allows only incremental forward movement; moving backward is possible only by "jumping" all the way back to the start using Move_To_Start. Retreat is just the inverse of Advance.

Note that Retreat can be implemented by layering, i.e., by extending any implementation of List_Kernel by layering just as we've done for many other extensions earlier in the course. You should know how to write that code! However, the execution time of the layered implementation is linear in the length of the left string of the list. The challenge here is to implement List_Retreat so all the operations (except Finalize/destructor) take constant time, independent of the sizes of the left and right strings of the list. This is possible only by implementing all the List_Retreat operations directly, i.e., not by layering on an existing implementation of List_Kernel but by creating an entirely new implementation that is based on a doubly-linked list data structure.

Method

Here's what to do:

Copy the initial lab #5 files to your own working directory and get into that directory:
```
cp -R /class/sce/now/222/labs/lab05/Lab05/ .
```
```
cd Lab05
```
Get into an emacs window and visit your Lab05 directory. You should see a file called List_Retreat_Test.cpp, a test driver you can use for testing. You shouldn't have to edit this file before building it, since it already contains the code to instantiate your List_Retreat implementation with Item replaced by Text. The executable List_Retreat_Sample has been compiled from this test driver with a correct but not necessarily efficient implementation of List_Retreat, 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/List/Retreat_2.h (which initially contains empty bodies for the operations to be implemented) by supplying code for the bodies of the public interface operations Move_To_Start, Move_To_Finish, Advance, Retreat, Add_Right, Remove_Right, the accessor, Left_Length, and Right_Length, and the private operations Initialize and Finalize. It is suggested that you model your code after List_Kernel_1 (see CT/List/Kernel_1.h, which also was copied into your Lab05 directory for reference). Note the differences, however, by comparing the Rep field names and the conventions in the files Kernel_1.h and Retreat_2.h. Most important are that the latter uses a doubly-linked list data structure rather than a singly-linked list, and that the latter uses a "smart node" at both ends rather than just at the start. However, a fair amount of the new code is virtually identical to that in Kernel_1.h, despite these differences. You just have to ferret out the subtle differences!
When you are satisfied that your program works, get into your Lab05 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?? lab5 CT/List/Retreat_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.

Possible Maintenance Activities

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

Implement List_Retreat without the two "smart nodes". Then explain the purpose of these nodes and why they deserve to be called "smart nodes" rather than the traditional "dummy nodes".
Modify the test driver program, or create a new program from scratch, so you can estimate the execution times for the various List_Retreat operations.

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