chapter12.html

think like a computer scientist

<PRE>
  Card aceOfSpades (3, 1);
  apvector<Card> deck (52, aceOfSpades);
</PRE>

<P>This code builds a deck with 52 identical cards, like a special deck for a 
magic trick. Of course, it makes more sense to build a deck with 52 different 
cards in it. To do that we use a nested loop.</P>

<P>The outer loop enumerates the suits, from 0 to 3. For each suit, the inner 
loop enumerates the ranks, from 1 to 13.  Since the outer loop iterates 4 
times, and the inner loop iterates 13 times, the total number of times the body
is executed is 52 (13 times 4).</P>

<PRE>
  int i = 0;
  for (int suit = 0; suit <= 3; suit++) {
    for (int rank = 1; rank <= 13; rank++) {
      deck[i].suit = suit;
      deck[i].rank = rank;
      i++;
    }
  }
</PRE>

<P>I used the variable <TT>i</TT> to keep track of where in the deck the next 
card should go.</P>

<P>Notice that we can compose the syntax for selecting an element from an array
(the <TT>[]</TT> operator) with the syntax for selecting an instance variable 
from an object (the dot operator). The expression <TT>deck[i].suit</TT> means 
``the suit of the ith card in the deck''.</P>

<P>As an exercise, encapsulate this deck-building code in a function called 
<TT>buildDeck</TT> that takes no parameters and that returns a fully-populated 
vector of <TT>Card</TT>s.</P>


<BR><BR>
<H3>12.7 The <TT>printDeck</TT> function</H3>

<P>Whenever you are working with vectors, it is convenient to have a function 
that prints the contents of the vector. We have seen the pattern for traversing
a vector several times, so the following function should be familiar:</P>

<PRE>
void printDeck (const apvector<Card>& deck) {
  for (int i = 0; i < deck.length(); i++) {
    deck[i].print ();
  }
}
</PRE>

<P>By now it should come as no surprise that we can compose the syntax for 
vector access with the syntax for invoking a function.</P>

<P>Since <TT>deck</TT> has type <TT>apvector<Card></TT>, an element of 
<TT>deck</TT> has type <TT>Card</TT>. Therefore, it is legal to invoke 
<TT>print</TT> on <TT>deck[i]</TT>.</P>


<BR><BR>
<H3>12.8 Searching</H3>

<P>The next function I want to write is <TT>find</TT>, which searches through a
vector of <TT>Card</TT>s to see whether it contains a certain card. It may not 
be obvious why this function would be useful, but it gives me a chance to 
demonstrate two ways to go searching for things, a <TT>linear</TT> search and a
<TT>bisection</TT> search.</P>  

<P>Linear search is the more obvious of the two; it involves traversing the 
deck and comparing each card to the one we are looking for. If we find it we 
return the index where the card appears. If it is not in the deck, we return 
-1.</P>

<PRE>
int find (const Card& card, const apvector<Card>& deck) {
  for (int i = 0; i < deck.length(); i++) {
    if (equals (deck[i], card)) return i;
  }
  return -1;
}
</PRE>

<P>The loop here is exactly the same as the loop in <TT>printDeck</TT>. In 
fact, when I wrote the program, I copied it, which saved me from having to 
write and debug it twice.</P>

<P>Inside the loop, we compare each element of the deck to <TT>card</TT>. The 
function returns as soon as it discovers the card, which means that we do not 
have to traverse the entire deck if we find the card we are looking for. If the
loop terminates without finding the card, we know the card is not in the deck
and return <TT>-1</TT>.</P>

<P>To test this function, I wrote the following:</P>

<PRE>
  apvector<Card> deck = buildDeck ();

  int index = card.find (deck[17]);
  cout << "I found the card at index = " << index << endl;
</PRE>

<P>The output of this code is</P>

<PRE>
I found the card at index = 17
</PRE>


<BR><BR>
<H3>12.9 Bisection search</H3>

<P>If the cards in the deck are not in order, there is no way to search that is
faster than the linear search. We have to look at every card, since otherwise 
there is no way to be certain the card we want is not there.</P>

<P>But when you look for a word in a dictionary, you don't search linearly 
through every word. The reason is that the words are in alphabetical order. As 
a result, you probably use an algorithm that is similar to a bisection search:
</P>

