C++ From Scratch

Contents


8

Using Polymorphism


In this Chapter

The linked list class works, but it cries out for a bit of improvement. Each node in the list is forever checking to see whether there is a next node in the list before taking action:

void Node::Insert(char theChar)
{
     if ( ! nextNode )
          nextNode = new Node(theChar);
     else
          nextNode->Insert(theChar);
}

This creates code that is a bit more difficult to maintain. As an object-oriented designer, I notice that I'm asking each node to be capable of being the head node in the list, an internal node in the list, or the tail of the list. There is nothing special about these positions--they are just nodes.

Because any node can be internal or the tail, it can't know whether it has a next node, so it must test. If a node knew that it was an internal node, it would always know that there was a next node ("If I'm not the tail, there must be at least one after me"). If it knew that it was the tail, it would know there was no next node (such is the meaning of being the tail node; objects live a very existential existence, and they often major in epistemology).

Specialization

This leads me to a redesign. In it, I have three types of nodes: One is the head node, one is the tail, and the third is the internal node.

You've already seen that the LinkedList class you created can mark the head node position, and that this class has special responsibilities such as supporting an offset operator. Let's break out the InternalNode from the TailNode.

When we say that the LinkedList, InternalNode, and TailNode are all nodes, this tells us that we are thinking about a specialization/generalization relationship. The LinkedList, InternalNode, and TailNode are specializations of Node. The LinkedList has the special requirement that it act as an interface to the list, which leads me to the design shown in Figure 8.1

Figure 8.1 Node Specialization.

In this design, shown here in UML notation, we indicate that the LinkedList, InternalNode, and TailNode are all kinds of Node. This brings us back to the conversation about specialization/generalization in Chapter 1, "Introduction."

The specialization relationship establishes an is-a relationship: That is, a TailNode is-a Node. Furthermore, the specialization relationship indicates that TailNode adds to the definition of Node. It says that this is a special kind of Node--one that marks the end of a list.

Similarly, InternalNode specializes Node to mean a node that manages associated data and that, by implication, does not mark the tail of the list.

Finally, LinkedList is-a node, a very special node that marks the head of the list and that provides an interface to users of the list. We could have called this the head node, but we want to focus on the user's perception: To the user, the head node is the linked list. Thus, we bridge the gap between the architect's view (in which this is the head node in a linked list) and the user's view (in which this is the linked list) by having it inherit from Node but calling it LinkedList.


NOTE: The specialization/generalization relationship is reciprocal. Because LinkedList, TailNode, and InternalNode specialize Node, Node in turn becomes a generalization of the commonality between all three of these classes. Programmers talk about factoring out common features from the derived classes up into the base classes. Thus, you can factor out all the common responsibilities of the three classes up into Node.


Benefits from Specialization

The first benefit you receive from this design is that Node can serve to hold the common characteristics of LinkedList, InternalNode, and TailNode. The things they have in common in this design are that any Node can exist in a list, that you can tell any Node to insert a new data object, and that you can tell a Node to display itself.

In addition, by specializing Node, this design of TailNode maintains the Node features but adds the special capability to mark the end of the list. This specialization is manifest in the differences in how TailNode responds to a request to Insert data, which it handles differently than, for example, an InternalNod e does.

Polymorphism

The need to handle Insert() in a special way might be a good reason to create a new class, but you can imagine that it would make your code much more complicated. Each Node would have to know what it pointed to: If it pointed to an InternalNode, it would call InternalNodeInsert, and if it pointed to a TailNode, it would call TailNodeInsert. What a bother.

We want to say, "I have a Node, I don't know what kind. It might be an InternalNode or it might be a TailNode. When I call Insert(), I want my Node to act one way if it is an InternalNode, and in a different way if it is a TailNode."

This is called polymorphism: poly means many and morph means form. We want the Node to take on many forms. C++ supports polymorphism, which means that the client can call Insert on the Node and the compiler will take care of making the right thing happen. In this case, the right thing means that if the Node is really an InternalNode, InternalNode::Insert() will be called; if the Node is really a TailNode, TailNode::Insert() will be called instead.

Abstract Data Types

You want to create InternalNode objects to hold your data, and you want to create a single TailNode object and a single LinkedList object. You will never instantiate a Node object, though. The Node object exists only as an abstraction so that you can say "I will call the next node," and not worry about which kind of node it is. The Node class is called an abstract data type (ADT) because it exists only to provide an abstraction for the classes that inherit from it.

The classes that are derived from your ADT (in this case, LinkedList, InternalNode, and TailNode) can be concrete, and thus can have objects instantiated. Alternatively, you can derive ADTs from other ADTs. Ultimately, however, you must derive a concrete class so that you can create objects.


Abstract Data Type--A class that provides a common interface to a number of classes that derive from it. You can never instantiate an Abstract Data Type.

concrete class--A class that is not abstract and that can therefore be instantiated.


