Accelerated C++ Solution to Exercise 5-3

Exercise 5-3

By using a typedef, we can write one version of the program that implements either a vector-based solution or a list-based on. Write and test this version of the program.

Solution

To do this, I have essentially re-engineered the Chapter 5 program / my Solution to Exercise 5-0 (Part 1/3). The following outlines the change:

  1. I have replaced the old extract_fails.cpp (that contains the four extract_fail functions with different names – v1/v2/v3/v4), with two partitioned files, namely extract_fails_v3.cpp, and extract_fails_v4.cpp. The corresponding headers are also split – i.e. I now have extract_fails_v3.h and extract_fails.v4.h. Splitting the file into two files enable me to have two functions both called the same name. i.e. extract_fail(). The idea is that, when it comes to writing the main() program, I can #include either the v3 or v4 header file – I only include one of these functions at a time.
  2. I moved the bool fgrade() function to the grade.cpp file, and declared in the corresponding grade.h header file. This is to enable me to do that file splitting as mentioned above.
  3. Generalise the main() program so that I can switch between running the vector-based (v3) list-based (v4) functions easily. Only two line changes are required at the main() program level – i.e. (1) the #include line, and (2) the typedef line. I have highlighted this in the main program.
  4. Remove the sort part in the main program. Note that because the syntax for the algorithm sort is different between vector and list, I have to exclude the sorting part here for simplicity. (Based on a number of internet forum, apparently the Author wanted to use this exercise to demonstrate the needs of C++ templates, which will be taught in later chapters).
  5. Also for simplicity, I shall remove the bits about formatting (e.g. padding the Student’s name for fix-wdith outlook). I shall also exclude the try / catch / throw bits in the main program for better readability.

The Project

Because so much re-engineering has been done, I shall summarise the now re-engineered files here. I have learnt also a bit more about the use of header files and #include directives – i.e. a good combination usage of the two enable us to include only what we need for the particular file / program – so we don’t have ambiguity.

Acpp5p3MgntTree

main.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "Student_info.h"
#include "grade.h"

// ********************** AMEND THIS  *************************
// Solution to Exercise 5-3: Pick one of the followings (v3 or v4)
// #include "extract_fails_v3.h"      // vector<Student_info>
#include "extract_fails_v4.h"      // list<Student_info>
// ************************************************************

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

int main()
{

    // ********************* AMEND THIS ***************************
    // Solution to Exercise 5-3: Pick one of the followings
    //typedef vector<Student_info> Student_group;
    typedef list<Student_info> Student_group;
    // ************************************************************

    Student_group students;
    Student_info record;

    // read and store all the student's data.
    while (read(cin, record))
        students.push_back(record);

    // Extract the failed students
    Student_group students_failed = extract_fails(students);

    // sort vector and sort list are different
    // so we remove from here for now.

    cout << endl;

    // Report passing students
    cout << "These students have passed." << endl;
    for (Student_group::const_iterator iter = students.begin();
         iter != students.end(); ++iter)
        cout << iter->name << " (" << grade(*iter) << ")" << endl;

    cout << endl;

    // Report failing students
    cout << "These students have failed." << endl;
    for (Student_group::const_iterator iter = students_failed.begin();
         iter != students_failed.end(); ++iter)
        cout << iter->name << " (" << grade(*iter) << ")" << endl;

    return 0;
}

extract_fails_v3.h

#ifndef GUARD_EXTRACT_FAILS_V3_H
#define GUARD_EXTRACT_FAILS_V3_H

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

std::vector<Student_info> extract_fails(std::vector<Student_info>& students);

#endif // GUARD_EXTRACT_FAILS_V3_H

extract_fails_v3.cpp

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

using std::vector;

