Exercise 7-8

Change the cross-reference program to find all the URLs in a file, and write all the lines on which each distinct URL occurs.

Solution

This is surprisingly easy if you have completed the previous exercises. Chapter 7 of the book has provided the instruction to solve this. This exerise is about “doing it”.

This is the solution strategy:

1. Use the entire project as per Solution to Exercise 7-7. i.e. main.cpp, split.cpp/.h, xref.cpp/.h.
2. Add the find_url function components as per Solution to Exercise 6-0 (Part 4 / 7). i.e. find_urls.cpp/.h, not_url_char.cpp/.h, url_beg.cpp/.h, url_end.cpp/.h.
3. Update the main function so that this bit of code…

// Call xref using split by default. 
map<string, vector<int> > ret = xref(cin);

… is replaced by this (using find_urls)….

// Call xref using find_urls (instead of the default split) 
map<string, vector<int> > ret = xref(cin, find_urls);

Though split.cpp and split.h will not be called directly, the function split may is included by the xref function. So for safety, I will leave it in the project.

The Project

In the following section I, for clarity sake, I shall include the entire project (C++ header and source files).

Source File List

• main.cpp
• find_urls.cpp
• not_url_char.cpp
• split.cpp
• url_beg.cpp
• url_end.cpp
• xref.cpp

Header File List

• find_urls.h
• not_url_char.h
• split.h
• url_beg.h
• url_end.h
• xref.h

Source Files

main.cpp

#include <iostream> // std::cin, std::cout, std::endl
#include <map> // std::map
#include <string> // std::string
#include <vector> // std::vector
#include "xref.h" // xref
#include "find_urls.h" // find_urls

using std::cin; 
using std::cout; 
using std::endl; 
using std::map; 
using std::string; 
using std::vector;

// Find all the lines that refer to each word in the input 
// (S7.3/128) 

int main() { 

  // Call xref using find_urls (instead of the default split) 
  map<string, vector<int> > ret = xref(cin, find_urls);

  // Write the results. 
  for (map<string, vector<int> >::const_iterator it = ret.begin(); it != ret.end(); ++it) {

    // Find number of lines the word has appeared
    vector<int>::size_type numLines = (it->second).size();

    // Write the word
    cout << it->first << " occurs on ";
    if (numLines == 1)
      cout << "line: ";
    else
      cout << "lines: ";

    // Followed by one or more line numbers.
    vector<int>::const_iterator line_it = it->second.begin();
    cout << *line_it;   // write the first line number

    ++line_it;

    // Write the rest of the line numbers, if any.
    while (line_it != it->second.end()) {
      cout << ", " << *line_it;
      ++line_it;
    }

    // Write a new line to separate each word from the next.
    cout << endl;

  }

  return 0; 
} 

find_urls.cpp

#include <string> // string
#include <vector> // vector
#include "url_beg.h" // url_beg
#include "url_end.h" // url_end

using std::string; 
using std::vector;

vector<string> find_urls(const string& s) { 

  vector<string> ret; 
  typedef string::const_iterator iter; 
  iter b = s.begin(), e = s.end();

  // look through the entire input 
  while (b != e) {

    // look for one or more letters followed by ://
    b = url_beg(b, e);

    // if we found it
    if (b != e) {
      // get the rest of the URL
      iter after = url_end(b, e);

      // remember the URL
      ret.push_back(string(b, after));

      // advance b and check for more URLs on this line
      b = after;
    }
  } return ret; 
}

not_url_char.cpp

#include <string> // string, isalnum
#include <algorithm> // find

using std::string;

bool not_url_char(char c) { 

  // characters, in addition to alphanumerics, that can appear in a URL 
  static const string url_ch = "~;/?:@=&$-_.+!*'(),";

  // see whether c can appear in a URL and return the negative 
  return !(isalnum(c) || find(url_ch.begin(), url_ch.end(), c) != url_ch.end() ); 

}

split.cpp

#include <string> // string
#include <vector> // vector
#include <cctype> // isspace
#include <algorithm> // find_if

using std::vector; 
using std::string; 
using std::isspace; 
using std::find_if;

// true if the argument is whitespace, false otherwise 
// (S6.1.1/103) 
bool space(char c) { return isspace(c); }

// false if the argument is whitespace, true otherwise 
// (S6.1.1/103) 
bool not_space(char c) { return !isspace(c); }

// Scan a line and split into words. Return a vector that contains these words. 
// (S6.1.1/103) 
vector<string> split(const string& str) { 
  typedef string::const_iterator iter; vector<string> ret;

  iter i = str.begin(); while (i != str.end()) {

  // Ignore leading blanks
  i = find_if(i, str.end(), not_space);

  // Find end of next word
  iter j = find_if(i, str.end(), space);

  // Copy the characters in ([i, j)
  if (i != str.end())
    ret.push_back(string(i, j));

  // Re-initialize
  i = j;

  } 

  return ret; 

}

url_beg.cpp

#include <string> // string, isalpha
#include <algorithm> // search
#include "not_url_char.h" // not_url_char

using std::string;