How This Is Implemented in C++

Until now, we've not discussed a word about how all this is implemented in C++. That is because we have rightly been focused on design, not implementation.

The design calls for all three of these classes to specialize Node. You implement that design concept of specialization by using inheritance. Thus, you will have LinkedList, TailNode, and InternalNode inherit from Node.

The Syntax of Inheritance

When you declare a class, you can indicate the class from which it derives by writing a colon after the class name, the type of derivation (public or otherwise), and the class from which it derives. For now, focus only on public inheritance because that is what implements the design concept of specialization/generalization.

Thus, to indicate that InternalNode is a specialization of Node, or that InternalNode derives from Node, you write

class InternalNode : public Node

NOTE: When one class specializes another, we say that the specialized class is derived from the more general class, and that the more general class is the base class.


The class from which you derive must have been declared already, or you receive a compiler error.

Overriding Functions

A LinkedList object has access to all the member functions in class Node, as well as to any member functions the declaration of the LinkedList class might add. It can also override a base class function. Overriding a function means changing the implementation of a base class function in a derived class. When you instantiate an object of the derived class and call an overridden method, the right thing happens.


NOTE: When a derived class creates a function with the same return type and signature as a member function in the base class, but with a new implementation, it is said to override that method.


This is very handy because it allows an InternalNode to specialize how it handles some methods (such as Insert()) and simply inherit the implementation of other methods.

When you override a function, its signature must be identical to the signature of the function in the base class. The signature is the function prototype, other than the return type: the name, the parameter list, and the keyword const (if it is used).

Virtual Methods

I have emphasized the fact that an InternalNode object is-a Node object. So far that has meant only that the InternalNode object has inherited the attributes (data) and capabilities (methods) of its base class. In C++, however, the is-a relationship runs deeper than that.

C++ extends its polymorphism, allowing pointers to base classes to be assigned to derived class objects. Thus, you can write

Node * pNode = new InternalNode;

This creates a new InternalNode object on the heap and returns a pointer to that object, which it assigns to a pointer to Node. This is fine because an InternalNode is-a Node.

In fact, this is the key to polymorphism. You can create all kinds of Windows--they can each have a draw() method that does something different (the list box draws a rectangle, the radio button draws a circle). You can create a pointer to a Window without regard to what type of Window you have, and when you call

pWindow->Draw();

the Window is drawn properly.

Similarly, you can have a pointer to any kind of Node, a LinkedList, an InternalNode, or a TailNode, and you can call Insert() on that node without regard to what kind of Node it is. The right thing will happen.

Here's how it works: You use the pointer to invoke a method on Node, for example Insert(). If the pointer is really pointing to a TailNode, and if TailNode has overridden Insert(), the overridden version of Insert is called. If TailNode does not override Insert(), it inherits this method from its base class, Node, and Node::Insert() is called.

This is accomplished through the magic of virtual functions.


NOTE: C++ programmers use the terms method and function interchangeably. This confusion comes from the fact that C++ has two parents: the object-oriented languages such as SmallTalk, which use the term method, and C, which uses the term function.


How Virtual Functions Work

When a derived object, such as an InternalNode object, is created, first the constructor for the base class is called, and then the constructor for the derived class is called. Figure 8.2 shows how the InternalNode object looks after it is created. Note that the Node part of the object is contiguous in memory with the InternalNode part.

Figure 8.2 The InternalNode object after it is created.

