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

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

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

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

This is part 3 of the 3-part Exercise 7-0. Click here to see the other parts.

Exercise Exercise 7-0 (Part 3 / 3)

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.

Background

This is one of my current favourite exercise – quite hard to understand at first, but once you’ve got it, all becomes so clear (and that burst of satisfying laughter when things clicked in the end – “Wow this is so cool!”). This exercise is about generating a random sentence, based on an input “Grammar” definition that we provide to the program. The input Grammar definition table (as per S7.4/129) is displayed below – column 1 lists the categories, and column 2 the corresponding rules.

<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>

The program generates a random sentence based on the category “<sentence>” – it then recursively expand the associating rules in a “random” manner.

My aim of this post is to summarise all the C++ source and header files (in the form of a complete Code::Block project), run the program, and confirms that the program works as expected. As Andrew Koeing / Barbara Moo (Authors of the book) have already gone through a great deal on explaining how this entire program works, I believe it is appropriate, rather than repeat explaining how this program works here, to just simply suggest to refer to the text book – see Section 7.4 (Page 129) for the detail explanation.

A Note on Random Number Generator

The source code nrand.cpp contains a very clever approach to generate a random number within a desirable range in an evenly distributed manner. The Author has compared this approach with an alternative “not-as-good” approach that uses modulus – % (which generate random number in a non-evenly distributed manner. i.e. some random number are “more likely” than the others.). See S7.4.4/135 for details. One thing to note is that the code uses rand() – i.e. running the program 100 times result in generating the same set of “random” results. This feature actually is as designed – as it enables the program easier to debug. Only when the program is fully tested, we then add a srand() at the top of the program ti make the whole thing to appear even more “random” – i.e. the results in multiple program run are likely to differ.

In this post I will include two main programs – one without the srand (like the example in the book – so each job run gives the same set of random results), and one with the srand (to show that results can differ from multiple job run). The srand() “seeds” a new form of randomness every time when the program is run – dependent on the system clock time.

In addition, there are many “C++ Random Number Generator” related article online (a simple Google search will return lots of good articles). I have found a few that are quite interesting – but all in all, I think all these solutions eventually sort of converge back to the method described by the Accelerated C++ text book!

• C++ Random Numbers (cplusplus.com) 
• Random Number Generator (daniweb.com)

The Project

Here wraps up all the source codes that I use – I have modified the original main program by adding a for loop – so instead of creating just one sentence, it generates multiple sentences – to demonstrate / give us a better “feel” on randomness. I have included here two main programs – one without a srand(), and the other with a srand(). I shall test both main programs accordingly – but effectively, the one without srand() will create the same set of “random results” in every job run. Whereas the one with the srand() will create different sets of “random results” in every job run.

Source File List

• main.cpp – by default without srand for Test 1. Uncomment the srand for Test 2.
• bracketed.cpp
• gen_aux.cpp
• gen_sentence.cpp
• nrand.cpp
• read_grammar.cpp
• split.cpp

Header File List

• bracketed.h
• gen_aux.h
• gen_sentence.h
• nrand.h
• read_grammar.h
• split.h

Source Files

main.cpp

(Simply uncomment the srand() for Test 2 – with srand)

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

#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::vector;

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

int main()
{
  srand(time(NULL));   // Added. Seed new form of randomness.

  Grammar grammar = read_grammar(cin);

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

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

    // write the first word, if any
    vector<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;
}

bracketed.cpp

#include <string>     // std::string

using std::string;

// Determine whether a string is surrounded by brackets <>
// (S7.4.3/132)
bool bracketed(const string& s)
{
  return s.size() > 1 &&
         s[0] == '<' &&
         s[s.size() - 1] == '>';
}

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
// (S7.4.3/132)
void gen_aux(const Grammar& g, const string& word, vector<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.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 Grammer object
// (S7.4.3/132)
vector<string> gen_sentence(const Grammar& g)
{
  vector<string> ret;
  gen_aux(g, "<sentence>", ret);
  return ret;
}

nrand.cpp

#include <stdexcept>    // std::domain_error
#include <cstdlib>      // rand(), RAND_MAX

using std::domain_error;
using std::rand;


// return a random integer in the range [0, n)
// (S7.4.4/135)
int nrand(int n)
{
  if (n <= 0 || n > RAND_MAX)
    throw domain_error("Argument to nrand is out of range");

  const int bucket_size = RAND_MAX / n;
  int r;

  do r = rand() / bucket_size;
  while (r >= n);

  return r;
}

read_grammar.cpp

#include "read_Grammar.h"    // Grammar, Rule
#include <istream>           // std::istream
#include <string>            // std::string
#include <vector>            // std::vector
#include "split.h"           // split

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

// Read a Grammar from a given input stream
// (S7.4.1/131)
Grammar read_grammar(istream& in)
{
  Grammar ret;
  string line;

  // read the input
  while (getline(in, line)) {

    // split the input into words
    vector<string> entry = split(line);

    if (!entry.empty())
      // use the category to store the associated rule
      ret[entry[0]].push_back(Rule(entry.begin() + 1, entry.end()));

  }
  return ret;
}

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;
}

Header Files

bracketed.h

#ifndef GUARD_BRACKETED_H
#define GUARD_BRACKETED_H

// bracketed.h

#include <string>

bool bracketed(const std::string&);

#endif // GUARD_BRACKETED_H

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>&);

#endif // GUARD_GEN_AUX_H

gen_sentence.h

#ifndef GUARD_GEN_SENTENCE_H
#define GUARD_GEN_SENTENCE_H

// gen_sentence.h

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

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

#endif // GUARD_GEN_SENTENCE_H

nrand.h

#ifndef GUARD_NRAND_H
#define GUARD_NRAND_H

// nrand.h

int nrand(int);

