Adding Your Own Class to Sprocket

Part 1 - A Linked List Class

By Dave Mark, MacTech Magazine Regular Contributing Author

Last month, we finally got into our new (and ever evolving) framework, Sprocket. In the next few columns, we’re going to create a new set of classes designed to add functionality to Sprocket. This month, we’ll create and test our new classes and next month we’ll step through the process of adding the classes to Sprocket.

I know, I know. Last month I said we were going to take a closer look at Sprocket’s window classes. Bear with me. Every time I dig into this C++ framework stuff, my perspective changes and I get a new sense of the direction in which I should be heading. We’ll get to the window classes eventually.

A Linked List Class

Every framework needs some sort of linked list class. You might want to maintain a list of CDs or your favorite movies. You might be building some sort of network server that maintains a list of network service requests. Whatever your need, there are probably a million ways to design a linked list class that fits the bill. In some cases, you’ll adopt a general approach, designing a set of classes intended for many different applications. In other cases, you’ll have a specific functional or performance need and you’ll design a class that might not be of much use to anyone else, but will solve your problem.

Dave Falkenburg (Sprocket’s daddy) and I were chatting a few weeks ago about some of the features Dave envisioned for Sprocket’s future. One of these features centered around a method for keeping track of your application’s documents. As an example, when the user quits your application, you need to step through each of your open documents, calling each document’s close method. Some applications solve this problem by stepping through the window list maintained by the system for every open application. Besides the technical mumbo-jumbo you have to go through to maintain compatibility with older versions of the MacOS, there are two basic problems with this approach. Some of your windows may not be associated with a document, and some of your documents may require more than a single window.

The linked list classes we’re going to explore this month were designed specifically to maintain a list of document object pointers. As you’ll see, I tried to generalize the linked list classes so that you could use them to store pointers to any objects you like, but the member functions (aka, methods) were designed with document management in mind. We’ll get into the specifics of maintaining a list of document object pointers next month when we add the classes to Sprocket. This month we’re going to enter the classes, then take them for a test drive.

The List Tester Project

This month’s source code was tested using both CodeWarrior and Symantec C++. Pick your favorite compiler and build a new iostream-based project. Figure 1 shows my CodeWarrior project window. Be sure you add the three libraries shown. If you intend on generating PowerPC code, you’ll need to swap the two 68K-specific libraries for those appropriate to the PowerPC.

Figure 1. The CodeWarrior version of the ListTester project.

Figure 2 shows the Symantec C++ version of the ListTester project window. If you are using Symantec C++, be sure to add the three libraries CPlusLib, ANSI++, and IOStreams to your project. You can have this done automatically by selecting “C++ IoStreams Project” from the list of project types that appear when you select New Project from the THINK Project Manager’s File menu.

Figure 2. The Symantec C++ version of the ListTester project.

As you can see from the two figures, you’ll be adding 3 source code files to the project. In addition, you’ll be creating 2 additional include files, bringing the grand total to 5. The next five sections contain the source code for each of these five files. Type in the code (assuming you haven’t already downloaded it), save it under the appropriate file name, and add each of the 3 “.cp” files to the project.

Main.cp

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

void    CountAndDisplayLinks( TLinkedList *listPtr );

int main()
{
    TLinkedList     *listPtr;
    char            *string;
    char            *s1 = "Frank Zappa",
                    *s2 = "Violent Femmes",
                    *s3 = "Jane Siberry";
    
    listPtr = new TLinkedList;
    
    listPtr->CreateAndAddLink( s1 );
    listPtr->CreateAndAddLink( s2 );
    listPtr->CreateAndAddLink( s3 );
    
    CountAndDisplayLinks( listPtr );
    
    cout << "-----\n";
    
    string = (char *)listPtr->GetNthLinkObject( 2UL );
    listPtr->FindAndDeleteLink( string );
    
    CountAndDisplayLinks( listPtr );
    
    return 0;
}
CountAndDisplayLinks

void    CountAndDisplayLinks( TLinkedList *listPtr )
{
    unsigned long    counter, numLinks;
    char            *string;
    
    numLinks = listPtr->CountLinks();

    cout << "This list has ";
    cout << numLinks;
    cout << " links...\n";
    
    for ( counter = 1; counter <= numLinks; counter++ )
    {
        cout << "Link #" << counter << ": ";
        string = (char *)listPtr->GetNthLinkObject( counter );
        
        cout << string << "\n";
    }
}