// separate passing and failing student records
// version 3: iterators but no indexing; still potentially slow
// (S5.3/82)
vector<Student_info> extract_fails(vector<Student_info>& students)
{
    vector<Student_info> fail;
    vector<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

extract_fails_v4.h

#ifndef GUARD_EXTRACT_FAILS_V4_H
#define GUARD_EXTRACT_FAILS_V4_H

// extract_fails_v4.h
#include <list>
#include "Student_info.h"

std::list<Student_info> extract_fails(std::list<Student_info>& students);

#endif // GUARD_EXTRACT_FAILS_V4_H

extract_fails_v4.cpp

#include "Student_info.h"
#include "grade.h"
#include <list>

using std::list;

// separate passing and failing student records
// version 4: use list instead of vector (essentially the same as version 3 otherwise)
// (S5.5/85)
list<Student_info> extract_fails(list<Student_info>& students)
{
    list<Student_info> fail;
    list<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

grade.h

#include "Student_info.h"
#include "grade.h"
#include <list>

using std::list;

// separate passing and failing student records
// version 4: use list instead of vector (essentially the same as version 3 otherwise)
// (S5.5/85)
list<Student_info> extract_fails(list<Student_info>& students)
{
    list<Student_info> fail;
    list<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

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

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

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_MEDIAN_H

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

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

Test Program and Results

For all tests below (vector based and list based) I shall supply this set of 10 lines student’s info as the input.

Kate 88.88 88.88 88.88 88.88 88.88
John 55.55 55.55 55.55 55.55 55.55
Pat 66.66 66.66 66.66 66.66 66.66
Joe 100.00 100.00 100.00 100.00 100.00
Mary 11.11 11.11 11.11 11.11 11.11
Bill 33.33 33.33 33.33 33.33 33.33
Jay 22.22 22.22 22.22 22.22 22.22
Bob 4.00 4.00 4.00 4.00 4.00
Fred 77.77 77.77 77.77 77.77 77.77
Louis 44.44 44.44 44.44 44.44 44.44

We shall see that both tests yield the same result.

Test 1 – vector based version

Amend the #include line and the typdef line accordingly.

// ********************** AMEND THIS  *************************
// Solution to Exercise 5-3: Pick one of the followings (v3 or v4)
#include "extract_fails_v3.h"      // vector<Student_info>
// #include "extract_fails_v4.h"      // list<Student_info>
// ************************************************************
// ********************* AMEND THIS ***************************
// Solution to Exercise 5-3: Pick one of the followings
typedef vector<Student_info> Student_group;
// typedef list<Student_info> Student_group;
// ************************************************************

Test 1 Result

These students have passed.
Kate (88.88)
Pat (66.66)
Joe (100)
Fred (77.77)

These students have failed.
John (55.55)
Mary (11.11)
Bill (33.33)
Jay (22.22)
Bob (4)
Louis (44.44)

Test 2 – list based version

Amend the #include line and the typdef line accordingly.

// ********************** AMEND THIS  *************************
// Solution to Exercise 5-3: Pick one of the followings (v3 or v4)
// #include "extract_fails_v3.h"      // vector<Student_info>
#include "extract_fails_v4.h"      // list<Student_info>
// ************************************************************
// ********************* AMEND THIS ***************************
// Solution to Exercise 5-3: Pick one of the followings
//typedef vector<Student_info> Student_group;
typedef list<Student_info> Student_group;
// ************************************************************

Test 2 Result

These students have passed.
Kate (88.88)
Pat (66.66)
Joe (100)
Fred (77.77)

These students have failed.
John (55.55)
Mary (11.11)
Bill (33.33)
Jay (22.22)
Bob (4)
Louis (44.44)

Reference

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

Accelerated C++ Solution to Exercise 5-2

Exercise 5-2

Write the complete new version of the student-grading program, which extracts records for failing students, using vectors. Write another that uses lists. Measure the performance difference on input files of 10 lines, 1,000 lines, and 10,000 lines.

Solution

The objective of this exercise is to compute the overall job run duration for the function vector<Student_info> extract_fails, and another function list<Student_info> extract_fails. These two functions are essentially the same, except one uses vector and the other uses list.

Fortunately the codes in Chapter 5 of the book (version 3 for vector and version 4 for list), or my Solution to Exercise 5-0 (Part 1/3) has already provided the skeleton structure for this. All I need to do is to adjust the program slightly to incorporate the followings:

  1. Have a pair of start and end time-stamps just before and after the extract_fails function.
  2. Compute the duration by taking the time difference between the end and start time.
  3. Display the duration.

Once we have these new features in our revised program, we are then able to re-run the program using varying number of input (lines).

As I did not recall there were any mentions about time-stamping in the book, I did a Google search and found this very clever clock_t technique (by Dolph) on the Stack Overflow Forum, in conjunction with the clock_t documentation on the cplusplus.com website.

i.e. the <ctime> directive, clock_t , clock(), and CLOCKS_PER_SEC.

This is how to use it.

    clock_t startTime = clock();
    doWhateverFunctionHere();
    clock_t endTime = clock();
    clock_t clockTicksTaken = endTime - startTime;
    double timeInSeconds = clockTicksTaken / (double) CLOCKS_PER_SEC;

The strategy is therefore:

  1. Make a copy of the entire project as per Solution to Exercise 5-0 (Part 1/3).
  2. Create a new extract_fails.cpp that contains two functions: Function test_extract_fails_v3 computes and displays the duration for the vector<Student_info> case. Function test_extract_fails_v4 is similar but for the list<Student_info> case. Wrap these under a header file extract_fails.h.
  3. Simplify the main program to enable easy invocation of each function.

The Project

For clarity sake I include the high level project tree here. Note that majority of the files are from Solution to Exercise 5-0 (Part 1/3) – any files that are not mentioned below are mentioned in that post. In this post I shall only include the new / revised files.

Acpp5p2MgntTree

  • main.cpp – revised for easy invocation of the functions test_extract_fails_v3 and Function test_extract_fails_v4.
  • test_extract_fails.cpp – contains the functions test_extract_fails_v3 and test_extract_fails_v4.
  • test_extract_fails.h – declare the functions in test_extract_fails.cpp.

main.cpp

#include "test_extract_fails.h"

int main()
{
    // invoke either one of the following as required
    // test_extract_fails_v3();
    test_extract_fails_v4();

    return 0;
}

test_extract_fails.cpp

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <iomanip>
#include <ios>
#include "grade.h"
#include "Student_info.h"
#include "extract_fails.h"
#include <ctime>

using std::string;
using std::vector;
using std::list;
using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::streamsize;


// There are two functions here.
//   - The top one is used to test out extract_fails version 3 (vector<Student_info>).
//   - The bottom one is for testing out extract_fails version 4 (list<Student_info>).

// for testing extract_fails_v3 - that uses vector<Student_info>
int test_extract_fails_v3()
{
    vector<Student_info> students;
    Student_info record;

    // read and store all the student's data.
    while (read(cin, record))
        students.push_back(record);

    // Extract the failed students (use extract_fails_v3) and time-stamp it!
    clock_t startTime = clock();
    vector<Student_info> students_failed = extract_fails_v3(students);
    clock_t endTime = clock();
    clock_t clockTicksTaken = endTime - startTime;
    double timeInSeconds = clockTicksTaken / (double) CLOCKS_PER_SEC;

    streamsize prec = cout.precision();
    cout << "Elapsed (in seconds): " << setprecision(30) << timeInSeconds
         << setprecision(prec) << endl;

    return 0;
}


// for testing extract_fails_v4 - that uses list<Student_info>
int test_extract_fails_v4()
{
    list<Student_info> students;
    Student_info record;

    // read and store all the student's data.
    while (read(cin, record))
        students.push_back(record);

    // Extract the failed students and time-stamp it!

    clock_t startTime = clock();
    list<Student_info> students_failed = extract_fails_v4(students);
    clock_t endTime = clock();
    clock_t clockTicksTaken = endTime - startTime;
    double timeInSeconds = clockTicksTaken / (double) CLOCKS_PER_SEC;

    streamsize prec = cout.precision();
    cout << "Elapsed (in seconds): " << setprecision(30) << timeInSeconds
         << setprecision(prec) << endl;

    return 0;
}

test_extract_fails.h

#ifndef GUARD_TEST_EXTRACT_FAILS_H
#define GUARD_TEST_EXTRACT_FAILS_H

int test_extract_fails_v3();
int test_extract_fails_v4();

#endif // GUARD_TEST_EXTRACT_FAILS_H

Test Program

I’ve run 3 trials for every individual tests and use these to compute the average job run duration for the extract_fail_v3 (vector) and extract_fail_v4 (list).

This is my sample set of 10 input lines.

Kate 88.88 88.88 88.88 88.88 88.88
John 55.55 55.55 55.55 55.55 55.55
Pat 66.66 66.66 66.66 66.66 66.66
Joe 100.00 100.00 100.00 100.00 100.00
Mary 11.11 11.11 11.11 11.11 11.11
Bill 33.33 33.33 33.33 33.33 33.33
Jay 22.22 22.22 22.22 22.22 22.22
Bob 4.00 4.00 4.00 4.00 4.00
Fred 77.77 77.77 77.77 77.77 77.77
Louis 44.44 44.44 44.44 44.44 44.44

To test out the case of 100, 1000, and 10000 lines, I simply “copy and paste” these 10 lines to fill the required number of lines. (This seems logical as our objective for this exercise is to compare performance of vector and list)

Test Result

File size Extract_fails_v3 (vector<Student_info>) Extract_fails_v4 (list<Student_info>)
10 lines 0.000 seconds 0.000 seconds
100 lines 0.003 seconds 0.001 seconds
1,000 lines 0.165 seconds 0.006 seconds
10,000 lines 9.300 seconds 0.045 seconds

From this we have just verified the hypothesis in S5.2.2/87 of the book – in which the Author suggested the exponential increase of job-run time when the input volume go beyond the magnitude of 10,000 lines.

Reference

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

Accelerated C++ Solution to Exercise 5-1

Exercise 5-1

Design and implement a program to produce a permuted index. A permuted index is one in which each phrase is indexed by every word in the phrase. So, given the following input,

The quick brown fox
jumped over the fence

the output would be

        The quick     brown fox              
  jumped over the     fence                  
  The quick brown     fox                    
                      jumped over the fence  
           jumped     over the fence         
              The     quick brown fox        
      jumped over     the fence              
                      The quick brown fox    

A good algorithm is suggested in The AWK Programming Language by Aho, Kernighan, and Weinberger (Addison-Wesley, 1998). That solution divides the problem into three steps:

Step 1

Read each line of the input and generate a set of rotations of that line. Each rotation puts the next word of the input in the first position and rotates the previous first word to the end of the phrase. So the output of this phrase for the first line of our input would be:

The quick brown fox
quick brown fox The
brown fox The quick
fox The quick brown

Of course, it will be important to know where the original phrase ends and where the rotated beginning begins.

Step 2

Sort the rotations.

Step 3

Un-rotate and write the permuted index, which involves finding the separator, putting the phrase back together, and writing it properly formatted.

Solution

The key to solving this problem is to first know what the problem is. The author is asking us to build a Permuted Index Page that will allow us to easily identify the position of a word within the given text. Think of it of the index page at the back of the book.

What is a Permuted Index Page?

This Wikipedia page has really helped me out a lot in understanding what a Permuted Index Page (a.k.a Key Word In Context Page, or KWIC Page) look like. (Note: the following two snapshots are originated from the Wikipedia page so all rights go to Wikipedia. I have merely annotated the snapshots to aid understanding what a Permuted Index Page look like – which I believe is vital in helping us to solve the problem. So thank you Wikipedia!)

Ok. Assume we have the following “article”:

Acpp5p1WikiKwic1

A Permuted Index Page may look like this:

Acpp5p1WikiKwic2

A Permuted Index Page lists the Permuted Indices (in bold text), sorted in alphabetical order for ease of lookup. Nice thing about a Permuted Index Page is that it allows us not only to find out quickly where the Permuted Index (a.k.a Key Word in Context (KWIC)) “word” is with respect to the article, it also exposes some texts one the left and right of the Permuted Index.

Think of a Google search. When we do a Google Search of a word, Google not only returns us with the potential web addresses, it also “exposes” some texts on the left and right of that search word (which is essentially equivalent to a Permuted Index in our case).

In C++ implementation term, it might be clearer if I draw around that Wikipedia table. This will hopefully give us more clues as to what our C++ implementation might be like.

Acpp5p1WikiKwic3

What may our Permuted Index Page look like?

So coming back to our case. We have the following “article”.

The quick brown fox
jumped over the fence

Our “ultimate” output, a Permuted Index Page, may look like this:

******************* ************************* ********** **********
*       The quick * * brown fox             * * Line 0 * * Word 2 *
* jumped over the * * fence                 * * Line 1 * * Word 3 *
* The quick brown * * fox                   * * Line 0 * * Word 3 *
*                 * * jumped over the fence * * Line 1 * * Word 0 *
*          jumped * * over the fence        * * Line 1 * * Word 1 *
*             The * * quick brown fox       * * Line 0 * * Word 1 *
*     jumped over * * the fence             * * Line 1 * * Word 2 *
*                 * * The quick brown fox   * * Line 0 * * Word 0 *
******************* ************************* ********** **********

Or in the form of a picture (for clarity sake):

Acpp5p1pic30

The Permuted Index Page listed above is the output of my C++ program. “Block 1” and “Block 2” essentially are what the Author asks us to produce. “Block 3” and “Block 4” are the “extras” that I decided to incorporate at the time of writing that C++ program – I just wanted to challenge myself and make the output a little bit more “perfect” let say!

To be able to use this output (a Permuted Index Page), we first need to know that the first words of “Block 2” are the Permuted Indices. i.e. the red bold words in the picture!

So, if I want to know where the word “fox” appear in the article, I look up “fox” in the Permuted Index page. It says the word “fox” is on Line 0, word 3. (recall we use a standard index convention in which the first line is called line 0. The second line is called line 1. And so on). The word “fox” is indeed the 3rd word on line 0.

Let’s try another one. Where does the word “over” appear? Easy. Line 1, Word 1 (i.e. second line, second word).

Where does the word “The” appear? Again, easy. Line 0, Word 0. (i.e. First line, first word).

Note that when we do the sort (against the red bold indices), we incorporate into our program to sort regardless of upper or lower case. I will expand a little bit later on how we do this (it’s very easy). All we need to know for now is that it is possible to sort regardless of upper / lower case.

C++ Algorithm and Implementation Strategy

Ok. Now we know what a Permuted Index Page is (and its purpose), what it looks like, and how we use it, let me show you my C++ algorithm and implementation strategy. There are many ways to do this. Some people may prefer maximum efficiency program for best performance. Some may prefer shortest program. When I write my program I aim to make it easiest to understand and easy to follow. I believe the best “beginner” program is the simplest and stupidest program (KISS – “Keep It Simple and Stupid”). That says, there are plenty of opportunities for improvements. But I believe a simple-to-understand program is always a good starting baseline.

The High Level Main Program

Do a quick skimp through of this main program without worrying too much about the details. I have written the main program with the aim that whoever reads the program, he/she should be able to “guess” what each statement tries to achieve without prior knowledge of the details. It aims to summarise the high level logic and I will explain the details a bit more more in the following sections to come.

int main()
{

    // read lines via standard console input and append to article
    vector<string> article = read_lines();

    // prepare an empty Permuted_index_collection
    vector<Permuted_index> Permuted_index_collection;

    // populate the Permuted_index_collection
    make_permuted_index_collection(article, Permuted_index_collection);

    // sort the Permuted_index_collection by the rotated_line string (i.e. the permuted index word)
    sort_permuted_index_collection(Permuted_index_collection);

    // extract and frame the left_block (left align)
    vector<string> left_block = frame(get_left_hand_side(Permuted_index_collection),"right",'*');

    // extract and frame the right block (right align)
    vector<string> right_block = frame(get_right_hand_side(Permuted_index_collection),"left",'*');

    // extract and frame the line_number block (left align)
    vector<string> line_number_block = frame(get_line_numbers(Permuted_index_collection),"left",'*');

    // extract and frame the word_number block (left align)
    vector<string> word_number_block = frame(get_word_numbers(Permuted_index_collection),"left",'*');

    // horizontal concatenate the blocks to form a permuted index page
    vector<string> Permuted_index_collection2 = hcat(left_block, right_block);
    vector<string> Permuted_index_collection3 = hcat(Permuted_index_collection2, line_number_block);
    vector<string> Permuted_index_collection4 = hcat(Permuted_index_collection3, word_number_block);

    // visualise the output
    vcout(Permuted_index_collection4);

    return 0;
}

Program Logic Step-by-step (in Pictures)

Here, I shall show you the logic that goes behind my own brain when I device this program.

Read the Input Article

I create a simple read function to read the input article (via the Standard Console Input), and parse the article to a vector<string> container – each line within the article is stored as a string object within the vector<string> container.

Acpp5p1pic5

// read lines via standard console input and append to article
vector<string> article = read_lines();

The read function looks like this:

vector<string> read_lines()
{
    string line;
    vector<string> ret;
    while (getline(cin, line))
        ret.push_back(line);

    return ret;
}

Create Permuted Index Objects

Now that we have the article stored in a vector<string>, our next step is to create a Permuted_index_collection container to store all the required Permuted_index objects (that will be created later on). Each Permuted_index object contains all the required information that we need to represent the particular line in the Permuted Index Page.

Firstly, we need to create an empty vector<Permuted_index> container for storing these Permuted_index objects later on.

Acpp5p1pic6

// prepare an empty Permuted_index_collection
vector<Permuted_index> Permuted_index_collection;

Now we have our Permuted_index_collection container we need to populate it with Permuted_index objects. We can use the “home-made” function make_permuted_index_collection to create new Permuted_index objects (using the vector<string> article created in the previously as input). This function will populate the vector<Permuted_index> Permuted_index_collection.

Acpp5p1pic7

// populate the Permuted_index_collection
make_permuted_index_collection(article, Permuted_index_collection);

As there are 8 words in the article, it is logical to expect 8 Permuted_index objects in total.

Acpp5p1pic8

Now, let’s talk more about each individual PermutePermuted_index object. Each Permuted_index object will contain 6 core properties which will be filled in by the function make_permuted_index_collection.

Acpp5p1pic31

These 6 properties, as we will see later on, will be proven extremely useful for us to construct that Permuted Index Page later on. For now, I will provide a brief description about these 6 properties. (and later on we will see these properties in action!)

vector<string>::size_type birth_id

The birth_id is number that I assign to the newly created Permuted_index object. This property will not actually be used downstream and is entirely optional. It is purely for me to keep track of the “seniority” of the object. As there are 8 words in the article I would expect to create 8 new Permuted_index objects. The first Permuted_index “born” will be labelled with birth_id 0. The second Permuted_index “born” will be labelled birth_id 1, etc…. the (last) 8th Permuted_index “born” will be labelled birth_id 7.

vector<string>::size_type line_number

There is a clue in the title. It keeps track of which line (within the article) the Permuted_index reside. Remember, line 0 is the first line. Line 1 is the second. Etc.

vector<string> line_elements

This is a vector<string> that contains all the words that appear in that particular line. For example, if this Permuted_index object corresponds to the key word “quick”, the line_elements would be {“The” “quick” “brown” “fox”}. i.e. it is the line that the key word “brown” resides. We store this line as vector<string> instead of string to enable us to generate that Permuted Index Page properly downstream (as you will see later on).

vector<string>::size_type position_in_line

This is the index position where the Permuted Index word appear in the line. Using the same example as above. The permuted index word “quick” corresponds to element 1 (i.e. second element) of the line_element {“The” “quick” “brown” “fox”}. I will demonstrate later on that the position_in_line is effectively the same as the number of rotations that we go through per line.

vector<string> rotated_line_elements

This is what the line_element will look like after we apply the rotations (we mention above that the number of rotations is the same value as position_in_line). Using the same example, if the Permuted_index word is “quick”, which has line_element of {“The” “quick” “brown” “fox”} and position_in_line (i.e. the rotations) of 1. Following a rotation (i.e. shifting words from right to left), the rotated_line_elements will be {“quick” “brown” “fox” “The” }. Notice that the goal of the rotation is to put that permuted index word “quick” to the front (element 0). For now, just accept it when I say, that the sole purpose of the rotated_line_elements is to help us do the “sorting” later on (as explained below).

string rotated_line

This is essentially a string version of the vector<string> rotated_line_elements. It shows what the line looks like after we apply the rotations. Using the same example. If the permuted index word is “quick”, which has rotated_line_element of {“quick” “brown” “fox” “The” }, the rotated_line is effectively “quick brown fox The”. The whole purpose of this property is for us to have a means to sort the Permuted_index objects within the vector<Permuted_index> container, by the rotated_line. i.e. we have a means to have a sorted Permuted Index Page by the Permuted Index words in alphabetical order.

Populate the Permuted Index Collection Container

Now, let’s go back to what happen when we use the function make_permuted_index_collection. The function essentially takes the vector<string> article as input, and go through multiple for loops in order to create each Permuted_index object sequentially and fill in the 6 properties (as described above).

There are two for loops.

  1. The outer for loop iterates through the lines in vector<string> article.
  2. The inner (nested) for loop iterates through each word along that particular line.

Acpp5p1pic32

This is what the function make_permuted_index_collection looks like. As you will see, all I am doing here are:

  1. Create a new Permuted_index object.
  2. Fill in the 6 properties for the newly created Permuted_index object.
  3. Add that new Permuted_index object to the vector<Permuted_index> Permuted_index_collection container.
void make_permuted_index_collection(const vector<string>& line_collection,
                                    vector<Permuted_index>& permuted_index_collection)
{
    // Input: line_collection
    // Output: permuted_index_collection

    vector<string>::size_type birth_count = 0;
    vector<string>::size_type line_number = 0;

    // create Permuted_index object fred one-by-one and parse to the permuted_index_collection
    for (vector<string>::size_type i = 0; i != line_collection.size(); ++i)
    {
        string line = line_collection[i];
        vector<string> words = split(line);

        // initialise fred's properties before we perform line element rotations
        std::vector<std::string>::size_type rotations = 0;
        vector<string> ro_words = words;

        for (vector<string>::size_type j = 0; j != words.size(); ++j)
        {
            // Create permuted_index object fred
            Permuted_index fred;
            fred.birth_id = birth_count;
            fred.line_number = line_number;
            fred.line_elements = words;
            fred.position_in_line = rotations;
            fred.rotated_line_elements = ro_words;
            fred.rotated_line = string_from_vec_str(ro_words);

            // append to the permuted_index_collection
            permuted_index_collection.push_back(fred);

            // re-initialise
            ro_words = rotate_line_elements(ro_words);
            ++rotations;
            ++birth_count;
        }
        ++line_number;
    }
}

The split function was explained in the text book (S5.6/88) and also in my Solution to Exercise 5-0 (Part 2/3), so I would not repeat here.

Note that fred.line_number and line_number are two different things within the code. fred.line_number corresponds to the property of the Permuted_index object. Whereas line_number corresponds to the local variable within the scope of make_permuted_index_collection. In the code we are simply filling the fred.line_number with the local calculated line_number. Other properties of “fred” are filled in pretty much the same way.

We have a rotate_line_elements function here. This is a “home made” function that I create to rotate the the line_elements – i.e. each rotation shifts the word to the left. If we rotate element 0, it gets rotated to the last element. (it just cycle through).

This is what the rotate_line_element function looks like.

vector<string> rotate_line_elements(const vector<string>& words)
{
    vector<string> ret;
    typedef vector<string>::size_type vc_sz;
    vc_sz size = words.size();

    for (vc_sz i = 0; i != size; ++i)
    {
        if (i == size - 1)
            ret.push_back(words[0]);
        else
            ret.push_back(words[i + 1]);
    }

    return ret;
}

For completeness and understanding sake, the following diagrams summarise the (6 core) properties of the 8 newly created Permuted_index objects, as a result of running the function make_permuted_index_collection.

Permuted_index object 0

Acpp5p1pic9

Permuted_index object 1

Acpp5p1pic10

Permuted_index object 2

Acpp5p1pic11

Permuted_index object 3

Acpp5p1pic12

Permuted_index object 4

Acpp5p1pic13

Permuted_index object 5

Acpp5p1pic14

Permuted_index object 6

Acpp5p1pic15

Permuted_index object 7

Acpp5p1pic16

Sort the Permuted Index Objects

OK. Our vector<string> Permuted_index_collection container is now populated. We are ready to do the sort (so the Permuted_index objects appear in alphabetical order within the Permuted Index Page).

We sort the Permuted_index object by one of its properties, the rotated_line which is of type string.

Acpp5p1pic17

We use a “home made” function sort_permuted_index_collection that helps us do this.

// sort the Permuted_index_collection by the rotated_line string (i.e. the permuted index word)
sort_permuted_index_collection(Permuted_index_collection);

This is what the function sort_permuted_index_collection looks like

void sort_permuted_index_collection(vector<Permuted_index>& x)
{
    sort(x.begin(), x.end(), compare);
}

As we are sorting Permuted_index objects by the property rotated_line string, we need to specify the “compare” argument.

bool compare(const Permuted_index& x, const Permuted_index& y)
{
    return lowcase(x.rotated_line) < lowcase(y.rotated_line);
}

Because I wish to sort the string regardless of upper or lower case, I use the “home made” lowcase function to essentially convert the strings to lower case before comparing (with the < operator). This way the letter case become insensitive which is what we want.

The “home made” lowcase function looks like this and it essentially converts all the char elements within the string to lower cases (with the help of the standard tolower function)

string lowcase(const string& s)
{
    string ret;
    for (string::size_type i = 0; i != s.size(); ++i)
    {
        ret.push_back(tolower(s[i]));
    }
    return ret;
}

The vector<Permuted_index> container now looks like this:

Acpp5p1pic19

Each “row” above corresponds to the properties of a Permuted_index object.

Create the “Four Blocks”

Now that our vector<Permuted_index> Permuted_index_collection container is created and sorted, we can use it and create the “four blocks” which we can combine together at the end to form our final Permuted Index Page. Below shows what the “Four blocks” will look like after we have created these.

Acpp5p1pic18

Note that each block is of type vector<string>. And each string element is of the same width which we can horizontally concatenate them easily later on.

Bearing this diagram in mind, the following sub sections walk through the derivation of the “Four Blocks”, namely

  • the Left Hand Block (the “Block 1”)
  • the Right Hand Block (the “Block 2”)
  • the Line Number Block (the “Block 3”)
  • the Word Number Block (the “Block 4”)

To create each block, we do two things:

  1. Create the vector<string> container and populate with the requirement elements.
  2. Apply the (enhanced home made) frame function against the vector<string> container to ensure all string elements are of the same (optimum) size (i.e. the width of the “block”). So that when we use the (home made) vcout function to display the vector<string> it appears like a “block” as the empty strings are all padded with empty spaces. The enhanced frame function will have the ability to left-align or right-align the string elements. The frame function will also provide us an option to choose what type of border character that suits our liking. (e.g. it can be a “*”, but it can also be something else if we wish).
The Enhanced Frame Function

The enhanced frame function is built on the original one as per text book (S5.8/93) and also my Solution to Exercise 5-0 (Part 3/3). The enhanced version offer two new options. i.e. (1) Right / Left align string elements, (2) flexible choice of border character. The enhanced frame function looks like this.

vector<string> frame(const vector<string>& v, const string& align, char c)
{
    vector<string> ret;
    string::size_type maxlen = width(v);
    string symbol(1, c);
    string border(maxlen + 4, c);

    // write the top border
    ret.push_back(border);

    // write each interior row, bordered by an asterisk and a space
    for (vector<string>::size_type i = 0; i != v.size(); ++i)
        if (align == "left")
            ret.push_back(symbol + " " + v[i] + string(maxlen - v[i].size(), ' ') + " " + symbol);
        else if (align == "right")
            ret.push_back(symbol + " " + string(maxlen - v[i].size(), ' ') + v[i]  + " " + symbol);

    // write the bottom border
    ret.push_back(border);

    return ret;
}

The frame function uses the (home made) width function which is already explained in the text book (S5.8.1/92) and also my Solution to Exercise 5-0 (Part 3/3).

Create the Left Hand Block (the “Block 1”)
// extract and frame the left_block (left align)
vector<string> left_block = frame(get_left_hand_side(Permuted_index_collection),"right",'*');

Acpp5p1pic20

Acpp5p1pic21

This is what the function get_left_hand_side looks like:

vector<string> get_left_hand_side(const vector<Permuted_index>& v)
{
    vector<string> ret;

    for (vector<Permuted_index>::const_iterator iter1 = v.begin();
            iter1 != v.end(); ++iter1)
    {
        vector<string> words = iter1->line_elements;
        vector<string>::size_type permuted_index_pos = iter1->position_in_line;
        string s;
        for (vector<string>::size_type i = 0; i != permuted_index_pos; ++i)
        {
            if (i == 0)
                s += words[i];
            else
                s += (" " + words[i]);
        }
        ret.push_back(s);
    }
    return ret;
}
Create the Right Hand Block (the “Block 2”)
// extract and frame the right block (right align)
vector<string> right_block = frame(get_right_hand_side(Permuted_index_collection),"left",'*');

Acpp5p1pic22

Acpp5p1pic23

This is what the function get_right_hand_side looks like:

vector<string> get_right_hand_side(const vector<Permuted_index>& v)
{
    vector<string> ret;</p>

<pre><code>for (vector<Permuted_index>::const_iterator iter1 = v.begin();
        iter1 != v.end(); ++iter1)
{
    vector<string> words = iter1->line_elements;
    vector<string>::size_type permuted_index_pos = iter1->position_in_line;
    string s;
    for (vector<string>::size_type i = permuted_index_pos; i != words.size(); ++i)
    {
        if (i == permuted_index_pos)
            s += words[i];
        else
            s += (" " + words[i]);
    }
    ret.push_back(s);
}
return ret;
Create the Line Number Block (the “Block 3”)
// extract and frame the line_number block (left align)
vector<string> line_number_block = frame(get_line_numbers(Permuted_index_collection),"left",'*');

Acpp5p1pic24

Acpp5p1pic25

This is what the function get_line_numbers looks like:

vector<string> get_line_numbers(const vector<Permuted_index>& v)
{
    vector<string> ret;

    for (vector<Permuted_index>::const_iterator iter1 = v.begin();
            iter1 != v.end(); ++iter1)
    {
        string s = "Line " + string_from_vec_str_size_type((iter1->line_number));
        ret.push_back(s);
    }
    return ret;
}

Note that Permuted_index::line_number is of type vector<string>::size_type. I would therefore need to do a conversion to string type. I created this home-made function string_from_vec_str_size_type which will help me to achieve this. The creation of this conversion function is inspired by this page on cplusplus.com.

The function string_from_vec_str_size_type looks like this (it requires the header <sstream> and the std::ostringstream as per the cplusplus.com page)

string string_from_vec_str_size_type(const vector<string>::size_type& any_size_type)
{
    string ret;              // string which will contain the result
    ostringstream convert;   // stream used for the conversion
    convert << any_size_type;      // insert the textual representation of 'Number' in the characters in the stream
    ret = convert.str();        // set 'any_integer' to the contents of the stream
    return ret;
}
Create the Word Number Block (the “Block 4”)
// extract and frame the word_number block (left align)
vector<string> word_number_block = frame(get_word_numbers(Permuted_index_collection),"left",'*');

Acpp5p1pic26

Acpp5p1pic27

This is what the function get_word_numbers looks like:

vector<string> get_word_numbers(const vector<Permuted_index>& v)
{
    vector<string> ret;

    for (vector<Permuted_index>::const_iterator iter1 = v.begin();
            iter1 != v.end(); ++iter1)
    {
        string s = "Word " + string_from_vec_str_size_type((iter1->position_in_line));
        ret.push_back(s);
    }
    return ret;
}

Note that Permuted_index::position_in_line is of type std::vector<std::string>::size_type, so we use the home-made function string_from_vec_str_size_type as explained in the previous section above.

Horizontal Concatenate the “Four Blocks”

Recall from the Solution to Exercise 5-0 (Part 3/3), or text book Chapter 5, we have the function hcat already on standby to easily concatenate two vectors horizontally. This is the time to use this hcat function!

Our goal is to horizontally concatenate the “Four Blocks” that we have just created.

Acpp5p1pic28

Though we can concatenate the “Four Blocks” all in one pass, for clarity sake I have decided to concatenate two vectors at a time. i.e.

// horizontal concatenate the blocks to form a permuted index page
vector<string> Permuted_index_collection2 = hcat(left_block, right_block);
vector<string> Permuted_index_collection3 = hcat(Permuted_index_collection2, line_number_block);
vector<string> Permuted_index_collection4 = hcat(Permuted_index_collection3, word_number_block);

Display the Permuted Index Page

Now that we have concatenated horizontally the “Four Blocks” into one vector<string> Permuted_index_collection4, let’s display it!

// visualise the output
vcout(Permuted_index_collection4);

I have created a simple function called vcout to help us do this. In fact I created this during my Solution to Exercise 5-0 (Part 3/3) so I am not going to re-explain here.

All we need to know is that, by applying the vcout function against the vector<string> Permuted_index_collection4, we get something like the following in the console output window – a Permuted Index Page!

Acpp5p1pic29

And this is it!

The Complete Project

To wrap up, let me document this entire Project here, including all the C++ source codes and header files here all in one place.

Acpp5p1MgntTree

Source File List

Header File List

Source Files

main.cpp

#include <string>               // std::string
#include <vector>               // std::vector
#include "read_lines.h"         // read_lines
#include "Permuted_index.h"     // Permuted_index
#include "split.h"              // split
#include "frame.h"              // frame
#include "hcat.h"               // hcat
#include "vcout.h"              // vcout

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

int main()
{

    // read lines via standard console input and append to article
    vector<string> article = read_lines();

    // prepare an empty Permuted_index_collection
    vector<Permuted_index> Permuted_index_collection;

    // populate the Permuted_index_collection
    make_permuted_index_collection(article, Permuted_index_collection);

    // sort the Permuted_index_collection by the rotated_line string (i.e. the permuted index word)
    sort_permuted_index_collection(Permuted_index_collection);

    // extract and frame the left_block (left align)
    vector<string> left_block = frame(get_left_hand_side(Permuted_index_collection),"right",'*');

    // extract and frame the right block (right align)
    vector<string> right_block = frame(get_right_hand_side(Permuted_index_collection),"left",'*');

    // extract and frame the line_number block (left align)
    vector<string> line_number_block = frame(get_line_numbers(Permuted_index_collection),"left",'*');

    // extract and frame the word_number block (left align)
    vector<string> word_number_block = frame(get_word_numbers(Permuted_index_collection),"left",'*');

    // horizontal concatenate the blocks to form a permuted index page
    vector<string> Permuted_index_collection2 = hcat(left_block, right_block);
    vector<string> Permuted_index_collection3 = hcat(Permuted_index_collection2, line_number_block);
    vector<string> Permuted_index_collection4 = hcat(Permuted_index_collection3, word_number_block);

    // visualise the output
    vcout(Permuted_index_collection4);

    return 0;
}

frame.cpp

#include <string>      // std::string
#include <vector>      // std::vector
#include <algorithm>   // std::max

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

string::size_type width(const vector<string>& v)
{
    string::size_type maxlen = 0;
    for(vector<string>::size_type i = 0; i != v.size(); ++i)
        maxlen = max(maxlen, v[i].size());
    return maxlen;
}

vector<string> frame(const vector<string>& v, const string& align, char c)
{
    vector<string> ret;
    string::size_type maxlen = width(v);
    string symbol(1, c);
    string border(maxlen + 4, c);

    // write the top border
    ret.push_back(border);

    // write each interior row, bordered by an asterisk and a space
    for (vector<string>::size_type i = 0; i != v.size(); ++i)
        if (align == "left")
            ret.push_back(symbol + " " + v[i] + string(maxlen - v[i].size(), ' ') + " " + symbol);
        else if (align == "right")
            ret.push_back(symbol + " " + string(maxlen - v[i].size(), ' ') + v[i]  + " " + symbol);

    // write the bottom border
    ret.push_back(border);

    return ret;
}

hcat.cpp

#include <string>      // std::string
#include <vector>      // std::vector
#include "frame.h"     // width

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

vector<string> hcat(const vector<string>& left, const vector<string>& right)
{
    vector<string> ret;

    // add 1 to leave a space between pictures
    string::size_type width1 = width(left) + 1;

    // indices to look at elements from left and right respectively
    vector<string>::size_type i = 0, j = 0;

    // continue until we've seen all rows from both pictures
    while (i != left.size() || j != right.size())
    {
        // construct new string to hold characters from both pictures
        string s;

        // copy a row from the left-hand side, if there is one
        if (i != left.size())
            s = left[i++];

        // pad to full width
        s += string(width1 - s.size(), ' ');

        // copy a row from teh right-hand side, if there is one
        if (j != right.size())
            s += right[j++];

        // add s to the picture we are creating
        ret.push_back(s);
    }

    return ret;
}

Permuted_index.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <sstream>   // ostringstream
#include "split.h"
#include "Permuted_index.h"

using std::string;
using std::vector;
using std::cin;
using std::cout;
using std::endl;
using std::tolower;
using std::sort;
using std::ostringstream;

vector<string> rotate_line_elements(const vector<string>& words)
{
    vector<string> ret;
    typedef vector<string>::size_type vc_sz;
    vc_sz size = words.size();

    for (vc_sz i = 0; i != size; ++i)
    {
        if (i == size - 1)
            ret.push_back(words[0]);
        else
            ret.push_back(words[i + 1]);
    }

    return ret;
}

string string_from_vec_str(const vector<string>& words)
{
    string ret;
    typedef vector<string>::const_iterator vc_citer;
    for (vc_citer iter = words.begin(); iter != words.end(); ++iter)
        if (iter == words.begin())
            ret += *iter;
        else
            ret += (" " + *iter);

    return ret;
}

void make_permuted_index_collection(const vector<string>& line_collection,
                                    vector<Permuted_index>& permuted_index_collection)
{
    // Input: line_collection
    // Output: permuted_index_collection

    vector<string>::size_type birth_count = 0;
    vector<string>::size_type line_number = 0;

    // create Permuted_index object fred one-by-one and parse to the permuted_index_collection
    for (vector<string>::size_type i = 0; i != line_collection.size(); ++i)
    {
        string line = line_collection[i];
        vector<string> words = split(line);

        // initialise fred's properties before we perform line element rotations
        std::vector<std::string>::size_type rotations = 0;
        vector<string> ro_words = words;

        for (vector<string>::size_type j = 0; j != words.size(); ++j)
        {
            // Create permuted_index object fred
            Permuted_index fred;
            fred.birth_id = birth_count;
            fred.line_number = line_number;
            fred.line_elements = words;
            fred.position_in_line = rotations;
            fred.rotated_line_elements = ro_words;
            fred.rotated_line = string_from_vec_str(ro_words);

            // append to the permuted_index_collection
            permuted_index_collection.push_back(fred);

            // re-initialise
            ro_words = rotate_line_elements(ro_words);
            ++rotations;
            ++birth_count;
        }
        ++line_number;
    }
}

string lowcase(const string& s)
{
    string ret;
    for (string::size_type i = 0; i != s.size(); ++i)
    {
        ret.push_back(tolower(s[i]));
    }
    return ret;
}

bool compare(const Permuted_index& x, const Permuted_index& y)
{
    return lowcase(x.rotated_line) < lowcase(y.rotated_line);
}

void sort_permuted_index_collection(vector<Permuted_index>& x)
{
    sort(x.begin(), x.end(), compare);
}

// (for quick test purpose) use this function to visualise the vector<Permuted_index> collection quickly
void print_permuted_index_collection(const vector<Permuted_index>& collection)
{
    for (vector<Permuted_index>::const_iterator iter = collection.begin(); iter != collection.end(); ++iter)
        cout << " Permuted_index: " << iter->birth_id
             << " | " << iter->line_number
             << " | " << string_from_vec_str(iter->line_elements)
             << " | " << iter->position_in_line
             << " | " << string_from_vec_str(iter->rotated_line_elements)
             << " | " << iter->rotated_line
             << " | " << iter->line_elements[iter->position_in_line]
             << endl;
}

vector<string> get_left_hand_side(const vector<Permuted_index>& v)
{
    vector<string> ret;

    for (vector<Permuted_index>::const_iterator iter1 = v.begin();
            iter1 != v.end(); ++iter1)
    {
        vector<string> words = iter1->line_elements;
        vector<string>::size_type permuted_index_pos = iter1->position_in_line;
        string s;
        for (vector<string>::size_type i = 0; i != permuted_index_pos; ++i)
        {
            if (i == 0)
                s += words[i];
            else
                s += (" " + words[i]);
        }
        ret.push_back(s);
    }
    return ret;
}

vector<string> get_right_hand_side(const vector<Permuted_index>& v)
{
    vector<string> ret;

    for (vector<Permuted_index>::const_iterator iter1 = v.begin();
            iter1 != v.end(); ++iter1)
    {
        vector<string> words = iter1->line_elements;
        vector<string>::size_type permuted_index_pos = iter1->position_in_line;
        string s;
        for (vector<string>::size_type i = permuted_index_pos; i != words.size(); ++i)
        {
            if (i == permuted_index_pos)
                s += words[i];
            else
                s += (" " + words[i]);
        }
        ret.push_back(s);
    }
    return ret;
}

// convert from number to string (http://www.cplusplus.com/articles/D9j2Nwbp/)
string string_from_int(int any_integer)
{
    string ret;              // string which will contain the result
    ostringstream convert;   // stream used for the conversion
    convert << any_integer;      // insert the textual representation of 'Number' in the characters in the stream
    ret = convert.str();        // set 'any_integer' to the contents of the stream
    return ret;
}

// clone from the same technique. i.e. convert from number to string (http://www.cplusplus.com/articles/D9j2Nwbp/)
// except i have replaced the parameter type from int, to const vector<string>::size_type&
string string_from_vec_str_size_type(const vector<string>::size_type& any_size_type)
{
    string ret;              // string which will contain the result
    ostringstream convert;   // stream used for the conversion
    convert << any_size_type;      // insert the textual representation of 'Number' in the characters in the stream
    ret = convert.str();        // set 'any_integer' to the contents of the stream
    return ret;
}

vector<string> get_line_numbers(const vector<Permuted_index>& v)
{
    vector<string> ret;

    for (vector<Permuted_index>::const_iterator iter1 = v.begin();
            iter1 != v.end(); ++iter1)
    {
        string s = "Line " + string_from_vec_str_size_type((iter1->line_number));
        ret.push_back(s);
    }
    return ret;
}

vector<string> get_word_numbers(const vector<Permuted_index>& v)
{
    vector<string> ret;

    for (vector<Permuted_index>::const_iterator iter1 = v.begin();
            iter1 != v.end(); ++iter1)
    {
        string s = "Word " + string_from_vec_str_size_type((iter1->position_in_line));
        ret.push_back(s);
    }
    return ret;
}

read_lines.cpp

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

using std::string;
using std::vector;
using std::cin;
using std::getline;

// Read lines and return the line collection
vector<string> read_lines()
{
    string line;
    vector<string> ret;
    while (getline(cin, line))
        ret.push_back(line);

    return ret;
}

split.cpp

#include <string>    // std::string
#include <vector>    // std::vector
#include <cctype>    // std::isspace

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

// scan a string of texts, split into words, return a vector that contains these words.
// (S5.6/88)
vector<string> split(const string& s)
{
    vector<string> ret;
    typedef string::size_type string_size;
    string_size i = 0;

    // invariant: we have processed characters original value of [i, i)
    while (i != s.size() )
    {
        // ignore leading blanks
        // invariant: characters in range [original i, current i)
        while (i != s.size() && isspace(s[i]))
            ++i;

        // find end of next word
        string_size j = i;

        // invariant: none of the characters in range [original j, current j) is a space
        while (j != s.size() && !isspace(s[j]))
            ++j;

        // if we found some non-whitespace characters
        if (i != j)
            // copy from s starting at i and taking j - i chars
            ret.push_back(s.substr(i, j - i));
            i = j;
    }
    return ret;
}

vcout.cpp

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

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

int vcout(const vector<string>& v)
{
    for (vector<string>::const_iterator iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

frame.h

#ifndef GUARD_FRAME_H
#define GUARD_FRAME_H

#include <string>
#include <vector>

std::string::size_type width(const std::vector<std::string>&);
std::vector<std::string> frame(const std::vector<std::string>&, const std::string&, const char);

#endif // GUARD_FRAME_H

hcat.h

#ifndef GUARD_HCAT_H
#define GUARD_HCAT_H

#include <string>
#include <vector>

std::vector<std::string> hcat(const std::vector<std::string>&, const std::vector<std::string>&);

#endif // GUARD_HCAT_H

Permuted_index.h

#ifndef GUARD_PERMUTED_INDEX_H
#define GUARD_PERMUTED_INDEX_H

#include <string>
#include <vector>

struct Permuted_index
{
    std::vector<std::string>::size_type birth_id;
    std::vector<std::string>::size_type line_number;
    std::vector<std::string> line_elements;
    std::vector<std::string>::size_type position_in_line;
    std::vector<std::string> rotated_line_elements;
    std::string rotated_line;
};

bool compare(const Permuted_index&, const Permuted_index&);

std::string string_from_vec_str(const std::vector<std::string>&);
std::string string_from_vec_str_size_type(const std::vector<std::string>::size_type&);
std::string string_from_int(int);

void make_permuted_index_collection(const std::vector<std::string>&, std::vector<Permuted_index>&);
void sort_permuted_index_collection(std::vector<Permuted_index>&);
void print_permuted_index_collection(const std::vector<Permuted_index>&);

std::vector<std::string> rotate_line_elements(const std::vector<std::string>&);
std::vector<std::string> get_left_hand_side(const std::vector<Permuted_index>&);
std::vector<std::string> get_right_hand_side(const std::vector<Permuted_index>&);
std::vector<std::string> get_line_numbers(const std::vector<Permuted_index>&);
std::vector<std::string> get_word_numbers(const std::vector<Permuted_index>&);

#endif // GUARD_PERMUTED_INDEX_H

read_lines.h

#ifndef GUARD_READ_LINES_H
#define GUARD_READ_LINES_H

#include <string>
#include <vector>

std::vector<std::string> read_lines();

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

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

int vcout(const std::vector<std::string>&);

#endif // GUARD_VCOUT_H

Test Program

This summarises my program test input and output.

Test 1  – The quick brown fox

The quick brown fox
jumped over the fence
^Z
******************* ************************* ********** **********
*       The quick * * brown fox             * * Line 0 * * Word 2 *
* jumped over the * * fence                 * * Line 1 * * Word 3 *
* The quick brown * * fox                   * * Line 0 * * Word 3 *
*                 * * jumped over the fence * * Line 1 * * Word 0 *
*          jumped * * over the fence        * * Line 1 * * Word 1 *
*             The * * quick brown fox       * * Line 0 * * Word 1 *
*     jumped over * * the fence             * * Line 1 * * Word 2 *
*                 * * The quick brown fox   * * Line 0 * * Word 0 *
******************* ************************* ********** **********

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

Test 2  – Shakespeare’s To be, or Not to be

Just to make sure the program works regardless of article content. let’s try and create a Permuted Index Page for William Shakespeare’s famous poem “To be, or Not to be”. And the program works! (cool isn’t it!)

When he himself might his quietus make
With a bare bodkin? who would fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscover'd country from whose bourn
No traveller returns, puzzles the will
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all;
And thus the native hue of resolution
Is sicklied o'er with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn awry,
And lose the name of action. - Soft you now!
The fair Ophelia! Nymph, in thy orisons
Be all my sins remember'd.
^Z
************************************************* ****************************************************** *********** **********
*                        That flesh is heir to, * * 'tis a consummation                                * * Line 7  * * Word 5 *
*                                       Whether * * 'tis nobler in the mind to suffer                  * * Line 1  * * Word 1 *
*                  And lose the name of action. * * - Soft you now!                                    * * Line 32 * * Word 6 *
*                                          With * * a bare bodkin? who would fardels bear,             * * Line 20 * * Word 1 *
*                   That flesh is heir to, 'tis * * a consummation                                     * * Line 7  * * Word 6 *
*                       Or to take arms against * * a sea of troubles,                                 * * Line 3  * * Word 5 *
*                               No more; and by * * a sleep to say we end                              * * Line 5  * * Word 4 *
*                      To grunt and sweat under * * a weary life,                                      * * Line 21 * * Word 5 *
*                          And lose the name of * * action. - Soft you now!                            * * Line 32 * * Word 5 *
*               But that the dread of something * * after death,                                       * * Line 22 * * Word 6 *
*                               Or to take arms * * against a sea of troubles,                         * * Line 3  * * Word 4 *
*                                            Be * * all my sins remember'd.                            * * Line 34 * * Word 1 *
*       Thus conscience does make cowards of us * * all;                                               * * Line 27 * * Word 7 *
*                                    The slings * * and arrows of outrageous fortune,                  * * Line 2  * * Word 2 *
*                                      No more; * * and by a sleep to say we end                       * * Line 5  * * Word 2 *
*                                               * * And by opposing end them? To die: to sleep;        * * Line 4  * * Word 0 *
*                                               * * And enterprises of great pith and moment           * * Line 30 * * Word 0 *
*                                               * * And lose the name of action. - Soft you now!       * * Line 32 * * Word 0 *
*                                               * * And makes us rather bear those ills we have        * * Line 25 * * Word 0 *
*                 And enterprises of great pith * * and moment                                         * * Line 30 * * Word 5 *
*                  For who would bear the whips * * and scorns of time,                                * * Line 14 * * Word 6 *
*                                      To grunt * * and sweat under a weary life,                      * * Line 21 * * Word 2 *
*                       The insolence of office * * and the spurns                                     * * Line 17 * * Word 4 *
*                                The heart-ache * * and the thousand natural shocks                    * * Line 6  * * Word 2 *
*                                               * * And thus the native hue of resolution              * * Line 28 * * Word 0 *
*                                    Or to take * * arms against a sea of troubles,                    * * Line 3  * * Word 3 *
*                                The slings and * * arrows of outrageous fortune,                      * * Line 2  * * Word 3 *
*          With this regard their currents turn * * awry,                                              * * Line 31 * * Word 6 *
*                 To sleep: perchance to dream: * * ay, there's the rub;                               * * Line 9  * * Word 5 *
*                                        With a * * bare bodkin? who would fardels bear,               * * Line 20 * * Word 2 *
*                                               * * Be all my sins remember'd.                         * * Line 34 * * Word 0 *
*                                   Devoutly to * * be wish'd. To die, to sleep;                       * * Line 8  * * Word 2 *
*                                            To * * be, or not to be: that is the question:            * * Line 0  * * Word 1 *
*                              To be, or not to * * be: that is the question:                          * * Line 0  * * Word 5 *
*                                 For who would * * bear the whips and scorns of time,                 * * Line 14 * * Word 3 *
*                           And makes us rather * * bear those ills we have                            * * Line 25 * * Word 4 *
*         With a bare bodkin? who would fardels * * bear,                                              * * Line 20 * * Word 7 *
*                                   With a bare * * bodkin? who would fardels bear,                    * * Line 20 * * Word 3 *
*           The undiscover'd country from whose * * bourn                                              * * Line 23 * * Word 5 *
*                                               * * But that the dread of something after death,       * * Line 22 * * Word 0 *
*                                  No more; and * * by a sleep to say we end                           * * Line 5  * * Word 3 *
*                                           And * * by opposing end them? To die: to sleep;            * * Line 4  * * Word 1 *
*                                    That makes * * calamity of so long life;                          * * Line 13 * * Word 2 *
*                Is sicklied o'er with the pale * * cast of thought,                                   * * Line 29 * * Word 6 *
*         When we have shuffled off this mortal * * coil,                                              * * Line 11 * * Word 7 *
*    For in that sleep of death what dreams may * * come                                               * * Line 10 * * Word 9 *
*                                          Thus * * conscience does make cowards of us all;            * * Line 27 * * Word 1 *
*                 That flesh is heir to, 'tis a * * consummation                                       * * Line 7  * * Word 7 *
*        The oppressor's wrong, the proud man's * * contumely,                                         * * Line 15 * * Word 6 *
*                              The undiscover'd * * country from whose bourn                           * * Line 23 * * Word 2 *
*                     Thus conscience does make * * cowards of us all;                                 * * Line 27 * * Word 4 *
*                        With this regard their * * currents turn awry,                                * * Line 31 * * Word 4 *
*                          For in that sleep of * * death what dreams may come                         * * Line 10 * * Word 5 *
*         But that the dread of something after * * death,                                             * * Line 22 * * Word 7 *
*         The pangs of despised love, the law's * * delay,                                             * * Line 16 * * Word 7 *
*                                  The pangs of * * despised love, the law's delay,                    * * Line 16 * * Word 3 *
*                                               * * Devoutly to be wish'd. To die, to sleep;           * * Line 8  * * Word 0 *
*                     Devoutly to be wish'd. To * * die, to sleep;                                     * * Line 8  * * Word 5 *
*                  And by opposing end them? To * * die: to sleep;                                     * * Line 4  * * Word 6 *
*                               Thus conscience * * does make cowards of us all;                       * * Line 27 * * Word 2 *
*                                  But that the * * dread of something after death,                    * * Line 22 * * Word 3 *
*                        To sleep: perchance to * * dream: ay, there's the rub;                        * * Line 9  * * Word 4 *
*               For in that sleep of death what * * dreams may come                                    * * Line 10 * * Word 7 *
*             No more; and by a sleep to say we * * end                                                * * Line 5  * * Word 9 *
*                               And by opposing * * end them? To die: to sleep;                        * * Line 4  * * Word 3 *
*                                           And * * enterprises of great pith and moment               * * Line 30 * * Word 1 *
*                                           The * * fair Ophelia! Nymph, in thy orisons                * * Line 33 * * Word 1 *
*                 With a bare bodkin? who would * * fardels bear,                                      * * Line 20 * * Word 6 *
*                                          That * * flesh is heir to, 'tis a consummation              * * Line 7  * * Word 1 *
*                                          Than * * fly to others that we know not of?                 * * Line 26 * * Word 1 *
*                                               * * For in that sleep of death what dreams may come    * * Line 10 * * Word 0 *
*                                               * * For who would bear the whips and scorns of time,   * * Line 14 * * Word 0 *
*           The slings and arrows of outrageous * * fortune,                                           * * Line 2  * * Word 6 *
*                      The undiscover'd country * * from whose bourn                                   * * Line 23 * * Word 3 *
*                                          Must * * give us pause: there's the respect                 * * Line 12 * * Word 1 *
*                            And enterprises of * * great pith and moment                              * * Line 30 * * Word 3 *
*                                            To * * grunt and sweat under a weary life,                * * Line 21 * * Word 1 *
*        And makes us rather bear those ills we * * have                                               * * Line 25 * * Word 8 *
*                                       When we * * have shuffled off this mortal coil,                * * Line 11 * * Word 2 *
*                                          When * * he himself might his quietus make                  * * Line 19 * * Word 1 *
*                                           The * * heart-ache and the thousand natural shocks         * * Line 6  * * Word 1 *
*                                 That flesh is * * heir to, 'tis a consummation                       * * Line 7  * * Word 3 *
*                                       When he * * himself might his quietus make                     * * Line 19 * * Word 2 *
*                         When he himself might * * his quietus make                                   * * Line 19 * * Word 4 *
*                           And thus the native * * hue of resolution                                  * * Line 28 * * Word 4 *
*                And makes us rather bear those * * ills we have                                       * * Line 25 * * Word 6 *
*                                           For * * in that sleep of death what dreams may come        * * Line 10 * * Word 1 *
*                           Whether 'tis nobler * * in the mind to suffer                              * * Line 1  * * Word 3 *
*                      The fair Ophelia! Nymph, * * in thy orisons                                     * * Line 33 * * Word 4 *
*                                           The * * insolence of office and the spurns                 * * Line 17 * * Word 1 *
*                                    That flesh * * is heir to, 'tis a consummation                    * * Line 7  * * Word 2 *
*                                               * * Is sicklied o'er with the pale cast of thought,    * * Line 29 * * Word 0 *
*                     To be, or not to be: that * * is the question:                                   * * Line 0  * * Word 7 *
*                    Than fly to others that we * * know not of?                                       * * Line 26 * * Word 6 *
*               The pangs of despised love, the * * law's delay,                                       * * Line 16 * * Word 6 *
*              To grunt and sweat under a weary * * life,                                              * * Line 21 * * Word 7 *
*                That makes calamity of so long * * life;                                              * * Line 13 * * Word 6 *
*                     That makes calamity of so * * long life;                                         * * Line 13 * * Word 5 *
*                                           And * * lose the name of action. - Soft you now!           * * Line 32 * * Word 1 *
*                         The pangs of despised * * love, the law's delay,                             * * Line 16 * * Word 4 *
*                          Thus conscience does * * make cowards of us all;                            * * Line 27 * * Word 3 *
*             When he himself might his quietus * * make                                               * * Line 19 * * Word 6 *
*                                          That * * makes calamity of so long life;                    * * Line 13 * * Word 1 *
*                                           And * * makes us rather bear those ills we have            * * Line 25 * * Word 1 *
*              The oppressor's wrong, the proud * * man's contumely,                                   * * Line 15 * * Word 5 *
*        For in that sleep of death what dreams * * may come                                           * * Line 10 * * Word 8 *
*                                  That patient * * merit of the unworthy takes,                       * * Line 18 * * Word 2 *
*                               When he himself * * might his quietus make                             * * Line 19 * * Word 3 *
*                    Whether 'tis nobler in the * * mind to suffer                                     * * Line 1  * * Word 5 *
*             And enterprises of great pith and * * moment                                             * * Line 30 * * Word 6 *
*                                            No * * more; and by a sleep to say we end                 * * Line 5  * * Word 1 *
*                When we have shuffled off this * * mortal coil,                                       * * Line 11 * * Word 6 *
*                                               * * Must give us pause: there's the respect            * * Line 12 * * Word 0 *
*                                        Be all * * my sins remember'd.                                * * Line 34 * * Word 2 *
*                                  And lose the * * name of action. - Soft you now!                    * * Line 32 * * Word 3 *
*                                  And thus the * * native hue of resolution                           * * Line 28 * * Word 3 *
*               The heart-ache and the thousand * * natural shocks                                     * * Line 6  * * Word 5 *
*                                               * * No more; and by a sleep to say we end              * * Line 5  * * Word 0 *
*                                               * * No traveller returns, puzzles the will             * * Line 24 * * Word 0 *
*                                  Whether 'tis * * nobler in the mind to suffer                       * * Line 1  * * Word 2 *
*               Than fly to others that we know * * not of?                                            * * Line 26 * * Word 7 *
*                                     To be, or * * not to be: that is the question:                   * * Line 0  * * Word 3 *
*       And lose the name of action. - Soft you * * now!                                               * * Line 32 * * Word 9 *
*                             The fair Ophelia! * * Nymph, in thy orisons                              * * Line 33 * * Word 3 *
*                                   Is sicklied * * o'er with the pale cast of thought,                * * Line 29 * * Word 2 *
*                             And lose the name * * of action. - Soft you now!                         * * Line 32 * * Word 4 *
*                             For in that sleep * * of death what dreams may come                      * * Line 10 * * Word 4 *
*                                     The pangs * * of despised love, the law's delay,                 * * Line 16 * * Word 2 *
*                               And enterprises * * of great pith and moment                           * * Line 30 * * Word 2 *
*                                 The insolence * * of office and the spurns                           * * Line 17 * * Word 2 *
*                         The slings and arrows * * of outrageous fortune,                             * * Line 2  * * Word 4 *
*                       And thus the native hue * * of resolution                                      * * Line 28 * * Word 5 *
*                           That makes calamity * * of so long life;                                   * * Line 13 * * Word 3 *
*                            But that the dread * * of something after death,                          * * Line 22 * * Word 4 *
*                            That patient merit * * of the unworthy takes,                             * * Line 18 * * Word 3 *
*           Is sicklied o'er with the pale cast * * of thought,                                        * * Line 29 * * Word 7 *
*       For who would bear the whips and scorns * * of time,                                           * * Line 14 * * Word 8 *
*                 Or to take arms against a sea * * of troubles,                                       * * Line 3  * * Word 7 *
*             Thus conscience does make cowards * * of us all;                                         * * Line 27 * * Word 5 *
*           Than fly to others that we know not * * of?                                                * * Line 26 * * Word 8 *
*                         When we have shuffled * * off this mortal coil,                              * * Line 11 * * Word 4 *
*                              The insolence of * * office and the spurns                              * * Line 17 * * Word 3 *
*                                      The fair * * Ophelia! Nymph, in thy orisons                     * * Line 33 * * Word 2 *
*                                        And by * * opposing end them? To die: to sleep;               * * Line 4  * * Word 2 *
*                                           The * * oppressor's wrong, the proud man's contumely,      * * Line 15 * * Word 1 *
*                                        To be, * * or not to be: that is the question:                * * Line 0  * * Word 2 *
*                                               * * Or to take arms against a sea of troubles,         * * Line 3  * * Word 0 *
*               The fair Ophelia! Nymph, in thy * * orisons                                            * * Line 33 * * Word 6 *
*                                   Than fly to * * others that we know not of?                        * * Line 26 * * Word 3 *
*                      The slings and arrows of * * outrageous fortune,                                * * Line 2  * * Word 5 *
*                     Is sicklied o'er with the * * pale cast of thought,                              * * Line 29 * * Word 5 *
*                                           The * * pangs of despised love, the law's delay,           * * Line 16 * * Word 1 *
*                                          That * * patient merit of the unworthy takes,               * * Line 18 * * Word 1 *
*                                  Must give us * * pause: there's the respect                         * * Line 12 * * Word 3 *
*                                     To sleep: * * perchance to dream: ay, there's the rub;           * * Line 9  * * Word 2 *
*                      And enterprises of great * * pith and moment                                    * * Line 30 * * Word 4 *
*                    The oppressor's wrong, the * * proud man's contumely,                             * * Line 15 * * Word 4 *
*                         No traveller returns, * * puzzles the will                                   * * Line 24 * * Word 3 *
*              To be, or not to be: that is the * * question:                                          * * Line 0  * * Word 9 *
*                     When he himself might his * * quietus make                                       * * Line 19 * * Word 5 *
*                                  And makes us * * rather bear those ills we have                     * * Line 25 * * Word 3 *
*                                     With this * * regard their currents turn awry,                   * * Line 31 * * Word 2 *
*                                Be all my sins * * remember'd.                                        * * Line 34 * * Word 4 *
*                    And thus the native hue of * * resolution                                         * * Line 28 * * Word 6 *
*               Must give us pause: there's the * * respect                                            * * Line 12 * * Word 6 *
*                                  No traveller * * returns, puzzles the will                          * * Line 24 * * Word 2 *
* To sleep: perchance to dream: ay, there's the * * rub;                                               * * Line 9  * * Word 8 *
*                    No more; and by a sleep to * * say we end                                         * * Line 5  * * Word 7 *
*              For who would bear the whips and * * scorns of time,                                    * * Line 14 * * Word 7 *
*                     Or to take arms against a * * sea of troubles,                                   * * Line 3  * * Word 6 *
*       The heart-ache and the thousand natural * * shocks                                             * * Line 6  * * Word 6 *
*                                  When we have * * shuffled off this mortal coil,                     * * Line 11 * * Word 3 *
*                                            Is * * sicklied o'er with the pale cast of thought,       * * Line 29 * * Word 1 *
*                                     Be all my * * sins remember'd.                                   * * Line 34 * * Word 3 *
*                                   For in that * * sleep of death what dreams may come                * * Line 10 * * Word 3 *
*                             No more; and by a * * sleep to say we end                                * * Line 5  * * Word 5 *
*                                            To * * sleep: perchance to dream: ay, there's the rub;    * * Line 9  * * Word 1 *
*          And by opposing end them? To die: to * * sleep;                                             * * Line 4  * * Word 8 *
*             Devoutly to be wish'd. To die, to * * sleep;                                             * * Line 8  * * Word 7 *
*                                           The * * slings and arrows of outrageous fortune,           * * Line 2  * * Word 1 *
*                        That makes calamity of * * so long life;                                      * * Line 13 * * Word 4 *
*                And lose the name of action. - * * Soft you now!                                      * * Line 32 * * Word 7 *
*                         But that the dread of * * something after death,                             * * Line 22 * * Word 5 *
*               The insolence of office and the * * spurns                                             * * Line 17 * * Word 6 *
*            Whether 'tis nobler in the mind to * * suffer                                             * * Line 1  * * Word 7 *
*                                  To grunt and * * sweat under a weary life,                          * * Line 21 * * Word 3 *
*                                         Or to * * take arms against a sea of troubles,               * * Line 3  * * Word 2 *
*            That patient merit of the unworthy * * takes,                                             * * Line 18 * * Word 6 *
*                                               * * Than fly to others that we know not of?            * * Line 26 * * Word 0 *
*                                               * * That flesh is heir to, 'tis a consummation         * * Line 7  * * Word 0 *
*                          To be, or not to be: * * that is the question:                              * * Line 0  * * Word 6 *
*                                               * * That makes calamity of so long life;               * * Line 13 * * Word 0 *
*                                               * * That patient merit of the unworthy takes,          * * Line 18 * * Word 0 *
*                                        For in * * that sleep of death what dreams may come           * * Line 10 * * Word 2 *
*                                           But * * that the dread of something after death,           * * Line 22 * * Word 1 *
*                            Than fly to others * * that we know not of?                               * * Line 26 * * Word 4 *
*                                      But that * * the dread of something after death,                * * Line 22 * * Word 2 *
*                                               * * The fair Ophelia! Nymph, in thy orisons            * * Line 33 * * Word 0 *
*                                               * * The heart-ache and the thousand natural shocks     * * Line 6  * * Word 0 *
*                                               * * The insolence of office and the spurns             * * Line 17 * * Word 0 *
*                   The pangs of despised love, * * the law's delay,                                   * * Line 16 * * Word 5 *
*                        Whether 'tis nobler in * * the mind to suffer                                 * * Line 1  * * Word 4 *
*                                      And lose * * the name of action. - Soft you now!                * * Line 32 * * Word 2 *
*                                      And thus * * the native hue of resolution                       * * Line 28 * * Word 2 *
*                                               * * The oppressor's wrong, the proud man's contumely,  * * Line 15 * * Word 0 *
*                         Is sicklied o'er with * * the pale cast of thought,                          * * Line 29 * * Word 4 *
*                                               * * The pangs of despised love, the law's delay,       * * Line 16 * * Word 0 *
*                        The oppressor's wrong, * * the proud man's contumely,                         * * Line 15 * * Word 3 *
*                  To be, or not to be: that is * * the question:                                      * * Line 0  * * Word 8 *
*                   Must give us pause: there's * * the respect                                        * * Line 12 * * Word 5 *
*     To sleep: perchance to dream: ay, there's * * the rub;                                           * * Line 9  * * Word 7 *
*                                               * * The slings and arrows of outrageous fortune,       * * Line 2  * * Word 0 *
*                   The insolence of office and * * the spurns                                         * * Line 17 * * Word 5 *
*                            The heart-ache and * * the thousand natural shocks                        * * Line 6  * * Word 3 *
*                                               * * The undiscover'd country from whose bourn          * * Line 23 * * Word 0 *
*                         That patient merit of * * the unworthy takes,                                * * Line 18 * * Word 4 *
*                            For who would bear * * the whips and scorns of time,                      * * Line 14 * * Word 4 *
*                 No traveller returns, puzzles * * the will                                           * * Line 24 * * Word 4 *
*                              With this regard * * their currents turn awry,                          * * Line 31 * * Word 3 *
*                           And by opposing end * * them? To die: to sleep;                            * * Line 4  * * Word 4 *
*                           Must give us pause: * * there's the respect                                * * Line 12 * * Word 4 *
*             To sleep: perchance to dream: ay, * * there's the rub;                                   * * Line 9  * * Word 6 *
*                     When we have shuffled off * * this mortal coil,                                  * * Line 11 * * Word 5 *
*                                          With * * this regard their currents turn awry,              * * Line 31 * * Word 1 *
*                      And makes us rather bear * * those ills we have                                 * * Line 25 * * Word 5 *
*        Is sicklied o'er with the pale cast of * * thought,                                           * * Line 29 * * Word 8 *
*                        The heart-ache and the * * thousand natural shocks                            * * Line 6  * * Word 4 *
*                                               * * Thus conscience does make cowards of us all;       * * Line 27 * * Word 0 *
*                                           And * * thus the native hue of resolution                  * * Line 28 * * Word 1 *
*                   The fair Ophelia! Nymph, in * * thy orisons                                        * * Line 33 * * Word 5 *
*    For who would bear the whips and scorns of * * time,                                              * * Line 14 * * Word 9 *
*                                      Devoutly * * to be wish'd. To die, to sleep;                    * * Line 8  * * Word 1 *
*                                               * * To be, or not to be: that is the question:         * * Line 0  * * Word 0 *
*                                 To be, or not * * to be: that is the question:                       * * Line 0  * * Word 4 *
*                        Devoutly to be wish'd. * * To die, to sleep;                                  * * Line 8  * * Word 4 *
*                     And by opposing end them? * * To die: to sleep;                                  * * Line 4  * * Word 5 *
*                           To sleep: perchance * * to dream: ay, there's the rub;                     * * Line 9  * * Word 3 *
*                                               * * To grunt and sweat under a weary life,             * * Line 21 * * Word 0 *
*                                      Than fly * * to others that we know not of?                     * * Line 26 * * Word 2 *
*                       No more; and by a sleep * * to say we end                                      * * Line 5  * * Word 6 *
*                                               * * To sleep: perchance to dream: ay, there's the rub; * * Line 9  * * Word 0 *
*             And by opposing end them? To die: * * to sleep;                                          * * Line 4  * * Word 7 *
*                Devoutly to be wish'd. To die, * * to sleep;                                          * * Line 8  * * Word 6 *
*               Whether 'tis nobler in the mind * * to suffer                                          * * Line 1  * * Word 6 *
*                                            Or * * to take arms against a sea of troubles,            * * Line 3  * * Word 1 *
*                            That flesh is heir * * to, 'tis a consummation                            * * Line 7  * * Word 4 *
*                                            No * * traveller returns, puzzles the will                * * Line 24 * * Word 1 *
*              Or to take arms against a sea of * * troubles,                                          * * Line 3  * * Word 8 *
*               With this regard their currents * * turn awry,                                         * * Line 31 * * Word 5 *
*                            To grunt and sweat * * under a weary life,                                * * Line 21 * * Word 4 *
*                                           The * * undiscover'd country from whose bourn              * * Line 23 * * Word 1 *
*                     That patient merit of the * * unworthy takes,                                    * * Line 18 * * Word 5 *
*          Thus conscience does make cowards of * * us all;                                            * * Line 27 * * Word 6 *
*                                     Must give * * us pause: there's the respect                      * * Line 12 * * Word 2 *
*                                     And makes * * us rather bear those ills we have                  * * Line 25 * * Word 2 *
*                No more; and by a sleep to say * * we end                                             * * Line 5  * * Word 8 *
*           And makes us rather bear those ills * * we have                                            * * Line 25 * * Word 7 *
*                                          When * * we have shuffled off this mortal coil,             * * Line 11 * * Word 1 *
*                       Than fly to others that * * we know not of?                                    * * Line 26 * * Word 5 *
*                    To grunt and sweat under a * * weary life,                                        * * Line 21 * * Word 6 *
*                    For in that sleep of death * * what dreams may come                               * * Line 10 * * Word 6 *
*                                               * * When he himself might his quietus make             * * Line 19 * * Word 0 *
*                                               * * When we have shuffled off this mortal coil,        * * Line 11 * * Word 0 *
*                                               * * Whether 'tis nobler in the mind to suffer          * * Line 1  * * Word 0 *
*                        For who would bear the * * whips and scorns of time,                          * * Line 14 * * Word 5 *
*                                           For * * who would bear the whips and scorns of time,       * * Line 14 * * Word 1 *
*                           With a bare bodkin? * * who would fardels bear,                            * * Line 20 * * Word 4 *
*                 The undiscover'd country from * * whose bourn                                        * * Line 23 * * Word 4 *
*             No traveller returns, puzzles the * * will                                               * * Line 24 * * Word 5 *
*                                Devoutly to be * * wish'd. To die, to sleep;                          * * Line 8  * * Word 3 *
*                                               * * With a bare bodkin? who would fardels bear,        * * Line 20 * * Word 0 *
*                              Is sicklied o'er * * with the pale cast of thought,                     * * Line 29 * * Word 3 *
*                                               * * With this regard their currents turn awry,         * * Line 31 * * Word 0 *
*                                       For who * * would bear the whips and scorns of time,           * * Line 14 * * Word 2 *
*                       With a bare bodkin? who * * would fardels bear,                                * * Line 20 * * Word 5 *
*                               The oppressor's * * wrong, the proud man's contumely,                  * * Line 15 * * Word 2 *
*           And lose the name of action. - Soft * * you now!                                           * * Line 32 * * Word 8 *
************************************************* ****************************************************** *********** **********

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

Reference

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

Accelerated C++ Solution to Exercise 5-0

Exercise 5-0

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

Solution

Chapter 5 contains 3 core sets of applications. I believe it makes sense to split Exercise 5-0 into 3 separate parts (i.e. 3 separate posts) for greater relevance and readability. Click the hyperlinks below to drill down.

Part 1 / 3

Click here to see full Solution to Exercise 5-0 (Part 1 / 3) : We extend the Solution to Exercise 4-0 (i.e. the student grading program) to include a capability that split the set of students (objects) into two groups – namely the passing students and failing students. This capability is enabled by a new “home-made” function called extract_fails. This function can be written in 4 different versions in which all 4 versions deliver the same result, with the slight difference in terms of efficiency. It goes from version 1 being the most primitive / inefficient, to version 4 being the most elegant / efficient. We will describe and test out each version one-by-one.

Part 2 / 3

Click here to see full Solution to Exercise 5-0 (Part 2 / 3): This is a very simple program with the purpose of splitting a line of text (i.e. a input string) into words (i.e. an output vector<string>).

Part 3 / 3

Click here to see full Solution to Exercise 5-0 (Part 3 / 3): This is a fairly clever yet simple-to-understand program. This exercise demonstrates 4 things: (1) how to create a paragraph and store in the form of a vector<string> container, (2) how to display the paragraph with and without a frame, (3) how to concatenate two paragraph “pictures” vertically, (4) how to concatenate two paragraph “pictures” horizontally.

Remark

If in doubt, try reading through chapter 5 multiple times to help understanding how the “bits and pieces” work individually and as a whole. It’s all in the book. What the book does not contain however, is the actual implementation of programs through an IDE (like Code::Block) and demonstrate what the the output results may look like. This post (and all the other posts in this Accelerated C++ series) aims to fill in that gap.

Reference

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

Accelerated C++ Solution to Exercise 5-0 (Part 3 / 3)

This is Part 3 of the 3-part  Solution to Exercise 5-0.

Exercise 5-0 (Part 3 / 3)

This is a fairly clever yet simple-to-understand program. This exercise demonstrates 4 things: (1) how to create a paragraph and store in the form of a vector<string> container, (2) how to display the paragraph with and without a frame, (3) how to concatenate two paragraph “pictures” vertically, (4) how to concatenate two paragraph “pictures” horizontally.

The Program Logic

  1. User to create a paragraph by providing multiple lines of input, via the console window.
  2. The program store the paragraph in the form of a vector<string> container called p – each string element corresponds the an input line. e.g. p[0] is the first line, p[1] is the second line, etc.
  3. A function called vcout may be used to display a vector<string> container in the form of a paragraph via the console window.
  4. A function called frame may be used to take in a vector<string> container and return a new vector<string> container representing a “framed” paragraph.
  5. A function called vcat may be used to concatenate multiple paragraph “box-like pictures” vertically. e.g. imagine two box-like paragraph pictures are stacked vertically.
  6. A function called hcat may be used to concatenate multiple paragraph “box-like pictures” horizontally. e.g. imagine two box-like paragraph pictures are aligned horizontally.
  7. An sub-function called width (used by the frame and hcat functions) is in place to ensure the paragraphs behave in a “box-like” shape when we add a frame around it, or concatenate horizontally.
  8. Within the main program, we apply the functions vcout, frame, vcat, and hcat in multiple combinations to demonstrate it is very easy to display the vector<string> p in the form of “box-like pictures” and in multiple ways. e.g. apply a frame around a paragraph, stack the two box-like picture paragraphs vertically / horizontally.

The Project

This is what the management tree looks like in Code::Block:

Acpp5p0p3MgntTree

C++ Source Files

  • main.cpp – this is the first program that is run during the implementation phase.
  • frame.cpp – contains the frame and width functions.
  • hcat.cpp – contains the hcat function.
  • vcat.cpp – contains the vcat function.
  • vcout.cpp – contains the vcout function.

C++ Header Files

  • frame.h – declare the functions in frame.cpp.
  • hcat.h – declare the functions in hcat.cpp.
  • vcat.h – declare the functions in vcat.cpp.
  • vcout.h – declare the functions in vcout.cpp.

Source Files

main.cpp

#include <iostream>  // cin, cout, endl, getline
#include <vector>    // vector
#include <string>    // string
#include "frame.h"   // width, frame
#include "vcat.h"    // vcat
#include "hcat.h"    // hcat
#include "vcout.h"   // vcout

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

int main()
{
    string s;            // line
    vector<string> p;    // paragraph

    // read multiple lines to make a paragraph
    while (getline(cin, s))
        p.push_back(s);

    // have a play, manipulate and display paragraph (p) in multiple ways

    cout << "----------------------------------------------------\n"
            "Display: p                                          \n"
            "----------------------------------------------------\n";
    vcout(p);

    cout << "-----------------------------------------------------\n"
            "Display: frame(p)                                    \n"
            "-----------------------------------------------------\n";
    vcout(frame(p));

    cout << "-----------------------------------------------------\n"
            "Display: vcat(p, frame(p))                           \n"
            "-----------------------------------------------------\n";
    vcout(vcat(p,frame(p)));

    cout << "-----------------------------------------------------\n"
            "Display: vcat(frame(p), p)                           \n"
            "-----------------------------------------------------\n";
    vcout(vcat(frame(p),p));

    cout << "-----------------------------------------------------\n"
            "Display: hcat(p, frame(p))                           \n"
            "-----------------------------------------------------\n";

    vcout(hcat(p,frame(p)));

    cout << "-----------------------------------------------------\n"
            "Display: hcat(frame(p), p)                           \n"
            "-----------------------------------------------------\n";
    vcout(hcat(frame(p),p));

    cout << "-----------------------------------------------------\n"
            "Display: vcat(hcat(frame(p), p), hcat(p, frame(p)))  \n"
            "-----------------------------------------------------\n";
    vcout(vcat(hcat(frame(p), p), hcat(p, frame(p))));

    return 0;
}

frame.cpp

#include <string>      // string
#include <vector>      // vector
#include <algorithm>   // max

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

string::size_type width(const vector<string>& v)
{
    string::size_type maxlen = 0;
    for(vector<string>::size_type i = 0; i != v.size(); ++i)
        maxlen = max(maxlen, v[i].size());
    return maxlen;
}

vector<string> frame(const vector<string>& v)
{
    vector<string> ret;
    string::size_type maxlen = width(v);
    string border(maxlen + 4, '*');

    // write the top border
    ret.push_back(border);

    // write each interior row, bordered by an asterisk and a space
    for (vector<string>::size_type i = 0; i != v.size(); ++i)
        ret.push_back("* " + v[i] + string(maxlen - v[i].size(), ' ') + " *");

    // write the bottom border
    ret.push_back(border);

    return ret;
}

hcat.cpp

#include <string>      // string
#include <vector>      // vector
#include "frame.h"     // width

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

vector<string> hcat(const vector<string>& left, const vector<string>& right)
{
    vector<string> ret;

    // add 1 to leave a space between pictures
    string::size_type width1 = width(left) + 1;

    // indices to look at elements from left and right respectively
    vector<string>::size_type i = 0, j = 0;

    // continue until we've seen all rows from both pictures
    while (i != left.size() || j != right.size())
    {
        // construct new string to hold characters from both pictures
        string s;

        // copy a row from the left-hand side, if there is one
        if (i != left.size())
            s = left[i++];

        // pad to full width
        s += string(width1 - s.size(), ' ');

        // copy a row from teh right-hand side, if there is one
        if (j != right.size())
            s += right[j++];

        // add s to the picture we are creating
        ret.push_back(s);
    }

    return ret;
}

vcat.cpp

#include <string>      // string
#include <vector>      // vector

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

vector<string> vcat(const vector<string>& top, const vector<string>& bottom)
{
    // copy the top picture
    vector<string> ret = top;

    // copy entire bottom picture (option 1 and option 2 have the same effect - pick whichever!)

    // option 1
    for (vector<string>::const_iterator it = bottom.begin();
         it != bottom.end(); ++it)
        ret.push_back(*it);

    // option 2
    /*
    ret.insert(ret.end(), bottom.begin(), bottom.end());
    */

    return ret;
}

vcout.cpp

#include <iostream>
#include <string>    // string
#include <vector>    // vector

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

int vcout(const vector<string>& v)
{
    for (vector<string>::const_iterator iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

frame.h

#ifndef GUARD_FRAME_H
#define GUARD_FRAME_H

#include <string>
#include <vector>

std::string::size_type width(const std::vector<std::string>&);
std::vector<std::string> frame(const std::vector<std::string>&);

#endif // GUARD_FRAME_H

hcat.h

#ifndef GUARD_HCAT_H
#define GUARD_HCAT_H

#include <string>
#include <vector>

std::vector<std::string> hcat(const std::vector<std::string>&, const std::vector<std::string>&);

#endif // GUARD_HCAT_H

vcat.h

#ifndef GUARD_VCAT_H
#define GUARD_VCAT_H

#include <string>
#include <vector>

std::vector<std::string> vcat(const std::vector<std::string>&, const std::vector<std::string>&);

#endif // GUARD_VCAT_H

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

int vcout(const std::vector<std::string>&);

#endif // GUARD_VCOUT_H

Test Program

I have written the main program in a way that is easy enough to test out multiple combination of function usage (i.e. frame, vcat, and hcat) against the vector<string> p (the paragraph).

In this test, as soon as the program starts up, I provide the following 5 lines (followed by the end-of-file button. i.e. F6 for Windows).

  1. this is an
  2. example
  3. to
  4. illustrate
  5. framing

Test Result

this is an
example
to
illustrate
framing
^Z
----------------------------------------------------
Display: p
----------------------------------------------------
this is an
example
to
illustrate
framing
-----------------------------------------------------
Display: frame(p)
-----------------------------------------------------
**************
* this is an *
* example    *
* to         *
* illustrate *
* framing    *
**************
-----------------------------------------------------
Display: vcat(p, frame(p))
-----------------------------------------------------
this is an
example
to
illustrate
framing
**************
* this is an *
* example    *
* to         *
* illustrate *
* framing    *
**************
-----------------------------------------------------
Display: vcat(frame(p), p)
-----------------------------------------------------
**************
* this is an *
* example    *
* to         *
* illustrate *
* framing    *
**************
this is an
example
to
illustrate
framing
-----------------------------------------------------
Display: hcat(p, frame(p))
-----------------------------------------------------
this is an **************
example    * this is an *
to         * example    *
illustrate * to         *
framing    * illustrate *
           * framing    *
           **************
-----------------------------------------------------
Display: hcat(frame(p), p)
-----------------------------------------------------
************** this is an
* this is an * example
* example    * to
* to         * illustrate
* illustrate * framing
* framing    *
**************
-----------------------------------------------------
Display: vcat(hcat(frame(p), p), hcat(p, frame(p)))
-----------------------------------------------------
************** this is an
* this is an * example
* example    * to
* to         * illustrate
* illustrate * framing
* framing    *
**************
this is an **************
example    * this is an *
to         * example    *
illustrate * to         *
framing    * illustrate *
           * framing    *
           **************

This is overall a very nice program that demonstrates the ease of manipulating a vector as long as the functions are well written and in place.

Reference

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

Accelerated C++ Solution to Exercise 5-0 (Part 2 / 3)

This is Part 2 of the 3-part Solution to Exercise 5-0.

Exercise 5-0 (Part 2 / 3)

This is a very simple program with the purpose of splitting a line of text (i.e. a input string) into words (i.e. an output vector<string>).

The Problem

Start from scratch, we need to write a program that is able to read in a line of text, and be able to split it into words. The full description and explanation of the program can be found in Chapter 5 of the book.

Solution Strategy

The text book sample program for this (part 2) exercise is fairly simple. It only requires 3 files which I can group into a small project as usual – I will describe this in the Project section below.

There is also one core learning from this chapter regarding sequential container processing using either (1) index, or (2) iterator. Both methods are effectively the same. e.g. assuming v is a vector<string>, the two following codes have the same effect (of displaying container elements to the output console).

Sequential Container Processing with Index:

        for (vector<string>::size_type i = 0; i != v.size(); ++i)
            cout << v[i] << endl;

Sequential Container Processing with Iterator:

        for (vector<string>::const_iterator iter = v.begin(); iter != v.end(); ++iter)
            cout << (*iter) << endl;

Remark

As the Author mentioned in the book, however:

  • Index is good for random container processing, whereas
  • Iterator is good for sequential container processing.

It is always a good idea to bear this in mind.

The Project

This is what the management tree looks like in Code::Block:

Acpp5p0p2MgntTree

C++ Source Files

  • main.cpp – this is the first program that is run during the implementation phase.
  • split.cpp – contains the split function.

C++ Header Files

  • split.h – declare the functions in the source file split.cpp.

Source Files

main.cpp

#include <iostream>  // cin, cout, endl, getline
#include <vector>    // vector
#include <string>    // string
#include "split.h"   // split

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

// (5.7/90)
int main()
{
    string s;

    // read and split each line of input
    while (getline(cin, s))
    {
        vector<string> v = split(s);

        // write each word in v
        for (vector<string>::const_iterator iter = v.begin(); iter != v.end(); ++iter)
            cout << (*iter) << endl;
    }
    return 0;
}

split.cpp

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

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

// scan a string of texts, split into words, return a vector that contains these words.
// (S5.6/88)
vector<string> split(const string& s)
{
    vector<string> ret;
    typedef string::size_type string_size;
    string_size i = 0;

    // invariant: we have processed characters original value of [i, i)
    while (i != s.size() )
    {
        // ignore leading blanks
        // invariant: characters in range [original i, current i)
        while (i != s.size() && isspace(s[i]))
            ++i;

        // find end of next word
        string_size j = i;

        // invariant: none of the characters in range [original j, current j) is a space
        while (j != s.size() && !isspace(s[j]))
            ++j;

        // if we found some non-whitespace characters
        if (i != j)
            // copy from s starting at i and taking j - i chars
            ret.push_back(s.substr(i, j - i));
            i = j;
    }
    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

Test Results

I am going to enter the following 3 lines when the program starts up. I should see the individual words (separated by empty space) displayed on the screen straight after I hit the enter button.

  1. Hello world, how are we today?
  2. Nice, so the program works!
  3. Bye bye
Hello world, how are we today?
Hello
world,
how
are
we
today?
Nice, so the program works!
Nice,
so
the
program
works!
Bye bye
Bye
bye
^Z

The program works as expected!

Reference

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

Accelerated C++ Solution to Exercise 5-0 (Part 1 / 3)

This is Part 1 of the 3-part Solution to Exercise 5-0.

Exercise 5-0 (Part 1 / 3)

We extend the Solution to Exercise 4-0 (i.e. the student grading program) to include a capability that split the set of students (objects) into two groups – namely the passing students and failing students. This capability is enabled by a new “home-made” function called extract_fails. This function can be written in 4 different versions in which all 4 versions deliver the same result, with the slight difference in terms of efficiency. It goes from version 1 being the most primitive / inefficient, to version 4 being the most elegant / efficient. We will describe and test out each version one-by-one.

The Problem

The objective of this exercise is to enhance the Chapter 4 program so that we are able to determine, out of the entire Student_info object population, which ones belong to the passing group, and which ones belong to the failing group.

The Solution Strategy

There are many good ways to implement this Chapter 5 example program. Here is my strategy:

  1. Make a copy of the entire Chapter 4 project. i.e. the Project as per Solution to Exercise 4-0.
  2. Add a C++ source file extract_fails.cpp. It contains the 4 versions of the extract_fail function. To make it easy to test later, I simply create 4 functions. Namely: extract_fails_v1, extract_fails_v2, extract_fails_v3, extract_fails_v4. The function fgrade is also stored in this file.
  3. Add a corresponding C++ header file. i.e. extract_fails.h.
  4. Adjust the main function to make it suitable for testing. Note that extract_fail version 1, 2 and 3 use vector<Student_info> container, whereas version 4 uses list<Student_info> container. Because of this, I will have two versions of main program for the testing – i.e. no1_main() for testing out extract_fail version 1, 2, 3. no2_main() for testing out extract_fail version 4.

The Project

I partition the program into smaller chunks – i.e. in C++ source files and header files. This diagram below shows what the Code::Block Management Tree look like after successful creation of these files.

Acpp5p0p1MgntTree

Note that majority of these files are straight copies of the Chapter 4 Program. (i.e. Solution to Exercise 4-0). (the ones that are NOT circled in red)

In this exercise we add these files (circled in red as per snapshot diagram above): extract_fails.cpp, extract_fails.h. We also amend the main.cpp accordingly so that we are able to test out the newly written functions using tailored main program.

C++ Source Files

  • main.cpp – (Adjust accordingly) this is the first program that is run during the implementation phase.
  • extract_fails.cpp – (New!) contains the fgrade function, and the 4 versions extract_fail functions.
  • grade.cpp – (From Chapter 4) contains all functions relating to computing grades.
  • median.cpp – (From Chapter 4) contains all functions relating to computing median.
  • Student_info.cpp – (From Chapter 4) contains all functions relating to handling a Student_info object.

C++ Header Files

  • extract_fails.h – (New!) declare the functions as defined in extract_fails.cpp.
  • grade.h – (From Chapter 4) declare the functions as defined in grade.cpp.
  • median.h – (From Chapter 4) declare the functions as defined in median.cpp
  • Student_info.h – (From Chapter 4) declare the functions as defined in Student_info.cpp, plus defining the data structure of the Student_info (object) type.

Source Files

main.cpp (Adjust accordingly)

#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <list>
#include "grade.h"
#include "Student_info.h"
#include "extract_fails.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::list;

// There are two main programs here.
//   - The top one is used to test out extract_fails version 1, 2, and 3.
//   - The bottom one is for testing out extract_fails version 4.
// Simply replace the no1_main() or no2_main() with main() to activate the main program to run

// for testing extract_fails_v1 / v2 / v3 - that uses vector
int no1_main()
{
    vector<Student_info> students;
    Student_info record;

    // read and store all the student's data.
    while (read(cin, record))
        students.push_back(record);

    // Extract the failed students (use extract_fails_v1 / v2 / v3)
    vector<Student_info> students_failed = extract_fails_v3(students);

    // sort vectors
    sort(students.begin(),students.end(),compare);
    sort(students_failed.begin(),students_failed.end(),compare);

    // Report passing students
    cout << "These students have passed." << endl;
    for (vector<Student_info>::const_iterator i = students.begin();
         i != students.end(); ++i)
        cout << i->name << endl;

    // Report failing students
    cout << "These students have failed." << endl;
    for (vector<Student_info>::const_iterator i = students_failed.begin();
         i != students_failed.end(); ++i)
        cout << i->name << endl;

    return 0;
}


// for testing extract_fails_v4 - that uses list
int no2_main()
{
    list<Student_info> students;
    Student_info record;

    // read and store all the student's data.
    while (read(cin, record))
        students.push_back(record);

    // Extract the failed students
    list<Student_info> students_failed = extract_fails_v4(students);

    // sort lists
    students.sort(compare);
    students_failed.sort(compare);

    // Report passing students
    cout << "These students have passed." << endl;
    for (list<Student_info>::const_iterator i = students.begin();
         i != students.end(); ++i)
        cout << i->name << endl;

    // Report failing students
    cout << "These students have failed." << endl;
    for (list<Student_info>::const_iterator i = students_failed.begin();
         i != students_failed.end(); ++i)
        cout << i->name << endl;

    return 0;
}

extract_fails.cpp

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

using std::vector;
using std::list;


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

// separate passing and failing student records
// version 1: maintain two vectors (pass and fail) within local scope
// Can use up lots of memory resource.
// (S5.1/76)
vector<Student_info> extract_fails_v1(vector<Student_info>& students)
{
    vector<Student_info> pass, fail;

    for (vector<Student_info>::size_type i = 0;
         i != students.size(); ++i)
         if (fgrade(students[i]))
            fail.push_back(students[i]);
         else
            pass.push_back(students[i]);

    students = pass;
    return fail;
}

// separate passing and failing student records
// version 2: maintain one vector (fail) within local scope. Update pass vector by reference.
// correct but potentially slow. (Still use up lots of memory resource but less than version 1)
// (S5.1.1/77)
vector<Student_info> extract_fails_v2(vector<Student_info>& students)
{
    vector<Student_info> fail;
    vector<Student_info>::size_type i = 0;

    // invariant: elements [0,i) of students represent passing grades
    while (i != students.size())
    {
        if (fgrade(students[i]))
        {
            fail.push_back(students[i]);
            students.erase(students.begin() + i);
        }
        else
            ++ i;
    }
    return fail;
}

// separate passing and failing student records
// version 3: iterators but no indexing; still potentially slow
// (S5.3/82)
vector<Student_info> extract_fails_v3(vector<Student_info>& students)
{
    vector<Student_info> fail;
    vector<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

// separate passing and failing student records
// version 4: use list instead of vector (essentially the same as version 3 otherwise)
// (S5.5/85)
list<Student_info> extract_fails_v4(list<Student_info>& students)
{
    list<Student_info> fail;
    list<Student_info>::iterator iter = students.begin();
    while (iter != students.end())
    {
        if (fgrade(*iter))
        {
            fail.push_back(*iter);
            iter = students.erase(iter);
        }
        else
            ++iter;
    }
    return fail;
}

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

extract_fails.h

#ifndef GUARD_EXTRACT_FAILS_H
#define GUARD_EXTRACT_FAILS_H

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

bool fgrade(const Student_info&);
std::vector<Student_info> extract_fails_v1(std::vector<Student_info>&);
std::vector<Student_info> extract_fails_v2(std::vector<Student_info>&);
std::vector<Student_info> extract_fails_v3(std::vector<Student_info>&);
std::list<Student_info> extract_fails_v4(std::list<Student_info>&);

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

We need to do four tests to test out the extract_fails function version 1, 2, 3, and 4 accordingly.

As seen in the main.cpp, I have made a note on how to do this:

// There are two main programs here.
//   - The top one is used to test out extract_fails version 1, 2, and 3.
//   - The bottom one is for testing out extract_fails version 4.
// Simply replace the no1_main() or no2_main() with main() to activate the main program to run

For clarity purpose I will list out exactly how to change the main.cpp accordingly for this program testing.

To test extract_fails version 1:

  1. Inside no1_main(), replace the extract_fails_XX to extract_fails_v1.
  2. Replace no1_main() with main().

To test extract_fails version 2:

  1. Inside no1_main(), replace the extract_fails_XX to extract_fails_v2.
  2. Replace no1_main() with main().

To test extract_fails version 3:

  1. Inside no1_main(), replace the extract_fails_XX to extract_fails_v3.
  2. Replace no1_main() with main().

To test extract_fails version 4:

  1. Inside no2_main(), replace the extract_fails_XX to extract_fails_v4.
  2. Replace no2_main() with main().

Notes

Note again, no1_main() focuses on vector<string>, whereas no2_main() focuses on list<string>.

I have also taken the liberty to test out the sort function (highlighted in S5.1.1/86 of the text book). i.e.

To sort a vector, do:

    // sort vectors
    sort(students.begin(),students.end(),compare);
    sort(students_failed.begin(),students_failed.end(),compare);

To sort a list, do:

    // sort lists
    students.sort(compare);
    students_failed.sort(compare);

Results

I have run through all 4 versions above and confirm that all give the same result. Some snapshots captured below.

Recall that the finalGrade = ( 20% x midTermGrade ) + (40% x finalTermGrade) + (40% x medianOfHomeworkGrades)

To simplify the test, I know that, if I provide the same value for midTermGrade, finalTermGrade, and homeworkGrades, then the finalGrade should technically be the same value. e.g. if all grades are 90, then the finalGrade is bound to be 90 also. The idea is that, I know the passing grade is 60 or above (and likewise, failing grade is less than 60). By providing the grades for a list of students, I can easily determine (using my head) whether the student should pass or fail. I can then compare with the test result computed by the program. If the program is working as expected, both set of test results should match. (And they indeed do).

Test 1

Aim of this test is to prove that the program is able to split the group of students into two groups – the passing and failing groups.

aaa 90 90 90 90 90
bbb 80 80 80 80 80
ccc 70 70 70 70 70
ddd 60 60 60 60 60
eee 50 50 50 50 50
fff 40 40 40 40 40
ggg 30 30 30 30 30
hhh 10 10 10 10 10
iii 0 0 0 0 0
^Z
^Z
These students have passed.
aaa
bbb
ccc
ddd
These students have failed.
eee
fff
ggg
hhh
iii

Test 2

Aim of this test is essentially the same as test 1, plus the ability to sort.

fff 40 40 40 40 40
bbb 80 80 80 80 80
ccc 70 70 70 70 70
iii 0 0 0 0 0
eee 50 50 50 50 50
aaa 90 90 90 90 90
hhh 10 10 10 10 10
ddd 60 60 60 60 60
ggg 30 30 30 30 30
^Z
^Z
These students have passed.
aaa
bbb
ccc
ddd
These students have failed.
eee
fff
ggg
hhh
iii

Test 3

Aim of this test is to show that the program runs okay when all students have passing grades.

aaa 90 90 90 90 90
bbb 80 80 80 80 80
ccc 70 70 70 70 70
ddd 60 60 60 60 60
^Z
^Z
These students have passed.
aaa
bbb
ccc
ddd
These students have failed.

Test 4

Aim of this test is to show that the program runs okay when all students have failing grades.

eee 50 50 50 50 50
fff 40 40 40 40 40
ggg 30 30 30 30 30
hhh 10 10 10 10 10
iii 0 0 0 0 0
^Z
^Z
These students have passed.
These students have failed.
eee
fff
ggg
hhh
iii

Test 5

Aim of this test is to show that the program runs okay even when we provide no input data at all.

^Z
These students have passed.
These students have failed.

Conclusion

  1. We have successfully put all the files and sub-programs together, implemented the algorithm in an IDE like Code::Block, in a “partitioned” manner (as suggested by the Author at S4.3/65).
  2. We have tested all 4 versions of the extract_fail function. Though I have not proved it here, we know that (according to the Author) that version 1 is least efficient and version 4 is most efficient (2 and 3 are somewhat in the middle).
  3. We have learnt abut iterator, vector and list. Our confident level with using C++, have gone up another notch.

Reference

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

Accelerated C++ Solution to Exercise 4-8

Exercise 4-8

If the following code is legal, what can we infer about the return type of f?

double d = f() [n]

Solution

The return type of the function f is of type double. The logic is a follows:

  • The statement is trying to define a variable double d. i.e. a variable called d of type double.
  • The equal (=) sign assigns whatever that is on the right (of the equal sign), to the left (of the equal sign).
  • As we know that the left-hand-side is of type double, it must be true that the right must also be of type double.
  • Hence, the return type of the function f, is indeed of type double.

Reference

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

Accelerated C++ Solution to Exercise 4-7

Exercise 4-7

Write a program to calculate the average of the numbers stored in a vector<double>.

Solution

In comparison to the previous exercises in this chapter 4, this problem is (fortunately)  quite simple to solve.

Solution Strategy:

  1. In the main program, have a while loop to read individual value x (of type double) one by one, and parse to a container called numbers (of type vector<double>).
  2. Create a function compute_average that reads the vector<double> numbers, and return the average value (of type double).
  3. This function will throw a domain_error if the vector is empty (i.e. no numbers provided). This is to avoid the disgraceful error as a result of division by zero. (note that the average is computed as sum of the values inside the vector, divided by the size of the vector. If the size of the vector is zero, we will have the division by zero issue).
  4. Within the main program, display the average value using the std::cout.

The Program

Since we are only dealing with one function, it may be simpler to just define the function at the top of the main.cpp file (rather than partitioning the programing into multiple C++ header and source files).

The program looks like this.

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

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


double compute_average(const vector<double>& v)
{
    typedef vector<double>::size_type vtype;
    vtype v_size = v.size();

    if (v_size == 0) throw domain_error("no numbers provided - vector is empty!");

    double sum = 0;
    for (vtype i = 0; i != v_size ; ++i)
    {
        sum += v[i];
    }
    return sum / v_size;
}

int main()
{
    double x;
    vector<double> numbers;
    while (cin >> x)
    {
        numbers.push_back(x);
    }
    try
    {
        cout << "Average: " << compute_average(numbers);
    }
    catch (domain_error e)
    {
        cout << e.what();
    }
    cout << endl;

    return 0;
}

Result

Test 1

The average value of the 6 numbers is computed correctly.

2.5 3.5 4.5 5.5 8.5 9.5
^Z
Average: 5.66667

Test 2

The average value of the 5 numbers is computed correctly.

111.11
222.22
333.33
444.44
555.55
^Z
Average: 333.33

Test 3

For empty vector (no number provided scenario), the try and catch block successfully throw the domain_error message,

^Z
no numbers provided - vector is empty!

Reference

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

Accelerated C++ Solution to Exercise 4-6

Exercise 4-6

Rewrite the Student_info structure, and the read and grade functions, so that they calculate each student’s grades as part of reading the input, and store only the final grade.

Solution

Having spent a couple of hours solving this problem, it reminds me of the typical experience at work. i.e. changing / updating some else’s code! I got there in the end :)

In this post I will:

  1. Describe the problem and solution in depth.
  2. Summarise my solution to this exercise – under the Project section.
  3. Run some tests using both the old and new solutions / programs – to confirm that we indeed get the same results.

Problem and Solution

The exercise requires us to re-write the chapter 4 partitioned textbook program (as demonstrated in my Solution to Exercise 4-0) in a way that will effectively change the structure of the Student_info object. Note also the new requirement to “calculate each student’s grades as part of reading the input, and store only the final grade” – i.e. we only store the final grade. We do not store the mid-term score, final-term score, and the homework scores in the Student_info objects. We can visualise this change in the Student_info.h header file.

Update the Student_info structure in Student_info.h

Before the change:

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

After the change:

struct Student_info
{
    std::string name;
    double final_grade;
};

In both cases we keep the string name as it is. The major differences are:

  • During the “before” stage we store all input data (i.e. double midterm, double final, vector<double> homework) to the Student_info object. The program uses a downstream process to compute and display the double final_grade on the fly using a for loop. The double final_grade never get stored in the Student_info object.
  • During “after” stage we read in all input data on the fly, and immediate use these to compute the double final_grade. We store the double final_grade to the Student_info object. We discard the input data (mid-term score, final-term score, and the homework scores).

The change of the Student_info object gives us an hint that, all functions that take the Student_info object as input, might need changing as well. If we following the main program, we bump into the:

while (read(cin, record)) { }

This corresponds to the function istream& read(istream&, Student_info&) in Student_info.cpp source file.

Update a read function in Student_info.cpp

The original function parse all the incoming data to the Student_info object.

Before the change:

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

In the new version, we only wish to use the double midterm, double final, vector<double> homework temporarily purely for the purpose of computing the double final_grade. To do this, we can create local variables to cater for the temporarily usages, and only store the double final_grade in the end.

After the change:

istream& read(istream& is, Student_info& s)
{
    double midterm;
    double final;
    vector<double> homework;

    is >> s.name >> midterm >> final;

    // read and store all the student's homework scores (to the temporary vector<double> container)
    read_hw(is, homework);

    // compute the student's overall score, and store to the Student_info object
    try
    {
        s.final_grade = grade(midterm, final, homework);
    }
    catch (domain_error e)
    {
        s.final_grade = -1;  // indicating student has done no homework
    }
    return is;
}

See that the new version function istream& read(istream&, Student_info&), parses the mid-term score to the local variable double midterm, the final-term score to the local variable double final, the homework scores to the local container vector<double> homework (using the read_hw function, which is unchanged).

I now have a try block to compute the double final_grade straight away (and store in the Student_info object) using the function grade(double, double, double), which is unchanged. If no error, the final_grade is stored in the Student_info object. Otherwise (when no homework is submitted. i.e. the homework vector is empty), then I force set the final_grade to -1 to imply no homework. As the score is always positive, we can be very certain that -1 is not the result of computation of the final_grade.

In summary, the enhanced read function enables us to “fill in” the values of the new Student_info structure – for each Student_info object, we require the student’s name, and the student’s (computed) final grade.

Update the main program to display report

The original main program contains a step to compute the double final_grade on the fly and display within a for loop. In the new version program we no longer need to compute double final_grade on the fly, as the read function above has taken care this and store the double final_grade away as a property of the Student_info object. In the new version main program, we just need to simply use the std::cout to display Student_info::final_grade.

Before the change

    // write the names and grades
    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]);
            streamsize prec = cout.precision();
            cout << setprecision(3) << final_grade
                 << setprecision(prec);
        }
        catch (domain_error e)
        {
            cout << e.what();
        }
        cout << endl;
    }

After the change

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

        streamsize prec = cout.precision();

        // write the overall_grade out directly
        cout << setprecision(3)
             << students[i].final_grade
             << setprecision(prec) << endl;
    }

Note that the new version step purely display the results. Much simplier than the original version.

What we should also notice is that the new verrsion no longer require the use of the function double grade(const Student_info&) – we can safely remove this from both the grade.cpp source file and grade.h header file.

The Project – Putting Everything Together

I now wrap up the solution to this exercise by documenting the entire project – which is essentially and updated version of my Solution to Exercise 4-0. I have tried my best to highlight the “before” and “after” via commenting within the codes. I will run some tests at the end of the post using both the old and new solutions / programs – to confirm that we do indeed get the same results.

C++ Source Files

  • main.cpp – this is the first program that is run during the implementation phase.
  • grade.cpp – contains all functions relating to computing grades.
  • median.cpp – contains all functions relating to computing median.
  • Student_info.cpp – contains all functions relating to handling a Student_info object.

C++ Header Files

  • grade.h – declare the functions as defined in grade.cpp
  • median.h – declare the functions as defined in median.cpp
  • Student_info.h – declare the functions as defined in Student_info.cpp, plus defining the data structure of the Student_info (object) type.

This diagram below shows what the Code::Block Management Tree look like after successful creation of these files (note that this is the same as the one in the Solution to Exercise 4-0).

Acpp4p0MgntTree

Source Files

main.cpp

#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
/* #include <stdexcept> */  // Exercise 4-6: no longer required
#include <string>
#include <vector>
#include "grade.h"
#include "Student_info.h"

using std::cin;
using std::cout;
using std::endl;
/* using std::domain_error; */   // Exercise 4-6: no longer required
using std::max;
using std::setprecision;
using std::sort;
using std::streamsize;
using std::string;
using std::vector;

// Exercise 4-6: adjusted from the for loop onwards
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
    for (vector<Student_info>::size_type i = 0;
         i != students.size(); ++i)
    {
        // write the name, padded on the right to maxlen + 1 characters
        cout << students[i].name
             << string(maxlen + 1 - students[i].name.size(), ' ');

        streamsize prec = cout.precision();

        // write the overall_grade out directly
        cout << setprecision(3)
             << students[i].final_grade
             << setprecision(prec) << endl;
    }

    cout << endl;
    cout << "*****************************************************************" << endl;
    cout << "*** Note: a grade of -1 implies student has done no homework. ***" << endl;
    cout << "*****************************************************************" << endl;
    return 0;
}

grade.cpp

#include <stdexcept>  // Exercise 4-6:  added this
#include <vector>
#include "grade.h"    // Exercise 4-6:  added this
#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));
}

// Exercise 4-6: the following function is no longer required.
/*
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"
#include "grade.h"
#include <stdexcept>
/* #include <iostream> */   // Exercise 4-6: no longer required

using std::istream;
using std::vector;
using std::domain_error;
/* using std::cout; */    // Exercise 4-6: no longer required

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

// Exercise 4-6:  modified the following function
//    now read student's name, and compute the overall_grade directly.
//    Store only the student's name and final_grade to the Student_info object
//    we use local variable to handle the rest

istream& read(istream& is, Student_info& s)
{
    double midterm;
    double final;
    vector<double> homework;

    is >> s.name >> midterm >> final;

    // read and store all the student's homework scores (to the temporary vector<double> container)
    read_hw(is, homework);

    // compute the student's overall score, and store to the Student_info object
    try
    {
        s.final_grade = grade(midterm, final, homework);
    }
    catch (domain_error e)
    {
        s.final_grade = -1;  // indicating student has done no 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

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

// Exercise 4-6: the following function is no longer required.
/*
 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;

    // Exercise 4-6: no longer need to the followings in the Student_info object
    /*
    double midterm, final;
    std::vector<double> homework;
    */

    // Exercise 4-6: store only final_grade
    double final_grade;
};

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 will now run some tests using both the original and the revised programs. If the revised program report the same figures as the original program, we should be fairly confident that our revised program is (more or less) correct.

  • Test 1 – submit all required inputs. i.e. Student’s name, mid-term score, final-term score, and homework scores.
  • Test 2 – same as Test 1 except this time, we ommit the homework scores.

Test 1 Result

Original Program (Solution to Exercise 4-0)

Johnny 10 20 30 40 50
Fred 20 30 40 50 60
Joe 30 40 50 60 70
^Z
^Z
Fred   36
Joe    46
Johnny 26

Revised Program (Solution to Exercise 4-6)

Johnny 10 20 30 40 50
Fred 20 30 40 50 60
Joe 30 40 50 60 70
^Z
^Z
Fred   36
Joe    46
Johnny 26

*****************************************************************
*** Note: a grade of -1 implies student has done no homework. ***
*****************************************************************

Both programs gave the same results – as expected.

Test 2 Result

Original Program (Solution to Exercise 4-0)

Johnny 10 20
Fred 20 30
Joe 30 40 50 60 70
^Z
^Z
Fred   student has done no homework
Joe    46
Johnny student has done no homework

Revised Program (Solution to Exercise 4-6)

Johnny 10 20
Fred 20 30
Joe 30 40 50 60 70
^Z
^Z
Fred   -1
Joe    46
Johnny -1

*****************************************************************
*** Note: a grade of -1 implies student has done no homework. ***
*****************************************************************

Both programs gave the same results – as expected.

Conclusion

We have rewritten the program (from Solution to Exercise 4-0) as required by the problem. The test results suggest the revised program is reasonably correct.

Reference

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

A Scientific Programming Sketchbook