#endif // GUARD_NRAND_H

read_grammar.h

#ifndef GUARD_READ_GRAMMAR_H
#define GUARD_READ_GRAMMAR_H

// read_grammar.h

#include <vector>      // std::vector
#include <string>      // std::string
#include <map>         // std::map
#include <istream>     // std::istream

typedef std::vector<std::string> Rule;
typedef std::vector<Rule> Rule_collection;
typedef std::map<std::string, Rule_collection> Grammar;

Grammar read_grammar(std::istream&);

#endif // GUARD_READ_GRAMMAR_H

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

// split.h

#include <vector>
#include <string>

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

#endif // GUARD_SPLIT_H

Test Program

I have two set of tests. Test 1 uses main.cpp (without srand), and Test 2 uses main.cpp (with srand). For each test, I shall submit the same Grammar rules:

<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>

Test 1 – main.cpp (without srand)

Because this version does not has a srand() at the top, each usage of rand() relies on the same “seed” – i.e. same set of “random results” in every job run.

Job-run 0

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

Job-run 1

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

Job-run 2

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

Test 2 – main.cpp (with srand)

Because this version has a srand() at the top, each usage of rand() relies on the a new “seed” – i.e. new set of “random results” in every job run. All subsequent job runs may produce differnt results.

Job-run 0

the dog jumps wherever it wants
the brown cat jumps under the sky
the cat jumps on the stairs
the brown absurd large table sits wherever it wants
the table jumps under the sky

Job-run 1

the table sits under the sky
the cat sits under the sky
the absurd brown table sits on the stairs
the brown absurd large absurd large table jumps under the sky
the brown table sits wherever it wants

Job-run 2

the dog sits wherever it wants
the absurd dog jumps under the sky
the table sits wherever it wants
the absurd cat sits under the sky
the dog jumps on the stairs

Reference

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

This is part 2 of the 3-part Exercise 7-0. Click here to see the other parts.

Exercise 7-0 (Part 2 / 3)

Use associative arrays to find all the lines that refer to each word in the input. As per S7.3/126.

Solution

Section 7.3 (Page 126) introduces a method to find all the lines that refer to each word in the input, with the aid of associative arrays. This is so called a “Cross Reference Table”. See the text book for detail description.

Special Note on Line Number

Note that the cross-reference program (xref) as presented by the author of the book uses line 1 to represent the first line (instead of line 0). Likewise, line 2 to represent the second line (instead of line 1). i.e. the line number is always “one more” in comparison to our index system in which index 0 represents the first item.

But then I guess it makes sense as in most editor (like Microsoft Word), whenever we search for a line, it makes more sense from a human perspective that line 1 represents the first line, etc.

Just something to bear in mind – as it is likely that we switch between using 0 or 1 to represent the first line, depending on the problem / application that we are facing.

The Project

Here wrap up the project showing all the source and header files Used.

Source File List

• main.cpp
• split.cpp
• xref.cpp

Header File List

• split.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

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) {

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

    // 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;
}

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;
}

xref.cpp

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

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

// Find all the lines that refer to each word in the input
// (S7.3/126)
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)
      ret[*it].push_back(line_number);
  }

  return ret;
}

Header Files

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

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 Program

I now submit some words to the console input upon running the program. The program quickly identify the line numbers (that each word resides) and display results as expected.

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

Reference

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

This is part 1 of the 3-part Exercise 7-0. Click here to see the other parts.

Exercise 7-0 (Part 1 / 3)

Use associative arrays to count words – in this particular exercise, we shall use the map from the standard library.

Solution

Section 7.2 (Page 124) of the textbook contains a very nice and compact main function that performs easy word counting with associating arrays using the map utility. The program is very easy to understand. See the text book for detail description.

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

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

int main()
{
  string s;
  map<string, int> counters;  // store each word and an associated counter

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

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

  return 0;
}

Test Program

I now submit some words to the console input upon running the program. The program quickly counts the words and display results as expected.

apple orange banana
orange orange
apple banana
mango
^Z
apple   2
banana  2
mango   1
orange  3

One more thing to note is that the associative array automatically sort the key of the key-value pair. i.e. the pair<const K, V>.

Reference

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

Exercise 6-9

Use a library algorithm to concatenate all the elements of a vector<string>.

Solution

In Chapter 6, the author introduces the accumulate algorithm which enables easy summation of all numeric elements within a vector<double>.

If you look at section 6.5 (page 121 of the book), the accumulate function takes this form: accumulate(b, e, t), in which arguments b and e defines the asymmetric range [b, e) of the vector elements to be subject for the summation. the argument t represents the initial value of the summation and implies the type the accumulation.

For instance, if we wish to sum all the elements within the vector<double> numbers, with the initial value of 0.0, the summation is computed as accumulate(numbers.begin(), numbers.end(), 0.0).

To concatenate all the elements of a vector<string>, interestingly, we can also leverage this accumulate function.

For instance, if we wish to sum (concatenate) all the elements within the vector<string> words, with the initial value of “” (implies empty vector), the concatenation is computed as accumulate(words.begin(), words.end(), “”). i.e. concatenating all the string elements will give us a giant (longer) string. (It’s an overload!)

Test Program

Fortunately, this concept can be tested out easily by submitting the following very simple main program. One realisation is that the accumulate function is actually under the <numeric> directive, not the <algorithm> directive as I had originally thought.

#include <iostream>    // cout, endl;
#include <vector>      // vector
#include <string>      // string
#include <numeric>     // accumulate

using std::vector;
using std::string;
using std::cout;
using std::endl;
using std::accumulate;

int main () {
    string s = "abc";
    vector<string>  vec (20, s);
    string sentence = accumulate( vec.begin(), vec.end(), string("") );
    cout << sentence << endl;
}

Result