LinkedList.h

#ifndef        _LINKEDLIST_
#define        _LINKEDLIST_

#ifndef        _LINK_
#include    "Link.h"
#endif

const OSErr kLinkedList_LinkNotFoundErr = -2;
const OSErr kLinkedList_CouldNotDeleteLinkErr = -3;
class TLinkedList
class    TLinkedList
{
  public:
                            TLinkedList();
    virtual                 ~TLinkedList();

    virtual    OSErr       CreateAndAddLink(void *objectPtr);
    virtual    OSErr       FindAndDeleteLink(void *objectPtr);
    virtual unsigned long  CountLinks();
    virtual void   *GetNthLinkObject(unsigned long linkIndex);

  protected:
    virtual void            DeleteAllLinks();
    TLink                   *FindLink( void *objectPtr );
    virtual OSErr           DeleteLink( TLink *linkPtr );
    
    TLink                   *fFirstLinkPtr;
    TLink                   *fLastLinkPtr;
};

#endif

LinkedList.cp

#include "LinkedList.h"
#include "Link.h"

TLinkedList::TLinkedList()
{
    fFirstLinkPtr = nil;
    fLastLinkPtr = nil;
}
TLinkedList::~TLinkedList
TLinkedList::~TLinkedList()
{
    DeleteAllLinks();
}
TLinkedList::CreateAndAddLink

OSErr TLinkedList::CreateAndAddLink( void *objectPtr )
{
    TLink    *newLinkPtr;
    
    newLinkPtr = new TLink( objectPtr );
    
    if ( newLinkPtr == nil )
        return kLink_BadLinkErr;

    if ( fFirstLinkPtr == nil )
        fFirstLinkPtr = newLinkPtr;
    
    if ( fLastLinkPtr != nil )
        fLastLinkPtr->SetNextLink( newLinkPtr );

    newLinkPtr->SetPrevLink( fLastLinkPtr );
    newLinkPtr->SetNextLink( nil );
    
    fLastLinkPtr = newLinkPtr;
    
    return noErr;
}
TLinkedList::FindAndDeleteLink

OSErr TLinkedList::FindAndDeleteLink( void *objectPtr )
{
    TLink        *foundLinkPtr;
    
    foundLinkPtr = FindLink( objectPtr );
    
    if ( foundLinkPtr == nil )
        return kLinkedList_LinkNotFoundErr;
    else
        return DeleteLink( foundLinkPtr );
}
TLinkedList::CountLinks
unsigned long TLinkedList::CountLinks()
{
    TLink            *currentLinkPtr;
    unsigned long    numLinks;
    
    numLinks = 0;
    currentLinkPtr = fFirstLinkPtr;
    
    while ( currentLinkPtr != nil )
    {
        numLinks++;
        currentLinkPtr = currentLinkPtr->GetNextLink();
    }
    
    return numLinks;
}
TLinkedList::GetNthLinkObject

void    *TLinkedList::GetNthLinkObject( unsigned long linkIndex )
{
    TLink            *currentLinkPtr;
    unsigned long    numLinks, curLinkIndex;
    
    numLinks = CountLinks();
    
    if ( (linkIndex < 1) || (linkIndex > numLinks) )
        return nil;
    
    curLinkIndex = 0;
    currentLinkPtr = fFirstLinkPtr;
    
    for (curLinkIndex=1; curLinkIndex<linkIndex; curLinkIndex++)
        currentLinkPtr = currentLinkPtr->GetNextLink();
        
    return currentLinkPtr->GetObjectPtr();
}
TLinkedList::DeleteAllLinks

void TLinkedList::DeleteAllLinks()
{
    TLink        *currentLinkPtr, *nextLinkPtr;
    
    currentLinkPtr = fFirstLinkPtr;
    
    while ( currentLinkPtr != nil )
    {
        nextLinkPtr = currentLinkPtr->GetNextLink();
        delete currentLinkPtr;
        currentLinkPtr = nextLinkPtr;
    }
    
    fFirstLinkPtr = nil;
    fLastLinkPtr = nil;
}
TLinkedList::FindLink

