This book focuses on the manipulation of complex and powerful data structures. The fundamental data structure, beyond arrays and other built-in types, is the list.
Before you begin work on the list, however, you will need a good String class. Strings, of course, are essential in building your messaging system as described on day 1, and they will be an integral component of many of the other classes you will see today and on future days.
Today you will learn
The fundamental building block of your Note class will be strings. Strings are blocks of text such as sentences or paragraphs.
Your String class will allow for the creation and manipulation of variable-length sequences of characters. You decide to allow strings of zero to 65,535 characters; that is, you will index the strings using an unsigned int, and your strings will all fit in one 64K segment if you run your program on an 80x86 machine.
Your String class will look to the user like a C-style array of characters, but it will provide its own memory management, bounds checking, and sophisticated set of operators. Your preliminary design calls for supporting string concatenation and comparison, copying, and dynamic reallocation of memory as required.
You will overload const char * conversion operators so that your strings can be used wherever C-style strings are required, such as in standard library function calls. Other operators will enable you to directly access a non-constant char * if required.
You will treat the String object as a string, not as a pointer to a char *. You can allocate String objects on the stack or the heap, but each string object will manage its own internal memory on the heap. Clients of your String class therefore get the convenience of stack-based objects without losing the flexibility of dynamic allocation. Because stack-based string objects will be destroyed automatically when exceptions are thrown, exception cleanup becomes trivial if you declare your string objects on the stack.
Listing 3.1 provides the interface to the string object, which you should save in a file called string.hpp. This file is used throughout the rest of the book.
Listing 3.1 Using the String Class Interface
1: // Listing 3.1 - Using the String Class Interface
2:
3: #include <iostream.h>
4: #include <string.h>
5: #define int unsigned int
6: enum BOOL { FALSE, TRUE };
7:
8: class xOutOfBounds {};
9:
10: class String
11: {
12: public:
13:
14: // constructors
15: String();
16: String(const char *);
17: String (const char *, int length);
18: String (const String&);
19: ~String();
20:
21: // helpers and manipulators
22: int GetLength() const { return itsLen; }
23: BOOL IsEmpty() const { return (BOOL) (itsLen == 0); }
24: void Clear(); // set string to 0 length
25:
26: // accessors
27: char operator[](int offset) const;
28: char& operator[](int offset);
29: const char * GetString()const { return itsCString; }
30:
31: // casting operators
32: operator const char* () const { return itsCString; }
33: operator char* () { return itsCString;}
34:
35: // operators
36: const String& operator=(const String&);
37: const String& operator=(const char *);
38:
39: void operator+=(const String&);
40: void operator+=(char);
41: void operator+=(const char*);
42:
43: int operator<(const String& rhs)const;
44: int operator>(const String& rhs)const;
45: int operator<=(const String& rhs)const;
46: int operator>=(const String& rhs)const;
47: int operator==(const String& rhs)const;
48: int operator!=(const String& rhs)const;
49:
50:
51: // friend functions
52: String operator+(const String&);
53: String operator+(const char*);
54: String operator+(char);
55:
56: friend ostream& operator<< (ostream&, const String&);
57:
58: private:
59: // returns 0 if same, -1 if this is less than argument,
60: // 1 if this is greater than argument
61: int StringCompare(const String&) const; // used by Boolean operators
62:
63:
64: char * itsCString;
65: int itsLen;
66: };
67:
Output:
None.
Analysis:
String.hpp attempts to provide the fundamental features of a String class. It has four constructors, although more may be added later. Note that the String class explicitly provides a default constructor (line 15). Remember that if you provide any constructors, the default constructor (the constructor with no parameters) no longer is provided by the compiler; if you need one, you must write it explicitly.
A constructor is provided to create a String object from a C-style null-terminated string (henceforth called a C-style string). Another constructor creates a string of a maximum length based on a C-style string and, finally, a copy constructor is provided.
The destructor is explicitly provided, as are a number of helper functions: GetLength(), which returns the length of the string (not including the terminating null); IsEmpty(), which returns TRUE if the string has length 0; and Clear(), which removes the string and sets the length to 0.
The offset operator ([]) is twice overloadedin line 27, it is the read-only version; and in line 28, it is the read-write (nonconstant) version.
The assignment operator (=) also is twice overloadedonce to provide assignment of Strings, and then again to provide assignment of C-style strings.
Operator plus-equals is overloaded to allow the addition of Strings to other Strings, to single characters, and to C-style strings. In lines 51 through 54, operator plus is overloaded three times to allow adding Strings to other Strings, to C-style strings, and to single characters.
The Boolean operators are overloaded in lines 43 through 48. Finally, the ostream insertion operator (<<) is overloaded on line 58. An extraction operator (>>) is not provided at this time, because its use is not anticipated, but this easily can be added later.
The helper function StringCompare() is designated as private, because only member functions of the class will ever need to call this function directly. It is used by the Boolean operators, as you will see in the next listing.
Finally, itsString is the C-style string that provides internal storage for the String's characters, and itsLen provides the current length of itsString.
Listing 3.2 provides the implementation of the string object, which you should save in a file called string.cpp. This file will be used throughout the rest of the book.
Listing 3.2 Using String Class Implementation
1: #include "string.hpp"
2: // default constructor creates string of 0 bytes
3: String::String()
4: {
5: itsCString = new char[1];
6: itsCString[0] = '\0';
7: itsLen=0;
8: }
9:
10: String::String(const char *rhs)
11: {
12: itsLen = strlen(rhs);
13: itsCString = new char[itsLen+1];
14: strcpy(itsCString,rhs);
15: }
16:
17: String::String (const char *rhs, int length)
18: {
19: itsLen = strlen(rhs);
20: if (length < itsLen)
21: itsLen = length; // max size = length
22: itsCString = new char[itsLen+1];
23: memcpy(itsCString,rhs,itsLen);
24: itsCString[itsLen] = '\0';
25: }
26:
27: // copy constructor
28: String::String (const String & rhs)
29: {
30: itsLen=rhs.GetLength();
31: itsCString = new char[itsLen+1];
32: memcpy(itsCString,rhs.GetString(),itsLen);
33: itsCString[rhs.itsLen]='\0';
34: }
35:
36: String::~String ()
37: {
38: Clear();
39: }
40:
41: void String::Clear()
42: {
43: delete [] itsCString;
44: itsLen = 0;
45: }
46:
47: //non constant offset operator
48: char & String::operator[](int offset)
49: {
50: if (offset > itsLen)
51: {
52: // throw xOutOfBounds();
53: return itsCString[itsLen-1];
54: }
55: else
56: return itsCString[offset];
57: }
58:
59: // constant offset operator
60: char String::operator[](int offset) const
61: {
62: if (offset > itsLen)
63: {
64: // throw xOutOfBounds();
65: return itsCString[itsLen-1];
66: }
67: else
68: return itsCString[offset];
69: }
70:
71: // operator equals
72: const String& String::operator=(const String & rhs)
73: {
74: if (this == &rhs)
75: return *this;
76: delete [] itsCString;
77: itsLen=rhs.GetLength();
78: itsCString = new char[itsLen+1];
79: memcpy(itsCString,rhs.GetString(),itsLen);
80: itsCString[rhs.itsLen]='\0';
81: return *this;
82: }
83:
84: const String& String::operator=(const char * rhs)
85: {
86: delete [] itsCString;
87: itsLen=strlen(rhs);
88: itsCString = new char[itsLen+1];
89: memcpy(itsCString,rhs,itsLen);
90: itsCString[itsLen]='\0';
91: return *this;
92: }
93:
94:
95: // changes current string, returns nothing
96: void String::operator+=(const String& rhs)
97: {
98: unsigned short rhsLen = rhs.GetLength();
99: unsigned short totalLen = itsLen + rhsLen;
100: char *temp = new char[totalLen+1];
101: for (int i = 0; i<itsLen; i++)
102: temp[i] = itsCString[i];
103: for (int j = 0; j<rhsLen; j++, i++)
104: temp[i] = rhs[j];
105: temp[totalLen]='\0';
106: *this = temp;
107: delete temp;
108: }
109:
110: int String::StringCompare(const String& rhs) const
111: {
112: return strcmp(itsCString, rhs.GetString());
113: }
114:
115: String String::operator+(const String& rhs)
116: {
117:
118: char * newCString = new char[GetLength() + rhs.GetLength() + 1];
119: strcpy(newCString,GetString());
120: strcat(newCString,rhs.GetString());
121: String newString(newCString);
122: return newString;
123: }
124:
125:
126: String String::operator+(const char* rhs)
127: {
128:
129: char * newCString = new char[GetLength() + strlen(rhs)+ 1];
130: strcpy(newCString,GetString());
131: strcat(newCString,rhs);
132: String newString(newCString);
133: return newString;
134: }
135:
136:
137: String String::operator+(char rhs)
138: {
139: int oldLen = GetLength();
140: char * newCString = new char[oldLen + 2];
141: strcpy(newCString,GetString());
142: newCString[oldLen] = rhs;
143: newCString[oldLen+1] = '\0';
144: String newString(newCString);
145: return newString;
146: }
147:
148:
149:
150: int String::operator==(const String& rhs) const
151: { return (StringCompare(rhs) == 0); }
152: int String::operator!=(const String& rhs)const
153: { return (StringCompare(rhs) != 0); }
154: int String::operator<(const String& rhs)const
155: { return StringCompare(rhs) < 0; }
156: int String::operator>(const String& rhs)const
157: { return (StringCompare(rhs) > 0); }
158: int String::operator<=(const String& rhs)const
159: { return (StringCompare(rhs) <= 0); }
160: int String::operator>=(const String& rhs)const
161: { return (StringCompare(rhs) >= 0); }
162:
163: ostream& operator<< (ostream& ostr, const String& str)
164: {
165: ostr << str.itsCString;
166: return ostr;
167: }
Output:
None.
Analysis:
Listing 3.2 provides the implementation for the String class. The default constructor in lines 5 through 11 initializes itsString to zero length and itsLen to zero.
The second constructor takes a C-style string, sets itsLen to the length of that string, and then allocates memory for itsString. Finally, the contents of the C-style string are copied into itsString.
The third constructor is much like the first, except that strncpy() is used, setting a maximum size of the new itsString member variable. Note that itsLen is set to the actual size of the new string, because that may be smaller than the length parameter. This member function might be called with String("hello", 20), for example. Even though the maximum length of the new String is set to 20, only 5 bytes are required.
The copy constructor is implemented in lines 31 through 39. Note that each character of the old string is copied to the corresponding character of the new string, and then the string is null terminated. Memcpy is used for greater speed and efficiency.
The destructor (lines 36 through 38) calls Clear() (lines 44 through 48), which deletes the space allocated for the itsString, and sets itsLen to zero.
The String class overrides the offset operator ([]) to allow its clients ready access to the individual characters of the string. Some clients will want to be able to modify a single character, using the array accessor as an l-value in expressions such as myString[5]='*';. Other clients will want to access the character as an R-Value (char theChar = myString[5];, for example).
Two versions of the accessor thus are supplied. The first, in lines 50 through 60, returns a nonconstant reference to the character. The second, in lines 62 through 72, returns a character by value; the method itself therefore is const.
Note that because a character is small (no larger than four bytes, and often only one) there is no advantage to returning a const char &. You could do so, but you don't gain anything, and returning by value is simpler.
Because the String class allocates and manages dynamic memory (the pointer to the character array), it requires a copy constructor (lines 32 through 39) and operator equals (lines 87 through 96). The latter is overloaded on lines 90 through 99 to allow assignment to a String from a const character array.
The (private) StringCompare() function (lines 112 through 118) examines the current string against a second string by passing their internal strings to the standard library strncmp. This method acts as an interface between the user-defined String class and the standard string library function, and is used by the various comparison operators on lines 121 through 137.
Finally, in lines 139 through 143, a non-member insertion operator (<<) is defined that inserts a String object into a Stream buffer.
Listing 3.3 provides a simple driver program to exercise some of the String class functionality.
Listing 3.3 Using a Driver Program to Exercise the String Class
1: // Listing 3.3 - Using a Driver Program to Exercise the String Class
2:
3: #include "string.hpp"
4: #include <iostream.h>
5: void main()
6: {
7: char buffer[255];
8: String helloStr("Hello");
9: String worldStr(" world");
10: cout << helloStr << endl;
11: cout << worldStr << endl;
12: helloStr+=worldStr;
13: cout << helloStr << endl;
14:
15: String t1 = worldStr + worldStr;
16: String t2 = worldStr + " series";
17: String t3 = worldStr + '!';
18:
19: cout << "t1: " << t1 << endl;
20: cout << "t2: " << t2 << endl;
21: cout << "t3: " << t3 << endl;
22:
23: cout << "\nEnter string 1: ";
24: cin >> buffer;
25: String S1(buffer);
26: cout << "Enter string 2: ";
27: cin >> buffer;
28: String S2(buffer);
29: cout << "\n";
30: if (S1 < S2)
31: cout << "S1 is less" << endl;
32: else if ( S1 == S2)
33: cout << "They are the same!" << endl;
34: else
35: cout << "S1 is greater" << endl;
36: try // if your compiler doesn't support templates, comment this out
37: {
38: char theChar = S1[(int)3];
39: cout << "The fourth character of S1 is " << theChar << endl;
40: }
41: catch(...) // if your compiler doesn't support templates, comment this
out
42: {
43: cout << "Unable to display the fourth character!" << endl;
44: }
45: }
Output:
Hello
world
Hello world
t1: world world
t2: world series
t3: world!
Enter string 1: this
Enter string 2: thin
S1 is greater
The fourth character of S1 is s
Note: If your compiler does not support exceptions, change lines 36 through 44 to the following:
36: if (strlen(S1) >= 4)
37: {
38: char theChar = S1[3];
39: cout << "The fourth character of S1 is " << theChar << endl;
40: }
41: else
42: {
43: cout << "Unable to display the fourth character!" << endl;
44: }
Analysis:
In lines 8 and 9, Strings helloStr and worldStr are created and then concatenated and printed. In lines 15 through 17, three temporary strings are created to exercise the overloaded addition operator, and then are printed in lines 19 through 21.
The user is prompted for two words in lines 23 and 24--in this case, this and thin--and the words are compared. Because this ends with s and thin ends with n, and because s is later in the alphabet, this is considered to be "greater" than thin.
Finally, the fourth character (s) is accessed using the offset operator ([]).
DO put the declaration in a header file (.hpp).
DO put the definition in an implementation file.
DO get all the essential functionality into the class.
DON'T assume that you must provide every imaginable function for the class even before you need it.
Now that you have a good, working String class with which to build your notes and other objects in ROBIN, it is time to turn your attention to issues of data management. Over time, you will need to create an entire database of notes, which are indexed and storable on disk. The next few days will introduce many of the concepts and classes you will need for this project, but today you will start by examining how data can be managed and manipulated in memory.
A linked list is one way to implement a dynamic array of objects. The significant limitation of arrays is that you must decide, at compile time, how many objects you will hold in the array. But what if you don't know? You have only two choices with an array: you can take a reasonable guess and risk running out of room, or you can create a very large array and risk wasting a lot of memory.
A linked list provides much of the functionality of an array, but it enables you to size the list at run time, adding nodes (elements or members of the list) and removing them at will. Linked lists can be searched, sorted, and otherwise manipulated as needed. Simple linked lists, however, provide poor performance when quick access to an individual node is needed. During the next few days, you will explore more complex cousins of the linked list to overcome this limitation.
Figure 3.1 illustrates a simple, singly linked list. The list is singly linked because each node points only to the next node in the list, not to any other nodes.
Figure 3.1 A singly linked list.
Note: A linked list provides the functionality of an array without the restriction of having a fixed size. You can provide the best of both worlds by creating an Array class with Array syntax, which grows and shrinks as your needs change. To create such an array, store the data in a linked list.
You might be tempted to create a linked list of notes, and then perhaps another linked list of Strings, and so on. It quickly will become apparent, however, that linked lists are so fundamental that you will be using them in many different places. A template offers the flexibility you need, without significant overhead.
Creating a template always is easiest if you start with a well-debugged working example. You therefore will create a linked list of notes, get it working, and then parameterize it. Listing 3.4 provides the header for a linked list of notes. Listing 3.5 provides the implementation for the linked list, and listing 3.6 provides a simple driver program.
Listing 3.4 Declaring a Message, Node, and Linked List
1: // Listing 3.4 - Declaring a Message, Node, and Linked List
2:
3: #include <iostream.h>
4: #include "String.hpp" // string class
5:
6: typedef unsigned long ULONG;
7: typedef unsigned short USHORT;
8:
9: // minimal Note class
10: class Note
11: {
12: public:
13: Note(const String& text):
14: itsText(text), itsDate(0L)
15: {itsNoteNumber = theNoteNumber++;}
16: ~Note(){}
17: const String& GetText()const { return itsText; }
18: long GetDate() const { return itsDate; }
19: ULONG GetNoteNumber() const { return itsNoteNumber; }
20: int operator<(const Note& rhs) { return itsNoteNumber
< rhs.GetNoteNumber(); }
21: void Display() const
22: { cout << "Note #: " << itsNoteNumber;
23: cout << " Text: " << itsText << endl; }
24: static ULONG theNoteNumber;
25: private:
26: String itsText;
27: ULONG itsDate;
28: ULONG itsNoteNumber;
29: };
30:
31: // **************** Note Node class ************
32: class Node
33: {
34: public:
35: Node (Note*);
36: ~Node();
37: void InsertAfter(Node*);
38: Node * GetNext() { return itsNext; }
39: void SetNext(Node * next) { itsNext = next; }
40: Note * GetNote() const;
41: int operator<(const Node &rhs) {return itsNote < (rhs.GetNote());}
42:
43: private:
44:
45: Note *itsNote;
46: Node * itsNext;
47: };
48:
49:
50: // **************** Note List ************
51: class NoteList
52: {
53: public:
54: NoteList();
55: ~NoteList();
56: ULONG GetCount() const { return itsCount; }
57: void Insert(Note *);
58: void Iterate(void (Note::*f)()const) ;
59: Note* operator[](ULONG) ;
60: Note* FindNote(ULONG & NoteNumber ) ;
61:
62: private:
63: Node itsHead;
64: ULONG itsCount;
65: };
Output:
None. This is the class declaration.
Analysis:
The declarations begin, in lines 3 and 4, by including two necessary header files. The first, iostream.h, is provided by the compiler vendor and declares all the iostream objects. The second, String.hpp, is the header for the String class you built earlier.
In lines 9 through 29, a minimal Note class is declared. This provides a convenient object to store in your linked list. Each note object consists of a String, a date, and a unique identification number. For now, the date is stored as an unsigned long and is set to 0. This serves as a placeholder for information you will need in later versions of the Note object.
Each Note is numbered sequentially using a static member variable, theMsgNumber, which is incremented as each Message is instantiated.
The Note object is instantiated with a string representing the note the user wants to record. The body of the constructor (line 15) initializes the individual note's sequential number while incrementing the static counter.
The Display() member function prints the note number and the text of its String object to the console, taking advantage of the fact that the String class overloaded the insertion operator to allow writing String objects directly to cout.
Note that all member functions are declared inline; again this class exists, for now, only to provide an object to store in the lists.
A Node class is declared in lines 31 through 42 and, again, this is specific to the Note class. When you write the template version of this class later today, you will see how to generalize this type. For now, a Node class is constructed with a pointer to a Note and is responsible for pointing to the next Node in the list, as well as for returning the Note pointer on demand.
The NoteList is declared in lines 51 through 65. Each NoteList object consists of a Node object and a running count of all the Nodes in the list. The count, of course, could be computed as needed, but it is a small amount of data to store and doing so optimizes how quickly the class can return its count. Note that the contained Node does not hold data for the list; it provides a convenient entry point for accessing the other nodes in the list, thereby simplifying inserting new nodes and walking the list.
In line 58, the member function Iterate() is declared. This function is used to call any member function of the Note class that matches the appropriate signature (taking no parameters, returning void, and having a constant to this pointer). Iterate() is used to iterate over each Node in the list, calling the appropriate function in its Note object.
Listing 3.5 Implementing Note, Node, and List Classes
1: #include "0304.hpp"
2:
3: // Listing 3.5 - Implementing Note, Node, and List Classes
4:
5: // *** node implementations ****
6:
7: Node::Node(Note* pNote):
8: itsNote(pNote),
9: itsNext(0)
10: {}
11:
12: Node::~Node()
13: {
14: delete itsNote;
15: itsNote = 0;
16: delete itsNext;
17: itsNext = 0;
18: }
19:
20: void Node::InsertAfter(Node* newNode)
21: {
22: newNode->SetNext(itsNext);
23: itsNext=newNode;
24: }
25:
26: Note * Node::GetNote() const
27: {
28: if (itsNote)
29: return itsNote;
30: else
31: return NULL; //error
32: }
33:
34: // Implementations for Lists...
35:
36: NoteList::NoteList():
37: itsCount(0),
38: itsHead(0) // initialize head node to have no note
39: {}
40:
41: NoteList::~NoteList()
42: {
43: }
44:
45:
46: Note * NoteList::operator[](ULONG offSet)
47: {
48: Node* pNode = itsHead.GetNext();
49:
50: if (offSet+1 > itsCount)
51: return NULL; // error
52:
53: for (ULONG i=0;i<offSet; i++)
54: pNode = pNode->GetNext();
55:
56: return pNode->GetNote();
57: }
58:
59: Note* NoteList::FindNote(ULONG & NoteNumber )
60: {
61: for (Node * pNode = itsHead.GetNext();
62: pNode!=NULL;
63: pNode = pNode->GetNext()
64: )
65: {
66: if (pNode->GetNote()->GetNoteNumber() == NoteNumber)
67: break;
68: }
69: if (pNode == NULL)
70: return NULL;
71: else
72: return pNode->GetNote();
73: }
74:
75: void NoteList::Insert(Note* pNote)
76: {
77: Node * NewNode = new Node(pNote);
78: itsCount++;
79: for (Node * pNode = &itsHead;;pNode = pNode->GetNext())
80: {
81: if (pNode->GetNext() == NULL || *(pNode->GetNext()) < *NewNode)
82: {
83: pNode->InsertAfter(NewNode);
84: break;
85: }
86: }
87: }
88:
89: void NoteList::Iterate(void (Note::*func)()const)
90: {
91: for (Node* pNode = itsHead.GetNext();
92: pNode;
93: pNode=pNode->GetNext()
94: )
95: (pNode->GetNote()->*func)();
96:
97: }
Output:
None.
Analysis:
In line 3, the header file (as shown in the previous listing) is included. Lines 7 through 10 represent the very simple constructor for the Node class, and lines 12 through 18 show the destructor.
The implementation of InsertAfter() occurs in lines 20 through 24. This takes a pointer to a node and inserts it into the list after the current node.
The implementation for the linked list itself begins in line 34.
The insert method in lines 76 through 87 provides the capability to add a Note and have it inserted in the correct position based on the note's number.
Here's how it works: a new node is created in line 77 and initialized with the new note. The list's counter is incremented in line 79. A for loop is started, and a pointer is initialized to point to the itsHead member of the list. There is no test condition in the loop, and each time through the pointer pNode is reset to point to the next node in the list.
At each node point, a test is conducted in line 81. If there is no following node, or if the note attached to the following node has a higher number than the new note's number, the new note is inserted into the list. The actual insertion is accomplished by the node after which you are inserting the new node.
The accessor function ([]) shown in lines 46 through 57 returns the Note object associated with the Node at the offset provided. Note that if the offset is beyond the end of the list, no exception is thrown a Null pointer simply is returned. This is not considered an error in this case, and so there is no need for an exception. You might decide to implement your list so that this is considered an error, in which case you might throw an exception if there are no nodes in your list (line 51).
Note also that in this linked list, there is no way to jump directly to a given offset. Instead, you must walk the list, as shown in lines 53 and 54. This is a severe limitation of simple linked lists, and one that will be addressed in coming days when you learn about more complex data structures such as Trees.
The FindNote() function walks the list looking for a Note object in which the itsNumber member matches the number provided. This is accomplished by walking the list and asking each node to ask its associated note what its number is by calling GetNoteNumber() (line 66).
Finally, in lines 89 through 95, the member function NoteList::Iterate() is defined. This takes as its only parameter a pointer to a member function of class Note, which itself takes no parameters, is constant, and returns void. The Iterate() member function itself is constant as well. For every Node in the list, the member function pointed to by the parameter is invoked on the Note object held by the Node.
Listing 3.6 Using the Driver Program for the Linked List
1: // Listing 3.6 - Using the Driver Program for the Linked List
2:
3: #include "0304.hpp"
4: #include <stdlib.h>
5:
6: ULONG Note::theNoteNumber = 0;
7: void main()
8: {
9: NoteList pl;
10: Note * pNote = 0;
11: ULONG choice;
12: char buffer[256];
13:
14: while (1)
15: {
16: cout << "\n(0)Quit (1)Add Note ";
17: cin >> choice;
18: if (!choice)
19: break;
20:
21: cin.ignore(255,'\n');
22: cout << "\nText: ";
23: cin.getline(buffer,255);
24: pNote = new Note(buffer);
25: pl.Insert(pNote);
26: }
27:
28: cout << "\n\nResults: \n" << endl;
29: void (Note::*pFunc)()const = Note::Display;
30: pl.Iterate(pFunc);
31:
32: cin.ignore(255,'\n');
33: cout << "\nFind Note: ";
34: cin.getline(buffer,255);
35: ULONG position = atol(buffer);
36: pNote = pl.FindNote(position);
37: if (pNote)
38: cout << "\nFound! " << endl;
39: pNote->Display();
40: }
Output:
(0)Quit (1)Add Note 1
Text: Wash the car
(0)Quit (1)Add Note 1
Text: Write the next chapter
(0)Quit (1)Add Note 0
Results:
Note #: 0 Text: Wash the car
Note #: 1 Text: Write the next chapter
Find Note: 1
Found!
Note #: 1 Text: Write the next chapter
Analysis:
The driver program exists only to ensure that you have created a valid and working linked list. The program initializes the static member theNoteNumber in line 6, outside of the main() function, as required. It then, in line 9, instantiates a NoteList object.
The user repeatedly is prompted to enter a new note in the while loop in lines 14 through 26. Each time the user does create a new note, the user is prompted to enter the text. A new note then is created and inserted into the linked list.
The extraction operator (>>) is not used, because the user may want to enter a multiword note. The new line from the choice therefore is eaten in line 21, and getline is used to take the user's entire input into the character buffer that was declared in line 12.
In lines 28 through 30, the results are printed by assigning the Display() method of Note to the pointer to member function pFunc. This pointer then is passed to the Iterate() function of the linked list, and each member of the list is printed.
In line 33, the user is prompted to enter a number, and that note is retrieved. Remember that this list counts from zero, as an array would.
New Term: A node is an entry in a list. The node contains either the data for the list or a pointer to the data for the list, and it acts as an interface between the list and the objects contained in the list.
Now that you have a working list class, it is fairly straightforward to parameterize it by using templates. The goal is to be able to separate the Node and List concepts from the particular objects stored in each. Listing 3.7 provides the declarations of a Node and List template and their implementations, as well as a driver program that declares two simple classes designed to show the flexibility of the List template.
Listing 3.7 Using a Parameterized List Class
1: #include <iostream.h>
2: #include "String.hpp" // string class
3: #include <stdlib.h>
4:
5: typedef unsigned long ULONG;
6: typedef unsigned short USHORT;
7:
8: // minimal Note class
9: class Note
10: {
11: public:
12: Note(const String& text):
13: itsText(text), itsDate(0L)
14: {itsNoteNumber = theNoteNumber++;}
15: ~Note(){}
16:
17: const String& GetText()const { return itsText; }
18: long GetDate() const { return itsDate; }
19: ULONG GetNoteNumber() const { return itsNoteNumber; }
20:
21: int operator<(const Note& rhs)
22: { return itsNoteNumber < rhs.GetNoteNumber(); }
23: BOOL operator==(const Note& rhs)
24: {(BOOL)(return itsText == rhs.GetText()); }
25:
26: operator long() { return itsNoteNumber; }
27:
28: void Display() const
29: { cout << "Note #: " << itsNoteNumber;
30: cout << " Text: " << itsText << endl; }
31:
32: static ULONG theNoteNumber;
33: private:
34: String itsText;
35: ULONG itsDate;
36: ULONG itsNoteNumber;
37: };
38:
39:
40: // **************** Node class ************
41: template <class T>
42: class Node
43: {
44: public:
45: Node (T*);
46: ~Node();
47: void InsertAfter(Node *);
48: Node * GetNext() const { return itsNext; }
49: void SetNext(Node * next) { itsNext = next; }
50: T & GetObject() const { return *itsObject; }
51: BOOL operator<(const Node &rhs) const;
52: BOOL operator==(const T& rhs) const;
53:
54: private:
55: T * itsObject;
56: Node * itsNext;
57: };
58:
59: // **************** Object List ************
60: template <class T>
61: class List
62: {
63: public:
64: List();
65: ~List();
66: ULONG GetCount() const { return itsCount; }
67: void Insert(T &);
68: void Iterate(void (T::*f)()const);
69: T & operator[](ULONG);
70: T * FindObject(const T& target );
71:
72: private:
73: Node<T> itsHead;
74: ULONG itsCount;
75: };
76:
77: // *** node implementations ****
78:
79: template <class T>
80: Node<T>::Node(T * pObject):
81: itsObject(pObject),
82: itsNext(0)
83: {}
84:
85: template <class T>
86: Node<T>::~Node()
87: {
88: delete itsObject;
89: itsObject = 0;
90: delete itsNext;
91: itsNext = 0;
92: }
93:
94: template <class T>
95: void Node<T>::InsertAfter(Node* newNode)
96: {
97: newNode->SetNext(itsNext);
98: itsNext=newNode;
99: }
100:
101: template <class T>
102: BOOL Node<T>::operator<(const Node &rhs) const
103: {
104: return(BOOL)(*itsObject < rhs.GetObject());
105: }
106:
107: template <class T>
108: BOOL Node<T>::operator==(const T& target) const
109: {
110: return (BOOL)(*itsObject == target);
111: }
112:
113: // Implementations for Lists...
114:
115: template<class T>
116: List <T>::List():
117: itsCount(0),
118: itsHead(0) // initialize head node to have no Object
119: {}
120:
121: template<class T>
122: List <T>::~List()
123: {
124: }
125:
126: template<class T>
127: T & List<T>::operator[](ULONG offSet)
128: {
129: if (offSet+1 > itsCount)
130: return itsHead.GetObject(); // error
131:
132: Node<T>* pNode = itsHead.GetNext();
133:
134: for (ULONG i=0;i<offSet; i++)
135: pNode = pNode->GetNext();
136:
137: return pNode->GetObject();
138: }
139:
140: template<class T>
141: T* List<T>::FindObject(const T& target )
142: {
143: for (Node<T> * pNode = itsHead.GetNext();
144: pNode!=NULL;
145: pNode = pNode->GetNext()
146: )
147: {
148: if ( *pNode == target)
149: break;
150: }
151: if (pNode == NULL)
152: return 0;
153: else
154: return &(pNode->GetObject());
155: }
156:
157: template<class T>
158: void List<T>::Insert(T & Object)
159: {
160: Node<T> * NewNode = new Node<T>(&Object);
161:
162: for (Node<T> * pNode = &itsHead;;pNode = pNode->GetNext())
163: {
164: if (pNode->GetNext() == NULL || *NewNode < *(pNode->GetNext()) )
165: {
166: pNode->InsertAfter(NewNode);
167: itsCount++;
168: break;
169: }
170: }
171: }
172:
173: template<class T>
174: void List<T>::Iterate(void (T::*func)()const)
175: {
176: for (Node<T>* pNode = itsHead.GetNext();
177: pNode;
178: pNode=pNode->GetNext()
179: )
180: (pNode->GetObject().*func)();
181: }
182:
183: ULONG Note::theNoteNumber = 0;
184: void main()
185: {
186: List<Note> pl;
187: Note * pNote = 0;
188: ULONG choice;
189: char buffer[256];
190:
191: while (1)
192: {
193: cout << "\n(0)Quit (1)Add Note ";
194: cin >> choice;
195: if (!choice)
196: break;
197:
198: cin.ignore(255,'\n');
199: cout << "\nText: ";
200: cin.getline(buffer,255);
201: pNote = new Note(buffer);
202: pl.Insert(*pNote);
203: }
204:
205: cout << "\n\nResults: \n" << endl;
206: void (Note::*pFunc)()const = Note::Display;
207: pl.Iterate(pFunc);
208:
209: cin.ignore(255,'\n');
210: cout << "\nFind Note with text: ";
211: cin.getline(buffer,255);
212: Note target(buffer);
213: pNote=0;
214: pNote = pl.FindObject(target);
215: if (pNote)
216: {
217: cout << "\nFound! " << endl;
218: pNote->Display();
219: }
220: else
221: cout << "Note not found." << endl;
222: }
Output:
(0)Quit (1)Add Note 1
Text: Walk the walk
(0)Quit (1)Add Note 1
Text: Talk the talk
(0)Quit (1)Add Note 0
Results:
Note #: 0 Text: Walk the walk
Note #: 1 Text: Talk the talk
Find Note with text: Talk the talk
Found!
Note #: 1 Text: Talk the talk
The implementation for the Node and List classes is similar to the previous example. Because the list was undergoing parameterization, a few additional changes were made to allow the list to be used with a wide variety of objects.
Analysis:
In listing 3.6, matches are made based on a specific characteristic of notes (the note number). In listing 3.7, for the more generalized template, matches are made on the basis of the overloaded operator==() in the object itself.
In lines 23 and 24, the Note implements its new operator==(), which allows the List to compare two Note objects. This is critical to building a generalized List class; other objects now can be stored in this type of list if they implement both operator<() and operator==().
The Node class also implements operator<() and operator==(), and this time is careful not to make these inline, because the client may need to override these templates with specific functions for some instances of Node.
The FindObject() method of List, in line 70, changes to take a reference to the parameterized type object, so that the object itself can determine an accurate match on any particular characteristic of that object.
Note that the implementation of Node's overloaded operators (lines 111 through 121) pass on the comparison and equate operations to the objects themselves. Also, carefully note that the decision on when to use references and when to use pointers now is made with more consistency; use pointers when the pointer might be null otherwise, use references.
Today you learned how to create a String object to allow flexible handling of text. You also learned how to create a simple linked list and to manipulate the nodes in the list. Finally, you reviewed creating a template based on a well-tested existing class; in this case, the linked list was parameterized to hold any object that can be treated as a ULONG.
Q: Is this the final design for the String class?
A: The goal of a good early design is to provide a nearly-complete class. As work on your program continues, other functionality may be added, but the more complete the early design, the better. A weak, early class exposes you to the danger that you will have to go back and rework early code as your design changes.
Q: Why bother having a String class? Why not use C-style strings?
A: The String class protects the user from several bugs that are common even to experienced programmers, such as forgetting to allocate space for the trailing NULL, and writing past the end of the buffer.
Q: What else does the String class provide that C-style strings don't provide?
A: With a user-defined class such as String, you can add useful operators such as operator+ for concatenation and operator< for alphabetization.
Q: Why did you first write the List class without making it a template, instead of just making a template?
A: Debugging a Template class is much harder than debugging a simple class, and many debuggers don't support templates at all. After you have a specific example of a class, making a template out of it is relatively straightforward.
Q: Why was the entire node object included inside the list, rather than just including a pointer to the first node in the list?
A: Including the node simplifies the insertion and removal code. Without the included node, you would have to include special handling for insertions before the first node, and insertions into an empty list.
The Workshop provides quiz questions to help you solidify your understanding of the material covered, and exercises to provide you with experience in using what you have learned. Try to answer the quiz and exercise questions before checking the answers in Appendix A, and make sure that you understand the answers before continuing to the next chapter.
Go to: Table of Contents | Next Page