Assignment 4


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

 






Linked Lists

Link to old version of 
this assignment

What is a Linked List?


Linked lists are among the most useful data structures in
Computer Science, and are therefore very heavily used in lots
of different applications. For this assignment, we will
concentrate on the doubly-linked list, which is
perhaps the most useful of all linked lists. Here’s what a
doubly-linked list looks like:



As you can see, the linked list consists of a number of list
items
linked together in both the forward direction and
the reverse direction. The links are typically pointers, and
that is what we will use to implement this kind of list.


Why are Linked Lists so Useful?


Linked lists are useful because they are very flexible.
You can use a linked list as a collection mechanism;
that is, the linked list can collect together items which
have something in common with each other. For example,
perhaps you wish to collect together all the people who work
in your office. Or all the people who work for a particular
boss.

Sometimes the order of items in a list is important, and
sometimes it isn’t. It all depends on what your needs might
be. Perhaps you don’t care about the order at all, in which
case you could treat the items in a list as a set of
items (in the Mathematical sense), or a multi-set of
items (where the value of an item can be duplicated within
the list).

Alternatively, you might wish to maintain the items in the
list in a particular order — perhaps alphabetically, or by
employee number, or by salary.


Linked List Operations


There are obviously a number of useful operations that a
linked list should support. For example:

  1. Adding an item to a list
  2. Removing an item from a list
  3. Determining whether an item is currently in the list
    or not.
  4. Determining how many items are currently in the list
  5. Navigating through the list in order to access the
    items in a list

Depending on how you are using the list, you may need only
the ability to add or remove an item at the end of a list, or
at the front of a list, or to add or remove an item anywhere
in the list. Similarly, you may need only to navigate the
list from the start to the end, or you may need to move both
in the forward direction or in the reverse direction. You may
wish to start at the beginning of the list, at its end, or
anywhere in between.


Doubly-Linked Lists


The doubly-linked list is very flexible in its ability to
support the above features. Doubly-linked lists allow you to:

  1. Add an item anywhere in the list
  2. Remove an item from anywhere in the list
  3. Navigate in any direction, from any starting point in
    the list

The doubly-linked list supports these features by using
two pointers in each list item:

  1. A next pointer
  2. A previous pointer

In addition, it is very useful to add one more pointer in
each list item:

  1. A list pointer — a pointer to the
    list in which the list item currently resides

The next pointer, as its name suggests, points to
the next list item in the list. The previous pointer
similarly points to the previous list item in the list. If a
list item is the first one in the list, then its previous
pointer is NULL. If a list item is the last one in the list,
then its next pointer is NULL. In this way, we can
navigate through the list and have a way of ensuring that we
don’t “fall off” at either end of the list.

The list pointer serves two purposes:

  1. A flag indicating whether the list item is currently
    in a list (we assume that a list item is either in a
    single list, or it is in no list). If the list item
    is not currently in a list, then its list
    pointer is NULL. If the list item is currently in a
    list, then the list pointer points to the owning
    list.
  2. If the list item is in a list, then the list pointer
    provides convenient access to the owning list’s
    context, which the list item code will need for its
    purposes.

Class Design


To implement such a doubly-linked list, we will be
implementing three classes:

  • A List
    class, each instance of which represents a
    doubly-linked list
  • A ListItem
    class, each instance of which represents an item that
    can exist in a List
  • A ListIterator
    class, which encapsulates the necessary context to
    allow multiple concurrent iterations (navigations)
    through a List

What must each class provide to support the necessary
features? Well, let’s cut to the chase, and give you some
code to start with:


#ifndef __LIST_H
#define __LIST_H
//
// list.h
//

#include <string>
using namespace std;

/////////// Forward references /////////

class ListItem;

/////////// Class List ///////////////

class List
{
    friend class ListItem;

  public:
    List();   // Constructor
    ~List();  // Destructor

    // Access
    ListItem *GetFirst() const; // Returns ptr to first item in list
    ListItem *GetLast() const;  // Returns ptr to last item in list
    int GetCount() const;       // Returns count of items in list

    // Operations
    void Append(ListItem &item); // Appends an item to the end of the list
    void Purge();                // Removes all items from the list