Running the main program confirms that the concatenation can be performed using the accumulate algorithm. i.e. the 20 elements of string “abc” have been concatenated into one giant string element.

abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc

Process returned 0 (0x0)   execution time : 0.394 s
Press any key to continue.

Reference

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

Exercise 6-8

Write a single function that can be used to classify students based on criteria of your choice. Test this function by using it in place of the extract_fails program, and use it in the program to analyse student grades.

Some Background

In the Solution to Exercise 6-7 we created a new extractDidnt function by making a copy of the original “one-pass” extract_fails function, followed by making minor adjustments (such as replacing the predicate pgrade to did_all_hw). The downside of this approach (i.e. making a copy of a skeleton code and adjusting it) is that we may end up with many near-duplicated codes (with only minor differences). Having to maintain so many codes may become difficult to manage in long run. The author asks us to create a single (more generic) function that is capable to deal with multiple similar scenarios – so at the end of the day we only need to maintain 1 single piece of code, instead of (say) a hundred.

Solution

If we look at the extract_fail and extractDidnt codes that we wrote in Solution to Exercise 6-7, we note that the one most important difference is third argument called by the stable_partition function – pgrade vs did_all_hw (which are both predicates). Both of these are essentially some sort of criteria that return true or false.

The new extractOnCriteria function

Building on the skeleton extract_fail function, this is my version of that “one single (more generic)” function:

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if
#include "Student_info.h"     // Student_info

using std::vector;

// a more generic version of extract_fail code (originated (S6.3.2/119))
vector<Student_info> extractOnCriteria(vector<Student_info>& students,
                                       bool criteria(const Student_info&))
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), criteria);

  vector<Student_info> extracted(students.begin(), iter);  // changed
  students.erase(students.begin(), iter);                  // changed

  return extracted;
}

This diagram summarises what this implementation does:

Note these adjustments:

• The third argument (a predicate) is now renamed to something more generic – criteria.
• Added a second parameter bool criteria(const Student_info&) to enable us to parse the criteria into the implementation. For example, when we call the extractOncriteria from the main program, we can parse either the pgrade or did_all_hw via the second argument.
• The two lines above the return statement – note that the range is now from students.begin() to iter – instead of iter to students.end() as per the extract_fail function. (Why you may ask? Well, instead of trying to convince you, I would suggest you to just simply compare the above diagram with the ones in Solution to Exercise 6-7 – things will become clear then.)

The Project

Just to wrap things up and enable ease of testing, I now summarise the C++ source and header files here.

Source File List

• main.cpp
• did_all_hw.cpp
• extractOnCriteria.cpp
• fgrade.cpp
• grade.cpp
• median.cpp
• Student_info.cpp

Header File List

• did_all_hw.h
• extractOnCriteria.h
• fgrade.h
• grade.h
• median.h
• Student_info.h

Source Files

main.cpp

#include <iostream>                      // cin, cout, endl
#include <vector>                        // vector

#include "Student_info.h"                // Student_info

#include "extractOnCriteria.h"           // extractOnCriteria

#include "did_all_hw.h"                  // did_all_hw
#include "fgrade.h"                      // fgrade

#include "grade.h"                       // grade

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

int main()
{
  // read the student records
  Student_info student;
  vector<Student_info> students;
  while (read(cin, student))
    students.push_back(student);

  // identify students who did and didnt do all homework
  vector<Student_info> didnt = students;
  vector<Student_info> did = extractOnCriteria(didnt, did_all_hw);

  cout << "nThese students did all homework:" << endl;
  for (vector<Student_info>::const_iterator i = did.begin();
       i != did.end(); ++i)
    cout << (i->name) << endl;

  cout << "nThese students didn't do all homework:" << endl;
  for (vector<Student_info>::const_iterator i = didnt.begin();
       i != didnt.end(); ++i)
    cout << (i->name) << endl;


  // identify students who have passed or failed
  vector<Student_info> passed = students;
  vector<Student_info> failed = extractOnCriteria(passed, fgrade);

  cout << "nThese students have passed:" << endl;
  for (vector<Student_info>::const_iterator i = passed.begin();
       i != passed.end(); ++i)
    cout << (i->name) << " (" << grade(*i) << ")" << endl;

  cout << "nThese students have failed:" << endl;
  for (vector<Student_info>::const_iterator i = failed.begin();
       i != failed.end(); ++i)
    cout << (i->name) << " (" << grade(*i) << ")" << endl;

  return 0;
}

did_all_hw.cpp

#include <algorithm>           // find
#include "Student_info.h"      // Student_info

// Has the student done all the homework?
// (S6.2.1/110)
bool did_all_hw(const Student_info& s)
{
  return ((find(s.homework.begin(), s.homework.end(), 0)) == s.homework.end());
}

extractOnCriteria.cpp

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if
#include "Student_info.h"     // Student_info

using std::vector;

// a more generic version of extract_fail code (originated (S6.3.2/119))
vector<Student_info> extractOnCriteria(vector<Student_info>& students,
                                       bool criteria(const Student_info&))
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), criteria);

  vector<Student_info> extracted(students.begin(), iter);  // changed
  students.erase(students.begin(), iter);                  // changed

  return extracted;
}

fgrade.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"         // grade

// predicate to determine whether a student failed
// (S5.1/75)
bool fgrade(const Student_info& s)
{
    return grade(s) < 60;
}

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>
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

#include "Student_info.h"

using std::istream;
using std::vector;

// we are interested in sorting the Student_info object by the student's name
bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}

// read student's name, midterm exam grade, final exam grade, and homework grades
// and store into the Student_info object
// (as defined in S4.2.2/62)
istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    // read and store all the student's homework grades
    read_hw(is, s.homework);
    return is;
}

