UMBC CMSC202, Computer Science II, Fall 1998, Sections 0101, 0102, 0103, 0104

Project 4: Class Derivation

Due: Monday, November 23, 1998

Objective:

Background:

The goal of this project is to extend the GenList class to allow the client to use a linked list much like an array. The premise is that we can combine the simplicity of arrays with the efficiency of linked lists. For example, we want the client to be able to refer to an item in a linked list using an integer index. Thus,

The twist:

Extending the GenList class as described above is fairly straightforward --- we simply have to overload the [] operator and add a few new member functions. The i^th item of a linked list can be accessed simply by traversing the linked list from the beginning and counting up to i. So, of course, there must be a twist to this project. Consider what would happen if the client simply wanted to print out each item of the list using a for loop and the [] operator. Each time the client accesses the linked list, we would have to start from the beginning of the linked list to find the i^th item. This is horribly inefficient because it uses O(n²) time for a process that should take O(n) time.

One way to improve the performance of these operations is to use a caching strategy. Whenever we access the i^th item in the linked list, we can "remember" the index i and a pointer associated with the i^th item. These would be stored as data members of the class derived from GenList. If the client accesses the (i+1)^th item in the next operation, we can find this item starting from the i^th item rather than the beginning of the linked list. This saves a lot of time if the linked list is long. For several reasons, it is actually more convenient to store the pointer to the (i-1)^th item instead of the pointer to the i^th item. For example, if the client wants to delete the i^th item right after finding it, then we need the pointer to the (i-1)^th item to accomplish this without starting from the beginning of the array.

A big problem with this caching scheme (and with caching schemes in general) is that the cached values may become invalid. For example, if we access the i^th item in the linked list and immediately insert a new item in the beginning of the linked list, then the pointer we cached is no longer valid as the pointer associated with the i^th item. Fortunately, all the functions which modify the linked list in such a way also set the data member cache_status to dirty. The indicates that the cached values are no longer valid and we must start at the beginning to find the i^th item.

This caching strategy doesn't solve all of our problems with efficiency. If the user wants to access items in the linked list in reverse order or in some random order, then these operations would be slow compared to an array. However, it can be argued that many, if not most, of the operations can be improved significantly using this caching scheme. There are many possible variations to the caching scheme we use here. For example, we can cache several pointers instead of just one. We will not pursue these variations in this project. However, it should be noted that in many areas of computer science --- including computer architecture, networks and operating systems --- developing a sophisticated and efficient caching strategy is of critical importance.

Assignment:

Your assignment is to extend the GenList class using the caching strategy described above. Your extension should include the following:

1. An overloaded [] operator that takes an integer parameter. This operator should return a reference to ListCell.

2. A member function insert(). This function should allow the client to insert a new ListCell before the i^th item. The insert() function should make a copy of the data being inserted.

3. A member function extract(). This function should remove the i^th item from the linked list and return a pointer to this item.

4. A member function find(). This function should return the index of the first item on the linked list that matches the given ListCell item.

Each of the 4 functions above must implement the caching strategy. Your derived linked list class must remain generic. I.e., it should still be possible to insert integers and strings into the same linked list. For testing purposes, you must create a publicly derived class from ListCell called StudentRecord that holds the following data:

1. The student's name in a variable length string. (Do not use fixed length character arrays.)

2. The student's ID number.

3. The student's major.

4. The student's GPA.

For the StudentRecord class, you must implement all the virtual functions in the ListCell class. This is in addition to the constructors and destructors.

Implementation Issues:

1. The first item in the linked list should have index 0.

2. If the client uses an invalid index for the linked list, your member functions should simply print out an error message and quit. This is analogous to a segmentation fault in normal arrays.

3. The insert() function should allow the client to insert a new item using an index equal to the number items in the list. The new item would become the last item in the linked list.

4. The virtual comparison function for your StudentRecord class should compare the names of two StudentRecords. Thus, the find() function becomes find by name.

5. Your classes should be derived from the GenList and ListCell classes presented in class. The source code for the implementation of these classes are available in the directory: /afs/umbc.edu/users/c/h/chang/pub/cs202/project4/

   These are provided to you so you can work on this project on your own computers. You should not make any changes to either the declaration or the implementation of these classes. All new features should be put into the derived classes. If you think there is an error in the implementation of the base classes, contact the instructor.

What to turn in:

Turn in all the files that are needed to compile your program, except for genlist.h and genlist.C. Your programs should work without any modifications to these files. In addition, you should turn in a main program that sufficiently demonstrates the caching features and the genericness of your programs. Include a typescript file and a README file for the graders.

Extra Credit:

The Perl programming language is used extensively for scripting web sites. One of the very convenient features of Perl is called associative arrays. An associative array essentially allows you to index an "array" using a string instead of an integer index. In our project, you would be able to obtain the StudentRecord for a student named "John Smith" using the syntax:

where L is a linked list. If the linked list does not contain a StudentRecord of a student named "John Smith", then a new item is added to the linked list with that name. How should caching be handled with this feature? Using the same string index twice should not result in a search through the linked list twice.

For an extra 10%, implement associative arrays for your list class including an efficient caching scheme. The asociative array feature does not have to work with derivations of ListCell other than StudentRecord. As usual, extra credit is all or nothing --- you either get 10% or 0% extra credit.