string::const_iterator url_beg(string::const_iterator b, string::const_iterator e) { 

  static const string sep = "://"; 
  typedef string::const_iterator iter;

  // i marks where the separator was found iter i = b;

  while ((i = search(i, e, sep.begin(), sep.end() )) != e) {

    // make sure the separator isn't at the beginning or end of the line
    if (i != b && i + sep.size() != e) {

      // beg marks the beginning of the protocol-name
      iter beg = i;
      while (beg != b && isalpha(beg[-1]))
        --beg;

      // is there at least one appropriate character before and after the separator?
      if (beg != i && !not_url_char(i[sep.size()]))
        return beg;
    }

    // the separator we found wasn't part of a URL; advance i past this separator
    i += sep.size();

  } 

  return e; 

}

url_end.cpp

#include <string> // string
#include <vector> // vector
#include <algorithm> // find_if
#include "not_url_char.h" // not_url_char

using std::string;

string::const_iterator url_end(string::const_iterator b, string::const_iterator e) { 
  return find_if(b, e, not_url_char); 
}

xref.cpp

#include <iostream> // std::cin, std::istream
#include <map> // std::map
#include <string> // std::string
#include <vector> // std::vector
#include <algorithm> // std::find
#include "split.h" // split

using std::cin; 
using std::map; 
using std::string; 
using std::vector; 
using std::istream; 
using std::find;

// Find all the lines that refer to each word in the input 
// In this program, the first line is represented by line 1, 
// second line is represented by line 2, etc. 
// (S7.3/126) 
// Adjusted as per Exercise 7-3: store only non-duplicated line numbers. 

map<string, vector<int> > xref(istream& in, vector<string> find_words(const string&) = split) { 

  string line; int line_number = 0; map<string, vector<int> > ret; // map string to vector<int>

  // Read the next line while (getline(in, line)) { ++line_number;

    // Break the input line into words
    vector<string> words = find_words(line);

    // remember that each word occurs on the current line
    for (vector<string>::const_iterator it = words.begin();
         it != words.end(); ++it) {

      // store only non-duplicated line numbers.
      if ( find( ret[*it].begin(), ret[*it].end(), line_number) == ret[*it].end() )
        ret[*it].push_back(line_number);
    }


  }

  return ret; 
}

Header Files

find_urls.h

#ifndef GUARD_FIND_URLS_H
#define GUARD_FIND_URLS_H
#include <vector>
#include <string>

std::vector<std::string> find_urls(const std::string&);

#endif // GUARD_FIND_URLS_H

not_url_char.h

#ifndef GUARD_NOT_URL_CHAR_H
#define GUARD_NOT_URL_CHAR_H

bool not_url_char(char);

#endif // GUARD_NOT_URL_CHAR_H

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

#include <vector>
#include <string>

std::vector<std::string> split(const std::string&);

#endif // GUARD_SPLIT_H

url_beg.h

#ifndef GUARD_URL_BEG_H

#define GUARD_URL_BEG_H

std::string::const_iterator url_beg(std::string::const_iterator, std::string::const_iterator);

#endif // GUARD_URL_BEG_H

url_end.h

#ifndef GUARD_URL_END_H

#define GUARD_URL_END_H

#include <string>

std::string::const_iterator url_end(std::string::const_iterator, std::string::const_iterator);

#endif // GUARD_URL_END_H

xref.h

#ifndef GUARD_XREF_H

#define GUARD_XREF_H

// xref.h

#include <iostream> // std::istream
#include <map> // std::map
#include <string> // std::string
#include <vector> // std::vector
#include "split.h" // split

std::map<std::string, std::vector<int> > 
xref(std::istream&, std::vector<std::string> find_words(const std::string&) = split);

#endif // GUARD_XREF_H

Test Result

Run the program and submit some random text confirms the program works as expected.

hello world http://google.co.uk and http://bbc.co.uk
and http://yahoo.com and maybe http://google.co.uk
also http://bbc.co.uk
and http://yahoo.com
and of course http://google.co.uk
and finally http://w3schools.com
and http://google.com
^Z 
http://bbc.co.uk occurs on lines: 1, 3 
http://google.co.uk occurs on lines: 1, 2, 5 
http://google.com occurs on line: 7 
http://w3schools.com occurs on line: 6 
http://yahoo.com occurs on lines: 2, 4

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000

Exercise 7-7

Change the driver for the cross-reference program so that it writes line if there is only one line and lines otherwise.

Solution

The solution to this exercise is surprisingly simple. To clarify the question a bit – it essentially asks us to have some sort of if-else condition in place.

For instance…

• If the word “apple” occurs only on one line, we print “apple occurs on line: ” (followed by the line number).
• Otherwise, if the word “apple” occurs on multiple lines, we print “apple occurs on lines: ” (followed by the line numbers).

Recall that the Solution to Exercise 7-3 already provides the skeleton project that reports non-duplicated word occurrence line numbers. It therefore makes sense to use that project as the baseline project, and do the adjustment on top of it.

It turns out that there is only one small bit of code that needs changing, and it resides at the main.cpp file (the main function).

This is the original snippet within the main function:

    // Write the word
    cout << it->first << " occurs on line(s): ";

