ch08.htm

C++ From Scratch: An Object-Oriented Approach is designed to walk novice programmers through the ana

<p>Although we put the keyword <tt>virtual</tt> 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.</p>
<p><tt>InternalNode</tt> adds two private variables: <tt>myChar</tt> and <tt>nextNode</tt>. 
  It is clear why <tt>myChar</tt> can't be in <tt>Node:</tt> Only <tt>InternalNode</tt> 
  classes have a character for which they are responsible. Why not put <tt>nextNode</tt> 
  up in the base class, then? After all, nodes exist in a linked list. You'd expect 
  all nodes to have a <tt>nextNode</tt>.</p>
<p>This is true of all nodes <i>except</i> for <tt>TailNode</tt>. Because <tt>TailNode</tt> 
  does not have a <tt>nextNode</tt>, it doesn't make sense for this attribute 
  to be in the base class. </p>
<p>You can put this pointer in the base and then give <tt>TailNode</tt> a null 
  <tt>nextNode</tt> pointer. That might work, but it doesn't map to the semantics 
  of a <tt>Node</tt>. A <tt>Node</tt> is an object that lives in a linked list. 
  It is not part of our definition that a <tt>Node</tt> must point to another 
  <tt>Node</tt>, only that it must be in the list. <tt>TailNodes</tt> are in the 
  list, but they don't point to a <tt>nextNode</tt>. Thus, this pointer is not 
  an intrinsic aspect of a <tt>Node</tt>, so I've left it out of the base class.</p>
<p>The declaration for <tt>TailNode</tt> begins on line 32, and once again you 
  can see that the pure virtual functions are overridden. The distinguishing characteristics 
  of <tt>TailNode</tt> are shown in the implementation of these methods, which 
  we'll consider in a moment.</p>
<p>Finally, on line 45 you see <tt>LinkedList</tt> declared. Again, the pure virtual 
  methods are overridden, but this time, on lines 54 and 55, you see new public 
  methods: <tt>Add</tt> and <tt>SetDuplicates</tt>. These methods support the 
  functionality of this class, to provide an interface for the <tt>LinkedList</tt> 
  to the client classes. </p>
<p>Note also that on line 58 we've moved <tt>Insert()</tt> to the private section 
  of <tt>LinkedList</tt>. The only <tt>Node</tt> class that any non-<tt>Node</tt> 
  interacts with is this one, and <tt>Insert</tt> is not part of the <tt>LinkedList</tt> 
  class's public interface. When a client wants to add a character to the list, 
  it calls <tt>LinkedList::Add()</tt>, which is shown on line 54. </p>
<p><tt>Node</tt>'s <tt>Insert()</tt> method is public, however--when nodes interact 
  with one another (for example, when <tt>LinkedList</tt> is adding objects to 
  an <tt>InternalNode</tt>), the <tt>InsertMethod</tt> is used.</p>
<p>Let's look at the implementation of <tt>LinkedList</tt> in Listing 8.3, adding 
  <tt>Game</tt> 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.</p>