TLink    *TLinkedList::FindLink( void *objectPtr )
{
    TLink        *currentLinkPtr;
    
    currentLinkPtr = fFirstLinkPtr;
    
    while ( currentLinkPtr != nil )
    {
        if ( currentLinkPtr->GetObjectPtr() == objectPtr )
            return currentLinkPtr;
            
        currentLinkPtr = currentLinkPtr->GetNextLink();
    }
    return nil;
}
TLinkedList::DeleteLink

OSErr    TLinkedList::DeleteLink( TLink *linkPtr )
{
    if ( linkPtr == nil )
        return kLinkedList_CouldNotDeleteLinkErr;
    
    if ( linkPtr == fFirstLinkPtr )
        fFirstLinkPtr = linkPtr->GetNextLink();
    else
        linkPtr->GetPrevLink()->
  SetNextLink( linkPtr->GetNextLink() );

    if ( linkPtr == fLastLinkPtr )
        fLastLinkPtr = linkPtr->GetPrevLink();
    else
        linkPtr->GetNextLink()->
  SetPrevLink( linkPtr->GetPrevLink() );
    return noErr;
}

Link.h

#ifndef        _LINK_
#define        _LINK_

#include <types.h>

const short kLink_BadLinkErr = -1;
class TLink
class    TLink
{
  public:
                    TLink( void *objectPtr );
    virtual         ~TLink();
    virtual void    SetPrevLink( TLink *prevLinkPtr )
                        { fPrevLinkPtr = prevLinkPtr; }
    virtual void    SetNextLink( TLink *nextLinkPtr )
                        { fNextLinkPtr = nextLinkPtr; }
    virtual TLink   *GetPrevLink()
                        { return fPrevLinkPtr; }
    virtual TLink   *GetNextLink()
                        { return fNextLinkPtr; }
    virtual void    *GetObjectPtr()
                        { return fObjectPtr; }

  protected:
      TLink         *fPrevLinkPtr;
      TLink         *fNextLinkPtr;
      void          *fObjectPtr;
};

#endif

Link.cp

#include "Link.h"
TLink::TLink
TLink::TLink( void *objectPtr )
{
    fObjectPtr = objectPtr;
    fPrevLinkPtr = nil;
    fNextLinkPtr = nil;
}

TLink::~TLink()
{
}

Running LinkTester

Once all your code is typed in and the appropriate files are added to your project, you’re ready to go. When you run ListTester, an iostream console window will appear, showing the following output:

This list has 3 links...
Link #1: Frank Zappa
Link #2: Violent Femmes
Link #3: Jane Siberry
-----
This list has 2 links...
Link #1: Frank Zappa
Link #2: Jane Siberry

Now let’s make some sense out of all this. LinkedList.h contains the declaration of a linked list class, namely TLinkedList. We’ll start all our class names off with the letter T to stay compatible with Sprocket. It’s just a convention and doesn’t affect the code in any way. Pure semantics. LinkedList.cp contains the definitions of the TLinkedList member functions.

A TLinkedList consists of a series of TLink objects, all linked together via pointers. A TLinkedList object is an entire linked list, while a TLink is a single link in the list. Link.h contains the declaration of the TLink class, and Link.cp contains the definitions of the TLink member functions.

If this is your first time working with linked lists, take some time to read up on the basics, Learn C on the Macintosh will get you started, but it doesn’t really get into any theory. Once you understand the basic linked list mechanism, you’ll want to explore some of the more sophisticated data structures and the algorithms that make them work. There are a lot of good books out there. My personal favorite is Volume 1 (“Fundamental Algorithms”) of Donald Knuth’s series The Art of Computer Programming.

ListTester starts by creating a new TLinkedList object, then adds three new links to the list. The links contain three C text strings, but could easily handle a document object or any other block of data. Once we add the three links to the list, we call a routine that displays the contents of the list.

Next, we call a member function to delete the second link in the list, then display the list again. That’s about it. Let’s take a look at the source code.

Main.cp

main.cp starts off by including <iostream.h>, which gives it access to cout and the rest of the iostream library. We also include LinkedList.h to give us access to the members of the TLinkedList class.

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

CountAndDisplayLinks() walks through a linked list and displays the strings embedded in the list.

void    CountAndDisplayLinks( TLinkedList *listPtr );

