ch06.htm

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

  the linked list structure. The client is oblivious to the existence of nodes 
  (note that <tt>headNode</tt> is private).</p>
<p>The best way to understand the implementation of these methods is to see them 
  in action. Let's change <tt>Game</tt> to use a <tt>LinkedList</tt> as its <tt>solution</tt>, 
  as shown in Listing 6.9.</p>
<h4> Listing 6.9 The Game Class Declaration</h4>
<pre>
<tt>0:  #include "List0606_LL.h"</tt>
<tt>1:  </tt>
<tt>2:  class Game</tt>
<tt>3:  {</tt>
<tt>4:  public:</tt>
<tt>5:      Game            ();</tt>
<tt>6:      ~Game            ()        {}</tt>
<tt>7:      void    Display    (const LinkedList * pList) const</tt>
<tt>7a:      { pList-&gt;Display(); }</tt>
<tt>8:      const LinkedList &amp;  GetSolution    () const { return solution; }</tt>
<tt>9:      void    Play    ();</tt>
<tt>10:      void    Score    (const char * thisGuess, int &amp;</tt>
<tt>10a:            correct, int &amp; position);</tt>
<tt>11:  </tt>
<tt>12:  private:</tt>
<tt>13:      int        HowMany    (const char * theString, char theChar);</tt>
<tt>14:  </tt>
<tt>15:      bool        duplicates;</tt>
<tt>16:      int        howManyLetters;</tt>
<tt>17:      int        howManyPositions;</tt>
<tt>18:      int        round;</tt>
<tt>19:      LinkedList        solution;</tt>
<tt>20:  };</tt>
</pre>
<p><tt>Game</tt> is unchanged except for the last line, where the <tt>solution</tt> 
  member variable is changed to type <tt>LinkedList</tt>. </p>
<blockquote>
  <hr>
  <p><strong>NOTE: </strong> When one class contains another, as <tt>Game</tt> 
    contains <tt>LinkedList</tt>, it can do so by value or by reference. <tt>LinkedList</tt> 
    contains <tt>Node</tt> by reference (see Figure 6.10).</p>
  <hr>
</blockquote>
<p><b>Figure 6.10 </b><i>Containing the node by reference.</i></p>
<blockquote>
  <hr>
  <p><strong>NOTE: </strong> <tt>Game</tt>, on the other hand, contains <tt>LinkedList</tt> 
    by value and is diagrammed in the UML as shown in Figure 6.11. The filled 
    in diamond indicates <i>by value</i>.</p>
  <hr>
</blockquote>
<p><b>Figure 6.11 </b><i>Containing linked list by value. <a name="_Toc445687426"></a></i></p>
<h2> <a name="Heading13">Run it!</a></h2>
<p>Let's run through one play of Decryptix! and see how the <tt>LinkedList</tt> 
  is used. Our driver program is unchanged, as shown in Listing 6.10. We begin 
  by instantiating a <tt>Game</tt> object, which brings us into <tt>Game</tt>'s 
  constructor as shown in Listing 6.11. </p>
<blockquote>
  <hr>
  <p> When you make an instance of an object, you are said to <i>instantiate</i> 
    it.</p>
  <hr>
</blockquote>
<blockquote>
  <hr>
  <p><strong>NOTE: </strong> To save room, I've left out the beginning of <tt>Game</tt>'s 
    constructor, in which the member variables <tt>howManyLetters</tt>, <tt>howManyPositions</tt>, 
    and <tt>duplicates</tt> are set because this logic is unchanged. </p>
  <hr>