    // Debugging member functions
    void Dump(const string prefix = "") const;        
                                // Dump contents of list
                                // (prefix is a string that prefixes
                                //  each line of the dumped output)

  private:
    // Disable copy constructor for List
    List(const List &);
    // Disable assignment for List
    List &operator=(const List &);

    // Data members
    ListItem *m_first;    // Pointer to the first list item
    ListItem *m_last;    // Pointer to the last list item
    int m_count;         // Count of list items currently in list
};

////////// Class ListItem //////////////

class ListItem
{
  public:
    ListItem(void *data);    // Constructor (associates with data)
    ~ListItem();            // Destructor

    // Operations
    void Add(List &list, ListItem *prevItem);
                            // Add this ListItem to the specified list
                            // following the specified prevItem
                            // (if prevItem is NULL, place at front of list)

    void Remove();            // Remove this list item from the list it is in

    // Access member functions
    ListItem *GetNext() const;     // Return ptr to next item in list
    ListItem *GetPrevious() const; // Return ptr to previous item in list
    const List *GetList() const;   // Return ptr to the list item's list
    void *GetData();               // Returns ptr to data for item

    // Debugging member functions
    void Dump(const string prefix = "") const;
                                // Dump contents of list item
                                // (prefix is a string that prefixes
                                //  each line of the dumped output)
  private:
    // Disable copy constructor for ListItem
    ListItem(const ListItem &);
    // Disable assignment for ListItem
    ListItem &operator=(const ListItem &);

    // Data members
    ListItem  *m_next;    // Pointer to next item in the list
    ListItem  *m_prev;    // Pointer to previous item in the list
    List      *m_list;    // Pointer to the list the item currently is in
    void      *m_data;    // Pointer to data
};

/////////// Class ListIterator ////////////

class ListIterator
{
  public:
    ListIterator(const List &list);  // Constructor
    ~ListIterator();           // Destructor

    // Access
    const List *GetList() const; // Return ptr to the iterator's list
    ListItem *GetCurrent() const;// Return ptr to current list item
    ListItem *GetNext();         // Move to next item and return ptr to it
    ListItem *GetPrevious();     // Move to previous item and return ptr to it
    bool  AtFirst() const;       // return true if current item is first item
    bool  AtLast() const;        // return true if current item is last item

  private:
    // Disable copy constructor for ListIterator
    ListIterator(const ListIterator &);
    // Disable assignment for ListIterator
    ListIterator &operator=(const ListIterator &);

    // Data
    const List *m_list;       // The list we are iterating through
    ListItem   *m_current;    // Points to the current item in the list
};

#endif // __LIST_H


Note:
The above classes are incomplete, and show no
implementation details. That’s your job!

Warning: Do not change any of these class members, their signatures, or their access
(public or private). Furthermore, do not
add any other data members or member functions. These
classes will be used and modified in later
assignments, and if you change them here, you will
have difficulty following the instructions in the
later assignments. YOU HAVE BEEN WARNED!


The List Class


As you might guess, a doubly-linked list is represented by
an instance of class List.
Its primary purpose is to provide the necessary state of the
list — specifically, to point at the first item in the list,
and the last item in the list, so that we can start
navigation at the appropriate places. It also keeps track of
the number of items currently in the list.

Aside from the obvious access methods, the List class
supports two operations:

  • Append()
    — adds an item to the end of the List
  • Purge()
    — removes all items from the List.

[Hint: Where, in particular,
would you think the
Purge() operation would be useful within the List class?]

In
addition, there is a


Dump()

member function, which is a convenient debugging tool.  It prints out
the contents of the list in internal form — that is, the hexadecimal values
of the
List‘s
private pointers, and also prints out the internal contents of each of the
ListItems
in the
List.


The ListItem Class