We can change it easily to the following to achieve that if-else conditioning. We essentially resolves the number of non-duplicate line occurences for the word beforehand. We can then use it to construct the if-else logic and display either “line” or “lines” accordingly.

    // Find number of lines the word has appeared
    vector<int>::size_type numLines = (it->second).size();

    // Write the word
    cout << it->first << " occurs on ";
    if (numLines == 1)
      cout << "line: ";
    else
      cout << "lines: ";

Surprisingly simple.

The Project

Simply…

1. Re-use that Project as per Solution to Exercise 7-3.
2. Replace the main.cpp file as per followings.

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include "xref.h"     // xref

using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::string;
using std::vector;

// Find all the lines that refer to each word in the input
// (S7.3/128)
int main()
{
  // Call xref using split by default.
  map<string, vector<int> > ret = xref(cin);

  // Write the results.
  for (map<string, vector<int> >::const_iterator it = ret.begin();
       it != ret.end(); ++it) {

    // Find number of lines the word has appeared
    vector<int>::size_type numLines = (it->second).size();

    // Write the word
    cout << it->first << " occurs on ";
    if (numLines == 1)
      cout << "line: ";
    else
      cout << "lines: ";

    // Followed by one or more line numbers.
    vector<int>::const_iterator line_it = it->second.begin();
    cout << *line_it;   // write the first line number

    ++line_it;
    // Write the rest of the line numbers, if any.
    while (line_it != it->second.end()) {
      cout << ", " << *line_it;
      ++line_it;
    }
    // Write a new line to separate each word from the next.
    cout << endl;
  }

  return 0;
}

Test Result

Running this new version main code gives us the result as expected.

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on lines: 1, 3
banana occurs on lines: 1, 3
mango occurs on line: 4
orange occurs on lines: 1, 2

Reference

Exercise 7-6

Reimplement the gen_sentence program using two vectors: One will hold the fully unwound, generated sentence, and the other will hold the rules and will be used as a stack. Do not use any recursive calls.

Solution

After spending hours scratching my head and still getting stuck on this question, I decided to turn to Google for help. Eventually I discovered this Github Solution Code (uploaded by the Author himself) to this exercise. For the sake of learning, I simply picked out the “bits and pieces” from the Author’s code (such as the core concepts and snippets) and integrated these to my own solution. So let me disclose this upfront – the solution that you are seeing in this page is a result of the great help and pointer from the Author himself. Nevertheless, I believe it is the right thing to do to at least try and understand how the core concept work. The mission of this post is to add some additional documentation to demonstrate that we actually understand the concepts and techniques presented by the Author.

In the followings, I shall:

1. Disclose the project (i.e. the C++ source and header files) that I use in my learning.
2. Test run the job to confirm that it works.
3. Demonstrate that we understand the new concept by manually draw out the step by step logic.

The Project

First, open the baseline project (i.e. the C++ source and header files) as per Solution to Exercise 7-0 (Part 3 / 3). Once the baseline project is opened up in (say) Code::Block, replace the following files with the newer version.

• gen_aux.h – use this newer version.
• gen_aux.cpp – use this newer version.
• gen_sentence.cpp – use this newer version.

Newer Version Souce and Header Files

This summarises the newer version source and header files.

gen_aux.h

#ifndef GUARD_GEN_AUX_H
#define GUARD_GEN_AUX_H

// gen_aux.h

#include <string>             // std::string
#include <vector>             // std::vector
#include "read_grammar.h"     // Grammar

void gen_aux(const Grammar&, const std::string&, std::vector<std::string>&,
             std::vector<std::string>&);

#endif // GUARD_GEN_AUX_H

gen_aux.cpp

#include <string>            // std::string
#include <vector>            // std::vector
#include <stdexcept>         // logic_error

#include "read_grammar.h"    // Grammar, Rule, Rule_collection
#include "bracketed.h"       // bracketed
#include "nrand.h"           // nrand

using std::string;
using std::vector;
using std::logic_error;

// Look up the input Grammar, and expand
// (modified version of S7.4.3/132)
void gen_aux(const Grammar& g, const string& token,
       vector<string>& sentence, vector<string>& tokens) {
  if (!bracketed(token)) {
    sentence.push_back(token);
  } else {
    // locate the rule that corresponds to `token'
    Grammar::const_iterator it = g.find(token);

    if (it == g.end())
      throw logic_error("empty rule");

    // fetch the set of possible rules
    const Rule_collection& c = it->second;

    // from which we select one at random
    const Rule& r = c[nrand(c.size())];

    // push rule's tokens onto stack of tokens
    // (in reverse order, because we're pushing and popping from the back)
    for (Rule::const_reverse_iterator i = r.rbegin(); i != r.rend(); ++i)
      tokens.push_back(*i);
  }
}

gen_sentence.cpp

#include <vector>             // std::vector
#include <string>             // std::string
#include "read_grammar.h"     // Grammar
#include "gen_aux.h"          // gen_aux

using std::vector;
using std::string;

