chapter15.html

think like a computer scientist

  return numElements;
}
</PRE>

<P>Why do we have to prevent client programs from changing 
<TT>getNumElements</TT>? What are the invariants for this type, and how could a
client program break an invariant. As we look at the rest of the <TT>Set</TT> 
member function, see if you can convince yourself that they all maintain the 
invariants.</P>

<P>When we use the <TT>[]</TT> operator to access the <TT>apvector</TT>, it 
checks to make sure the index is greater than or equal to zero and less than 
the length of the <TT>apvector</TT>. To access the elements of a set, though, 
we need to check a stronger condition. The index has to be less than the number
of elements, which might be smaller than the length of the <TT>apvector</TT>.
</P>

<PRE>
apstring Set::getElement (int i) const
{
  if (i &lt; numElements) {
    return elements[i];
  } else {
    cout << "Set index out of range." << endl;
    exit (1);
  }
}
</PRE>

<P>If <TT>getElement</TT> gets an index that is out of range, it prints an 
error message (not the most useful message, I admit), and exits.</P>

<P>The interesting functions are <TT>find</TT> and <TT>add</TT>. By now, the 
pattern for traversing and searching should be old hat:</P>

<PRE>
int Set::find (const apstring& s) const
{
  for (int i=0; i&lt;numElements; i++) {
    if (elements[i] == s) return i;
  }
  return -1;
}
</PRE>

<P>might be useful to make it return the index of the element.</P>

<PRE>
int Set::add (const apstring& s)
{
  // if the element is already in the set, return its index
  int index = find (s);
  if (index != -1) return index;

  // if the apvector is full, double its size
  if (numElements == elements.length()) {
    elements.resize (elements.length() * 2);
  }

  // add the new elements and return its index
  index = numElements;
  elements[index] = s;
  numElements++;
  return index;
}
</PRE>

<P>The tricky thing here is that <TT>numElements</TT> is used in two ways. It 
is the number of elements in the set, of course, but it is also the index of 
the next element to be added.</P>

<P>It takes a minute to convince yourself that that works, but consider this: 
when the number of elements is zero, the index of the next element is 0. When 
the number of elements is equal to the length of the <TT>apvector</TT>, that 
means that the vector is full, and we have to allocate more space (using
<TT>resize</TT>) before we can add the new element.</P>

<P>Here is a state diagram showing a <TT>Set</TT> object that initially 
contains space for 2 elements.</P>

<P CLASS=1><IMG SRC="images/set.png" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/set.png"></P>

<P>Now we can use the <TT>Set</TT> class to keep track of the cities we find in
the file. In <TT>main</TT> we create the <TT>Set</TT> with an initial size 
of 2:</P>

<PRE>
  Set cities (2);
</PRE>

<P>Then in <TT>processLine</TT> we add both cities to the <TT>Set</TT> and 
store the index that gets returned.</P>

<PRE>
  int index1 = cities.add (city1);
  int index2 = cities.add (city2);
</PRE>

<P>I modified <TT>processLine</TT> to take the <TT>cities</TT> object as a 
second parameter.</P>


<BR><BR>
<H3>15.7 <TT>apmatrix</TT></H3>

<P>An <TT>apmatrix</TT> is similar to an <TT>apvector</TT> except it is 
two-dimensional. Instead of a length, it has two dimensions, called 
<TT>numrows</TT> and <TT>numcols</TT>, for ``number of rows'' and ``number of 
columns.''</P>

<P>Each element in the matrix is indentified by two indices; one specifies the 
row number, the other the column number.</P>

<P>To create a matrix, there are four constructors:</P>

<PRE>
  apmatrix<char> m1;
  apmatrix<int> m2 (3, 4);
  apmatrix<double> m3 (rows, cols, 0.0);
  apmatrix<double> m4 (m3);
</PRE>

<P>The first is a do-nothing constructor that makes a matrix with both 
dimensions 0. The second takes two integers, which are the initial number of 
rows and columns, in that order.  The third is the same as the second, except 
that it takes an additional parameter that is used to initialized the elements 
of the matrix. The fourth is a copy constructor that takes another 
<TT>apmatrix</TT> as a parameter.</P>

<P>Just as with <TT>apvectors</TT>, we can make <TT>apmatrix</TT>es with any 
type of elements (including <TT>apvector</TT>s, and even <TT>apmatrix</TT>es).
</P>

<P>To access the elements of a matrix, we use the <TT>[]</TT> operator to 
specify the row and column:</P>

<PRE>
  m2[0][0] = 1;
  m3[1][2] = 10.0 * m2[0][0];
</PRE>

<P>If we try to access an element that is out of range, the program prints an 
error message and quits.</P>

<P>The <TT>numrows</TT> and <TT>numcols</TT> functions get the number of rows 
and columns. Remember that the row indices run from 0 to <TT>numrows() -1</TT> 
and the column indices run from 0 to <TT>numcols() -1</TT>.</P>


<P>The usual way to traverse a matrix is with a nested loop. This loop sets 
each element of the matrix to the sum of its two indices:</P>

<PRE>
  for (int row=0; row < m2.numrows(); row++) {
    for (int col=0; col < m2.numcols(); col++) {
      m2[row][col] = row + col;
    }
  }
</PRE>

<P>This loop prints each row of the matrix with tabs between the elements and 
newlines between the rows:</P>

<PRE>
  for (int row=0; row < m2.numrows(); row++) {
    for (int col=0; col < m2.numcols(); col++) {
      cout << m2[row][col] << "\t";
    }
    cout << endl;
  }