Not surprisingly, an item in a doubly-linked list is
represented by an instance of class ListItem.
Its primary purpose is to hold the three pointers we talked
about above, and to support the basic operations on a ListItem:

  • ListItem()
    the constructor associates data with the list item.
    Since we don’t know what you might want to put in a
    list, this is a void *
    pointer, which must be cast appropriately, once you
    retrieve the data from a list item.
  • Add()
    — adds the item to a specified List,
    following the specified previous item. [Hint:
    What should this do if the item is already in a
    List?]
  • Remove()
    — removes the item from the List
    it is in. 

    [Hint: What should this do if
    the item is not in any
    List
    ?]
  • Data()
    this returns a void *
    pointer to the data the list item represents.
    Typically, this must be typecast to the proper type
    before you can use the pointer to access the data
    structure.  This implies that you must already know what is
    being held in the list item.

[Hint: What should the ListItem
destructor do? ]

As
before, there is a


Dump()

member function, which is a convenient debugging tool.  It prints out
the contents of the list item in internal form — that is, the hexadecimal
values of the
ListItem‘s
private pointers
.


The ListIterator Class


Whenever you wish to navigate through a doubly-linked
list, you need to maintain some context — where you are
currently positioned within the list. We could have
maintained that context within the List
class itself, but that would mean that we could only have a
single navigation active against a specific list at a time.
That is often quite restrictive, so instead we invent a
class, ListIterator,
which serves to maintain the necessary context, and in
general encapsulates the necessary support for iterating
(navigating) through a specific list.

ListIterator
supports the following operations:

  • ListIterator()
    — the constructor is responsible for associating the
    ListIterator
    with the specified List,
    and for setting its starting position at the first
    item in that List.
  • GetList()
    — Returns a pointer to the associated
    List.
  • GetNext()
    — Moves the current position to the next item in the
    List.
    If there is no next item, does not change the current
    position, and returns NULL.
  • GetPrevious()
    — Moves the current position to the previous item in
    the List.
    If there is no previous item, does not change the
    current position, and returns NULL.
  • AtFirst()
    — returns a Boolean value indicating whether the
    current position is at the first item in the
    List
  • AtLast()
    — returns a Boolean value indicating whether the
    current position is at the last item in the
    List.
  • GetCurrent()
    — This is merely an access method, and returns a
    pointer to the current item for the
    ListIterator.
    There should always be a current item for a
    ListIterator
    (i.e. it should never become NULL, nor should it
    point at anything other than a list item that is in
    the List
    being navigated by the ListIterator.). 
    There is only one exception to this: When the
    ListIterator is
    associated with a List
    that is currently empty;  only in that case may the GetCurrent()
    member function return a null pointer.  (Note, however, that the
    ListIterator class should
    be able to handle the case where the association is made with an empty
    list, and subsequently the list has items added to it. See below.)

The Assignment


Your task is to implement the three classes, List, ListItem and ListIterator. Place
the class declarations all in a single file,
list.h (as shown in the above
code), and their implementations in a single file,
list.cpp.

Here are some hints you will need to pay attention to:

  • Since these classes refer to each other, we
    need to use one or more forward references
    so that the classes will compile. Thus the need to specify
    the following line before the List class
    declaration:

class ListItem;

This will forward declare the ListItem
class so that the List
class can refer to ListItem
without the compiler complaining. Note that, since a
forward declaration does not provide any information
about a class other than its name, if you have code that
refers to information about that class, such as its size
or its members, your compiler will complain — sometimes
with some very strange error messages!

  • These three classes work together as a family of
    classes
    to support a single piece of
    functionality. It is necessary to
    declare appropriate friendship
    relationships among the classes. I have already included the
    necessary friendship declarations;  try to keep
    these to a minimum — do not
    make every class a friend of every other class.  In fact, you
    do not need to make any additions of this kind for this assignment.
  • Since all of these classes contain data members which
    are pointers, we have disabled their copy constructors and
    assignment operators, by placing the declarations of those methods in the class’s
    private section.  You do not need to implement these member
    functions.


Start by placing all your implementation code in the
list.cpp file, and don’t worry about
run-time efficiency. It’s
much better to get the code working first, and then
worry about how to make it fast — not the other way
around. Later, if you have time, you can consider
making the appropriate modifications to speed up the
code — mostly making essential member functions inline.


Here is a start at the list.cpp
file, with the Dump()
member functions coded for you, to give you a starting point:


//
// list.cpp
//