// Generate a sentence based on a Grammar object
// (modified version of S7.4.3/132)
vector<string> gen_sentence(const Grammar& g) {
  vector<string> sentence;
  vector<string> tokens;
  tokens.push_back("<sentence>");

  while (!tokens.empty()) {
    string token = tokens.back();
    tokens.pop_back();
    gen_aux(g, token, sentence, tokens);
  }

  return sentence;
}

Test Result

Note: the result might differ when you run the job due to the nrand(). Core concept remains true though.

<noun>          cat
<noun>          dog
<noun>          table
<noun-phrase>   <noun>
<noun-phrase>   <adjective> <noun-phrase>
<adjective>     large
<adjective>     brown
<adjective>     absurd
<verb>          jumps
<verb>          sits
<location>      on the stairs
<location>      under the sky
<location>      wherever it wants
<sentence>      the <noun-phrase> <verb> <location>
^Z
the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Understanding the concept

Let’s use the first output sentence to illustrate our understanding of the core concept used by the gen_sentence and gen_aux functions.

the large brown dog sits wherever it wants

The billion dollar question, how did the program generate this line?

To demonstrate my understanding, I’ve manually put together a couple of simple Excel tables to walk through the logic.

Recall that this is the input grammar table:

The gen_sentence and gen_aux can give the following output values:

Some Notes To This Example

For some extra clarity, I include here a brief explanation of what each column means.

tokens non-empty?

If non-empty, the while loop inside the gen_sentence step would keep expanding tokens and construct the string sentence. Otherwise, the while loop stop and we have our sentence! (Note that we start by expanding the top level “<sentence>”)

vector<string> sentence;
vector<string> tokens;
tokens.push_back("<sentence>");
while (!tokens.empty()) {
    // some codes to expand <sentence> and construct the string sentence.
}
return sentence;

const string& token

This is the last element of tokens, implied by this statement within the gen_sentence step:

string token = tokens.back();

Is token bracketed?

If the token is bracketed, it implies the token corresponds to a Grammar category and need expanding. If it is not bracketed, we  simply append the text the the string sentence.

if (!bracketed(token)) {
    // some codes to construct the string sentence.
} else {
    // some codes to expand the token.
}

const Rule& r

If the token is bracketed (i.e. a Grammar category), the const Rule& r is essentially the Grammar rule. I highlight this in orange.

vector<string>& sentence

If the token is not bracketed, we simply append the text to the string sentence. This column shows what the constructed string sentence look like. I highlight the newly appended element in blue.

(Updated) vector<string>& tokens

This is the interesting part and is updated by a combination of the gen_sentence and gen_aux steps.

• The tokens.pop_back() statement remove the last element of tokens (hence the strike-through in the table).
• If token (i.e. the token column) is bracketed, the for loop within the gen_aux function appends the entire rule (highlighted in orange) in reverse order. This is a very clever technique to get the tokens expand and string sentence constructed in the expected order. (it’s easier to visualise this via the Excel table above instead of explaning in writing!).

Summary

Walking through the logic as illustrated in the Excel table, the program generates and return the complete string sentence. The actual sentence may get constructed differently due to the nrand().

Reference

Exercise 7-5

Reimplement the grammar program using a list as the data structure in which we build the sentence.

Solution

This exercise is somewhat similar to Exercise 5-2 / 5-3 / 5-4, in which our objective is to replace all the relevant vector with list.

Here is the solution strategy:

1. Make a copy of the entire project as per Solution to Exercise 7-0 (Part 3 / 3) – i.e. the textbook Grammar / Generate Sentence program.
2. Replace all the vector with list, in main.cpp, gen_sentence.cpp/.h, gen_aux.cpp/.h.

The main.cpp function

Start with the main program – we notice the:

#include <vector>

// Some codes....

using std::vector;

// Some codes....

vector<string> sentence = gen_sentence(grammar);

// Some codes....

vector<string>::const_iterator it = sentence.begin();

We simply need to replace all the vector with list.

Here we can see the return type of the function gen_sentence needs to be changed from vector<string> to list<string>.

The gen_sentence function

We need to replace all the vector with list in the gen_sentence.cpp (source file) and gen_sentence.h (header file).

gen_sentence.cpp

#include <vector>

// Some codes....

using std::vector;

// Some codes....

list<string> gen_sentence(const Grammar& g)
{
  list<string> ret;
  gen_aux(g, "<sentence>", ret);
  return ret;
}

gen_sentence.h

// Some codes....

#include <vector>

std::vector<std::string> gen_sentence(const Grammar&);

// Some codes....

From this we see that we may need to adjust the gen_aux function to cater for the vector-to-list change.

The gen_aux function

Looking at the gen_aux.cpp (source file) and gen_aux.h (header file) reveals that we need to replace the vector with list.

gen_aux.cpp

#include <vector>

// Some codes....

using std::vector;

// Some codes....

void gen_aux(const Grammar& g, const string& word, vector<string>& ret)
{
  // Some codes....
}

gen_aux.h

// Some codes....

#include <vector>

void gen_aux(const Grammar&, const std::string&, std::vector<std::string>&);

// Some codes....

The Project

Just simply make a copy of the entire project as per Solution to Exercise 7-0 (Part 3 / 3), and do the vector-to-list replacement as mentioned above.