When a virtual function is created in an object, the object must keep track of that function. Many compilers build a virtual function table, called a v-table. One of these tables is kept for each type, and each object of that type keeps a virtual table pointer (called a vptr or v-pointer) that points to that table. (Although implementations vary, all compilers must accomplish the same thing, so you won't be too wrong with this description.)


v-table--The virtual function table used to achieve polymorphism

vptr or v-pointer--The Virtual Function Table Pointer, which is provided for every object from a class with at least one virtual method


Each object's vptr points to the v-table that, in turn, has a pointer to each of the virtual functions. When the Node part of the InternalNode is created, the vptr is initialized to point to the correct part of the v-table, as shown in Figure 8.3.

Figure 8.3 The v-table of a node.

When the InternalNode constructor is called and the InternalNode part of this object is added, the vptr is adjusted to point to the virtual function overrides (if any) in the InternalNode object (see Figure 8.4).

Figure 8.4 The v-table of a InternalNode.

When a pointer to a Node is used, the vptr continues to point to the correct function, depending on the "real" type of the object. Thus, when Insert() is invoked, the correct (InternalNode) version of the function is invoked.

Virtual Destructors

It is legal and common to pass a pointer to a derived object when a pointer to a base object is expected. What happens when that pointer to a derived subject is deleted? If the destructor is virtual, as it should be, the right thing happens: The derived class's destructor is called. Because the derived class's destructor automatically invokes the base class's destructor, the entire object is properly destroyed.

The rule of thumb is this: If any of the functions in your class are virtual, the destructor needs to be virtual as well.

The ANSI/ISO standard dictates that you can vary the return type, but few compilers support this. If you change the signature--the name, number, or type of parameters or whether the method is const--you are not overriding the method, you are adding a new method.

It is important to note that if you add a new method with the same name as another method in the base class, you hide the base class method and the client can't get to it. Take a look at Listing 8.1, which illustrates this point.

Listing 8.1 Hiding the Base Class Method

0:  #include <iostream>
1:  using namespace std;
2:  
3:  class Base
4:  {
5:  public:
6:      Base() { cout << "Base constructor\n"; }
7:      virtual ~Base() { cout << "Base destructor\n"; }
8:      virtual void MethodOne() { cout << "Base MethodOne\n"; }
9:      virtual void MethodTwo() { cout << "Base MethodTwo\n"; }
10:      virtual void MethodThree() 
11:          { cout << "Base MethodThree\n"; }
12:  private:
13:  };
14:  
15:  class Derived : public Base
16:  {
17:  public:
18:      Derived() { cout << "Derived constructor\n"; }
19:      virtual ~Derived() { cout << "Derived destructor\n"; }
20:      virtual void MethodOne() { cout << "Derived MethodOne\n"; }
21:      virtual void MethodTwo() { cout << "Derived MethodTwo\n"; }
22:      virtual void MethodThree(int myParam) 
23:          { cout << "Derived MethodThree\n"; }
24:  private:
25:  };
26:  
27:  int main()
28:  {
29:  
30:      Base * pb = new Base;
31:      pb->MethodOne();
32:      pb->MethodTwo();
33:      pb->MethodThree();  
34:  //    pb->MethodThree(5);  
35:      delete pb;
36:      cout << endl;
37:  
38:      Base * pbd = new Derived;
39:      pbd->MethodOne();
40:      pbd->MethodTwo();
41:      pbd->MethodThree();   
42:  //    pbd->MethodThree(5);  
43:      delete pbd;
44:      cout << endl;
45:  
46:      Derived * pd = new Derived;
47:      pd->MethodOne();
48:      pd->MethodTwo();   
49:  //    pd->MethodThree();    
50:      pd->MethodThree(5);  
51:      delete pd;
52:  
53:      return 0;
54:  }
Base constructor
Base MethodOne
Base MethodTwo
Base MethodThree
Base destructor
Base constructor
Derived constructor
Derived MethodOne
Derived MethodTwo
Base MethodThree
Derived destructor
Base destructor
Base constructor
Derived constructor
Derived MethodOne
Derived MethodTwo
Derived MethodThree
Derived destructor
Base destructor

In this example, we create a Base class and a Derived class. The Base class declares three methods virtual on lines 8-10, which will be overridden in the Derived class.

The overridden MethodThree differs from the base class's version in that it takes an extra parameter. This overloads the method (rather than overrides it) and hides the base class method. What is the effect? Let's see.

On line 30 we declare a pointer to a Base object, and we use this pointer to invoke MethodOne, MethodTwo, and both versions of MethodThree. The second, shown on line 34, won't compile and so is commented out. It won't compile because Base objects know nothing about this overload version.

The output shows that a Base constructor is called, followed by the three Base methods, ending with a call to the Base destructor. Pretty much as we might expect.

On line 38 we declare a pointer to a Base and initialize it with a Derived. This is the polymorphic form: We assign a specialized object to a pointer to a more general object. We call MethodOne, MethodTwo, and MethodThree, and they compile fine until we try to compile the version that takes an int. Because this is a pointer to a Base, it can't find this method and won't compile.

Let's look at the output. We see the Base constructor, and then the Derived constructor. That is how derived objects are constructed: base first. We then see a call to the Derived MethodOne. Polymorphism works! Here we have a Base pointer, but because we assigned a Derived object to it, when we call a virtual method, the right method is called. This is followed by a call to Derived MethodTwo, and then to Base MethodThree! As far as the Base pointer is concerned, Base MethodThree has not been overridden, so Derived inherits the Base method. Finally, the object is destroyed in the reverse order in which it was created.

The final set of code begins on line 46, where we create a Derived Pointer and initialize it with a Derived object. This time we can't call the version of MethodThree that was declared in Base because our new Derived object hides it. This proves the rule: If you overload a base class in the derived class, you must explicitly implement every version of the method (in this case you'd have to implement the version with no parameters) in the derived class, or it is hidden from your derived objects.

The output reflects the fact that this Derived object calls (of course) only derived methods.

To avoid the hiding, we can move the version of the method that takes an integer up into Base, or at a minimum we can implement the version with no parameters in the derived class. If we choose the first option, we can use both methods polymorphically. If we choose the latter, at least we can access the base method using a derived object.