<OL>
  <LI>Start in the middle somewhere.</LI>

  <LI>Choose a word on the page and compare it to the word you are looking for.
  </LI>

  <LI>If you found the word you are looking for, stop.</LI>

  <LI>If the word you are looking for comes after the word on the page, flip to
  somewhere later in the dictionary and go to step 2.</LI>

  <LI>If the word you are looking for comes before the word on the page, flip 
  to somewhere earlier in the dictionary and go to step 2.</LI>
</OL>

<P>If you ever get to the point where there are two adjacent words on the page 
and your word comes between them, you can conclude that your word is not in the
dictionary. The only alternative is that your word has been misfiled somewhere,
but that contradicts our assumption that the words are in alphabetical order.
</P>

<P>In the case of a deck of cards, if we know that the cards are in order, we 
can write a version of <TT>find</TT> that is much faster. The best way to write
a bisection search is with a recursive function. That's because bisection is 
naturally recursive.</P>

<P>The trick is to write a function called <TT>findBisect</TT> that takes two 
indices as parameters, <TT>low</TT> and <TT>high</TT>, indicating the segment 
of the vector that should be searched (including both <TT>low</TT> and 
<TT>high</TT>).</P>

<OL>
  <LI>To search the vector, choose an index between <TT>low</TT> and 
  <TT>high</TT>, and call it <TT>mid</TT>. Compare the card at <TT>mid</TT> to 
  the card you are looking for.</LI>

  <LI>If you found it, stop.</LI>

  <LI>If the card at <TT>mid</TT> is higher than your card, search in the range
  from <TT>low</TT> to <TT>mid-1</TT>.</LI>

  <LI>If the card at <TT>mid</TT> is lower than your card, search in the range 
  from <TT>mid+1</TT> to <TT>high</TT>.
</OL>

<P>Steps 3 and 4 look suspiciously like recursive invocations. Here's what this 
all looks like translated into C++:</P>

<PRE>
int findBisect (const Card& card, const apvector&lt;Card&gt;& deck,
                int low, int high) {
  int mid = (high + low) / 2;

  // if we found the card, return its index
  if (equals (deck[mid], card)) return mid;

  // otherwise, compare the card to the middle card
  if (deck[mid].isGreater (card)) {
    // search the first half of the deck
    return findBisect (card, deck, low, mid-1);
  } else {
    // search the second half of the deck
    return findBisect (card, deck, mid+1, high);
  }
}
</PRE>

<P>Although this code contains the kernel of a bisection search, it is still 
missing a piece. As it is currently written, if the card is not in the deck, it
will recurse forever. We need a way to detect this condition and deal with it 
properly (by returning <TT>-1</TT>).</P>

<P>The easiest way to tell that your card is not in the deck is if there are 
<I>no</I> cards in the deck, which is the case if <TT>high</TT> is less than 
<TT>low</TT>. Well, there are still cards in the deck, of course, but what I 
mean is that there are no cards in the segment of the deck indicated by 
<TT>low</TT> and <TT>high</TT>.</P>

<P>With that line added, the function works correctly:</P>

<PRE>
int findBisect (const Card& card, const apvector&lt;Card&gt;& deck,
                int low, int high) {

  cout << low << ", " << high << endl;

  if (high < low) return -1;

  int mid = (high + low) / 2;

  if (equals (deck[mid], card)) return mid;

  if (deck[mid].isGreater (card)) {
    return findBisect (card, deck, low, mid-1);
  } else {
    return findBisect (card, deck, mid+1, high);
  }
}
</PRE>

<P>I added an output statement at the beginning so I could watch the sequence 
of recursive calls and convince myself that it would eventually reach the base 
case. I tried out the following code:</P>

<PRE>
  cout << findBisect (deck, deck[23], 0, 51));
</PRE>

<P>And got the following output:</P>

<PRE>
0, 51
0, 24
13, 24
19, 24
22, 24
I found the card at index = 23
</PRE>

<P>Then I made up a card that is not in the deck (the 15 of Diamonds), and 
tried to find it. I got the following:</P>

<PRE>
0, 51
0, 24
13, 24
13, 17
13, 14
13, 12
I found the card at index = -1
</PRE>

<P>These tests don't prove that this program is correct. In fact, no amount of 
testing can prove that a program is correct. On the other hand, by looking at a
few cases and examining the code, you might be able to convince yourself.</P>