main() starts off by creating a new TLinkedList object. Notice that the TLinkedList constructor doesn’t take any parameters.

int main()
{
    TLinkedList     *listPtr;
    char            *string;
    char            *s1 = "Frank Zappa",
                    *s2 = "Violent Femmes",
                    *s3 = "Jane Siberry";
    
    listPtr = new TLinkedList;

Next, we call the CreateAndAddLink() member function to add our three text strings to the list. We then call CountAndDisplayLinks() to walk through the list and display the contents.

    listPtr->CreateAndAddLink( s1 );
    listPtr->CreateAndAddLink( s2 );
    listPtr->CreateAndAddLink( s3 );
    
    CountAndDisplayLinks( listPtr );
    
    cout << "-----\n";

Next, we’ll retrieve the second object in the list, so we can delete it by calling FindAndDeleteLink(). There are a few interesting things to note here. First, notice that we had to typecast the value returned by GetNthLinkObject() to a (char *). Each TLink features a data member which points to the data associated with that link. As you’ll see, the TLink stores the data as a (void *). The advantage of this strategy is that it lets you store any type of data you like in the list. You can even mix data types in a single list. The catch is, you have to know what the data type is when you retrieve it. If you plan on mixing data types, you can start each data block off with a flag that tells you its type, or you can add a data member to the TLink class (or, better yet, to a class you derive from TLink) that specifies the type of data stored in a link.

The second point of interest here is the fact that we deleted the data from the list using the data itself instead of specifying its position in the list. In other words, we said, go find the string “Violent Femmes” and delete it, rather than, delete the 2nd item in the list. There are definitely pros and cons to this approach. Since these classes were defined to handle documents, this approach should work just fine. A more sophisticated strategy might assign a serial number to each link, then delete the link by specifying its serial number. Since document object pointers will be unique, our approach should be OK. The true test will come down the road as we add more sophisticated document handling capabilities to Sprocket.

    string = (char *)listPtr->GetNthLinkObject( 2UL );
    listPtr->FindAndDeleteLink( string );

Finally, we redisplay the list to verify the link’s deletion.

    CountAndDisplayLinks( listPtr );
 
    return 0;
}

CountAndDisplayLinks() is pretty straightforward. We first call CountLinks() to find out how many links are in the list, then loop through that many calls to GetNthLinkObject().

void    CountAndDisplayLinks( TLinkedList *listPtr )
{
    unsigned long    counter, numLinks;
    char            *string;
    
    numLinks = listPtr->CountLinks();

    cout << "This list has ";
    cout << numLinks;
    cout << " links...\n";
    
    for ( counter = 1; counter <= numLinks; counter++ )
    {
        cout << "Link #" << counter << ": ";
        string = (char *)listPtr->GetNthLinkObject( counter );
        cout << string << "\n";
    }
}

LinkedList.h

LinkedList.h contains the declaration of the LinkedList class. As we did in our last C++ column, we start the .h file off with some code that prevents us from multiply declaring the class in case a .cp file includes this file and also includes another .h file that includes this file.

#ifndef        _LINKEDLIST_
#define        _LINKEDLIST_

#ifndef        _LINK_
#include    "Link.h"
#endif

These two constants are error codes returned by various TLinkedList member function. Though our little test program didn’t test for these errors, our Sprocket code definitely will. Until Sprocket supports true C++ exception handling, our error checking will consist of checking the return codes returned by member functions and bubbling the errors up to the routine that must deal with the error.

const OSErr kLinkedList_LinkNotFoundErr = -2;
const OSErr kLinkedList_CouldNotDeleteLinkErr = -3;

The TLinkedList class features a constructor, a destructor, and four public member functions. CreateAndAddLink() creates a new TLink, embeds the objectPtr in the link, then adds the link at the end of the list. FindAndDeleteLink() walks through the list till it finds a link containing a pointer that matches objectPtr. When the match is found, the link is deleted. CountLinks() returns the number of links in the list. GetNthLinkObject() walks down the list and returns the objectPtr embedded in the Nth link in the list.

As we discussed in an earlier column, marking the destructor and other member functions as virtual allows the proper member function to be called when a new class is derived from this class and a base class pointer holds a pointer to the derived class. For more details, look up virtual destructors in your favorite C++ book.