We can, actually, overcome many of these problems with a bit more magic. Let's take them in turn. To solve the first problem (shown on line 34), we have only to overload MethodThree in Base:

3:  class Base
4:  {
5:  public:
6:      Base() { cout << "Base constructor\n"; }
7:      virtual ~Base() { cout << "Base destructor\n"; }
8:      virtual void MethodOne() { cout << "Base MethodOne\n"; }
9:      virtual void MethodTwo() { cout << "Base MethodTwo\n"; }
10:      virtual void MethodThree() 
11:          { cout << "Base MethodThree\n"; }
        virtual void MethodThree(int param)
               { cout << "Base MethodThree(int)\n"; }
12:  private:
13:  };

To solve the problem on lines 42 and 49, we need only invoke the base class's method directly:

42:  //    pbd->Base::MethodThree(5);  

Here we use the Base class name, followed by the scoping operator (::), to invoke the Base version of this method. Hey! Presto! Now we've "unhidden" it, and we can call it.

Implementing Polymorphism

All this is fine in theory, but it remains highly abstract until you see it implemented in code. Let's take a look at the implementation of the newly object-oriented LinkedList (see Listing 8.2).

Listing 8.2 LinkedList

0:  #ifndef LINKEDLIST_H
1:  #define LINKEDLIST_H
2:  
3:  #include "DefinedValues.h"
4:  
5:  class Node  // abstract data type
6:  {
7:  public:
8:       Node(){}
9:       virtual ~Node() {}
10:       virtual void Display() const { }
11:       virtual int HowMany(char c) const = 0;
12:       virtual Node * Insert(char theCharacter) = 0;
13:       virtual char operator[](int offset) = 0;
14:  private:
15:  };
16:  
17:  class InternalNode: public Node
18:  {
19:  public:
20:       InternalNode(char theCharacter, Node * next);
21:       virtual ~InternalNode();
22:       virtual void Display() const;
23:       virtual int HowMany(char c) const;
24:       virtual Node * Insert(char theCharacter);
25:       virtual char operator[](int offset);
26:  
27:  private:
28:       char myChar; 
29:       Node * nextNode;
30:  };
31:  
32:  class TailNode : public Node
33:  {
34:  public:
35:       TailNode(){}
36:       virtual ~TailNode(){}
37:       virtual int HowMany(char c) const;
38:       virtual Node * Insert(char theCharacter);
39:       virtual char operator[](int offset);
40:  
41:  private:
42:  
43:  };
44:  
45:  class LinkedList : public Node
46:  {
47:  public:
48:       LinkedList();
49:       virtual ~LinkedList();
50:       virtual void Display() const;
51:       virtual int HowMany(char c) const;
52:       virtual char operator[](int offset);
53:  
54:       bool Add(char c);
55:       void SetDuplicates(bool dupes);
56:  
57:  private:
58:       Node * Insert(char c);
59:       bool duplicates;
60:       Node * nextNode;
61:  };
62:  
63: #endif 

This analysis begins on line 5 with the declaration of the Node class. Note that all the methods, with the exception of the constructor, are virtual.

Constructors cannot be virtual; destructors need to be virtual if any method is virtual; and I've made the rest of the methods virtual because I expect that they can be overridden in at least some of the derived classes.

Note that the first three methods--the constructor, the destructor, and Display()--all have inline implementations that do nothing. HowMany() (line 11), however, does not have an inline implementation. If you check Listing 8.2, which has the implementation for the classes that are declared in Listing 8.1, you will not find an implementation for Node::HowMany().

That is because Node::HowMany() is declared to be a pure virtual function by virtue of the designation at the end of the declaration, = 0. This indicates to the compiler that this method must be overridden in the derived class. In fact, it is the presence of one or more pure virtual functions in your class declaration that creates an ADT. To recap: In C++, an abstract data type is created by declaring one or more pure virtual functions in the class.


Pure Virtual Function--A member function that must be overridden in the derived class, and which makes the class in which it is declared an Abstract Data Type. You create a pure virtual function by adding = 0 to the function declaration.


The Node class is, therefore, an ADT from which you derive the concrete nodes you'll instantiate in the program. Every one of these concrete types must override the HowMany() and Insert() methods, as well as the offset operator. If a derived type fails to override even one of these methods, it too is abstract, and no objects can be instantiated from it.

On line 17, you see the declaration of the InternalNode class, which derives from Node. As you can see on lines 23-25, this class does override the three pure virtual functions of Node; thus, this is a concrete class from which you can instantiate objects.

Although we put the keyword virtual on lines 22-25, it is not necessary. When a method is virtual, it remains virtual all the way down the hierarchy of derived classes. So we could have left this designation out here, as we did on line 21.

InternalNode adds two private variables: myChar and nextNode. It is clear why myChar can't be in Node: Only InternalNode classes have a character for which they are responsible. Why not put nextNode up in the base class, then? After all, nodes exist in a linked list. You'd expect all nodes to have a nextNode.