<P>The number of recursive calls is fairly small, typically 6 or 7. That means 
we only had to call <TT>equals</TT> and <TT>isGreater</TT> 6 or 7 times, 
compared to up to 52 times if we did a linear search. In general, bisection is 
much faster than a linear search, especially for large vectors.</P>

<P>Two common errors in recursive programs are forgetting to include a base 
case and writing the recursive call so that the base case is never reached. 
Either error will cause an infinite recursion, in which case C++ will 
(eventually) generate a run-time error.</P>


<BR><BR>
<H3>12.10 Decks and subdecks</H3>

<P>Looking at the interface to <TT>findBisect</TT></P>

<PRE>
int findBisect (const Card& card, const apvector&lt;Card&gt;& deck,
		int low, int high) {
</PRE>

<P>it might make sense to treat three of the parameters, <TT>deck</TT>, 
<TT>low</TT> and <TT>high</TT>, as a single parameter that specifies a 
<B>subdeck</B>.</P>

<P>This kind of thing is quite common, and I sometimes think of it as an 
<B>abstract parameter</B>. What I mean by ``abstract,'' is something that is 
not literally part of the program text, but which describes the function of 
the program at a higher level.</P>

<P>For example, when you call a function and pass a vector and the bounds 
<TT>low</TT> and <TT>high</TT>, there is nothing that prevents the called 
function from accessing parts of the vector that are out of bounds. So you are 
not literally sending a subset of the deck; you are really sending the whole 
deck. But as long as the recipient plays by the rules, it makes sense to think 
of it, abstractly, as a subdeck.</P>

<P>There is one other example of this kind of abstraction that you might have 
noticed in Section 9.3, when I referred to an ``empty'' data structure. The 
reason I put ``empty'' in quotation marks was to suggest that it is not 
literally accurate. All variables have values all the time. When you create 
them, they are given default values. So there is no such thing as an empty 
object.</P>

<P>But if the program guarantees that the current value of a variable is never 
read before it is written, then the current value is irrelevant. Abstractly, it
makes sense to think of such a variable as ``empty.''</P>

<P>This kind of thinking, in which a program comes to take on meaning beyond 
what is literally encoded, is a very important part of thinking like a computer
scientist. Sometimes, the word ``abstract'' gets used so often and in so many 
contexts that it is hard to interpret. Nevertheless, abstraction is a central 
idea in computer science (as well as many other fields).</P>

<P>A more general definition of ``abstraction'' is ``The process of modeling a 
complex system with a simplified description in order to suppress unnecessary 
details while capturing relevant behavior.''</P>


<BR><BR>
<H3>12.11 Glossary</H3>

<DL>
  <DT>encode:</DT><DD> To represent one set of values using another set of 
  values, by constructing a mapping between them.</DD>

  <DT>abstract parameter:</DT><DD> A set of parameters that act together as a 
  single parameter.</DD>
</DL>

<BR>
<DIV CLASS=navigation><HR>
  <TABLE ALIGN=center WIDTH="100%" CELLPADDING=0 CELLSPACING=2>
  <TR>
    <TD><A HREF="chapter13.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter13.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="next" 
      SRC="images/next.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/next.gif"></A>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="up" 
      SRC="images/up.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/up.gif"></A>
    </TD>

    <TD><A HREF="chapter11.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter11.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="previous"
      SRC="images/previous.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/previous.gif"></A>
    </TD>

    <TD ALIGN=center BGCOLOR="#99CCFF" WIDTH="100%">
      <B CLASS=title>How to Think Like a Computer Scientist: Chapter 12</B>
    </TD>

    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="contents"
      SRC="images/contents.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/contents.gif"></A>
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>

    <TD>
      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""
      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">
    </TD>
  </TR>
  </TABLE>

  <B CLASS=navlabel>Next:</B>
  <SPAN CLASS=sectref><A HREF="chapter13.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter13.html">Chapter 13</A></SPAN>

  <B CLASS=navlabel>Up:</B>
  <SPAN CLASS=sectref><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">Index</A></SPAN>

  <B CLASS=navlabel>Previous:</B>
  <SPAN CLASS=sectref><A HREF="chapter11.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter11.html">Chapter 11</A></SPAN>

  <HR>
</DIV>
</BODY>
</HTML>