i.e.  use the following (list version) files as replacement of the original  (vector version) files:

Source File List (to change)

• main.cpp
• gen_sentence.cpp
• gen_aux.cpp

Header File List (to change)

• gen_sentence.h
• gen_aux.h

Source Files (to change)

main.cpp

#include <iostream>          // std::cin, std::cout, std::endl
#include <string>            // std::string
#include <list>              // std::list

#include "read_grammar.h"    // read_grammar
#include "gen_sentence.h"    // gen_sentence

#include <ctime>             // Added. std::time
#include <cstdlib>           // Added. std::srand

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::list;

using std::srand;
using std::time;

int main()
{
  // Uncomment thhe below srand() to seed new randomness in new job-runs.
  // srand(time(NULL));

  Grammar grammar = read_grammar(cin);

  for (int i = 0; i != 5; ++i) {

    // generate the sentence
    list<string> sentence = gen_sentence(grammar);

    // write the first word, if any
    list<string>::const_iterator it = sentence.begin();
    if (!sentence.empty()) {
      cout << *it;
      ++it;
    }

    // write the rest of the words, each preceded by a space
    while (it != sentence.end()) {
      cout << " " << *it;
      ++it;
    }

    cout << endl;
  }

  return 0;
}

gen_sentence.cpp

#include <list>             // std::list
#include <string>             // std::string
#include "read_grammar.h"     // Grammar
#include "gen_aux.h"          // gen_aux

using std::list;
using std::string;

// Generate a sentence based on a Grammer object
// (S7.4.3/132)
list<string> gen_sentence(const Grammar& g)
{
  list<string> ret;
  gen_aux(g, "<sentence>", ret);
  return ret;
}

gen_aux.cpp

#include <string>            // std::string
#include <list>              // std::list
#include <stdexcept>         // logic_error

#include "read_grammar.h"    // Grammar, Rule, Rule_collection
#include "bracketed.h"       // bracketed
#include "nrand.h"           // nrand

using std::string;
using std::list;
using std::logic_error;

// Look up the input Grammar, and expand
// (S7.4.3/132)
void gen_aux(const Grammar& g, const string& word, list<string>& ret)
{
  if (!bracketed(word)) {
    ret.push_back(word);
  } else {
    // locate the rule that corresponds to word
    Grammar::const_iterator it = g.find(word);
    if (it == g.end())
      throw logic_error("empty rule");

    // fetch the set of possible rules
    const Rule_collection& c = it->second;

    // from which we select one at random
    const Rule& r = c[nrand(c.size())];

    // recursively expand the selected rule
    for (Rule::const_iterator i = r.begin(); i != r.end(); ++i)
      gen_aux(g, *i, ret);
  }
}

gen_sentence.h

#ifndef GUARD_GEN_SENTENCE_H
#define GUARD_GEN_SENTENCE_H

// gen_sentence.h

#include <string>            // std::string
#include <list>              // std::list
#include "read_grammar.h"    // Grammar

std::list<std::string> gen_sentence(const Grammar&);

#endif // GUARD_GEN_SENTENCE_H

gen_aux.h

#ifndef GUARD_GEN_AUX_H
#define GUARD_GEN_AUX_H

// gen_aux.h

#include <string>             // std::string
#include <list>               // std::list
#include "read_grammar.h"     // Grammar

void gen_aux(const Grammar&, const std::string&, std::list<std::string>&);

#endif // GUARD_GEN_AUX_H

Test Program

Following replace all the vector-to-list replacements, and resubmit the program with the same input, we get the results as expected. In my case:

<noun>          cat
<noun>          dog
<noun>          table
<noun-phrase>   <noun>
<noun-phrase>   <adjective> <noun-phrase>
<adjective>     large
<adjective>     brown
<adjective>     absurd
<verb>          jumps
<verb>          sits
<location>      on the stairs
<location>      under the sky
<location>      wherever it wants
<sentence>      the <noun-phrase> <verb> <location>
^Z
the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Reference

Exercise 7-4

The output produced by the cross-reference program will be ungainly if the input file is large. Rewrite the program to break up the output if the lines get too long.

Background

The original cross-reference program as per Solution to Exercise 7-0 (Part 2 / 3) lacks control in terms of output line length. For example, if my input “article” contains tons of repeated words, such as this:

apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple
orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange
orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange
orange orange orange orange orange orange orange
banana banana banana
banana
banana banana banana
banana banana
banana banana banana banana banana banana banana
banana banana
apple apple apple apple apple apple apple apple apple apple apple apple apple apple
apple apple apple apple apple apple apple apple apple apple apple apple apple apple
apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple

Given the above input, the default program produces output summary like this:

apple occurs on line(s): 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 1
3, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13
banana occurs on line(s): 5, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10, 10
orange occurs on line(s): 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 4, 4, 4, 4, 4, 4, 4

The output lines may become very long – i.e. user may need to scroll left and right to see all the line numbers (not very user friendly). A bit “ungainly” as suggested by the author.