This is true of all nodes except for TailNode. Because TailNode does not have a nextNode, it doesn't make sense for this attribute to be in the base class.

You can put this pointer in the base and then give TailNode a null nextNode pointer. That might work, but it doesn't map to the semantics of a Node. A Node is an object that lives in a linked list. It is not part of our definition that a Node must point to another Node, only that it must be in the list. TailNodes are in the list, but they don't point to a nextNode. Thus, this pointer is not an intrinsic aspect of a Node, so I've left it out of the base class.

The declaration for TailNode begins on line 32, and once again you can see that the pure virtual functions are overridden. The distinguishing characteristics of TailNode are shown in the implementation of these methods, which we'll consider in a moment.

Finally, on line 45 you see LinkedList declared. Again, the pure virtual methods are overridden, but this time, on lines 54 and 55, you see new public methods: Add and SetDuplicates. These methods support the functionality of this class, to provide an interface for the LinkedList to the client classes.

Note also that on line 58 we've moved Insert() to the private section of LinkedList. The only Node class that any non-Node interacts with is this one, and Insert is not part of the LinkedList class's public interface. When a client wants to add a character to the list, it calls LinkedList::Add(), which is shown on line 54.

Node's Insert() method is public, however--when nodes interact with one another (for example, when LinkedList is adding objects to an InternalNode), the InsertMethod is used.

Let's look at the implementation of LinkedList in Listing 8.3, adding Game in Listings 8.4 and 8.5, and the driver program Decryptix! in Listing 8.6. This enables us to step through a few methods using the new object-oriented linked list.

Listing 8.3 Linked List Implementation

0:  #include "LinkedList.h"
1:  
2:  InternalNode::InternalNode(char theCharacter, Node * next):
3:  myChar(theCharacter),nextNode(next)
4:  {
5:  }
6:  
7:  InternalNode::~InternalNode() 
8:  { 
9:       delete nextNode;  
10:  }
11:  
12:  void InternalNode::Display() const 
13:  { 
14:       cout << myChar; nextNode->Display(); 
15:  } 
16:  
17:  int InternalNode::HowMany(char theChar) const
18:  {
19:       int myCount = 0;
20:       if ( myChar == theChar )
21:            myCount++;
22:       return myCount + nextNode->HowMany(theChar);
23:  }
24:  
25:  Node * InternalNode::Insert(char theCharacter)
26:  {
27:       nextNode = nextNode->Insert(theCharacter);
28:       return this;
29:  }
30:  
31:  char InternalNode::operator[](int offSet) 
32:  {
33:       if ( offSet == 0 )
34:            return myChar;
35:       else
36:            return (*nextNode)[--offSet];
37:  }
38:  
39:       
40:  int TailNode::HowMany(char theChar) const 
41:  { 
42:       return 0; 
43:  }
44:  
45:  Node * TailNode::Insert(char theChar)
46:  {
47:       return new InternalNode(theChar, this);
48:  }
49:  
50:  char TailNode::operator[](int offset) 
51:  { 
52:       ASSERT(false); 
53:       return ' '; 
54:  }
55:  
56:  
57:  
58:  LinkedList::LinkedList():
59:  duplicates(true)
60:  {
61:       nextNode = new TailNode;
62:  }
63:  
64:  LinkedList::~LinkedList() 
65:  { 
66:       delete nextNode; 
67:  }
68:  
69:  void LinkedList::Display() const 
70:  { 
71:       nextNode->Display(); 
72:  }
73:  
74:  int LinkedList::HowMany(char theChar) const
75:  {
76:       return nextNode->HowMany(theChar);
77:  }
78:  
79:  Node * LinkedList::Insert(char theChar)
80:  {
81:            nextNode = nextNode->Insert(theChar);
82:            return nextNode;
83:  }
84:  
85:  char LinkedList::operator[](int offSet) 
86:  {
87:       return (*nextNode)[offSet];
88:  }
89:  
90:  
91:  
92:  bool LinkedList::Add(char theChar)
93:  {
94:       if ( duplicates || HowMany(theChar) == 0 )
95:       {
96:            Insert(theChar);
97:            return true;
98:       }
99:       else
100:            return false;
101:  }
102:  
103:  
104:  void LinkedList::SetDuplicates(bool dupes)
105:  {
106:       duplicates = dupes;
107:  }

Listing 8.4 Game Header

0:  #ifndef GAME_H
1:  #define GAME_H
2:  
3:  #include "definedValues.h"
4:  #include "LinkedList.h"
5:  
6:  class Game
7:  {
8:  public:
9:       Game();
10:       ~Game(){}
11:       void Display(const LinkedList * pList)const
12:       { 
13:            pList->Display(); 
14:       }
15:       
16:       void Play();
17:       const LinkedList &  GetSolution() const 
18:       { 
19:            return solution; 
20:       }
21:       
22:       void Score(
23:            const char * thisGuess, 
24:            int & correct, 
25:            int & position
26:            );
27:  
28:  private:
29:            int HowMany(const char * theString, char theChar);
30:            LinkedList solution;
31:            int howManyLetters;
32:            int howManyPositions;
33:            int round;
34:            bool duplicates;
35:  };
36:  
37:  #endif