class    TLinkedList
{
  public:
                            TLinkedList();
    virtual                 ~TLinkedList();

    virtual    OSErr      CreateAndAddLink(void *objectPtr);
    virtual    OSErr      FindAndDeleteLink(void *objectPtr);
    virtual unsigned long CountLinks();
    virtual void    *GetNthLinkObject(unsigned long linkIndex);

The protected members are not intended for public consumption. Instead, they are used internally by the linked list member functions.

  protected:
    virtual void            DeleteAllLinks();
    TLink                   *FindLink( void *objectPtr );
    virtual OSErr           DeleteLink( TLink *linkPtr );
    
    TLink                   *fFirstLinkPtr;
    TLink                   *fLastLinkPtr;
};

#endif

LinkedList.cp

Since the TLinkedList member functions work with both TLinkedList and TLink members, we need to include both .h files.

#include "LinkedList.h"
#include "Link.h"

The TLinkedList constructor sets the pointers to the first and last links in the list to nil. By the way, nil is defined in <Types.h>. Also, note that all data members start with the letter f (again, just a convention).

TLinkedList::TLinkedList()
{
    fFirstLinkPtr = nil;
    fLastLinkPtr = nil;
}

The destructor deletes all the links in the list.

TLinkedList::~TLinkedList()
{
    DeleteAllLinks();
}

CreateAndAddLink() creates a new TLink, then uses the TLink member functions SetPrevLink() and SetNextLink() to connect the link into the linked list. Each link features a prev and a next pointer, pointing to the previous and next links in the list. These two pointers make our linked list a doubly-linked list. We won’t get into the advantages and disadvantages of doubly versus singly-linked lists here. Suffice it to say that we definitely could have solved our problem any number of ways.

OSErr TLinkedList::CreateAndAddLink( void *objectPtr )
{
    TLink    *newLinkPtr;
    
    newLinkPtr = new TLink( objectPtr );
    
    if ( newLinkPtr == nil )
        return kLink_BadLinkErr;

    if ( fFirstLinkPtr == nil )
        fFirstLinkPtr = newLinkPtr;
    
    if ( fLastLinkPtr != nil )
        fLastLinkPtr->SetNextLink( newLinkPtr );

    newLinkPtr->SetPrevLink( fLastLinkPtr );
    newLinkPtr->SetNextLink( nil );
    
    fLastLinkPtr = newLinkPtr;
    
    return noErr;
}

FindAndDeleteLink() calls FindLink() to find the link in the list, then deletes the link if it was found.

OSErr TLinkedList::FindAndDeleteLink( void *objectPtr )
{
    TLink        *foundLinkPtr;
    
    foundLinkPtr = FindLink( objectPtr );
    
    if ( foundLinkPtr == nil )
        return kLinkedList_LinkNotFoundErr;
    else
        return DeleteLink( foundLinkPtr );
}

CountLinks() starts off at the beginning of the list (at the link pointed to by fFirstLinkPtr), then uses GetNextLink() to walk down the list, counting links until we get to the last link, which will always have a next pointer of nil.

unsigned long TLinkedList::CountLinks()
{
    TLink            *currentLinkPtr;
    unsigned long    numLinks;
    
    numLinks = 0;
    currentLinkPtr = fFirstLinkPtr;
    
    while ( currentLinkPtr != nil )
    {
        numLinks++;
        currentLinkPtr = currentLinkPtr->GetNextLink();
    }
    
    return numLinks;
}

GetNthLinkObject() first checks to be sure the requested link is actually in the list.

void    *TLinkedList::GetNthLinkObject( unsigned long linkIndex )
{
    TLink            *currentLinkPtr;
    unsigned long    numLinks, curLinkIndex;
    
    numLinks = CountLinks();
    
    if ( (linkIndex < 1) || (linkIndex > numLinks) )
        return nil;

Once we know we’ve got a valid link, we’ll step through the list the proper number of times to get to the requested link, then call GetObjectPtr() to retrieve the object pointer.

    curLinkIndex = 0;
    currentLinkPtr = fFirstLinkPtr;
    
    for (curLinkIndex=1; curLinkIndex<linkIndex; curLinkIndex++)
        currentLinkPtr = currentLinkPtr->GetNextLink();
        
    return currentLinkPtr->GetObjectPtr();
}