This therefore motivates us to add a control in place that ensures the output line length never exceeds a pre-defined value. i.e. if we set max line length to be 30 characters, and the output result contains 100 characters, the program should be able to split into 4 lines (first 3 lines contain 30 characters, and the 4th line contains 10 characters). This way, the user won’t need to scroll left and right to see all line numbers – more user friendly.

The following section will describe a solution to this problem.

Solution

This is our solution strategy:

1. Make a copy of the project (i.e. source and header files) as per Solution to Exercise 7-0 (Part 2 / 3).
2. Update the main program to incorporate the desirable line-length control.

Incorporate Line-length Control

First of all, we need define a const string::size_type lineLength, which is the maximum line-length of the output.

We then need to have a means to concatenate various output values.

In the Solution to Exercise 5-1, we learnt that the variable type std::ostringstream (of <sstream>  directive) is way more superior in concatenation in comparison to std::string (of <string> directive). i.e. there seem to be much less constraints in terms of concatenating values of different types for a std::ostringstream than std::string. For this reason, we shall use std::ostringstream to store output. Note also that ostreamstring can be converted into a string easily.

When displaying the line numbers for each word, we implement a if-condition to ensure the line length doesn’t exceed our pre-defined lineLength. The modulus operator (%) will come in handy for this.

The Project

Just simply re-use the entire project from Solution to Exercise 7-0 (Part 2 / 3), and replace the main program with the following. (Note that for illustration sake the pre-defined lineLength is set to 60 characters max per line).

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include <sstream>    // std::ostringstream
#include "xref.h"     // xref

using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::string;
using std::vector;
using std::ostringstream;

// Find all the lines that refer to each word in the input
// (S7.3/128)
int main()
{
  // Call xref using split by default.
  map<string, vector<int> > ret = xref(cin);

  // Set the width of output line to this max width limit.
  const string::size_type lineLength = 60;

  // Write the results.
  for (map<string, vector<int> >::const_iterator it = ret.begin();
       it != ret.end(); ++it) {

    // We use ostreamstring for its powerful concatenation properties.
    // We can pretty much concatenate anything to an ostreamstring, in
    // comparison to string.
    ostringstream outputStream;

    // Write the word
    outputStream << it->first << " occurs on line(s): ";

    // Followed by one or more line numbers.
    vector<int>::const_iterator line_it = it->second.begin();
    outputStream << *line_it;
    ++line_it;

    // Write the rest of the line numbers, if any.
    while (line_it != it->second.end()) {
      outputStream << ", " << *line_it;
      ++line_it;
    }

    // Break outputStream into multiple lines with max width of lineLength.
    string outputLine = outputStream.str();
    for (string::size_type i = 0; i != outputLine.size(); ++i ) {
      if (i % lineLength == 0) {
        cout << endl;
      }
      cout << outputLine[i];
    }

    // Write a new line to separate each word from the next.
    cout << endl;
  }

  return 0;
}

Test Program

Re-submitting the same input (see the top of this post), our output now looks much more “controlled”, in terms of line length.

apple occurs on line(s): 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1
1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 1
2, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 1
3, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1
3, 13, 13, 13, 13, 13, 13, 13, 13, 13

banana occurs on line(s): 5, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 9
, 9, 9, 9, 9, 10, 10

orange occurs on line(s): 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4
, 4

Not perfect, but better.

Reference

Exercise 7-3

The cross-reference program from S7.3/126 could be improved: As it stands, if a word occurs more than once on the same input line, the porgram will report that line multiple times. Change the code so that it detects multiple occurences of the same line number and inserts the line number only once.

Background

Remember that when we run the Chapter 7 cross-reference program (i.e. Solution to Exercise 7-0 (Part 2 / 3) ), we have the following test results:

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2, 2

Note:

1. Recall that the xref program assumes the first line as line 1 (instead of 0), second line as line 2 (instead of 1). This is as designed.
2. The word “orange” appears on line 2 twice. So when it comes to being displayed in the summary, it shows the line number “2” twice.
3. The objective of this exercise is to only store non-duplicated line number.

Solution Strategy

We only need to make a very small enhancement – to adjust the xref function by adding a small bit of code. Include a if condition to check whether the line number already exists for the corresponding associative array. Use the find utility of the <algorithm> directive to help us do this.

The Project

We can reuse the entire project as per Solution to Exercise 7-0 (Part 2 / 3). Simply replace the xref.cpp file with this new one:

xref.cpp

#include <iostream>   // std::cin, std::istream
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include <algorithm>  // std::find
#include "split.h"    // split


using std::cin;
using std::map;
using std::string;
using std::vector;
using std::istream;
using std::find;

// Find all the lines that refer to each word in the input
// In this program, the first line is represented by line 1,
// second line is represented by line 2, etc.
// (S7.3/126)
// Adjusted as per Exercise 7-3: store only non-duplicated line numbers.
map<string, vector<int> >
xref(istream& in, vector<string> find_words(const string&) = split)
{
  string line;
  int line_number = 0;
  map<string, vector<int> > ret;  // map string to vector<int>

  // Read the next line
  while (getline(in, line)) {
    ++line_number;

    // Break the input line into words
    vector<string> words = find_words(line);

    // remember that each word occurs on the current line
    for (vector<string>::const_iterator it = words.begin();
         it != words.end(); ++it) {

      // store only non-duplicated line numbers.
      if ( find( ret[*it].begin(), ret[*it].end(), line_number) == ret[*it].end() )
        ret[*it].push_back(line_number);
    }
  }

  return ret;
}

