Assignment 5
[ Home ] [ Up ] [ Assignment 4 ] [ Assignment 5 ]

 

Linked Lists With Polymorphism

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, Secretaries, Programmers, Janitors -- yes, even VicePresidents and the ChairmanOfTheBoard (yes, even they gets 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 (and may not; it may turn into a self-study exercise). 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 up the wazoo (that means a LOT!). 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.
  1. 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 -- indeed, some C++ compilers don't yet implement them at all, and others don't implement all the necessary features! So compatibility and portability across platforms becomes 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.h>
#include "list.h"

class Person
{
public:
    Person(char *name); 
    ~Person();

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

    operator ListItem &() { return m_item; }

private:
    ListItem    m_item;
    char        *m_name;
};

#endif
 
// person.cpp

#include <iostream.h>
#include "person.h"

Person::Person(char *name) 
    : m_item(this), m_name(new char[strlen(name)+1])
{
    strcpy(m_name, name);
}

Person::~Person()   { delete [] m_name; }

void Person::Add(List &list, Person *prevPerson)
{
    m_item.Add(list, &(prevPerson->m_item));
}

void Person::Remove()
{
    m_item.Remove();
}

void Person::Print()
{
    cout << "Person: " << m_name << endl;
}
 
// test.cpp

#include "list.h"
#include "person.h"

static void ListPersons()
{
    List list;

    Person person[] = { Person("Fred"), Person("Mary"), Person("Joe") };

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

    ListIterator iter(list);
    
    for (ListItem *item = iter.CurrentItem(); item != 0; item = iter.NextItem())
    {
        Person *person = (Person *)(item->Data());
        person->Print();
    }
}

int main()
{
    ListPersons();

    return 0;
}

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?

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. 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.

Note: We're going to be moving things around inside the classes to make access to them more restricted. If you look at my original class definitions, you'll see that I placed the sections in each class so that public member functions come first, while private member functions and data members (remember, data members should always be private) come last, at the end. Why? To the clients of a class, the most important members are its public ones. Ideally, the clients of a class should have no interest in, and certainly not depend on, the private parts of a class.

We will be adding a protected section within the class. I place the protected section between the public and private sections. I strongly suggest you follow this example.

Here's what to do:

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

    This should leave only the destructor and the member functions int Count() and void Purge() public within the List class.

  2. In the ListItem class:
    1. Move the constructor, ListItem(void *data), and the member functions ListItem *Next() const, ListItem *Previous() const, and void Add(List &list, ListItem *prevItem) into a protected section of the class.
    2. Remove the member function void *Data(), 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 function void Remove() public within the ListItem class.

  3. In the ListIterator class:
    1. Move the constructor, ListIterator(List &list), and the member functions ListItem *Current(), ListItem *Next(), ListItem *Previous() 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 may 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? Because we made the constructor for the List class protected.

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 "list.h"

class PersonList;

// Person
class Person : public ListItem  // Note the public!
{
public:
    Person(char *name);
    Person(const Person &person);
    virtual ~Person();

    const char *Name() const  { return m_name; }

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

private:
    char        *m_name;
};

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

    void Append(Person &person); 
};

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

    Person *Current();
    Person *Next();
    Person *Previous();
};

#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:

Your tasks are to:

  1. Implement class Person, in person.cpp.
  2. Implement a corresponding set of classes for class Wine, in wine.h and wine.cpp.
  3. Modify the test program in test.cpp as follows:
    1. Combine the ListPersons() and ListWines() functions into a single file, and:
    2. Augment the main() function of the test program to call each of these functions.

The resulting main function should look like:

// ...

int main()
{
    ListPersons();
    ListWines();

    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!

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.

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 "person.h"

class EmployeeList;

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

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

private:
    double        m_salary;
};

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

    void Append(Employee &emp);
};

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

    Employee *Current();
    Employee *Next();
    Employee *Previous();
};

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

class Secretary;

// Manager
class Manager : public Employee
{
public:
    Manager(char *name, double salary);
    virtual ~Manager();

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

    void Print();

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
{
public:
    Secretary(char *name, double salary);
    virtual ~Secretary();

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

    void Print();

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. For example, Employee::Print() should pring out the Person information (using Person::Print()) and then print out the salary, as well. 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 boss' 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 function to test out your new functionality:

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.Current(); e != 0; e = iter.Next())
    {
        e->Print();
    }
}

Add a call in the main function to call it, so you can test with it.

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

 
This page was last changed on 11 May 2005