#include <iostream>
#include <cassert>	// For assert() -- use encouraged!
using namespace std;

#include "list.h"

/////////// List ////////////

void List::Dump(const string prefix) const
{
    // Print List information
    cout << prefix << "List at: " << this << endl
         << prefix << " Count:  " << GetCount() << endl
         << prefix << " First:  " << GetFirst() << endl
         << prefix << " Last:   " << GetLast() << endl;

    // Print all the ListItems
    for (ListItem *item = GetFirst();
         item != 0;
         item = item->GetNext()
        )
    {
        item->Dump(prefix + "  ");
    }
}

//////////// ListItem /////////////

void ListItem::Dump(const string prefix) const
{
    cout << prefix << " ListItem: " << this << endl
         << prefix << "   Next:  " << GetNext() << endl
         << prefix << "   Prev:  " << GetPrevious() << endl;
}

/////////////// ListIterator ////////////////


Of course, there’s lots else for you to fill in in this file!


Hints:

  • Remember to use initializer lists whenever possible
  • Try to avoid duplicating code as much as possible.  For example,
    there should be one, and only one, place where you provide code to add
    an element to a list; there should be one, and only one, place where you
    provide code to remove an element from a list.
  • Think about your List::Append
    member function: How should you implement it with the least amount of
    effort? 
    [Hint: My version of this function has a body consisting of a
    single statement.]
  • Think about how to code using as simple algorithms as possible (but
    not too simple!).  For example, my code for the List::Purge
    member function contains of four lines of code within the body of the
    function — and two of those lines each consists of a single curly
    brace.
  • Use the Dump member functions
    during your debugging — there’s a reason why I provided them for you to
    use!
  • When you come to write the code for adding an item to a list, remember
    that there are basically three cases:

    • When the item is to be inserted at the start of the list
    • When the item is to be inserted at the end of the list
    • When the item is to be inserted somewhere in the middle of the
      list.


    and remember that adding an item to an empty list is a special case
    of both of the first and second cases.   Try to ensure that
    you have all the necessary cases covered, and that the various data
    members which are pointers to various items in the list are all properly
    updated in all of the cases.  It’s easy to forget one or two! 
    Try to develop consistent practices.  It’s often helpful to draw
    yourself a diagram of all the links, before, during, and after an item
    is added to a list.

  • Similar thinking applies to when you come to write the code to remove
    an item from a list.
  • It may appear at first glance that the ListIterator::GetCurrent()
    member function is trivial to implement.  It would be, if it were
    not for the following situation that I wish this iterator to handle:

    • The iterator is created to be associated with a list that is
      empty.
    • Subsequently, items are added and removed from the list
    • The iterator is then used to iterate over the items in the list,
      based on the items that are actually in the list at that time.


    [Hint: What if the list was not empty when the iterator is created, but
    subsequently items are added to the beginning of the list before the
    iterator is used?   What should the iterator do then?]

    This means that the code for GetCurrent
    is not quite as simple as you might think.  In particular, while GetCurrent
    is conceptually const, because it must handle the above case, you will
    have to code it in such a way that it is not const.  See the
    slides on the web site for how to do this.

  • One more thing about GetCurrent
    It should only return with a NULL pointer under one condition:  if
    its associated list is currently empty
    .  Under all other
    circumstances, it should return a valid pointer to the list item that is
    currently located at within its associated list.  In particular,
    attempting to move from the last item in the list to the (non-existent)
    next item, or attempting to move from the first item in the list to the
    (non-existent) previous item, should not affect the value of the current
    pointer at all.


Testing Your Implementation


I’ve discovered that most of my students seem to struggle to create a
thorough test for their implementation.  So, to provide a (hopefully) good
example of how to test, and to provide you with some guidance on what
constitutes correct operation, here is a test program that tests just the basic
List/ListItem/ListIterator class operations:



#include <iostream>
using namespace std;
#include "list.h"

/*
 * testList.cpp
 */

/* 
 * Tests a ListIterator, by iterating forward through the list, 
 * then backward, then forward again.
 */