Test Program

Re-submitting the program with the same input, the program now produces non-duplicated line numbers per associative array (word).

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2

Reference

Exercise 7-2

Extend the program in S4.2.3/64 to assign letter grades by ranges:

A 90-100
B 80-89.99...
C 70-79.99...
D 60-69.99...
F < 60

Solution

The strategy:

1. Make a copy of the entire projects from Solution to Exercise 4-0. (i.e. the sample programs in Chapter 4 of the textbook).
2. Write a new home-made getLetterGrade function that returns a string letterGrade given an input (numeric) double grade, using if/else condition.
3. In the main program, use the getletterGrade function to compute the student’s string letterGrade. Have an associative array letterGradeCount that maps a string (letter grade) to integer (to keep track of letter grade occurrences).

The Program

Here summarises the entire Code::Block Project, including the header and source files.

Source File List

• main.cpp
• getletterGrade.cpp
• grade.cpp
• median.cpp
• Student_info.cpp

Header File List

• getletterGrade.h
• grade.h
• median.h
• Student_info.h

Source Files

main.cpp

#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <map>
#include "grade.h"
#include "Student_info.h"
#include "getLetterGrade.h"

using std::cin;
using std::cout;
using std::endl;
using std::domain_error;
using std::max;
using std::setprecision;
using std::sort;
using std::streamsize;
using std::string;
using std::vector;
using std::map;

int main()
{
  vector<Student_info> students;
  Student_info record;
  string::size_type maxlen = 0;   // the length of the longest name

  // read and store all the student's data.
  // Invariant:   students contain all the student records read so far
  //              maxlen contains the length of the longest name in students
  while (read(cin, record))
  {
    // find the length of longest name
    maxlen = max(maxlen, record.name.size());
    students.push_back(record);
  }

  // alphabetize the student records
  sort(students.begin(), students.end(), compare);

  // write the names and grades
  map<string, int> letterGradeCount;   // To store letter grade occurrences.
  for (vector<Student_info>::size_type i = 0;
       i != students.size(); ++i)
  {
    //write the name, padded on teh right to maxlen + 1 characters
    cout << students[i].name
         << string(maxlen + 1 - students[i].name.size(), ' ');

     //compute and write the grade
    try
    {
      double final_grade = grade(students[i]);
      string letterGrade = getLetterGrade(final_grade);
      letterGradeCount[letterGrade]++;         // Count Letter Grades.
      streamsize prec = cout.precision();
      cout << setprecision(3) << final_grade
           << setprecision(prec) << " (" << letterGrade << ")";
    }
    catch (domain_error e)
    {
      cout << e.what();
    }
    cout << endl;
  }
  // Display letter grade summary
  cout << "\nLetter Grade Summary" << endl;
  for (map<string, int>::const_iterator i = letterGradeCount.begin();
      i != letterGradeCount.end(); ++i)
    cout << i->first << ": " << i->second << endl;

  return 0;
}

getletterGrade.cpp

#include <string>

using std::string;

// Convert a numeric grade into a letter grade.
// (For Exercise 7-2)
string getLetterGrade(double grade) {

  string ret;

  if (grade >= 90.0)
    ret = "A";
  else if (grade >= 80.0 && grade < 90.0)
    ret = "B";
  else if (grade >= 70.0 && grade < 80.0)
    ret = "C";
  else if (grade >= 60.0 && grade < 70.0)
    ret = "D";
  else
    ret = "F";

  return ret;
}

grade.cpp

#include <stdexcept>
#include <vector>
#include "grade.h"
#include "median.h"
#include "Student_info.h"

using std::domain_error;
using std::vector;

// definitions for the grade functions from S4.1/52, S4.1.2/54, S4.2.2/63

// compute a student's overall grade from midterm and final exam
// grades and homework grade (S4.1/52)
double grade(double midterm, double final, double homework)
{
    return 0.2 * midterm + 0.4 * final + 0.4 * homework;
}

// compute a student's overall grade from midterm and final exam grades
// and vector of homework grades.
// this function does not copy its argument, because median (function) does it for us.
// (S4.1.2/54)
double grade(double midterm, double final, const vector<double>& hw)
{
    if (hw.size() == 0)
        throw domain_error("student has done no homework");
    return grade(midterm, final, median(hw));
}

// this function computes the final grade for a Student_info object
// (S4.2.2/63)
double grade(const Student_info& s)
{
    return grade(s.midterm, s.final, s.homework);
}

median.cpp

// source file for the median function
#include <algorithm>
#include <stdexcept>
#include <vector>

using std::domain_error;
using std::sort;
using std::vector;

// compute the median of a vector<double>
// (S4.1.1/53)
double median(vector<double> vec)
{
    typedef vector<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

    sort(vec.begin(),vec.end());

    vec_sz mid = size/2;

    return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}

Student_info.cpp