// read homework grades from an input stream into a vector<double>
// (as defined in S4.1.3/57)
istream& read_hw(istream& in, vector<double>& hw)
{
    if (in)
    {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}

header Files

did_all_hw.h

#ifndef GUARD_DID_ALL_HW_H
#define GUARD_DID_ALL_HW_H

// did_all_hw.h
#include "Student_info.h"  // Student_info

bool did_all_hw(const Student_info&);

#endif // GUARD_DID_ALL_HW_H

extractOnCriteria.h

#ifndef GUARD_EXTRACTONCRITERIA_H
#define GUARD_EXTRACTONCRITERIA_H

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

std::vector<Student_info>
extractOnCriteria(std::vector<Student_info>&,
                  bool criteria(const Student_info&));

#endif // GUARD_EXTRACTONCRITERIA_H

fgrade.h

#define GUARD_FGRADE_H

// fgrade.h

#include "Student_info.h"  // Student_info
#include "grade.h"         // grade

bool fgrade(const Student_info&);

#endif // GUARD_FGRADE_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
#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

As we see in the main program, we are going to use the extractOnCriteria twice – once against the fgrade predicate (to extract failed students), and once against the did_all_hw (to extract students who did all homework). We then display to confirm that the single extractOnCriteria function works! (and it does indeed).

pete 100 100 100 100 100
jon 90 90 0 0 0
mary 50 50 50 50 50
anna 40 40 0 0 0
gary 80 80 0 80 0
bob 100 100 100 0 0
ken 20 88 99 44 66
jay 99 39 40 80 0
bill 20 88 0 39 0
^Z
^Z

These students did all homework:
pete
mary
ken

These students didn't do all homework:
jon
anna
gary
bob
jay
bill

These students have passed:
pete (100)
bob (60)
ken (65.6)

These students have failed:
jon (54)
mary (50)
anna (24)
gary (48)
jay (51.4)
bill (39.2)

Reference

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

Exercise 6-7

The portion of the grading analysis program from S6.2.1/110 that read and classified student records depending on whether they did (or did not) do all the homework is similar to the problem we solved in extract_fails. Write a function to handle this subproblem.

Solution

The “one-pass” extract_fail program (as per S6.3.2/119 of the textbook) takes in a vector<Student_info> container, extracts out the failed students, and leave the passed students in that input vector<Student_info> container. The objective of this exercise is to reuse this concept on a somewhat scenario. i.e. to takes in the same vector<Student_info> container, extracts out the students who didn’t did all the homework, and leave the students who did the homework in that input vector<Student_info> container – we can build a function called (say) extractDidnt that builds on the extract_fail program.

The Skeleton extract_fail function

The original “one-pass” extract_fail function looks like this:

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if

#include "Student_info.h"
#include "fgrade.h"
#include "pgrade.h"

using std::vector;

// A single-pass solution to extract the failed students
// (S6.3.2/119)
vector<Student_info> extract_fails(vector<Student_info>& students)
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), pgrade);

  vector<Student_info> fail(iter, students.end());
  students.erase(iter, students.end());

  return fail;
}

The implementation does the following:

 

1. Process directly an input vector<Student_info> students container. Uses stable_parition to put the passed students to the front of that vector – with the help of its third argument pgrade as a predicate.
2. Instantiate a vector<Student_info> fail container to include only the failed students. We return this container at the end.
3. Erase those failed students from the original input vector<Student_info> students container, essentially keeping only the passed students.

The end result is, a new vector<Student_info> fail container that contains only the failed students, and a “reduced” vector<Student_info> students container that now contains only the passed Students.

The new extractDidnt function

Applying the same concept our new extractDidnt function may look like the following.

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if

#include "Student_info.h"
#include "did_all_hw.h"

using std::vector;

// A single-pass solution to extract the students who didn't do all homework
// adjusted version of S6.3.2/119) - for exercise 6-7
vector<Student_info> extractDidnt(vector<Student_info>& students)
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), did_all_hw);

  vector<Student_info> didnt(iter, students.end());
  students.erase(iter, students.end());

  return didnt;
}

The implementation does the following:

 

1. Process directly an input vector<Student_info> students container. Uses stable_parition to put the “did-all-homework” students to the front of that container – with the help of its third argument did_all_hw as a predicate.
2. Instantiate a new vector<Student_info> didnt container to include only the “did-not-do-all-homework” students. We return this container at the end.
3. Erase those “did-not-do-all-homework” students from the original input vector<Student_info> students container, essentially keeping only the passed students.

The end result is, a new vector<Student_info>  didnt container that contains only the “did-not-do-all-homework” students, and a “reduced” vector<Student_info> students container that now contains only the “did-all-homework” Students.

The Project

I now wrap the entire projects here, including all the source and header files used. Note that this project is built on the Project within my Solution to Exercise 6-6. (i.e. I have merely amended the main.cpp file, and added the extractDidnt.cpp file).

Source File List

• main.cpp
• average.cpp
• average_grade.cpp
• did_all_hw.cpp
• doAnalysis.cpp
• extractDidnt.cpp
• grade.cpp
• grade_aux.cpp
• median.cpp
• optimistic_median.cpp
• Student_info.cpp
• write_analysis.cpp

Header File List

• average.h
• average_grade.h
• did_all_hw.h
• doAnalysis.h
• extractDidnt.h
• grade.h
• grade_aux.h
• median.h
• optimistic_median.h
• Student_info.h
• write_analysis.h

Source Files

main.cpp

#include <iostream>                      // cin, cout, endl
#include <vector>                        // vector

#include "Student_info.h"                // Student_info
#include "extractDidnt.h"                // extractDidnt
#include "write_analysis.h"              // write_analysis

#include "grade_aux.h"                   // grade_aux
#include "average_grade.h"               // average_grade
#include "optimistic_median.h"           // optimistic_median

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