void testIterator(ListIterator &iter)
{
    cout << "The list contains " << iter.GetList()->GetCount() 
                                 << " items" << endl;
    cout << "The iterator is at the start of the list: " 
                                 << boolalpha << iter.AtFirst() << endl;

    ListItem *item = 0;
    cout << "Iterating forward..." << endl;
    for ( item = iter.GetCurrent(); item != 0; item = iter.GetNext() ) 
    {
        double *d = (double *) item->GetData();
        cout << *d << endl;
    }

    cout << "The iterator is at the end of the list: " 
                                 << boolalpha << iter.AtLast() << endl;    
    cout << "Iterating backward..." << endl;
    for ( item = iter.GetCurrent(); item != 0; item = iter.GetPrevious() ) 
    {
        double *d = (double *) item->GetData();
        cout << *d << endl;
    }

    cout << "The iterator is at the start of the list: " 
                                  << boolalpha << iter.AtFirst() << endl;    
    cout << "Iterating forward again..." << endl;
    for ( item = iter.GetCurrent(); item != 0; item = iter.GetNext() ) 
    {
        double *d = (double *) item->GetData();
        cout << *d << endl;
    }
}

/*
 * Main entry point to do a fairly complete test of the basic 
 * List/ListItem/ListIterator classes.
 */
int main()
{
    List list;
    ListIterator iter1(list);

    cout << "---Testing iteration through an empty list---" << endl;
    testIterator(iter1);

    cout << "---Initial list---" << endl;
    list.Dump();

    double d1 = 1.0, d2 = 2.0, d3 = 3.0, d4 = 4.0;

    ListItem item1(&d1);
    cout << "---Appending list item---" << endl;
    list.Append(item1);
    list.Dump();

    ListItem item2(&d2);
    cout << "---Adding list item to front of list---" << endl;
    item2.Add(list, 0);
    list.Dump();

    ListItem item3(&d3);
    cout << "---Inserting list item in the middle of list---" << endl;
    item3.Add(list, &item2);
    list.Dump();

    ListItem item4(&d4);
    cout << "---Adding list item to the end of list---" << endl;
    item4.Add(list, &item1);
    list.Dump();

    cout << "---Testing iterator initialized against full list---" << endl;

    ListIterator iter2(list);
    testIterator(iter2);

    cout << "---Testing iterator initialized against empty list---" << endl;
    testIterator(iter1);

    cout << "---Testing removal of item from end of list---" << endl;
    item4.Remove();
    list.Dump();

    cout << "---Testing removal of item from middle of list---" << endl;
    item3.Remove();
    list.Dump();

    cout << "---Testing removal of item from front of list---" << endl;
    item2.Remove();
    list.Dump();

    cout << "---Testing removal of item alone in list---" << endl;
    item1.Remove();
    list.Dump();

    cout << "---Adding items back to list---" << endl;
    list.Append(item1);
    list.Append(item2);
    list.Append(item3);
    list.Append(item4);
    list.Dump();

    cout << "---Testing purge---" << endl;
    list.Purge();
    list.Dump();

    cout << "---Ending main function---" << endl;
    cout << "***You should be testing the List destructor***" << endl;

    return 0;
}

Using Your Implementation


Wines


To give you an idea how you might use these classes in a
real situation, here’s an example.

Naturally, when I thought of lists, the first thing that came into my
mind was a wine list!  So here’s a very simple Wine class, some of
which you will be filling in.  Then there is a test program to give our
list implementation a reasonable degree of testing in a wine list situation.




#ifndef _WINE
#define _WINE
//
// wine.h
//

#include <string>
using namespace std;

class Wine
{
  public:
    Wine(const string &name, int year);
    Wine(const Wine &wine);
    ~Wine();

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

    int Year() const
    { 
        return m_year; 
    }

    // Assignment operator
    Wine &operator=(const Wine &wine);

    void Print() const;

  private:
    // Data members
    string m_name;
    int    m_year;
};

#endif

//
// wine.cpp
//

#include <iostream>
using namespace std;

#include "wine.h"

Wine::Wine(const string &name, int year)
    : m_name(name), m_year(year)
{}

void Wine::Print() const
{
    cout << "Wine: " << m_name << ", " << m_year << endl;
}