Listing 8.5 Game Implementation

0:  #include <time.h>
1:  #include "game.h"
2:  #include "definedvalues.h"
3:  
4:  Game::Game():
5:       round(1),
6:       howManyPositions(0),
7:       howManyLetters(0),
8:       duplicates(false)
9:  {
10:  
11:       bool valid = false;
12:       while ( ! valid )
13:       {
14:            while ( howManyLetters < minLetters 
15:                 || howManyLetters > maxLetters )
16:            {
17:                 cout << "How many letters? (" ;
18:                 cout << minLetters << "-" << maxLetters << "): ";
19:                 cin >> howManyLetters;
20:                 if ( howManyLetters < minLetters 
21:                      || howManyLetters > maxLetters )
22:                 {
23:                 cout << "please enter a number between ";
24:                 cout << minLetters << " and " << maxLetters << endl;
25:                 }
26:            }
27:  
28:            while ( howManyPositions < minPos || 
29:                 howManyPositions > maxPos )
30:            {
31:                 cout << "How many positions? (";
32:                 cout << minPos << "-" << maxPos << "): ";
33:                 cin >> howManyPositions;
34:                 if ( howManyPositions < minPos || 
35:                      howManyPositions > maxPos )
36:                 {
37:                      cout << "please enter a number between ";
38:                      cout << minPos <<" and " << maxPos << endl;
39:                 }
40:            }
41:  
42:            char choice = ' ';
43:            while ( choice != 'y' && choice != 'n' )
44:            {
45:                 cout << "Allow duplicates (y/n)? ";
46:                 cin >> choice;
47:            }
48:  
49:            duplicates = choice == 'y' ? true : false;
50:            solution.SetDuplicates(duplicates);
51:  
52:            if ( ! duplicates && howManyPositions > howManyLetters )
53:            {
54:          cout << "I can't put " << howManyLetters;
55:          cout << " letters in ";
56:          cout << howManyPositions ;
57:          cout << "positions without duplicates! Please try again.\n";
58:          howManyLetters = 0;
59:          howManyPositions = 0;
60:            }
61:            else
62:                 valid = true;
63:       }
64:  
65:  
66:       srand( (unsigned)time( NULL ) );
67:  
68:       for ( int i = 0; i < howManyPositions; )
69:       {
70:            int nextValue = rand() % (howManyLetters);
71:            char theChar = alpha[nextValue];
72:            if ( solution.Add(theChar) )
73:                 i++;
74:       }
75:  
76:       cout << "Exiting constructor. List: ";
77:       solution.Display();
78:       
79:  }
80:  
81:  inline int Game::HowMany(const char * theString, char theChar)
82:  {
83:       int count = 0;
84:       for ( int i = 0; i < strlen(theString); i++)
85:            if ( theString[i] == theChar )
86:                 count ++;
87:       return count;
88:  }
89:  
90:  void Game::Play()
91:  {
92:       char guess[80];
93:       int correct = 0;
94:       int position = 0;
95:       bool quit = false;
96:  
97:       while ( position < howManyPositions )
98:       {
99:  
100:            cout << "\nRound " << round;
101:            cout << ". Enter " << howManyPositions;
102:            cout << " letters between ";
103:            cout << alpha[0] << " and ";
104:            cout << alpha[howManyLetters-1] << ": ";
105:       
106:            cin >> guess;
107:  
108:            if ( strlen(guess) != howManyPositions )
109:            {
110:                 cout << "\n ** Please enter exactly ";
111:                 cout << howManyPositions << " letters. **\n";
112:                 continue;
113:            }
114:  
115:  
116:            round++;
117:  
118:            cout << "\nYour guess: " << guess << endl;
119:  
120:            Score(guess,correct,position);
121:            cout << "\t\t" << correct << " correct, ";
122:            cout << position << " in position." << endl;
123:       }
124:  
125:            cout << "\n\nCongratulations! It took you ";
126:  
127:            if ( round <= 6 )
128:                 cout << "only ";
129:  
130:            if ( round-1 == 1 )
131:                 cout << "one round!" << endl;
132:            else
133:                 cout << round-1 << " rounds." << endl;
134:  
135:  }
136:  
137:  
138:  void Game::Score(
139:                       const char * thisGuess, 
140:                       int & correct, 
141:                       int & position
142:                       )
143:  {
144:       correct = 0;
145:       position = 0;
146:  
147:  
148:       for ( int i = 0; i < howManyLetters; i++)
149:       {
150:            int howManyInGuess = HowMany(thisGuess, alpha[i]);
151:            int howManyInAnswer = solution.HowMany(alpha[i]);
152:            correct += howManyInGuess < howManyInAnswer ? 
153:                 howManyInGuess : howManyInAnswer;
154:       }
155:  
156:       for (  i = 0; i < howManyPositions; i++)
157:       {
158:            if ( thisGuess[i] == solution[i] )
159:                 position++;
160:       }
161:  
162:       ASSERT ( position <= correct );
163:  
164:  }