#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h
#include <iostream>
#include <string>
#include <vector>

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

</p>

Header Files

getletterGrade.h

#ifndef GUARD_GETLETTERGRADE_H
#define GUARD_GETLETTERGRADE_H

// getLetterGrade.h

#include <string>

std::string getLetterGrade(double);

#endif // GUARD_GETLETTERGRADE_H

grade.h

#ifndef GUARD_GRADE_H
#define GUARD_GRADE_H

//grade.h
#include <vector>
#include "Student_info.h"

double grade(double, double, double);
double grade(double, double, const std::vector<double>&);
double grade(const Student_info&);

#endif // GUARD_GRADE_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

// median.h - final version
#include <vector>
double median(std::vector<double>);

#endif // GUARD_MEDIAN_H

Student_info.h

#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h
#include <iostream>
#include <string>
#include <vector>

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

Test Program

I test the program by submitting a list of sample student grades. The program automatically compute and display the numeric and letter grades. It also creates a letter grade summary to count occurances per letter grade.

johnny   90 90 90 90 90
jason    85 85 85 85 85
billy    82 82 82 82 82
fred     80 80 80 80 80
frank    70 70 70 70 70
jay      66 66 66 66 66
bob      60 60 60 60 60
mary     50 50 50 50 50
ann      40 40 40 40 40
bill     30 30 30 30 30
goat     10 10 10 10 10
dog      0  0  0  0  0
^Z
^Z
ann    40 (F)
bill   30 (F)
billy  82 (B)
bob    60 (D)
dog    0 (F)
frank  70 (C)
fred   80 (B)
goat   10 (F)
jason  85 (B)
jay    66 (D)
johnny 90 (A)
mary   50 (F)

Letter Grade Summary
A: 1
B: 3
C: 1
D: 2
F: 5

Reference

Exercise 7-1

Extend the program from S7.2/124 to produce its output sorted by occurrence count. That is, the output should group all the words that occur once, followed by those that occur twice, and so on.

Solution

The strategy:

1. Start with the program from S7.2/124. i.e. The main program in Solution to Exercise 7-0 (Part 1 / 3).
2. Have a new (associative array) map<int, vector<string> > wordsByFreq to map int (word occurring frequency) to vector<string> (all the words at that occurring frequency). The key of this map is essentially the int frequency. In other words, this map is by default sort by the int frequency (as it is the key to this map).
3. We populate the map<string, int> counters as usual. Once it is fully populated, we use it to populate our wordsByFreq.
4. Once the wordsByFreq is fully populated, we use it to display all the words grouped by frequency.

The Program

The program is surprisingly easy to write / extend. As long as we know what a map is and how it works, this program should be fairly easy to understand.

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector

using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::string;
using std::vector;

int main()
{
  string s;
  map<string, int> counters;                // Store each word and an
                                            // associated counter
  map<int, vector<string> > wordsByFreq;    // Store all the words for
                                            // each frequency

  // read the input, keeping track of each word and how often we see it
  while (cin >> s)
    ++counters[s];

  cout << "\nDisplay words and associating frequency." << endl;
  // write the words and associated counts
  for (map<string, int>::const_iterator i = counters.begin();
       i != counters.end(); ++i) {
    cout << i->first << "\t" << i->second << endl;

    // Obtain words by frequency
    wordsByFreq[i->second].push_back(i->first);
  }

  // Display words by frequency
  cout << "\nDisplay words grouped by frequency." << endl;
  for (map<int, vector<string> >::const_iterator i = wordsByFreq.begin();
       i != wordsByFreq.end(); ++i) {
    cout << "\nFrequency: " << i->first << endl;

    for (vector<string>::const_iterator j = i->second.begin();
         j != i->second.end(); ++j)
      cout << *j << endl;

  }

  return 0;
}

Test Program

I am going to submit the same set of test input as per the word counting program of Solution to Exercise 7-0 (Part 1 / 3). The result looks correct.

apple orange banana
orange orange
apple banana
mango
^Z

Display words and associating frequency.
apple   2
banana  2
mango   1
orange  3

Display words grouped by frequency.

Frequency: 1
mango

Frequency: 2
apple
banana

Frequency: 3
orange

Reference

Exercise 7-0

Compile, execute, and test the programs in this chapter.

Solution

In Chapter 7 of the textbook there are 3 core concepts / programs introduced. For ease of documentation I shall dice this up into 3 parts as followings – simply click the hyperlink to drill down to see the post corresponding to the particular part.

Exercise 7-0 (Part 1 / 3): The Count-word Program.Relating to section 7.2 of the textbook (page 124-126). Use associative arrays to count words – in this particular exercise, we shall use the map from the standard library.

Exercise 7-0 (Part 2 / 3): The Cross-reference Program. Relating to section 7.3 of the textbook (page 126-129). Use associative arrays to find all the lines that refer to each word in the input.

Exercise 7-0 (Part 3 / 3): The Gen-sentence Program. Relating to section 7.4 of the textbook (page 129-136). One of my personal favourite. Use a combination of associative arrays and random number generator to generate a set of random sentences, based on a set of predefined Grammar Rules.

Reference