int main()
{
  // read the student records
  Student_info student;
  vector<Student_info> did;       // to store students who did all homework
  while (read(cin, student))
    did.push_back(student);

  // extract out the students who didnt do all homework
  vector<Student_info> didnt = extractDidnt(did);

  // verify that the analyses will show us something
  if (did.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }
  if (didnt.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }

  // do the analyses
  write_analysis(cout, "median", grade_aux, did, didnt);
  write_analysis(cout, "average", average_grade, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median, did, didnt);

  return 0;
}

average.cpp

#include <vector>  // vector
#include <numeric>  // numeric

using std::vector;
using std::accumulate;

// Compute average of elements
// (S6.2.3/115)
double average(const vector<double>& v)
{
  return accumulate(v.begin(), v.end(), 0.0) / v.size();
}

average_grade.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "average.h"  // average

// Compute the final grade using average of homework
// (S6.2.3/115)
double average_grade(const Student_info& s)
{
  return grade(s.midterm, s.final, average(s.homework));
}

did_all_hw.cpp

#include <algorithm>  // find
#include "Student_info.h"  // Student_info

// Has the student done all the homework?
// (S6.2.1/110)
bool did_all_hw(const Student_info& s)
{
  return ((find(s.homework.begin(), s.homework.end(), 0)) == s.homework.end());
}

doAnalysis.cpp

#include <vector>                    // vector
#include <algorithm>                 // transform
#include "Student_info.h"            // Student_info
#include "median.h"                  // median

using std::vector;
using std::transform;

// Exercise 6-6: a consolidated auxiliary function
double doAnalysis(const vector<Student_info>& students,
                  double useGradeScheme(const Student_info&))
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), useGradeScheme);
  return median(grades);
}

extractDidnt.cpp

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if

#include "Student_info.h"
#include "did_all_hw.h"

using std::vector;

// A single-pass solution to extract the students who didn't do all homework
// adjusted version of S6.3.2/119) - for exercise 6-7
vector<Student_info> extractDidnt(vector<Student_info>& students)
{
  vector<Student_info>::iterator iter =
      stable_partition(students.begin(), students.end(), did_all_hw);

  vector<Student_info> didnt(iter, students.end());
  students.erase(iter, students.end());

  return didnt;
}

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);
}

grade_aux.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include <stdexcept>  // domain_error

using std::domain_error;

// Auxiliary function to be parsed as argument to a function
// (S6.2.2/113)
double grade_aux(const Student_info& s)
{
  try {
    return grade(s);
  } catch (domain_error) {
    return grade(s.midterm, s.final, 0);
  }
}

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>
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];
}

optimistic_median.cpp

#include <vector>  // vector
#include <algorithm>  // remove_copy, back_inserter
#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "median.h"  // median

using std::vector;

// median of the nonzero elements of s.homework, or 0 if no such elements exist
double optimistic_median(const Student_info& s)
{
  vector<double> nonzero;
  remove_copy(s.homework.begin(), s.homework.end(),
              back_inserter(nonzero), 0);
  if (nonzero.empty())
    return grade(s.midterm, s.final, 0);
  else
    return grade(s.midterm, s.final, median(nonzero));
}

Student_info.cpp

#include "Student_info.h"

using std::istream;
using std::vector;

// we are interested in sorting the Student_info object by the student's name
bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}

// read student's name, midterm exam grade, final exam grade, and homework grades
// and store into the Student_info object
// (as defined in S4.2.2/62)
istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    // read and store all the student's homework grades
    read_hw(is, s.homework);
    return is;
}