Listing 8.6 Decryptix! Driver Program

0:  #include "definedValues.h"
1:  #include "game.h"
2:  
3:  int main()
4:  {
5:  
6:       cout << "Decryptix. Copyright 1999 Liberty Associates,";
7:       cout << " Inc. Version 0.3\n\n" << endl;
8:       bool playAgain = true;
9:  
10:       while ( playAgain )
11:       {
12:            char choice = ' ';
13:            Game theGame;
14:            theGame.Play();
15:  
16:            cout << "\nThe answer: ";
17:            theGame.GetSolution().Display();
18:            cout << "\n\n" << endl;
19:  
20:            while ( choice != 'y' && choice != 'n' )
21:            {
22:                 cout << "\nPlay again (y/n): ";
23:                 cin >> choice;
24:            }
25:  
26:            playAgain = choice == 'y' ? true : false;          
27:       }
28:            
29:       return 0;
30:  }

NOTE: The Game class declaration is unchanged from the previous version, and is reproduced here only as a convenience.


Let's start the analysis with the construction of the solution member variable of Game. Put a break point on line 58 of Listing 8.2. When the break point is hit, the first thing you do is check the call stack to see when in the execution of the program this constructor was called:

LinkedList::LinkedList() line 62
Game::Game() line 10 + 58 bytes
main() line 14 + 8 bytes

As you can see, main() called the Game constructor, which in turn called the LinkedList constructor. Line 14 of main() looks like this:

          Game theGame;

It's just as you expected--the construction of a Game object. Line 10 of Game is the opening brace, shown in the code as line 9 of Listing 8.4. Because the LinkedList member variable (solution) was not initialized, the compiler calls its constructor just before entering the body of Game's constructor.

Returning to Listing 8.2, line 58, note that the LinkedList initializes its duplicates member variable to true (line 59); then, on line 61, it creates a new TailNode and sets its own nextNode to point to the Tail. This creates an empty linked list, as shown in Figure 8.5.

Figure 8.5 An empty linked list.

LinkedList is thus automatically initialized to a first Node (LinkedList) and a last Node (TailNode); neither of them contains any data, but together they create the structure of the list.

If you continue stepping through the code, you find yourself in the body of the Game constructor (line 11 of Listing 8.4). Set a break point on line 66 and run to that break point so that you skip examining the initial user interface code that has not changed from previous chapters.

When you are prompted, choose five letters in five positions. The break point is hit, and we generate a seed for the random number generator, based on the time (as discussed in previous chapters). On line 70, we generate a random number and use that as an offset into the alpha array to generate our first character. By line 72 we have that first character, which in my case is 'd'.

