[ Home ] [ Up ] [ Assignment 1 ] [ Assignment 2 ] [ Assignment 3 ] [ Assignment 4 ] [ Assignment 5 ] [ Assignment 6 ] [ Assignment 7 ] [ Old Assignments ]

Why More About Linked Lists?

So you thought you'd seen all you ever wanted to know about linked lists after the last assignment? Read on...

While the previous design worked (at least if you implemented it right...), it had its drawbacks. Let's list some of them:

• The list classes were very generic. In particular, there was no type checking to provide compile-time checking to prevent mistakes. For example, imagine you had a list item that represented a Person and put it into a list, and then you navigated the list assuming that the list items represented Fruit or a Wine -- something other than a Person. You have to typecast the data from the list item from a void * to some other kind of pointer (having to typecast all the time can become a real pain, and it's very error-prone). Because there is no type-checking at compile time, your program will likely compile and link without problems. There is also no run-time type-checking, so you will likely get very strange results when you run your program. Even if you don't see anything obvious (like an access violation, core dump, or GPF), there's usually something evil going on under the surface. In fact, if you don't see something wrong, that's probably the time to start worrying, because you don't even know where to start looking. What's more it's usually a real bear to debug and fix these kinds of problems, even if you do see the symptoms.

• There was no support for homogeneous lists -- lists which can only contain items that represent a single type. What if you wanted to ensure that all the items in a list represented Persons? Or that they all represented Wines? There is no type-checking of that, at all -- again, neither at compile-time nor at run-time.

• Even the support for heterogeneous lists wasn't that great. While you often need to have a list of things that are of identical type, it's rare that you have a use for a list that can contain absolutely anything. More likely, you will have a list of related, or similar, items. For example, in a payroll application, you might have a list of Managers, Secretarys, Programmers, Janitors -- yes, even VicePresidents and the ChairmanOfTheBoard (yes, even they get paid!). They are of different types, but they are all related to each other -- they are all Employees. If you wish to ensure that only Employees (of whatever job description) may be contained in a list, the previous design doesn't help you much.

• That pesky ListItem class being separate from the data it represents is a real pain in the, er... Well, it's very clumsy and inconvenient. Couldn't we integrate it into the class that we wish to place in the list?

These shortcomings mostly boil down to lack of safety and convenience. It's hard enough work to come up a well-designed, solid and well-tested application.  Why can't the compiler help a little more, and then maybe you'd get home on time at least once a week? Well, it can, but you have to do some of the work -- more design. An investment in the proper up-front design can pay great dividends in making it easier to implement that design, and that can translate into less work (time, money...) to implement and test that design.

Let's take a look at what we might do to improve things...

Design Alternatives

Here are a couple of ideas on how we might be able to improve matters:

1. Have a ListItem actually contain, rather than point to, the data it represents.
2. Change every void * to a specific pointer type. This would allow you to have a homogeneous list, and would add the necessary type-checking.

Well, they're fine and dandy as ideas go, but both of them move us away from the idea that you would like to write the code for a list once, and then use it for whatever you wish to place in that list.

For example, let's say that you decided to have a ListItem contain a Person. Then you could place the ListItem in a List and (with the appropriate member functions) manipulate the List with the full knowledge that it can only contain Persons. With the proper code, you would also get type-checking, so you could detect at compile-time when you (or someone who uses your code) make a stupid mistake.

But what if you also wanted to make a List of Wines? and a List of Fruits? and a List of Employees? Then you would have to create a PersonListItem, and a WineListItem, and a FruitListItem, and.-- you get the picture... Not only that, to make it all consistent, you would have create a new List class and a new ListIterator class for each type of ListItem derivative you invent.

Sure, you could simply cut and paste the code to create new classes each time, with the appropriate changes in types, but what if someone found a bug in the original implementation? Could you reliably find all the places you'd cut and pasted the code to, and fix that bug everywhere it exists? Multiply that bug by a thousand or more, and the number of places to find each instance of each bug, and you might get a feeling for the problem you're creating for yourself. (It's called the most primitive form of code reuse -- cut, paste and hope the original doesn't break, and that you don't introduce new bugs in the copied version as you make changes.)

Well, this problem is really solved in C++ by template classes. Unfortunately, there are two problems with template classes:

1. We haven't got to that topic in the course. Be warned that it's a complex and advanced topic. On the other hand, the ISO C++ standard includes STL (the Standard Template Library), a very important generic programming library, which uses templates all over the place. Much of the C++ standard class library has been redefined and re-implemented using STL and templates, and so it's a road we will all have to take eventually.

2. Templates have historically been one of the most troublesome areas of C++. The ISO C++ standards committee wrestled with them for a long time, and came up with merely a compromise solution to some of the problems. Different C++ compilers have implemented templates in different ways, and with different features. So compatibility and portability across platforms can become a big issue when it comes to C++ templates. This will likely improve, now that the ISO C++ standards committee has finally published the C++ standard, but some vendors have been very slow to implement templates properly. Even if a vendor does implement templates properly, from the syntactic and semantic perspectives, that vendor may or may not do a good job of implementing them efficiently -- templates are notorious for causing 'code bloat', and you have to know what the sensible rules are to avoid that.

Phew! That said, what are we going to do in the absence of templates?

Containment

Well, first, take a look at a technique that I used in the previous assignment, in the list of Persons. I'll reproduce it here, so you don't have to flip pages or browse to it and back:

#ifndef _PERSON
#define _PERSON

// person.h

#include <string>
using namespace std;

#include "list.h"

class Person
{
public:
    Person(const string &name);
    Person(const Person &person);
    ~Person();

    const string &Name() const 
    {
        return m_name;
    }

    void Add(List &list, Person *prevPerson);
    void Remove();

    void Print() const;

    // Assignment operator
    Person &operator=(const Person &person);

    // Conversion function to ListItem &
    operator ListItem &()
    {
        return m_item;
    }

private:
    ListItem  m_item;
    string    m_name;
};

Note that here, instead of having the ListItem class contain an instance of class Person, class Person contains an instance of class ListItem. Kind of inside out thinking, don't you think?

This was a reasonable solution, except for one thorny problem: How, given an instance of class Person, do I treat that class like a ListItem, so it can be placed in the List? My solution was to introduce into the Person class a conversion function:

operator ListItem &() { return m_item; }

which allows an instance of class Person to be 'converted' to an instance of class ListItem. In this case, all this means is that the conversion function returns a reference to m_item, the ListItem instance contained within the Person class. With this, I can write code like:

list.Append(person[i]);

and have the conversion function do its silent work, making it look like I'm adding a Person to the list. In addition, I added some additional member functions to class Person:

void Add(List &list, Person *prevPerson);
void Remove();

which allow us to add and remove instances of class Person from a List, while providing type-safety (meaning that I know that I'm adding instances of Person to the list). Note that these new member functions are implemented using the existing ListItem member functions. They merely hide the details from users of the Person class, and also provide the stronger typing..

However, this code does not prevent a malicious or underachieving programmer from using the bare ListItem class. And we still have the problem of List and ListIterator knowing nothing about the Person class.

We could, of course, apply the same techniques to the List and ListIterator classes to produce PersonList and PersonIterator classes. 

But we won't, because there's a better way -- using inheritance and polymorphism.

The Assignment (Step 1)

Preparing for Polymorphism

Here's where you get to do some of the work:

First, make a copy of your original linked list classes, and create a new project to put the copies in. You can always go back to the old project if you want to have a taste of something that still works -- we're going to be making some changes that will initially stop things from working, and you may get frustrated for a while -- bear with me!

Making the List Classes (pseudo-)Abstract

Now, let's make some changes to the list classes to make them (sort of) abstract. Remember, an abstract class is one that cannot be instantiated by itself. For example, you might choose to make a Fish class abstract, since it's very generic. If asked to make an instance of class Fish, the first question you'd be likely to ask is "What kind of fish would you like?". Haddock, or Flounder would be good, but Fish is kind of non-specific. Making a class abstract highlights the fact that you can't really make an instance of that class, because you need more information.

Conventionally, we make a C++ class abstract by introducing into that class a pure virtual function. However, for the moment, at least, I'm not going to do that. Instead, I'll take a different approach so that I can introduce some different ideas and techniques.

Here's what to do:

1. In the List class:
   1. Move the constructor, List(), and the member functions, void Append(ListItem &item),  ListItem *GetFirst() const, and ListItem *GetLast() const, into a  protected section of the class.
   2. Make the destructor virtual.

   This should leave only the destructor and the member functions GetCount(), Purge(), and Dump() public within the List class.

2. In the ListItem class:
   1. Move the constructor, ListItem(void *data), and the member functions ListItem *GetNext() const,  ListItem *GetPrevious() const, and void Add(List &list, ListItem *prevItem) into a protected section of the class.
   2. Remove the member function void *GetData(), and the data member m_data.
   3. Change the constructor to ListItem() -- that is, remove the void *data argument.
   4. Make the destructor virtual.

   This should leave only the destructor and the member functions Remove(), GetList(), and Dump() public within the ListItem class.

3. In the ListIterator class:
   1. Move the constructor, ListIterator(List &list), and the member functions ListItem *GetCurrent(), ListItem *GetNext(), ListItem *GetPrevious() into a protected section of the class.
   2. Make the destructor virtual.

   This should leave only the destructor and the member functions bool AtFirst() const, and bool AtLast() const public within the ListIterator class.

Now try compiling the result. [Hmmmm.... A few compile-time errors, huh? Not to worry, it's expected.]

In order to get the list.cpp file to compile, you will have to add one or two friendship relationships among the three list classes. You should not have to change any code in list.cpp to make it compile -- only the changes I specified above in list.h.

However, you should expect the other .cpp files not to compile at this point.

For example, the line in file test.cpp:

List list;

will produce errors. Why? 

The Assignment (Step 2)

Using our Newly (pseudo-)Abstract Classes

So how are we going to use our new List, ListItem, and ListIterator classes?

Well, we're not, directly. We'll use them indirectly, by writing modified Wine and Person classes. In fact, for each one, we'll write a set of classes, derived from ListItem, List, and ListIterator. In this way, we can create Person-specific and Wine-specific versions of our List classes, while using inheritance to ensure that we share the code that implements the lists. At the same time, we now have classes that are strongly-typed.

I think you'll start to see how this approach can simplify the code you have to write to use these classes. For a start, you no longer have to typecast the data into the proper type; that's done for you by the Person-specific and Wine-specific classes.

To give you a head start, here is the modified header file for Person, person.h. Class Person no longer contains a ListItem member, but instead inherits (publically!) from ListItem.

#ifndef _PERSON
#define _PERSON

// person.h

#include <string>
using namespace std;

#include "list.h"

class PersonList;

// Person
class Person : public ListItem
{
public:
    Person(const string &name);
    Person(const Person &person); 
    virtual ~Person();

    const string &Name() const  
    { 
        return m_name; 
    }

    void Add(PersonList &list, Person *prevPerson);
    void Print() const;

    // Assignment operator
    Person &operator=(const Person &person);
                                  
    Person *GetNext() const;    
    Person *GetPrevious() const;

private:
    string  m_name;
};

// PersonList
class PersonList : public List 
{
public:
    PersonList() {}
    virtual ~PersonList() {}

    void Append(Person &person); 

    Person *GetFirst() const;
    Person *GetLast() const;
};

// PersonIterator
class PersonIterator : public ListIterator 
{
public:
    PersonIterator(PersonList &list);
    virtual ~PersonIterator();

    Person *GetCurrent() const;
    Person *GetNext();
    Person *GetPrevious();
};

#endif

Note that I have removed all traces of List, ListItem, or ListIterator from the public interfaces of these classes. The intent is to implement all the functionality of the Person classes using the functionality provided by those underlying list classes, without exposing that fact to the outside world..

Here's What to Do:

Person

Implement class Person, in person.cpp.

Here is a test program to run your Person class through its paces:

// testPerson.cpp

#include <iostream>
using namespace std;

#include "person.h"

static void display(PersonList &list)
{
    cout << "Contents of list:" << endl;
    PersonIterator iter(list);
    for (Person *person = iter.GetCurrent();
         person != 0;
         person = iter.GetNext()
        )
    {
        person->Print();
    }

    cout << "-----Dump------" << endl;
    list.Dump();
    cout << "---End Dump----" << endl;
}

static void ListPersons()
{
    Person fred("Fred");
    Person mary("Mary");
    Person joe("Joe");
    Person clive("Clive");
    Person nigel("Nigel");
    Person nostradamus("Nostradamus");
    Person einstein("Einstein");

    Person *items[] = { &fred, &mary, &joe, &clive, 
                        &nigel, &nostradamus, &einstein };

    Person *person;

    PersonList list;      // The list of people

    // The following List iterator is positioned so that
    // the list it associates with is empty at the time
    // of the association.
    PersonIterator iter(list);
    
    // Start testing

    cout << "Empty list..." << endl;
    display(list);

    cout << "Testing Append" << endl;
    cout << " Appending: "; 
    fred.Print();
    list.Append(fred);
    display(list);

    cout << "Testing a second Append" << endl;
    cout << " Appending: "; 
    nigel.Print();
    list.Append(nigel);
    display(list);

    cout << "Testing Add to front" << endl;
    cout << " Adding: "; 
    mary.Print();
    mary.Add(list, 0);
    display(list);

    cout << "Testing Add to end" << endl;
    cout << " Adding: "; 
    joe.Print();
    joe.Add(list, list.GetLast());
    display(list);

    cout << "Testing Add to middle" << endl;
    cout << " Adding: "; 
    clive.Print();
    clive.Add(list, &mary);
    display(list);

    cout << "------------Iterator testing------------" << endl;
    cout << "Testing iterator originally set on empty list..." << endl;   
    for (person = iter.GetCurrent(); 
         person != 0; 
         person = iter.GetNext())
    {
        person->Print();
    }

    cout << "Now reversing direction on iterator..." << endl;
    for (person = iter.GetCurrent();
         person != 0;
         person = iter.GetPrevious()
        )
    {
        person->Print();
    }

    cout << "Reversing direction again..." << endl;
    for (person = iter.GetCurrent();
         person != 0;
         person = iter.GetNext()
        )
    {
        person->Print();
    }
    cout << "--------End Iterator testing------------" << endl;

    cout << "Testing removal from middle" << endl;
    cout << " Removing: "; 
    clive.Print();
    clive.Remove();
    display(list);

    cout << "Testing removal from end" << endl;
    cout << " Removing: "; 
    joe.Print();    
    joe.Remove();
    display(list);

    cout << "Testing removal from front" << endl;
    cout << " Removing: "; 
    mary.Print();    
    mary.Remove();
    display(list);

    cout << "Testing removal from end" << endl;
    cout << " Removing: "; 
    nigel.Print();
    nigel.Remove();
    display(list);

    cout << "Testing removal of last item" << endl;
    cout << " Removing: "; 
    fred.Print();
    fred.Remove();
    display(list);

    // Finally, we test the actions of the List destructor

    // First, go through the items to check that they are not in
    // a list...
    cout << "Checking that removed items do not appear to be in a list" << endl;
    int len = sizeof(items)/sizeof(items[0]);
    int elem;
    int errors = 0;
    for (elem = 0; elem < len; elem++)
    {
        if (items[elem]->GetList() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still in a list" << endl;
        }
        if (items[elem]->GetNext() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a next ptr" << endl;
        }
        if (items[elem]->GetPrevious() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a previous ptr" << endl;
        }
    }
    
    // Now, create the list and populate it from the items
    cout << "Checking addition and removal to a dynamic list" << endl;
    PersonList *dynList = new PersonList();
    for (elem = len-1; elem >= 0; elem--)
    {
        dynList->Append(*(items[elem]));
    }
    
    // Display the list for validation
    display(*dynList);

    // Now destroy the list and examine the state of each
    // of the items that were in the list
    cout << "Destroying dynamic list" << endl;
    delete dynList;
    cout << "Checking that removed items do not appear to be in a list" << endl;
    for (elem = 0; elem < len; elem++)
    {
        if (items[elem]->GetList() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still in a list" << endl;
        }
        if (items[elem]->GetNext() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a next ptr" << endl;
        }
        if (items[elem]->GetPrevious() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a previous ptr" << endl;
        }
    }
    cout << errors << " errors detected" << endl;
}

int main()
{
    ListPersons();

    return 0;
}

Note: Of course, the program should work correctly. So test it, and show me the results.

Warning: Do not simply copy the code from List, ListItem, and ListIterator into the Person and Wine classes! This would be to miss the whole point of the exercise! You would not be benefiting from the code reuse you get from a single implementation of the code!

Wine

Implement a corresponding set of classes for class Wine, in wine.h and wine.cpp.

Here is a test program to run your Wine class through its paces:

// 
// testWine.cpp
//
#include <cstdlib>
#include <iostream>
using namespace std;

#include "wine.h"

static void display(WineList &list)
{
    cout << "Contents of list:" << endl;
    WineIterator iter(list);
    for (Wine *wine = iter.GetCurrent();
         wine != 0;
         wine = iter.GetNext()
        )
    {
        wine->Print();
    }

    cout << "-----Dump------" << endl;
    list.Dump();
    cout << "---End Dump----" << endl;
}

static void ListWines()
{
    Wine beaujolais("Beaujolais", 1970);
    Wine amontillado("Amontillado", 1964);
    Wine riesling("Riesling", 1980);
    Wine gewurztraminer("Gewurztraminer", 1993);
    Wine shiraz("Shiraz", 2003);
    Wine cabernet("Cabernet Sauvignon", 2001);

    // Each item in the following list is an instance
    // of ListItem, each pointing to its corresponding
    // Wine instance.
    Wine *items[] = { &beaujolais, &amontillado,
                      &riesling,   &gewurztraminer,
                      &shiraz,     &cabernet };

    Wine *wine;     // Wine pointer used in many places

    WineList list;  // The list of wines

    // The following List iterator is positioned so that
    // the list it associates with is empty at the time
    // of the association.
    WineIterator iter(list);

    // Start testing

    cout << "Empty list..." << endl;
    display(list);

    cout << "Testing Append" << endl;
    cout << " Appending: "; 
    wine = items[0];
    wine->Print();
    list.Append(*items[0]);
    display(list);

    cout << "Testing a second Append" << endl;
    cout << " Appending: "; 
    wine = items[4];
    wine->Print();
    list.Append(*items[4]);
    display(list);

    cout << "Testing Add to front" << endl;
    cout << " Adding: "; 
    wine = items[1];
    wine->Print();
    items[1]->Add(list, NULL);
    display(list);

    cout << "Testing Add to end" << endl;
    cout << " Adding: "; 
    wine = items[2];
    wine->Print();
    items[2]->Add(list, list.GetLast());
    display(list);

    cout << "Testing Add to middle" << endl;
    cout << " Adding: "; 
    wine = items[3];
    wine->Print();
    items[3]->Add(list, items[1]);
    display(list);

    cout << "------------Iterator testing------------" << endl;
    cout << "Testing iterator originally set on empty list..." << endl;   
    for (wine = iter.GetCurrent(); 
         wine != 0; 
         wine = iter.GetNext()
        )
    {
        wine->Print();
    }

    cout << "Now reversing direction on iterator..." << endl;
    for (wine = iter.GetCurrent();
         wine != 0;
         wine = iter.GetPrevious()
        )
    {
        wine->Print();
    }

    cout << "Reversing direction again..." << endl;
    for (wine = iter.GetCurrent();
         wine != 0;
         wine = iter.GetNext()
        )
    {
        wine->Print();
    }
    cout << "--------End Iterator testing------------" << endl;

    cout << "Testing removal from middle" << endl;
    cout << " Removing: "; 
    wine = items[3];
    wine->Print();
    items[3]->Remove();
    display(list);

    cout << "Testing removal from end" << endl;
    cout << " Removing: "; 
    wine = items[2];
    wine->Print();    
    items[2]->Remove();
    display(list);

    cout << "Testing removal from front" << endl;
    cout << " Removing: "; 
    wine = items[1];
    wine->Print();    
    items[1]->Remove();
    display(list);

    cout << "Testing removal from end" << endl;
    cout << " Removing: "; 
    wine = items[4];
    wine->Print();
    items[4]->Remove();
    display(list);

    cout << "Testing removal of last item" << endl;
    cout << " Removing: "; 
    wine = items[0];
    wine->Print();
    items[0]->Remove();
    display(list);

    // Finally, we test the actions of the List destructor

    // First, go through the items to check that they are not in
    // a list...
    cout << "Checking that removed items do not appear to be in a list" << endl;
    int len = sizeof(items)/sizeof(items[0]);
    int elem;
    int errors = 0;
    for (elem = 0; elem < len; elem++)
    {
        if (items[elem]->GetList() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still in a list" << endl;
        }
        if (items[elem]->GetNext() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a next ptr" << endl;
        }
        if (items[elem]->GetPrevious() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a previous ptr" << endl;
        }
    }
    
    // Now, create the list and populate it from the items
    cout << "Checking addition and removal to a dynamic list" << endl;
    WineList *dynList = new WineList();
    for (elem = len-1; elem >= 0; elem--)
    {
        dynList->Append(*items[elem]);
    }
    
    // Display the list for validation
    display(*dynList);

    // Now destroy the list and examine the state of each
    // of the items that were in the list
    cout << "Destroying dynamic list" << endl;
    delete dynList;
    cout << "Checking that removed items do not appear to be in a list" << endl;
    for (elem = 0; elem < len; elem++)
    {
        if (items[elem]->GetList() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still in a list" << endl;
        }
        if (items[elem]->GetNext() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a next ptr" << endl;
        }
        if (items[elem]->GetPrevious() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a previous ptr" << endl;
        }
    }
    cout << errors << " errors detected" << endl;

}

int main()
{
    ListWines();

    return 0;
}

The Assignment (Step 3)

Supporting Heterogeneous Lists of Related Items

The above changes improved matters somewhat:

1. Homogeneous lists are now easier to implement (if a little repetitious)
2. We now have strong typing, and no need for typecasting in our main code. (If you have any such typecasting in the code your wrote outside of the Person and Wine classes, then you need to check it;  it's probably incorrect and/or unnecessary.)

However, we don't yet have support for the kind of heterogeneous list that contains items which are not all identical types, but which are related to each other (as in the Employees example, earlier). So let's see what we can do to make this possible:

First, let's come up with a set of related classes: Employee, Manager, and Secretary. Note that Employee is derived from Person, and has related classes EmployeeList and EmployeeIterator, while Manager and Secretary are simply derived from Employee, and do not have their own list or iterator. With this infrastructure, we can support a heterogeneous list of items which are related to each other: they are all Employees.

#ifndef _EMPLOYEE
#define _EMPLOYEE

// employee.h

#include <string>
using namespace std;

#include "person.h"

class EmployeeList;

// Employee
class Employee : public Person
{
public:
    Employee(const string &name, double salary);
    Employee(const Employee &emp);
    virtual ~Employee();

    void Add(EmployeeList &list, Employee *prevEmployee);

    void Print() const;
    const string &GetPosition() const
    {
        return m_position;
    }

protected:
    void SetPosition(const string &position)
    {
        m_position = position;
    }

private:
    double m_salary;

    string m_position; // Name of position in organization
};

// EmployeeList
class EmployeeList : public PersonList
{
public:
    EmployeeList();
    virtual ~EmployeeList();

    void Append(Employee &emp);

    Employee *GetFirst() const;
    Employee *GetLast() const;
};

// EmployeeIterator
class EmployeeIterator : public PersonIterator
{
public:
    EmployeeIterator(EmployeeList &list);
    virtual ~EmployeeIterator();

    Employee *GetCurrent() const;
    Employee *GetNext();
    Employee *GetPrevious();
};

////////// Other types of Employees ///////////////

class Secretary;

// Manager
class Manager : public Employee
{
    friend class Secretary;

public:
    Manager(const string &name, double salary);
    virtual ~Manager();

    Secretary *GetSecretary() const;
    void SetSecretary(Secretary *sec);

    void Print() const;

private:
    // Don't allow copying or assignment of Managers
    Manager(const Manager &);
    Manager &operator=(const Manager &);

    //// Data //////
    Secretary *m_secretary;
};

// Secretary
class Secretary : public Employee
{
    friend class Manager;

public:
    Secretary(const string &name, double salary);
    virtual ~Secretary();

    Manager *GetManager() const;
    void SetManager(Manager *sec);

    void Print() const;

private:
    // Don't allow copying or assignment of Secretaries
    Secretary(const Secretary &);
    Secretary &operator=(const Secretary &);

    //// Data //////
    Manager *m_manager;
};

#endif

Here's What to Do:

Now implement these classes (in employee.h and employee.cpp). Creating Employee, EmployeeList, and EmployeeIterator is just like what you did before to construct Person, PersonList and PersonIterator, except that you derive Employee, et.al. from Person, et.al, rather than List, et.al.

Be sure to make each class' Print() function do something different.   Here is a starting point for employee.cpp, to show you what my Employee::Print() looks like, among other things:

//
// employee.cpp
//

#include <iostream>
#include <iomanip>
using namespace std;

#include "employee.h"

/////////// Class Employee /////////////

Employee::Employee(const string &name, double salary)
: Person(name), m_salary(salary)
{
    SetPosition("Employee");
}

void Employee::Print() const
{
    cout << GetPosition().c_str() << ": " << Name().c_str() 
	 << ", salary: " << fixed << setprecision(2) << m_salary 
         << endl;
}

// You implement the rest

Manager::Print() should print out the Employee information (using Employee.Print()), and then print out the secretary name, if any.

Secretary::Print() should print out the Employee information, and then print out the manager's name, if any.

Question: When you iterate through such a list, do you see the wrong Print() function being called for some items? What do you need to do to make sure that the proper Print() function is called for each item?

Here's a main program to test out your new functionality:

// test3.cpp

#include <iostream>
using namespace std;

#include "employee.h"

static void display(EmployeeList &list)
{
    cout << "Contents of list:" << endl;
    EmployeeIterator iter(list);
    for (Employee *employee = iter.GetCurrent();
         employee != 0;
         employee = iter.GetNext()
        )
    {
        employee->Print();
    }

    cout << "-----Dump------" << endl;
    list.Dump();
    cout << "---End Dump----" << endl;
}

static void ListEmployees()
{
    EmployeeList list;

    Employee  FredBloggs("Fred Bloggs", 25000);
    Manager   GenghisKhan("Genghis Khan", 105000);
    Secretary MargaretThatcher("Margaret Thatcher", 30000);
    Manager   BillGates("Bill Gates", 42000000);
    Employee  NewtGingrich("Newt Gingrich", 89000);
    Secretary Madonna("Madonna", 5000000);

    Employee *employee[] = 
    {
        &FredBloggs, &GenghisKhan, &MargaretThatcher,
        &BillGates, &NewtGingrich, &Madonna
    };

    GenghisKhan.SetSecretary(&MargaretThatcher);
    BillGates.SetSecretary(&Madonna);

    for (int i = 0; i < sizeof(employee)/sizeof(employee[0]); i++)
    {
        list.Append(*(employee[i]));
    }

    EmployeeIterator iter(list);

    for (Employee *e = iter.GetCurrent(); e != 0; e = iter.GetNext())
    {
        e->Print();
    }

    // Display the contents of the list
    display(list);
}

int main()
{
    ListEmployees();

    return 0;
}

Note that this function constructs a list of items that are all Employees, or of types derived from Employees.