<h4> Listing 8.3 Linked List Implementation</h4>
<pre>
<tt>0:  #include "LinkedList.h"</tt>
<tt>1:  </tt>
<tt>2:  InternalNode::InternalNode(char theCharacter, Node * next):</tt>
<tt>3:  myChar(theCharacter),nextNode(next)</tt>
<tt>4:  {</tt>
<tt>5:  }</tt>
<tt>6:  </tt>
<tt>7:  InternalNode::~InternalNode() </tt>
<tt>8:  { </tt>
<tt>9:       delete nextNode;  </tt>
<tt>10:  }</tt>
<tt>11:  </tt>
<tt>12:  void InternalNode::Display() const </tt>
<tt>13:  { </tt>
<tt>14:       cout &lt;&lt; myChar; nextNode-&gt;Display(); </tt>
<tt>15:  } </tt>
<tt>16:  </tt>
<tt>17:  int InternalNode::HowMany(char theChar) const</tt>
<tt>18:  {</tt>
<tt>19:       int myCount = 0;</tt>
<tt>20:       if ( myChar == theChar )</tt>
<tt>21:            myCount++;</tt>
<tt>22:       return myCount + nextNode-&gt;HowMany(theChar);</tt>
<tt>23:  }</tt>
<tt>24:  </tt>
<tt>25:  Node * InternalNode::Insert(char theCharacter)</tt>
<tt>26:  {</tt>
<tt>27:       nextNode = nextNode-&gt;Insert(theCharacter);</tt>
<tt>28:       return this;</tt>
<tt>29:  }</tt>
<tt>30:  </tt>
<tt>31:  char InternalNode::operator[](int offSet) </tt>
<tt>32:  {</tt>
<tt>33:       if ( offSet == 0 )</tt>
<tt>34:            return myChar;</tt>
<tt>35:       else</tt>
<tt>36:            return (*nextNode)[--offSet];</tt>
<tt>37:  }</tt>
<tt>38:  </tt>
<tt>39:       </tt>
<tt>40:  int TailNode::HowMany(char theChar) const </tt>
<tt>41:  { </tt>
<tt>42:       return 0; </tt>
<tt>43:  }</tt>
<tt>44:  </tt>
<tt>45:  Node * TailNode::Insert(char theChar)</tt>
<tt>46:  {</tt>
<tt>47:       return new InternalNode(theChar, this);</tt>
<tt>48:  }</tt>
<tt>49:  </tt>
<tt>50:  char TailNode::operator[](int offset) </tt>
<tt>51:  { </tt>
<tt>52:       ASSERT(false); </tt>
<tt>53:       return ' '; </tt>
<tt>54:  }</tt>
<tt>55:  </tt>
<tt>56:  </tt>
<tt>57:  </tt>
<tt>58:  LinkedList::LinkedList():</tt>
<tt>59:  duplicates(true)</tt>
<tt>60:  {</tt>
<tt>61:       nextNode = new TailNode;</tt>
<tt>62:  }</tt>
<tt>63:  </tt>
<tt>64:  LinkedList::~LinkedList() </tt>
<tt>65:  { </tt>
<tt>66:       delete nextNode; </tt>
<tt>67:  }</tt>
<tt>68:  </tt>
<tt>69:  void LinkedList::Display() const </tt>
<tt>70:  { </tt>
<tt>71:       nextNode-&gt;Display(); </tt>
<tt>72:  }</tt>
<tt>73:  </tt>
<tt>74:  int LinkedList::HowMany(char theChar) const</tt>
<tt>75:  {</tt>
<tt>76:       return nextNode-&gt;HowMany(theChar);</tt>
<tt>77:  }</tt>
<tt>78:  </tt>
<tt>79:  Node * LinkedList::Insert(char theChar)</tt>
<tt>80:  {</tt>
<tt>81:            nextNode = nextNode-&gt;Insert(theChar);</tt>
<tt>82:            return nextNode;</tt>
<tt>83:  }</tt>
<tt>84:  </tt>
<tt>85:  char LinkedList::operator[](int offSet) </tt>
<tt>86:  {</tt>
<tt>87:       return (*nextNode)[offSet];</tt>
<tt>88:  }</tt>
<tt>89:  </tt>
<tt>90:  </tt>
<tt>91:  </tt>
<tt>92:  bool LinkedList::Add(char theChar)</tt>
<tt>93:  {</tt>
<tt>94:       if ( duplicates || HowMany(theChar) == 0 )</tt>
<tt>95:       {</tt>
<tt>96:            Insert(theChar);</tt>
<tt>97:            return true;</tt>
<tt>98:       }</tt>
<tt>99:       else</tt>
<tt>100:            return false;</tt>
<tt>101:  }</tt>
<tt>102:  </tt>
<tt>103:  </tt>
<tt>104:  void LinkedList::SetDuplicates(bool dupes)</tt>
<tt>105:  {</tt>
<tt>106:       duplicates = dupes;</tt>
<tt>107:  }</tt>
</pre>
<h4> Listing 8.4 Game Header</h4>
<pre>
<tt>0:  #ifndef GAME_H</tt>
<tt>1:  #define GAME_H</tt>
<tt>2:  </tt>
<tt>3:  #include "definedValues.h"</tt>
<tt>4:  #include "LinkedList.h"</tt>
<tt>5:  </tt>
<tt>6:  class Game</tt>
<tt>7:  {</tt>
<tt>8:  public:</tt>
<tt>9:       Game();</tt>
<tt>10:       ~Game(){}</tt>
<tt>11:       void Display(const LinkedList * pList)const</tt>
<tt>12:       { </tt>
<tt>13:            pList-&gt;Display(); </tt>
<tt>14:       }</tt>
<tt>15:       </tt>
<tt>16:       void Play();</tt>
<tt>17:       const LinkedList &amp;  GetSolution() const </tt>
<tt>18:       { </tt>
<tt>19:            return solution; </tt>
<tt>20:       }</tt>
<tt>21:       </tt>
<tt>22:       void Score(</tt>
<tt>23:            const char * thisGuess, </tt>
<tt>24:            int &amp; correct, </tt>
<tt>25:            int &amp; position</tt>
<tt>26:            );</tt>
<tt>27:  </tt>
<tt>28:  private:</tt>
<tt>29:            int HowMany(const char * theString, char theChar);</tt>
<tt>30:            LinkedList solution;</tt>
<tt>31:            int howManyLetters;</tt>
<tt>32:            int howManyPositions;</tt>
<tt>33:            int round;</tt>
<tt>34:            bool duplicates;</tt>
<tt>35:  };</tt>
<tt>36:  </tt>
<tt>37:  #endif</tt>
</pre>
<h4> Listing 8.5 Game Implementation</h4>
<pre>
<tt>0:  #include &lt;time.h&gt;</tt>
<tt>1:  #include "game.h"</tt>
<tt>2:  #include "definedvalues.h"</tt>
<tt>3:  </tt>
<tt>4:  Game::Game():</tt>
<tt>5:       round(1),</tt>
<tt>6:       howManyPositions(0),</tt>
<tt>7:       howManyLetters(0),</tt>
<tt>8:       duplicates(false)</tt>
<tt>9:  {</tt>
<tt>10:  </tt>
<tt>11:       bool valid = false;</tt>
<tt>12:       while ( ! valid )</tt>
<tt>13:       {</tt>
<tt>14:            while ( howManyLetters &lt; minLetters </tt>
<tt>15:                 || howManyLetters &gt; maxLetters )</tt>
<tt>16:            {</tt>
<tt>17:                 cout &lt;&lt; "How many letters? (" ;</tt>
<tt>18:                 cout &lt;&lt; minLetters &lt;&lt; "-" &lt;&lt; maxLetters &lt;&lt; "): ";</tt>
<tt>19:                 cin &gt;&gt; howManyLetters;</tt>
<tt>20:                 if ( howManyLetters &lt; minLetters </tt>
<tt>21:                      || howManyLetters &gt; maxLetters )</tt>
<tt>22:                 {</tt>
<tt>23:                 cout &lt;&lt; "please enter a number between ";</tt>
<tt>24:                 cout &lt;&lt; minLetters &lt;&lt; " and " &lt;&lt; maxLetters &lt;&lt; endl;</tt>
<tt>25:                 }</tt>
<tt>26:            }</tt>
<tt>27:  </tt>
<tt>28:            while ( howManyPositions &lt; minPos || </tt>
<tt>29:                 howManyPositions &gt; maxPos )</tt>
<tt>30:            {</tt>
<tt>31:                 cout &lt;&lt; "How many positions? (";</tt>
<tt>32:                 cout &lt;&lt; minPos &lt;&lt; "-" &lt;&lt; maxPos &lt;&lt; "): ";</tt>
<tt>33:                 cin &gt;&gt; howManyPositions;</tt>
<tt>34:                 if ( howManyPositions &lt; minPos || </tt>
<tt>35:                      howManyPositions &gt; maxPos )</tt>
<tt>36:                 {</tt>
<tt>37:                      cout &lt;&lt; "please enter a number between ";</tt>
<tt>38:                      cout &lt;&lt; minPos &lt;&lt;" and " &lt;&lt; maxPos &lt;&lt; endl;</tt>
<tt>39:                 }</tt>
<tt>40:            }</tt>
<tt>41:  </tt>
<tt>42:            char choice = ' ';</tt>
<tt>43:            while ( choice != 'y' &amp;&amp; choice != 'n' )</tt>
<tt>44:            {</tt>
<tt>45:                 cout &lt;&lt; "Allow duplicates (y/n)? ";</tt>
<tt>46:                 cin &gt;&gt; choice;</tt>
<tt>47:            }</tt>
<tt>48:  </tt>
<tt>49:            duplicates = choice == 'y' ? true : false;</tt>
<tt>50:            solution.SetDuplicates(duplicates);</tt>
<tt>51:  </tt>
<tt>52:            if ( ! duplicates &amp;&amp; howManyPositions &gt; howManyLetters )</tt>
<tt>53:            {</tt>
<tt>54:          cout &lt;&lt; "I can't put " &lt;&lt; howManyLetters;</tt>
<tt>55:          cout &lt;&lt; " letters in ";</tt>
<tt>56:          cout &lt;&lt; howManyPositions ;</tt>
<tt>57:          cout &lt;&lt; "positions without duplicates! Please try again.\n";</tt>
<tt>58:          howManyLetters = 0;</tt>
<tt>59:          howManyPositions = 0;</tt>
<tt>60:            }</tt>
<tt>61:            else</tt>
<tt>62:                 valid = true;</tt>
<tt>63:       }</tt>
<tt>64:  </tt>
<tt>65:  </tt>
<tt>66:       srand( (unsigned)time( NULL ) );</tt>
<tt>67:  </tt>
<tt>68:       for ( int i = 0; i &lt; howManyPositions; )</tt>
<tt>69:       {</tt>
<tt>70:            int nextValue = rand() % (howManyLetters);</tt>
<tt>71:            char theChar = alpha[nextValue];</tt>
<tt>72:            if ( solution.Add(theChar) )</tt>
<tt>73:                 i++;</tt>
<tt>74:       }</tt>
<tt>75:  </tt>
<tt>76:       cout &lt;&lt; "Exiting constructor. List: ";</tt>
<tt>77:       solution.Display();</tt>
<tt>78:       </tt>
<tt>79:  }</tt>
<tt>80:  </tt>
<tt>81:  inline int Game::HowMany(const char * theString, char theChar)</tt>
<tt>82:  {</tt>
<tt>83:       int count = 0;</tt>
<tt>84:       for ( int i = 0; i &lt; strlen(theString); i++)</tt>
<tt>85:            if ( theString[i] == theChar )</tt>
<tt>86:                 count ++;</tt>
<tt>87:       return count;</tt>
<tt>88:  }</tt>
<tt>89:  </tt>
<tt>90:  void Game::Play()</tt>
<tt>91:  {</tt>
<tt>92:       char guess[80];</tt>
<tt>93:       int correct = 0;</tt>
<tt>94:       int position = 0;</tt>
<tt>95:       bool quit = false;</tt>
<tt>96:  </tt>
<tt>97:       while ( position &lt; howManyPositions )</tt>
<tt>98:       {</tt>
<tt>99:  </tt>
<tt>100:            cout &lt;&lt; "\nRound " &lt;&lt; round;</tt>
<tt>101:            cout &lt;&lt; ". Enter " &lt;&lt; howManyPositions;</tt>
<tt>102:            cout &lt;&lt; " letters between ";</tt>
<tt>103:            cout &lt;&lt; alpha[0] &lt;&lt; " and ";</tt>
<tt>104:            cout &lt;&lt; alpha[howManyLetters-1] &lt;&lt; ": ";</tt>
<tt>105:       </tt>