Stepping into the Add method causes us to jump to line 92 of Listing 8.2. On line 94, duplicates is tested and fails (we're not allowing dupes); therefore, the call to HowMany is made, passing in the parameter.

Stepping in here brings us to line 74. The LinkedList implementation of this is to return the value that is generated by calling HowMany on whatever the LinkedList points to. Step in, and you'll find yourself in the HowMany() method of TailNode. This makes sense; right now, LinkedList points to TailNode.

Because TailNode holds no data, it returns 0 regardless of what character it is given. This is returned to LinkedList::HowMany(), which in turn returns it to LinkedList::Add() on line 94. Because this satisfies the second condition in the OR statement, enter the body of the if statement on line 96.

Stepping into the Call to Insert jumps to line 80, the implementation of LinkedList::Insert(). LinkedList's strategy is to pass this request on to whatever it points to. Stepping in brings us to line 47, the implementation of TailNode::Insert().

TailNode always inserts a node when it is asked to. It knows that it is the tail, so it doesn't have to check--it can just make the insertion. This is the critical difference from the previous version. You'll remember that in Chapter 6, "Using Linked Lists," Node responded to Insert as follows:

void Node::Insert(char theChar)
{
     if ( ! nextNode )
          nextNode = new Node(theChar);
     else
          nextNode->Insert(theChar);
}

That is, it was necessary to see whether there were any more Nodes in the list. If not (if the current Node was the Tail), a new Node could be inserted. On the other hand, if the current Node was not the Tail, and therefore was an InternalNode, the Insert request would be passed down the list.

The new design obviates the need for the test: The TailNode knows that it is the tail, and it can just make the insertion. This simple division of responsibility is, in a small way, the very heart of object-oriented software development.

Let's examine the implementation in some detail. Line 47 returns the address of the new InternalNode that is created by passing in the character that is received as a parameter and the this pointer of the TailNode.

This jumps to the constructor for InternalNode, shown on line 2. Here you see the creation of the InternalNode. The character is inserted into the InternalNode's myChar member variable, and the this pointer from the TailNode is stored in the nextNode pointer of InternalNode.

The address of this InternalNode is then passed back to the caller of TailNode::Insert(), and in this case is assigned to the nextNode member variable of LinkedList (as shown on line 81). Finally, this address is returned by LinkedList::Insert, but the calling function--LinkedList::Add() on line 96--makes no use of it, and it is thrown on the floor. On line 97, we return true to the calling function on line 72 of Listing 8.4

We have now added a first letter to the linked list, and it worked great. It takes a lot longer to explain the process than to perform it. Next, let's track the second letter, now that you have an InternalNode in the linked list.

Adding a Second Letter

Return to line 92 of Listing 8.2. Once again, this steps you into LinkedList::HowMany() (line 74), this time passing in 'b'.

This time, LinkedList's nextNode points to an InternalNode (the one holding 'd'), so we now jump to line 17. Here a local variable myCount is initialized to zero. The InternalNode's member variable myCount ('d') is compared to the parameter theChar ('b'). Because they are not the same, myCount remains zero.

We now invoke HowMany() on the node that is pointed to by this InternalNode's nextNode pointer. Right now, the pointer points to TailNode, which we examined previously; it simply returns zero. That zero is added to myCount (also zero) for a total of zero, which is the value that is returned to LinkedList::Add().

This causes the second half of the OR statement on line 94 to return true (HowMany('b') equals zero), so the body of the if statement executes. This causes the call on Insert() to execute, with a jump to line 80, which is the implementation of LinkedList::Insert(). Again, LinkedList's strategy is to pass this request on to whatever it points to, which in this case is InternalNode's Insert() method (as shown on line 27). InternalNode's strategy is to call Insert() on the object to which its nextNode pointer points (in this case TailNode), and then to set its nextNode pointer to whatever value is returned.

Because the nextNode is the TailNode, InternalNode::Insert is now called. As you saw just a moment ago, it creates a new InternalNode for 'b' and tells that new node to point to the tail. It then returns the address of the new node, which is now assigned to the nextNode pointer of the node that holds 'd'. Thus, 'b' is appended to the list, as shown in Figure 8.6.

Figure 8.6

Appending 'b'.Examining operator[]

Let's take a look at Game::Score, beginning on line 138 of Listing 8.4. You've examined the fundamental logic in detail in previous chapters. (We're particularly interested in the letter by letter comparisons.) You've seen how LinkedList::HowMany() works; now take a look at the offset operator as it is used on line 158.

Stepping in to this code steps into Linkedlist::Operator[] on line 87 of Listing 8.2.


NOTE: Along the way, I've added test code at line 77 to print out the answer so that I can examine the behavior of the system as I test it. You want to remove both lines 76 and 77 before releasing this code.


Not surprisingly, all LinkedList does here is invoke this same operator on the node to which it points. Stepping in from line 87 brings you to line 31, InternalNode::operator[]. Take a look at your auto member variables, and you'll find that myChar is 'd', just as you might expect. The offset that was passed in is now tested. If it is 0, the call was for the first letter in the list. You will be at the first letter in the list, and you can return myChar, which is the case now. The letter 'd' is returned to LinkedList; LinkedList returns it to the calling method, score(), which--on line 158 of Listing 8.4--is compared with the value of the first character in the guess.

This is repeated, but with i set to 1. A call to solution[1] is invoked, bringing us back into LinkedList::operator[] on line 87 of Listing 8.2.

Stepping in from line 87 brings you back to InternalNode::operator[] on line 31. Take a look at your auto member variables, and you'll find that myChar is again 'd'--you're back at the first InternalNode in the list. The offset that was passed in (1) is now tested. Because it is not zero, the if statement on line 33 fails and the body of the else statement on line 36 executes:

36:            return (*nextNode)[--offSet];

This invokes the offset operator on the next Node in the list, passing in the decremented offSet value. Stepping in appears to bring us back to the top of the same method, but check your variables--myChar is now b, and offset is now zero. Perfect: You'll return the second letter in the list, exactly as you wanted.

The linked list works as you want, and by using inheritance, you've delegated responsibility for monitoring the head and tail of the list to specialized nodes. This simplifies the code and makes it easier to maintain.

The problem with this linked list, however, is that it can only be used by nodes that hold single characters. What if you have other data that you want to insert into your linked list? Must you really rewrite the linked list each time you change the kind of object that is contained? The next chapter, "Implementing Templates," takes a look at modifying your linked list so that it can handle any kind of data.


Contents

© Copyright 1999, Macmillan Computer Publishing. All rights reserved.