</PRE>


<BR><BR>
<H3>15.8 A distance matrix</H3>

<P>Finally, we are ready to put the data from the file into a matrix. 
Specifically, the matrix will have one row and one column for each city.</P>

<P>We'll create the matrix in <TT>main</TT>, with plenty of space to spare:</P>

<PRE>
  apmatrix<int> distances (50, 50, 0);
</PRE>

<P>Inside <TT>processLine</TT>, we add new information to the matrix by getting
the indices of the two cities from the <TT>Set</TT> and using them as matrix 
indices:</P>

<PRE>
  int dist = convertToInt (distString);
  int index1 = cities.add (city1);
  int index2 = cities.add (city2);

  distances[index1][index2] = distance;
  distances[index2][index1] = distance;
</PRE>

<P>Finally, in <TT>main</TT> we can print the information in a
human-readable form:</P>

<PRE>
  for (int i=0; i&lt;cities.getNumElements(); i++) {
    cout << cities.getElement(i) << "\t";

    for (int j=0; j<=i; j++) {
      cout << distances[i][j] << "\t";
    }
    cout << endl;
  }

  cout << "\t";
  for (int i=0; i&lt;cities.getNumElements(); i++) {
    cout << cities.getElement(i) << "\t";
  }
  cout << endl;
</PRE>

<P>This code produces the output shown at the beginning of the chapter. The 
original data is available from this book's web page.</P>


<BR><BR>
<H3>15.9 A proper distance matrix</H3>

<P>Although this code works, it is not as well organized as it should be. Now 
that we have written a prototype, we are in a good position to evaluate the 
design and improve it.</P>

<P>What are some of the problems with the existing code?</P>

<OL>
  <LI>We did not know ahead of time how big to make the distance matrix, so we 
  chose an arbitrary large number (50) and made it a fixed size. It would be 
  better to allow the distance matrix to expand in the same way a <TT>Set</TT> 
  does. The <TT>apmatrix</TT> class has a function called <TT>resize</TT> that 
  makes this possible.</LI><BR><BR>

  <LI>The data in the distance matrix is not well-encapsulated. We have to pass
  the set of city names and the matrix itself as arguments to 
  <TT>processLine</TT>, which is awkward. Also, use of the distance matrix is 
  error prone because we have not provided accessor functions that perform 
  error-checking. It might be a good idea to take the <TT>Set</TT> of city 
  names and the <TT>apmatrix</TT> of distances, and combine them into a single 
  object called a <TT>DistMatrix</TT>.</LI>
</OL>

<P>Here is a draft of what the header for a <TT>DistMatrix</TT> might look 
like:</P>

<PRE>
class DistMatrix {
private:
  Set cities;
  apmatrix&lt;int&gt; distances;

public:
  DistMatrix (int rows);

  void add (const apstring& city1, const apstring& city2, int dist);
  int distance (int i, int j) const;
  int distance (const apstring& city1, const apstring& city2) const;
  apstring cityName (int i) const;
  int numCities () const;
  void print ();
};
</PRE>

<P>Using this interface simplifies <TT>main</TT>:</P>

<PRE>
void main ()
{
  apstring line;
  ifstream infile ("distances");
  DistMatrix distances (2);

  while (true) {
    getline (infile, line);
    if (infile.eof()) break;
    processLine (line, distances);
  }

  distances.print ();
}
</PRE>

<P>It also simplifies <TT>processLine</TT>:</P>

<PRE>
void processLine (const apstring& line, DistMatrix& distances)
{
  char quote = '\"';
  apvector<int> quoteIndex (4);
  quoteIndex[0] = line.find (quote);
  for (int i=1; i&lt;4; i++) {
    quoteIndex[i] = find (line, quote, quoteIndex[i-1]+1);
  }

  // break the line up into substrings
  int len1 = quoteIndex[1] - quoteIndex[0] - 1;
  apstring city1 = line.substr (quoteIndex[0]+1, len1);
  int len2 = quoteIndex[3] - quoteIndex[2] - 1;
  apstring city2 = line.substr (quoteIndex[2]+1, len2);
  int len3 = line.length() - quoteIndex[2] - 1;
  apstring distString = line.substr (quoteIndex[3]+1, len3);
  int distance = convertToInt (distString);

  // add the new datum to the distances matrix
  distances.add (city1, city2, distance);
}
</PRE>

<P>I will leave it as an exercise to you to implement the member functions of 
<TT>DistMatrix</TT>.</P>


<BR><BR>
<H3>15.10 Glossary</H3>

<DL>
  <DT>ordered set:</DT><DD> A data structure in which every element appears 
  only once and every element has an index that identifies it.</DD>

  <DT>stream:</DT><DD> A data structure that represents a ``flow'' or sequence 
  of data items from one place to another. In C++ streams are used for input 
  and output.</DD>

  <DT>accumulator:</DT><DD> A variable used inside a loop to accumulate a 
  result, often by getting something added or concatenated during each 
  iteration.</DD>
</DL>

<BR>
<DIV CLASS=navigation><HR>
  <TABLE ALIGN=center WIDTH="100%" CELLPADDING=0 CELLSPACING=2>
  <TR>
    <TD><A HREF="app1.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/app1.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="chapter14.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter14.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 15</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="app1.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/app1.html">Appendix A</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="chapter14.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter14.html">Chapter 14</A></SPAN>

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