</blockquote>
<h4> Listing 6.10 Decryptix!.cpp</h4>
<pre>
<tt>{</tt>
<tt>while ( choice != 'y' &amp;&amp; choice != 'n' )</tt>
<tt>0:  #include "DefinedValues.h"</tt>
<tt>1:  #include "List0607_Game.h"</tt>
<tt>2:  </tt>
<tt>3:  int main()</tt>
<tt>4:  {</tt>
<tt>5:      cout &lt;&lt; "Decryptix. Copyright 1999 Liberty";</tt>
<tt>5a:        cout &lt;&lt; Associates, Inc. Version 0.4\n\n" &lt;&lt; endl;</tt>
<tt>6:      bool playAgain = true;</tt>
<tt>7:  </tt>
<tt>8:      while ( playAgain )</tt>
<tt>9:      {</tt>
<tt>10:          char choice = ' ';</tt>
<tt>11:          Game theGame;</tt>
<tt>12:          theGame.Play();</tt>
<tt>13:  </tt>
<tt>14:          cout &lt;&lt; "\nThe answer: ";</tt>
<tt>15:          theGame.GetSolution().Display();</tt>
<tt>16:          cout &lt;&lt; "\n\n" &lt;&lt; endl;</tt>
<tt>17:  </tt>
<tt>18:          while ( choice != 'y' &amp;&amp; choice != 'n' )</tt>
<tt>19:          {</tt>
<tt>20:              cout &lt;&lt; "\nPlay again (y/n): ";</tt>
<tt>21:              cin &gt;&gt; choice;</tt>
<tt>22:          }</tt>
<tt>23:  </tt>
<tt>24:          playAgain = choice == 'y' ? true : false;</tt>
<tt>25:      }</tt>
<tt>26:          </tt>
<tt>27:      return 0;</tt>
<tt>28:  }</tt>
</pre>
<h4> Listing 6.11 Implementing Game</h4>
<pre>
<tt>1:    Game::Game():</tt>
<tt>2:        round(1),</tt>
<tt>3:        howManyPositions(0),</tt>
<tt>4:        howManyLetters(0),</tt>
<tt>5:        duplicates(false)</tt>
<tt>6:    {</tt>
<tt>7:    </tt>
<tt>8:    //...</tt>
<tt>9:    </tt>
<tt>10:        srand( (unsigned)time( NULL ) );</tt>
<tt>11:    </tt>
<tt>12:        for ( int i = 0; i &lt; howManyPositions; )</tt>
<tt>13:        {</tt>
<tt>14:            int nextValue = rand() % (howManyLetters);</tt>
<tt>15:            char c = alpha[nextValue];</tt>
<tt>16:            if ( solution.Add(c, duplicates) )</tt>
<tt>17:                i++;</tt>
<tt>18:        }</tt>
<tt>19:    </tt>
<tt>20:        cout &lt;&lt; "Exiting constructor. List: ";</tt>
<tt>21:        solution.Display();</tt>
<tt>22:        </tt>
<tt>23:    }</tt>
</pre>
<p>We pick up the logic on line 14, within the <tt>for</tt> loop in which we create 
  our random numbers, turn them into characters on line 20, and then add them 
  to <tt>solution</tt> on line 21. It is here, when we call <tt>solution.add()</tt>, 
  that the logic of the <tt>LinkedList</tt> comes into play. This invokes <tt>LinkedList::Add()</tt>, 
  as shown in Listing 6.12.</p>
<h4> Listing 6.12 Implementing LinkedList</h4>
<pre>
<tt>1:  </tt>
<tt>2:  bool LinkedList::Add(char theChar, bool dupes)</tt>
<tt>3:  {</tt>
<tt>4:      bool inserted = false;</tt>
<tt>5:  </tt>
<tt>6:      if ( ! headNode )</tt>
<tt>7:      {</tt>
<tt>8:          headNode = new Node(theChar);</tt>
<tt>9:          inserted = true;</tt>
<tt>10:      }</tt>
<tt>11:      else if ( dupes || HowMany(theChar) == 0 )</tt>
<tt>12:      {</tt>
<tt>13:          headNode-&gt;Insert(theChar);</tt>
<tt>14:          inserted = true;</tt>
<tt>15:      }</tt>
<tt>16:  </tt>
<tt>17:      return inserted;</tt>
<tt>18:  }</tt>
<tt>19:  </tt>
<tt>20:  int LinkedList::HowMany(char theChar) const</tt>
<tt>21:  {</tt>
<tt>22:      return headNode-&gt;HowMany(theChar);</tt>
<tt>23:  }</tt>
<tt>24:  </tt>
<tt>25:  char LinkedList::offset(int offSetValue) </tt>
<tt>26:  {</tt>
<tt>27:      Node * pNode = headNode;</tt>
<tt>28:      for ( int i = 0; i &lt; offSetValue &amp;&amp; pNode; i++ )</tt>
<tt>29:          pNode = pNode-&gt;GetNext();</tt>
<tt>30:  </tt>
<tt>31:      ASSERT ( pNode );</tt>
<tt>32:      char c =  pNode-&gt;GetChar();</tt>
<tt>33:      return c;</tt>
<tt>34:  }</tt>
<tt>35:  </tt>
<tt>36:  char LinkedList::operator[](int offSetValue)</tt>
<tt>37:  {</tt>
<tt>38:      Node * pNode = headNode;</tt>
<tt>39:      for ( int i = 0; i &lt; offSetValue &amp;&amp; pNode; i++ )</tt>
<tt>40:          pNode = pNode-&gt;GetNext();</tt>
<tt>41:  </tt>
<tt>42:      ASSERT ( pNode );</tt>
<tt>43:      char c =  pNode-&gt;GetChar();</tt>
<tt>44:      return c;</tt>
<tt>45:  }</tt>
</pre>
<p>On line 6, <tt>LinkedList</tt> checks to see whether it already has a <tt>headNode</tt>. 
  To do this, it checks its <tt>headNode</tt> pointer, which was initialized to 
  <tt>NULL</tt> in <tt>LinkedList</tt>'s constructor. If that is pointer is still 
  <tt>NULL</tt>, no <tt>headNode</tt> exists, so one is now created, passing in 
  the character to be stored.</p>
<p>The constructor to <tt>Node</tt> was considered earlier (refer to Listing 6.3). 
  Remember that the <tt>Node</tt>'s member variable <tt>myChar</tt> is initialized 
  with the character passed in (<tt>theChar</tt>), and its member variable <tt>nextNode</tt> 
  is initialized with <tt>NULL</tt> as shown in Listing 6.13.</p>
<h4> Listing 6.13 Node Constructor</h4>
<pre>
<tt>0:  Node::Node(char theChar):</tt>
<tt>1:  myChar(theChar),nextNode(0)</tt>
<tt>2:  {</tt>
<tt>3:  }</tt>
</pre>
<p>This effectively adds the character to the linked list, storing it in the head 
  node.</p>
<p>If there already is a <tt>HeadNode</tt>, (that is, the pointer is not <tt>NULL</tt>), 
  we have a list already and must decide whether we want to add the character. 
  If we are accepting duplicates or if the character does not appear in the list 
  already (line 11), we add it by calling <tt>Insert</tt> on the <tt>headNode</tt> 
  (line 13). I already described <tt>HeadNode()::Insert</tt> in Listing 6.3. </p>
<p>We determine whether the character is in the list on line 11 by calling <tt>LinkedList::HowMany()</tt>, 
  as shown in Listing 6.14.</p>
<h4> Listing 6.14 LinkedList's HowMany Method</h4>
<pre>
<tt>0:  int LinkedList::HowMany(char theChar) const</tt>
<tt>1:  {</tt>
<tt>2:      return headNode-&gt;HowMany(theChar);</tt>
<tt>3:  }</tt>
</pre>
<p>As you can see, <tt>LinkedList</tt> does nothing but pass along the character 
  to the <tt>headNode</tt>, calling the logic that was considered earlier (in 
  Listing 6.3). The <tt>LinkedList</tt> method <tt>HowMany()</tt> is considered 
  a <i>wrapper</i> method: It wraps around the <tt>Node::HowMany()</tt> method, 
  encapsulating its interface, but delegating all the work to the encapsulated 
  method.</p>
<blockquote>
  <hr>
  <p> <b>wrapper</b>--A class is a wrapper for another when it provides a public 
    interface but delegates all the work to the contained class. </p>
  <p> <b>method</b>--A method is a wrapper for another method when it provides 
    an encapsulating interface to that method but delegates all the work to the 
    wrapped method. <a name="_Toc445687427"></a></p>
  <hr>
</blockquote>
<h2> <a name="Heading14">Playing the Game</a></h2>
<p>After the <tt>solution</tt> member linked list is populated, the <tt>Game</tt> 
  object is fully constructed and the next line in <tt>main()</tt> is a call to 
  the <tt>Game</tt>'s <tt>Play()</tt> method. This was considered earlier, and 
  you probably remember that <tt>Play()</tt> solicits a guess from the player 
  and then calls <tt>Game::Score()</tt>.</p>
<p><tt>Game::Score()</tt> was also considered earlier, but because solution is 
  now a linked list, this is worth another look. I've reproduced <tt>Game::Score()</tt> 
  in Listing 6.15 for your convenience.</p>
<h4> Listing 6.15 The Score Method</h4>
<pre>
<tt>0:void Game::Score(const char * thisGuess, int &amp; correct, int &amp; position)</tt>
<tt>1:  {</tt>
<tt>2:      correct = 0;</tt>
<tt>3:      position = 0;</tt>
<tt>4:  </tt>
<tt>5:  </tt>
<tt>6:      for ( int i = 0; i &lt; howManyLetters; i++)</tt>
<tt>7:      {</tt>
<tt>8:          int howManyInGuess = HowMany(thisGuess, alpha[i]);</tt>
<tt>9:          int howManyInAnswer = solution.HowMany(alpha[i]);</tt>
<tt>10:    correct += howManyInGuess &lt; howManyInAnswer ?</tt>
<tt>10a:            howManyInGuess : howManyInAnswer;</tt>
<tt>11:      }</tt>
<tt>12:  </tt>
<tt>13:      for (  i = 0; i &lt; howManyPositions; i++)</tt>
<tt>14:      {</tt>
<tt>15:          if ( thisGuess[i] == solution[i] )</tt>
<tt>16:              position++;</tt>
<tt>17:      }</tt>
<tt>18:  </tt>
<tt>19:      ASSERT ( position &lt;= correct )</tt>
<tt>20:  </tt>
<tt>21:  }</tt>
</pre>
<p>On line 9, we must determine how many times each character appears in <tt>solution</tt>. 
  We do this by calling <tt>HowMany()</tt> on <tt>solution</tt>, passing in each 
  character in turn. This calls <tt>LinkedList::HowMany()</tt>, which, as we just 
  saw, calls <tt>Node: