Data Structures - Chapter 6 - Programming Assignment
List Template Class

Data Structures and Other Objects Using C++
Second Edition
by Michael Main and Walter Savitch
ISBN 0-201-70297-5, Softcover, 816 pages

The Assignment:
You will start with your List class that uses a linked list to store the items. You will convert this class to a template class. Honors students will also implement an external iterator for the new template class.
Ensure that you can convert a container class to a template class. In fact, any time that you write a container class, it is a good idea to start by writing an ordinary container class. After the ordinary class is debugged, convert it to a template class.
Before Starting:
Read all of Chapter 6, with particular attention to Sections 6.3 through 6.5.
Due Date:
Files that you must write:
  1. list4.h: The header file for the new List template class. Actually, you don't have to write much of this file. Just start with a copy of your header file for the List class that uses a linked list. Change the documentation at the top to indicate that the class is now a template class. Make sure that you delete the part of the documentation that refers to the typedef (because you no longer have a typedef!). You can use the documentation at the top of page 280 as a guideline.

    Also, at the bottom of the header file, change the List class definition to a template class. When you do this change, follow the pattern in Step 1 on page 277. You will also need to change link1.h (the linked list toolkit) to link2.h (the template version of the linked list toolkit), and change each of your Node* member variables to a Node<Item>* member variable.

    Finally, at the bottom of the header file you will need the include statement:

    #include "list4.template"

    The reason for this include statement is explained in Step 3 on page 279.

  2. list4.template: The implementation file for the new List template class. Notice that the name of this file ends in ".template" rather than ".cxx". This is to remind you that template implementation files are never compiled on their own.

    To implement this file, start with a copy of the implementation from your ordinary list class and make the changes described in Step 2 on page 277. Some further clarifications are given on pages 278-286 and 295-296 (using the Bag class as an example).

Other files that you may find helpful:
  1. listtest.cxx: This is the same interactive test program that you used with the earlier Lists. If you want to use it with the new list, then copy it to your directory and open it with your editor. Then change the statement
    #include "list1.h"
    #include "list4.h"
    Also change each List to a List<double>.
  2. listex4.cxx: A non-interactive test program that will be used to grade the correctness of your new List class.
  3. link2.h and link2.template: Copy these files to your hw06 subdirectory. They contain the template version of the linked list toolkit from Section 6.4. You may use these files without changing them.

The List Template Class Using a Linked List
Discussion of the Assignment

Most of your work consists of following the pattern for converting a container class to a template class, as shown on pages 277-279. Also, you must use the template version of the linked list toolkit (link2.h instead of link1.h), and each Node* variable will be changed to a Node<Item>* variable. The conversion of the Bag (in Section 6.5) may serve as a good example to follow.

Extra Credit Work for This Assignment

For 5 extra points, bored students may wish to extend this assignment. The extra work that you do is probably worth more than the points that you earn (but there's more to life than points). Anyway, the extra work is to implement a second class which is an external iterator for your List template class. External iterators are discussed briefly on page 301, and an example is shown in Project 5 on page 305. In the case of the List, the new class will be called ListIterator with this definition at the end of list4.h:
    template <class Item>
    class ListIterator
        // CONSTRUCTOR
        ListIterator( );
        void attach(List<Item>& attached_list);
        void advance( );
        Item current( ) const;
        bool is_item( ) const;
Most of the member functions that are listed above are similar to the Bag's external iterator in Project 5 on page 305. However, the is_item function has an extra requirement: is_item() should return true only if the iterator has a current item and the attached List has not been changed since the attachement was made. How are you going to manage this last requirement? Here is one idea:
  1. The ListIterator class should be a friend of the List class and vice versa.
  2. The List has an extra member variable which is a head pointer for a linked list of addresses of those ListIterators that are currently attached to the List. There are also private List member functions that can be activated by a ListIterator to put the ListIterator's address on this linked list, or to take the address off the linked list. Let's call these functions put_on and take_off.
  3. The ListIterator has an extra member variable which is a pointer to the List that it's currently attached to. Let's call this member variable attached_to.
  4. The ListIterator also has a private member function called invalidate(). Calling this function will immediately invalidate the ListIterator.
  5. When attach is called, part of the work is to store the address of the List in attached_to. Also activate attached_to->put_on(this). (Remember that the keyword "this" is a pointer to the object that activated the member function; in other words, a pointer to the ListIterator.)
  6. If a ListIterator advances off its list, it should call attached_to->take_off(this), and set attached_to to NULL (to indicate that there is no longer a valid attached List.)
  7. Whenever a List changes via insert, attach, remove_current, or the destructor, the List should activate p->invalidate() for each pointer p on its linked list of pointers to ListIterators. Then clear this linked list.

Michael Main (