// read homework grades from an input stream into a vector<double>
// (as defined in S4.1.3/57)
istream& read_hw(istream& in, vector<double>& hw)
{
    if (in)
    {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}

write_analysis.cpp

#include <iostream>         // ostream, endl;
#include <vector>           // vector
#include <string>           // string
#include "Student_info.h"   // Student_info
#include "doAnalysis.h"     // doAnalysis

using std::ostream;
using std::endl;
using std::string;
using std::vector;

// Output result to compare the two groups of students who did and
// who didn't do all of their homework.
// (S6.2.3/113) | updated for Exercise 6-6
void write_analysis(ostream& out,
                    const string& name,
                    double useGradeScheme(const Student_info&),
                    const vector<Student_info>& did,
                    const vector<Student_info>& didnt)
{
  out << name << ": median(did) = " << doAnalysis(did, useGradeScheme) <<
                 ": median(didnt) = " << doAnalysis(didnt, useGradeScheme) <<
                 endl;
  return;
}

Header Files

average.h

#ifndef GUARD_AVERAGE_H
#define GUARD_AVERAGE_H

// average.h
#include <vector>

double average(const std::vector<double>&);

#endif // GUARD_AVERAGE_H

average_grade.h

#ifndef GUARD_AVERAGE_GRADE_H
#define GUARD_AVERAGE_GRADE_H

// average_grade.h
#include "Student_info.h"  // Student_info

double average_grade(const Student_info&);

#endif // GUARD_AVERAGE_GRADE_H

did_all_hw.h

#ifndef GUARD_DID_ALL_HW_H
#define GUARD_DID_ALL_HW_H

// did_all_hw.h
#include "Student_info.h"  // Student_info

bool did_all_hw(const Student_info&);

#endif // GUARD_DID_ALL_HW_H

doAnalysis.h

#ifndef GUARD_DOANALYSIS_H
#define GUARD_DOANALYSIS_H

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

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

#endif // GUARD_DOANALYSIS_H

extractDidnt.h

#ifndef GUARD_EXTRACTDIDNT_H
#define GUARD_EXTRACTDIDNT_H

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

std::vector<Student_info> extractDidnt(std::vector<Student_info>&);

#endif // GUARD_EXTRACTDIDNT_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

grade_aux.h

#ifndef GUARD_GRADE_AUX_H
#define GUARD_GRADE_AUX_H

// grade_aux.h
#include "Student_info.h"  // Student_info

double grade_aux(const Student_info&);

#endif // GUARD_GRADE_AUX_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_MEDIAN_H

optimistic_median.h

#ifndef GUARD_OPTIMISTIC_MEDIAN_H
#define GUARD_OPTIMISTIC_MEDIAN_H

// optimistic_median.h

#include "Student_info.h"  // Student_info

double optimistic_median(const Student_info&);

#endif // GUARD_OPTIMISTIC_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

write_analysis.h

#include <iostream>  // ostream;
#include <vector>  // vector
#include <string>  // string
#include "Student_info.h"  // Student_info

void write_analysis(std::ostream&,
                    const std::string&,
                    double useGradeScheme(const Student_info&),
                    const std::vector<Student_info>&,
                    const std::vector<Student_info>&);

#endif // GUARD_WRITE_ANALYSIS_H

Test Program

I now submit the same input (as the test to the original program / Solution to Exercise 6-0 (Part 5 / 7)). The test shows that we get the same result, implying the code updates are not causing observable issues.

pete 100 100 100 100 100
jon 90 90 0 0 0
mary 50 50 50 50 50
anna 40 40 0 0 0
gary 80 80 0 80 0
bob 100 100 100 0 0
ken 20 88 99 44 66
jay 99 39 40 80 0
bill 20 88 0 39 0
^Z
^Z
median: median(did) = 65.6: median(didnt) = 49.7
average: median(did) = 67.0667: median(didnt) = 52.7
median of homework turned in: median(did) = 65.6: median(didnt) = 57.1

Reference

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

Exercise 6-6

Note that the function from the previous exercise and the function from S6.2.2/113 and 6.2.3/115 do the same task. Merge these three analysis functions into a single function.

Some Background

This is regarding the “Compare Grading Scheme” sample codes as presented in chapter 6 of the book. The original codes may be found at Solution to Exercise 6-0 (Part 5 / 7).

One disclosure: though I eventually managed to complete this exercise and adjust all the codes, following a combination of trial-and-error (and a bit of Google-ing!), I have found it not an easy task to explain the solution to this entire problem – in some way I do find the idea of parsing a function as an argument to another function pretty abstract (and I believe things will only get better only after I have completed more C++ exercises and read on more.). For now, I shall do my best to explain my solution based on my understanding, which I hope will make sense! Please do forgive me if you ended up finding the following quite difficult to follow. I do wish I know a more systematic and simplified way to explain this solution! If you are not put off by this, read on!

Some Observations

OK. If you have also had a go running through the entirety of the “Compare Grading Scheme” project, you would likely have noticed that we have 3 very similar functions:

• average_analysis
• median_analysis
• optimistic_median_analysis

I shall recall these 3 functions below – note that they are pretty much identical, apart from the 4th argument of the transform function which corresponds to the associating grading scheme, respectively:

• average_grade
• grade_aux
• optimistic_median

average_analysis:

double average_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), average_grade);
  return median(grades);
}

median_analysis:

double median_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(), back_inserter(grades), grade_aux);
  return median(grades);
}

optimistic_median_analysis:

double optimistic_median_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), optimistic_median);
  return median(grades);
}

Opportunity to merge these 3 functions into one? Oh yes definitely!

Merging the three Analysis Functions into one

We note that the 3 functions are pretty much identical, apart from the 4th argument called by the transform function which corresponds to the associating grading scheme.

To merge the three functions into one, simply follow this strategy:

1. Make a copy of one of the analysis function (say, the median_analysis function) and use it as our new baseline for building up the new “merged” function. Rename the function to something that sounds more generic. Let’s rename it to doAnalysis.
2. Within the now doAnalysis function, rename that 4th argument called by the transform function with a more generic name. Let’s rename it to useGradeScheme. i.e. we use this as an “adaptor” for the 3 grading schemes (average_grade, grade_aux, and optimistic_median).
3. Add a second parameter useGradeScheme to the doAnalysis function so we can parse the grade scheme into the doAnalysis implementation itself. We need to ensure this parameter takes the same form as grade_aux (which has the same form as average_grade, which also has the same form as optimistic_median). i.e. they all take this form: double XXXX(const Student_info&). To make things consistent, this new second parameter must also be of the same form. i.e. the second parameter shall be written as double useGradeScheme(const Student_info&).

I summarise this strategy into a picture (which I hope will make it easier to understand).

Once we have completed the change, the new “merged” doAnalysis function shall look like this.

double doAnalysis(const vector<Student_info>& students,
                  double useGradeScheme(const Student_info&))
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), useGradeScheme);
  return median(grades);
}

Update the functions that are still calling the legacy analysis functions

Now that we have merged the 3 analysis functions into 1 new “merged” functions, we need to ensure all the whatever implementations that are still calling these 3 analysis functions (average_analysis, median_analysis, and optimistic_median_analysis) are also adjusted to use the new “merged” function. Otherwise those implementations would bump into errors as the 3 legacy analysis functions no longer exist! Our next task is therefore to identify the impacted implementations and make changes accordingly.

Fortunately, there is only one implementation impacted – the main function. The main function contains the following 3 lines, which still calls the legacy analysis functions (average_analysis, median_analysis, and optimistic_median_analysis) – as an argument to the function write_analysis.

  write_analysis(cout, "median", median_analysis, did, didnt);
  write_analysis(cout, "average", average_analysis, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median_analysis, did, didnt);

Because these analysis functions are used as an argument (which in this case, the 3rd argument) to another function, we must pay attention to that “another function” – write_analysis as we will likely need to adjust that as well.  So let’s take a look at the write_analysis function:

