Assignment 5


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

 






Linked Lists With Polymorphism

Link to old version of 
this assignment

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,
    Programmer
    s,
    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.
  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. 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.



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



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


 



This page was last changed on 13 May 2005