// You implement the remaining member functions of the Wine class

// 
// test1.cpp
//

#include <iostream>
using namespace std;

#include "list.h"
#include "wine.h"

static void display(List &list)
{
    cout << "Contents of list:" << endl;
    ListIterator iter(list);
    for (ListItem *item = iter.GetCurrent();
         item != 0;
         item = iter.GetNext()
        )
    {
        Wine *wine = (Wine *)(item->GetData());
        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.
    ListItem items[] = { &beaujolais, &amontillado,
                         &riesling,   &gewurztraminer,
                         &shiraz,     &cabernet };

    ListItem *item; // Item pointer used in several places
    Wine *wine;     // Wine pointer used in many places

    List 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.
    ListIterator iter(list);

    // Start testing

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

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

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

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

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

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

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

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

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

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

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

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

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

    cout << "Testing removal of last item" << endl;
    cout << " Removing: "; 
    wine = (Wine *)(items[0].GetData());
    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;
    List *dynList = new List();
    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;
}


Persons


Now, let’s look at an alternative approach to using such Lists, ListItems,
etc.

You may notice that it’s a little clumsy to separate a ListItem from the
data it represents. Here’s another, slightly different,
approach that makes things a little easier:




#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;
};

#endif

// person.cpp

#include <iostream>
using namespace std;

#include "person.h"

Person::Person(const string &name) 
    : m_item(this), m_name(name)
{}

void Person::Print() const
{
    cout << "Person: " << m_name << endl;
}

// You implement the remaining member functions of the Person class

// test2.cpp

#include <iostream>
using namespace std;

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

static void display(List &list)
{
    cout << "Contents of list:" << endl;
    ListIterator iter(list);
    for (ListItem *item = iter.GetCurrent();
         item != 0;
         item = iter.GetNext()
        )
    {
        Person *person = (Person *)(item->GetData());
        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 };

    ListItem *item;

    List 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.
    ListIterator 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, (Person *)(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 (item = iter.GetCurrent(); 
         item != 0; 
         item = iter.GetNext())
    {
        Person *person = (Person *)(item->GetData());
        person->Print();
    }

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

    cout << "Reversing direction again..." << endl;
    for (item = iter.GetCurrent();
         item != 0;
         item = iter.GetNext()
        )
    {
        Person *person = (Person *)(item->GetData());
        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++)
    {
        ListItem &item = *(items[elem]);
        if (item.GetList() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still in a list" << endl;
        }
        if (item.GetNext() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a next ptr" << endl;
        }
        if (item.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;
    List *dynList = new List();
    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++)
    {
        ListItem &item = *(items[elem]);
        if (item.GetList() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still in a list" << endl;
        }
        if (item.GetNext() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a next ptr" << endl;
        }
        if (item.GetPrevious() != 0)
        {
            errors++;
            cerr << "Element " << elem << " still has a previous ptr" << endl;
        }
    }
    cout << errors << " errors detected" << endl;
}

int main()
{
    ListPersons();

    return 0;
}


Testing Your Implementation


You will need to do a reasonable amount of testing to
ensure that your implementation of these classes actually
works correctly. The above test1.cpp
and test2.cpp files do
some reasonable amount of testing, but don’t feel restricted by them. 
If you do add your own tests, please create your own test main program –
it’s much easier for me to separate out your efforts from mine!

I strongly suggest that you freely instrument
your code so that you can turn on tracing and debugging
information when convenient and/or necessary. Adding a line
like:

cout << "Adding item at " << this << " after item at " << prevItem
     << " and before item at " << nextItem << endl;

at the appropriate place in your code can really help you
figure out what’s going on.  However, I don’t need to see all these
lines of code, so just use them for your debugging, and then clean them out
so I can read your code.

Note that the calls to the Dump member
functions may give you as much information as you need, but then again, if
you need to do your own tracing, you need to do it.

I expect
you to provide me with evidence (hard copy output
would be best) that you have tested the program
sufficiently. Since you will be using and enhancing
these classes in later assignments, it’s to your
advantage to make sure that they work, now!


 



This page was last changed on 09 Apr 2006