void write_analysis(ostream& out,
                    const string& name,
                    double analysis(const vector<Student_info>&),
                    const vector<Student_info>& did,
                    const vector<Student_info>& didnt)
{
  out << name << ": median(did) = " << analysis(did) <<
                 ": median(didnt) = " << analysis(didnt) << endl;
  return;
}

We know that the 3rd parameter double analysis(const vector<Student_info>&) corresponds to the legacy analysis function. When, say, median_analysis (as an argument) is parsed into this implementation (via this 3rd parameter) all the downstream analysis(XXX) within this implementation essentially get resolved into median_analysis(XXX). (likewise for the other two analysis functions).

As we have already mentioned, the median_analysis function shall be replaced by the new “merged” function called doAnalysis, which take this new form:

double doAnalysis(const vector<Student_info>& students,
                  double useGradeScheme(const Student_info&))

We must therefore adjust the analysis(XXX) accordingly to doAnalysis(XXX, XXX). i.e. we can replace the following:

  out << name << ": median(did) = " << analysis(did) <<
                 ": median(didnt) = " << analysis(didnt) << endl;

… with …

  out << name << ": median(did) = " << doAnalysis(did, useGradeScheme) <<
                 ": median(didnt) = " << doAnalysis(didnt, useGradeScheme) << endl;

We can declare the doAnalysis by simply doing a #include of the corresponding file.

For the useGradeScheme part however, we must parse it via the parameter. One way to do this is to replace the double analysis(const vector<Student_info>&), which we no longer need, to double useGradeScheme(const Student_info&), which we now need. I summarise this via a diagram below:

i.e. the now revised write_analysis function will look like this:

#include "doAnalysis.h"     // doAnalysis

void write_analysis(ostream& out,
                    const string& name,
                    double useGradeScheme(const Student_info&),
                    const vector<Student_info>& did,
                    const vector<Student_info>& didnt)
{
  out << name << ": median(did) = " << doAnalysis(did, useGradeScheme) <<
                 ": median(didnt) = " << doAnalysis(didnt, useGradeScheme) <<
                 endl;
  return;
}

Now that we have updated the write_analysis function, the logical next step is to update whatever implementation that call this write_analysis function, and adjust accordingly.

Let’s go back to the main function and look at the 3 lines again:

  write_analysis(cout, "median", median_analysis, did, didnt);
  write_analysis(cout, "average", average_analysis, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median_analysis, did, didnt);

We know from our new write_analysis function above, that the 3rd parameter is of the form double useGradeScheme(const Student_info&). It is therefore logical to parse an argumenet that satisfy this form. And we know that the useGradeScheme correspond to: average_grade, grade_aux, and optimistic_median. So, let’s do the replacement accordingly – I summarise this via a diagram.

The revised 3 lines in the main function will now look like this:

  write_analysis(cout, "median", grade_aux, did, didnt);
  write_analysis(cout, "average", average_grade, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median, did, didnt);

That’s pretty much all the changes required to solve this problem! (As I mentioned at the top of the post, I do find explaining the solution to this exercise not an easy task – if you still do not understand, I would recommend you to try compiling the files in the Project section below, run the program, test it out, confirm that it works, and try to understand how and why it has worked.

To see the complete project / source files, read on and try out!

The Project

To wrap things up, as usual, I shall publish my entire project here, including the source files and header files.

Source File List

• main.cpp
• average.cpp
• average_grade.cpp
• did_all_hw.cpp
• doAnalysis.cpp
• grade.cpp
• grade_aux.cpp
• median.cpp
• optimistic_median.cpp
• Student_info.cpp
• write_analysis.cpp

Header File List

• average.h
• average_grade.h
• did_all_hw.h
• doAnalysis.h
• grade.h
• grade_aux.h
• median.h
• optimistic_median.h
• Student_info.h
• write_analysis.h

Source Files

main.cpp

#include <iostream>                      // cin, cout, endl
#include <vector>                        // vector

#include "Student_info.h"                // Student_info
#include "did_all_hw.h"                  // did_all_hw
#include "write_analysis.h"              // write_analysis

#include "grade_aux.h"                   // grade_aux
#include "average_grade.h"               // average_grade
#include "optimistic_median.h"           // optimistic_median

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

// Compare the Grading Scheme
// (S6.2.3/114)
int main()
{
  // students who did and didn't do all their homework
  vector<Student_info> did, didnt;

  // read the student records and partition them
  Student_info student;
  while (read(cin, student)) {
    if (did_all_hw(student))
      did.push_back(student);
    else
      didnt.push_back(student);
  }

  // verify that the analyses will show us something
  if (did.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }
  if (didnt.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }

  // do the analyses
  write_analysis(cout, "median", grade_aux, did, didnt);
  write_analysis(cout, "average", average_grade, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median, did, didnt);

  return 0;
}

average.cpp

#include <vector>  // vector
#include <numeric>  // numeric

using std::vector;
using std::accumulate;

// Compute average of elements
// (S6.2.3/115)
double average(const vector<double>& v)
{
  return accumulate(v.begin(), v.end(), 0.0) / v.size();
}

average_grade.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "average.h"  // average

// Compute the final grade using average of homework
// (S6.2.3/115)
double average_grade(const Student_info& s)
{
  return grade(s.midterm, s.final, average(s.homework));
}

did_all_hw.cpp

#include <algorithm>  // find
#include "Student_info.h"  // Student_info

// Has the student done all the homework?
// (S6.2.1/110)
bool did_all_hw(const Student_info& s)
{
  return ((find(s.homework.begin(), s.homework.end(), 0)) == s.homework.end());
}

doAnalysis.cpp

#include <vector>                    // vector
#include <algorithm>                 // transform
#include "Student_info.h"            // Student_info
#include "median.h"                  // median

using std::vector;
using std::transform;

// Exercise 6-6: a consolidated auxiliary function
double doAnalysis(const vector<Student_info>& students,
                  double useGradeScheme(const Student_info&))
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), useGradeScheme);
  return median(grades);
}

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);
}