DeleteAllLinks() steps through the list and deletes every link in the list. Notice that we save the next pointer before we delete the link so we don’t delete the next pointer along with it.

void TLinkedList::DeleteAllLinks()
{
    TLink        *currentLinkPtr, *nextLinkPtr;
    
    currentLinkPtr = fFirstLinkPtr;
    
    while ( currentLinkPtr != nil )
    {
        nextLinkPtr = currentLinkPtr->GetNextLink();
        delete currentLinkPtr;
        currentLinkPtr = nextLinkPtr;
    }
    
    fFirstLinkPtr = nil;
    fLastLinkPtr = nil;
}

FindLink() steps through the list (does this stepping code look familiar?) and returns the current TLink if its object pointer matches the parameter. If the entire list is searched and no match is found, FindLink() returns nil.

TLink    *TLinkedList::FindLink( void *objectPtr )
{
    TLink        *currentLinkPtr;
    
    currentLinkPtr = fFirstLinkPtr;
    
    while ( currentLinkPtr != nil )
    {
        if ( currentLinkPtr->GetObjectPtr() == objectPtr )
            return currentLinkPtr;
            
        currentLinkPtr = currentLinkPtr->GetNextLink();
    }
    return nil;
}

DeleteLink() deletes the specified link, then reconnects the previous link with the link that follows the deleted link.

OSErr    TLinkedList::DeleteLink( TLink *linkPtr )
{
    if ( linkPtr == nil )
        return kLinkedList_CouldNotDeleteLinkErr;
    
    if ( linkPtr == fFirstLinkPtr )
        fFirstLinkPtr = linkPtr->GetNextLink();
    else
        linkPtr->GetPrevLink()->
 SetNextLink( linkPtr->GetNextLink() );

    if ( linkPtr == fLastLinkPtr )
        fLastLinkPtr = linkPtr->GetPrevLink();
    else
        linkPtr->GetNextLink()->
 SetPrevLink( linkPtr->GetPrevLink() );
    
    return noErr;
}

Link.h

Link.h includes <types.h> to give it access to the definition of nil.

#ifndef        _LINK_
#define        _LINK_


#include <types.h>

The TLink class includes a single error code.

const short kLink_BadLinkErr = -1;

In addition to the constructor and destructor, the TLink class includes two setter and three getter functions. A setter function sets a data member to a specified value. A getter function returns the value of a data member. Though you can mark the data members as public, it’s a better idea to limit access to them to getter and setter functions. By convention, getter and setter functions are defined in-line, rather than cluttering up the .cp file.

class    TLink
{
  public:
                    TLink( void *objectPtr );
    virtual         ~TLink();
    virtual void    SetPrevLink( TLink *prevLinkPtr )
                        { fPrevLinkPtr = prevLinkPtr; }
    virtual void    SetNextLink( TLink *nextLinkPtr )
                        { fNextLinkPtr = nextLinkPtr; }
    virtual TLink   *GetPrevLink()
                        { return fPrevLinkPtr; }
    virtual TLink   *GetNextLink()
                        { return fNextLinkPtr; }
    virtual void    *GetObjectPtr()
                        { return fObjectPtr; }

  protected:
      TLink         *fPrevLinkPtr;
      TLink         *fNextLinkPtr;
      void          *fObjectPtr;
};

#endif

Link.cp

Since our five getters and setters were defined in the header file, the file Link.cp is pretty skimpy. The constructor initializes the link’s data members and the destructor does nothing at all.

#include "Link.h"

TLink::TLink( void *objectPtr )
{
    fObjectPtr = objectPtr;
    fPrevLinkPtr = nil;
    fNextLinkPtr = nil;
}

TLink::~TLink()
{
}

Till Next Month...

I love data structures. They are the backbone of any software program. Once you master the linked list, you can move on to binary trees (which are my personal favorites), then to hash tables and the like. I’ll try to find an excuse to implement some of these structures as classes in a future column. In the meantime, experiment with these classes. Think about what you’d need to do to build a list of document objects using Sprocket. Where would you create the TLinkedList object? Would you need a global TLinkedList pointer? Where would you create the TLinks? Where would you put the code that deletes the TLinks? We’ll address all of these issues next month...