grade_aux.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include <stdexcept>  // domain_error

using std::domain_error;

// Auxiliary function to be parsed as argument to a function
// (S6.2.2/113)
double grade_aux(const Student_info& s)
{
  try {
    return grade(s);
  } catch (domain_error) {
    return grade(s.midterm, s.final, 0);
  }
}

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>
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];
}

optimistic_median.cpp

#include <vector>  // vector
#include <algorithm>  // remove_copy, back_inserter
#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "median.h"  // median

using std::vector;

// median of the nonzero elements of s.homework, or 0 if no such elements exist
double optimistic_median(const Student_info& s)
{
  vector<double> nonzero;
  remove_copy(s.homework.begin(), s.homework.end(),
              back_inserter(nonzero), 0);
  if (nonzero.empty())
    return grade(s.midterm, s.final, 0);
  else
    return grade(s.midterm, s.final, median(nonzero));
}

Student_info.cpp

#include "Student_info.h"

using std::istream;
using std::vector;

// we are interested in sorting the Student_info object by the student's name
bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}

// read student's name, midterm exam grade, final exam grade, and homework grades
// and store into the Student_info object
// (as defined in S4.2.2/62)
istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    // read and store all the student's homework grades
    read_hw(is, s.homework);
    return is;
}

// read homework grades from an input stream into a vector<double>
// (as defined in S4.1.3/57)
istream& read_hw(istream& in, vector<double>& hw)
{
    if (in)
    {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}

write_analysis.cpp

#include <iostream>         // ostream, endl;
#include <vector>           // vector
#include <string>           // string
#include "Student_info.h"   // Student_info
#include "doAnalysis.h"     // doAnalysis

using std::ostream;
using std::endl;
using std::string;
using std::vector;

// Output result to compare the two groups of students who did and
// who didn't do all of their homework.
// (S6.2.3/113) | updated for Exercise 6-6
void write_analysis(ostream& out,
                    const string& name,
                    double useGradeScheme(const Student_info&),
                    const vector<Student_info>& did,
                    const vector<Student_info>& didnt)
{
  out << name << ": median(did) = " << doAnalysis(did, useGradeScheme) <<
                 ": median(didnt) = " << doAnalysis(didnt, useGradeScheme) <<
                 endl;
  return;
}

Header Files

average.h

#ifndef GUARD_AVERAGE_H
#define GUARD_AVERAGE_H

// average.h
#include <vector>

double average(const std::vector<double>&);

#endif // GUARD_AVERAGE_H

average_grade.h

#ifndef GUARD_AVERAGE_GRADE_H
#define GUARD_AVERAGE_GRADE_H

// average_grade.h
#include "Student_info.h"  // Student_info

double average_grade(const Student_info&);

#endif // GUARD_AVERAGE_GRADE_H

did_all_hw.h

#ifndef GUARD_DID_ALL_HW_H
#define GUARD_DID_ALL_HW_H

// did_all_hw.h
#include "Student_info.h"  // Student_info

bool did_all_hw(const Student_info&);

#endif // GUARD_DID_ALL_HW_H

doAnalysis.h

#ifndef GUARD_DOANALYSIS_H
#define GUARD_DOANALYSIS_H

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

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

#endif // GUARD_DOANALYSIS_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

grade_aux.h

#ifndef GUARD_GRADE_AUX_H
#define GUARD_GRADE_AUX_H

// grade_aux.h
#include "Student_info.h"  // Student_info

double grade_aux(const Student_info&);

#endif // GUARD_GRADE_AUX_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_MEDIAN_H

optimistic_median.h

#ifndef GUARD_OPTIMISTIC_MEDIAN_H
#define GUARD_OPTIMISTIC_MEDIAN_H

// optimistic_median.h

#include "Student_info.h"  // Student_info

double optimistic_median(const Student_info&);

#endif // GUARD_OPTIMISTIC_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

write_analysis.h

#ifndef GUARD_WRITE_ANALYSIS_H
#define GUARD_WRITE_ANALYSIS_H

// write_analysis.h

#include <iostream>  // ostream;
#include <vector>  // vector
#include <string>  // string
#include "Student_info.h"  // Student_info

void write_analysis(std::ostream&,
                    const std::string&,
                    double useGradeScheme(const Student_info&),
                    const std::vector<Student_info>&,
                    const std::vector<Student_info>&);

#endif // GUARD_WRITE_ANALYSIS_H

Test Program

I now submit the same input (as the test to the original program / Solution to Exercise 6-0 (Part 5 / 7)). The test shows that we get the same result, implying the code updates are not causing observable issues.

pete 100 100 100 100 100
jon 90 90 0 0 0
mary 50 50 50 50 50
anna 40 40 0 0 0
gary 80 80 0 80 0
bob 100 100 100 0 0
ken 20 88 99 44 66
jay 99 39 40 80 0
bill 20 88 0 39 0
^Z
^Z
median: median(did) = 65.6: median(didnt) = 49.7
average: median(did) = 67.0667: median(didnt) = 52.7
median of homework turned in: median(did) = 65.6: median(didnt) = 57.1

Reference

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

Exercise 6-5

Write an analysis function to call optimistic_median.

Solution

This is covered under my Solution to Exercise 6-0 (Part 5 / 7). The analysis function is called optimistic_median_analysis (stored in the source file optimistic_median_analysis.cpp). It essentially parses the (pointer or memory address of the) optimistic_median function as an argument to another (transform) function. For this to work the optimistic_median function must not be overloaded.

Reference

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