Accelerated C++ Solution to Exercise 5-7

August 31, 2014 Johnny 3 Comments

Exercise 5-7

Given the implementation of frame in S5.8.1/93, and the following code fragment

vector<string> v;
frame(v);

describe what happens in this call. In particular, trace through how both the width function and the frame function operate. Now, run this code. If the results differ from your expectations, first understand why your expectations and the program differ, and then change one to match the other.

Solution

The frame function has a return type of vector<string>. To “frame” the vector<string> v means to pad all the string elements within v to the full optimum width as defined by the width function. (i.e. the length of the longest string element in v).

My expectation of running this code fragment:

The first statement of the code fragment creates an empty vector<string> v.
The second statement of the code fragment attempts to frame this empty vector<string> v.
When we apply frame(v), the width function returns a maxlen of 0 (i.e. the initialised maxlen value) – i.e. implying no elements in v.
The frame function by default however, always return a top and bottom border of four asterisks (*). So even though the for loop within the frame function processes an empty vector<string> v, at a minimum, frame(v) should return the top and bottom borders. i.e. element 0 contains “****”, and element 1 contains “****”. This is it!

If we however populate the vector<string> v with some elements, the frame function should behave as demonstrated in the text book Chapter 5, or Solution to Exercise 5-0 (Part 3/3). i.e. equal length string elements with width of at least 5. e.g. if vector<string> v contains just one string element “a”, then, frame(v) will return:

element 0: “*****”
element 1:”* a *” (note there is a space around the string element)
element 2: “*****

Test Program

Though we have used the frame function multiple times in the previous exercises already, for completeness sake I shall include my test program here and run a couple of tests, for prove of concept purposes – to confirm the test result agrees with my expectation.

main.cpp

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

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

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

int main()
{
    string s;            // line
    vector<string> v;    // paragraph
    while (getline(cin, s))
        v.push_back(s);

    vector<string> framedV = frame(v);

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

    return 0;
}

Test 1 – empty vector<string> v

As expected, if we frame an empty vector<string> v, by default the frame function should return the top and bottom border at the minimum default width of four asterisks (*).

^Z
****
****

Test 2 – non-empty vector<string> v

If we frame a non-empty vector<string> v, the output should be just as described in Chapter 5 – equal length string elements, with the width determined by the longest string (line) element.

This is
a test
over over
^Z
*************
* This is   *
* a test    *
* over over *
*************

Let’s do one more. Let’s verify our expectation if we only submit a string element “a”.

a
^Z
*****
* a *
*****

Bingo!

Reference

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

C++, Programming

Accelerated C++ Solution to Exercise 5-6

August 31, 2014 Johnny 6 Comments

Exercise 5-6

Rewrite the extract_fails function from S5.1.1/77 so that instead of erasing each failing student from the input vector students, it copies the records for the passing students to the beginning of students, and then uses the resize function to remove the extra elements from the end of students. How does the performance of this version compare with the one in S5.1.1/77?

Solution

The original (version 2) extract_fail function in the text book S5.1.1/77 looks like this – it uses the vector<XXX>::erase function.

{
    Student_group fail;
    Student_group::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;
}

Note that I have used the technique developed from my Solution to Exercise 5-4, in which all the vector<Student_info> are replaced by Student_group, using the C++ typedef. (Just trust me for now there is a typdef somewhere else that defines Student_group) I believe it makes sense to build on what we have learnt!

The newly “re-written” function will look like this it uses a combination of vector<XXX>::insert and vector<XXX>::resize functions.

Student_group extract_fails_v2_5p6(Student_group& students)
{
    Student_group fail;
    typedef Student_group::size_type VecSize;
    VecSize countPass = 0;

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

    return fail;
}

If after skimping through this new code and you fully understand the concepts / what’s going on, then congratulation you are done!

From a series of tests the new version happens to take 50% more time than the original version (when reaching around 10,000 lines of input) – performance results can be found at the bottom of the page under the Test Result section.

If you however would like to know more in details, such as how I derive this new code logic, then read on!

Code Logic – The insert/resize Method

The way I derive the eventual code was simply doing some sketches on paper (In face this is how I usually solve problems – making sketches and pictures!). Below shows the diagrams that I drawn – essentially I started with a hypothetical example and just work my way through using logic. Some notes:

The countPass is a counter to keep track of the number of passing students – this will be used later on to feed the vector<XXX>::resize function.
The i, is just an incrementing variable (our good old friend), to facilitate a while loop.

Acpp5p6Pic1a

Acpp5p6Pic1b

Acpp5p6Pic2a

Acpp5p6Pic2b

Have we reached the end of the vector? (yes)

Acpp5p6Pic3a

Use the resize function to keep only the passing students in vector<Student_info> students.

Acpp5p6Pic3b

And these are the final output!

Acpp5p6Pic3c

An Important Learning – iterator

This exercise has exposed an interesting fact: iterator does NOT work when the underlying vector changes size! i.e. the following code will not work (even though it looks correct). One must use vector indexing instead! (I spent an hour debugging this – a hard lesson learnt!). Must be a feature of vector iterator vs vector index.

Student_group extract_fails_v2_5p6(Student_group& students)
{
    Student_group fail;
    Student_group::iterator i = students.begin();
    Student_group::size_type countPass = 0;

    // invariant: elements [0,i) of students represent passing grades
    while (i != students.end())
    {
        if (fgrade(*i))
            fail.push_back(*i);
        else
        {
            students.insert(students.begin(), *i);
            ++countPass;
            ++i;
        }
        ++i;
    }
    students.resize(countPass);

    return fail;
}

The Project

Here are the complete set of header and source files that enable me to perform the test.

Header File List

extract_fails.h
grade.h
median.h
Student_group.h
Student_info.h

Source Files

main.cpp

#include <iostream>
#include <iomanip>
#include <ios>
#include <ctime>
#include "Student_info.h"
#include "Student_group.h" // switch between vector and list based Student_group here
#include "grade.h"
#include "extract_fails.h"

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::streamsize;

int main()
{

    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 and time-stamp it!
    clock_t startTime = clock();
    Student_group students_failed = extract_fails_v2(students);
    /* Student_group students_failed = extract_fails_v2_5p6(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;

    // Uncomment the following block to display passing and failing students
    /*
    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.cpp

#include "Student_info.h"
#include "Student_group.h"
#include "grade.h"

// separate passing and failing student records
// derived from S5.1.1/77
Student_group extract_fails_v2(Student_group& students)
{
    Student_group fail;
    Student_group::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;
}

// Required by Exercise 5-6
Student_group extract_fails_v2_5p6(Student_group& students)
{
    Student_group fail;
    typedef Student_group::size_type VecSize;
    VecSize countPass = 0;

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

    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.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 "Student_group.h"

Student_group extract_fails_v2(Student_group&);
Student_group extract_fails_v2_5p6(Student_group&);

#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&);
bool fgrade(const Student_info&);

#endif // GUARD_GRADE_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

#endif // GUARD_MEDIAN_H

Student_group.h

#ifndef GUARD_STUDENT_GROUP_H
#define GUARD_STUDENT_GROUP_H

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

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

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

Just simply amend the following line in the main() program accordingly for test purposes.

Student_group students_failed = extract_fails_v2(students);
/* Student_group students_failed = extract_fails_v2_5p6(students); */

Performance Comparison

I’ve run a few tests and recorded the job run time for the extract_fail step. from this it looks like the insert/resize method is actually slower than the erase method. But then, I guess it depends on the input file – i.e. depending on the ratio of passing students to failing students, the sequence of the passing and failing students, and potentially other factors.

	v2 (erase)	v2_5p6 (insert/resize)
10 lines	0.001 seconds	0.000 seconds
100 lines	0.003 seconds	0.004 seconds
1,000 lines	0.156 seconds	0.212 seconds
10,000 lines	9.79 seconds	16.6 seconds

Reference

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

C++, Programming

C++ Naming Convention – geosoft.no

August 28, 2014 Johnny

Having a consistent naming convention for C++ (and other programming languages) has been a challenge for years, mainly due to different developers have different styles, or just simply, different naming conventions seemingly are considered best for the particular type of problem to solve.

Nevertheless, it is always good to be “as consistent as possible”.

The first hit of Google search return me this C++ Programming Style Guidelines documentation by geosoft.no which I quite like.

At the time of writing this it consists of 94 high level guidelines. I have just had a read through it (took me about 30-40 minutes) and found it mostly agreeable. Especially the way we name variables and types, and the way we indent our code, etc. (it is natural to have opinions against certain guidelines!)

Like all things in life, there isn’t such thing called “one size fit all”. I believe this guideline however, would help reducing 80% of the pain that we go through in figuring out how to write consistent C++ codes. (I still have Scott Meyers’s Effective C++ book to read yet!)

C++, Programming

Accelerated C++ Solution to Exercise 5-5

August 28, 2014 Johnny 1 Comment

Exercise 5-5

Write a function named center(const vector<string>&) that returns a picture in which all the lines of the original picture are padded out to their full width, and the padding is as evenly divided as possible between the left and right sides of the picture. What are the properties of pictures for which such a function is useful? How can you tell whether a given picture has these properties?

Solution

When I first saw this question, straight away it reminded me of the frame function that the author built in Chapter 5 / my Solution to Exercise 5-0 (Part 3/3). The original frame function effectively pad all the strings with empty spaces, making all strings equal width and left aligned, and put a frame around it to make it “box-like” when we display the vector<string> line by line vertically – like a formatted article.

Also recall that in my Solution to Exercise 5-1 (about building a permuted index page), I modified the frame function so that it takes on additional parameters regarding whether the padding should be left-aligned or right-aligned. So instead of creating a brand new function center(const vector<string>&), I may as well reuse the frame function and enhance it so that we have an extra option to center-aligned.

In this post I shall describe how I modify the frame function to allow user to center-align the vector<string> “picture text”.

Algorithm

We know what the algorithm looks like for left-align and right-align for the frame function from Solution to Exercise 5-1. The algorithm for center-aligned is very similar. i.e. we use the width function to identify the max length of the string (within the vector<string>). We then compute how many padding spaces are required on both (left and right) sides of each individual text string – the padding on the left should be more or less the same as the right. The diagram below essentially summarises the equations in computing the various lengths required.

Acpp5p5Pic1

These equations are reflected in the enhanced frame.cpp code below.

The Project

Let me wrap up the whole project here – we should be able to figure out how the enhanced frame function works, and how we can easily use it. (Note that I have reused the knowledge / experience gained from the previous exercises in Chapter 5).

(The enhanced frame function is the answer to the exercise – the other codes are wrapped together for demonstration purposes.)

Acpp5p5MgntTree

main.cpp
frame.h
frame.cpp
read_lines.h
read_lines.cpp
vout.h
vout.cpp

Source and Header Files

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include "read_lines.h"
#include "frame.h"
#include "vcout.h"

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

int main()
{

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

    // padded each line of the article
    vector<string> paddedArticle = frame(article,"center",'*');

    // display the now padded article
    vcout(paddedArticle);

    return 0;
}

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

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, const string& align, char c)
{
    vector<string> ret;

    typedef string::size_type stringSize;
    stringSize  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);
        else if (align == "center")
        {
            stringSize leftPadSize = (maxlen - v[i].size() ) / 2 ;
            stringSize midLineSize = v[i].size();
            stringSize rightPadSize = maxlen - leftPadSize - midLineSize;
            string padLine = symbol + " " + string(leftPadSize, ' ')
                             + v[i] + string(rightPadSize, ' ') + " " + symbol;
            ret.push_back(padLine);
        }

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

    return ret;
}

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

read_lines.cpp

#include <string>    // string
#include <vector>    // vector
#include <iostream>   // cin, 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;
}

vout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

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

#endif // GUARD_VCOUT_H

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

Test Program

Test 1 – Center Align

Update this line in main program:

vector<string> paddedArticle = frame(article,"center",'*');

Test Result:

this is an
example
to
illustrate
framing
^Z
**************
* this is an *
*  example   *
*     to     *
* illustrate *
*  framing   *
**************

Test 2 – Left Align

Update this line in main program:

vector<string> paddedArticle = frame(article,"left",'*');

Test Result:

this is an
example
to
illustrate
framing
^Z
**************
* this is an *
* example    *
* to         *
* illustrate *
* framing    *
**************

Test 3 – Right Align

Update this line in main program:

vector<string> paddedArticle = frame(article,"right",'*');

Test Result:

this is an
example
to
illustrate
framing
^Z
**************
* this is an *
*    example *
*         to *
* illustrate *
*    framing *
**************

Reference

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

C++, Programming

Accelerated C++ Solution to Exercise 5-4

August 27, 2014 Johnny 3 Comments

Exercise 5-4

Look again at the driver functions you wrote in the previous exercise. Note that it is possible to write a driver that differs only in the declaration of the type for the data structure that holds the input file. If your vector and list test drivers differ in any other way, rewrite them so that they differ only in this declaration.

Solution

The objective is to further streamline the program, so that the only change required for switching between running a vector-based and list-based workstream is a one-liner change at the declaration level.

My Solution to Exercise 5-3 require 2-line change (rather than just 1-line), so obviously there are opportunities to improve. I also see that the program contains two near identical set of source and header files (i.e. extract_fails_v3.cpp/.h, extract_fails_v4.cpp/.h) – it is very likely that we can consolidate into just one set (i.e. extract_fails.cpp/.h) – as the only difference resides on the fact that one uses vector and the other uses list – other than that, the codes are effectively the same.

So here is a rather neat way to achieve our objective (and it works!)

Create a new Student_info.h to store the a new type Student_group (defined by typedef) – which may be either vector or list based. To switch between using vector-based Student_group or list-based Student_group, we just need to do a one-liner change in this file. All other files are intact.
Consolidate extract_fails_v3.cpp/.h (vector based) and extract_fails_v4.cpp/.h (list based) into one extract_fails.cpp/.h. (generic Student_group based)
Refresh the #include directives within the codes as required.

The Project

For completeness I shall include all the files here.

Acpp5p4MgntTree

main.cpp
extract_fails.h
extract_fails.cpp
grade.h
grade.cpp
median.h
median.cpp
Student_info.h
Student_info.cpp
Student_group.h

main.cpp

#include <iostream>
#include "Student_info.h"
#include "Student_group.h" // switch between vector and list based Student_group here
#include "grade.h"
#include "extract_fails.h"

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

int main()
{

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

#ifndef GUARD_EXTRACT_FAILS_H
#define GUARD_EXTRACT_FAILS_H

// extract_fails.h
#include "Student_group.h"

Student_group extract_fails(Student_group&);

#endif // GUARD_EXTRACT_FAILS_H

extract_fails.cpp

#include "Student_info.h"
#include "Student_group.h"
#include "grade.h"

// separate passing and failing student records
// derived from S5.5/85
Student_group extract_fails(Student_group& students)
{
    Student_group fail;
    Student_group::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

#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&);
bool fgrade(const Student_info&);

#endif // GUARD_GRADE_H

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

Student_group.h

#ifndef GUARD_STUDENT_GROUP_H
#define GUARD_STUDENT_GROUP_H

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

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

#endif // GUARD_STUDENT_GROUP_H

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 Student_group.h accordingly (one-liner change).

// ********************* AMEND THIS ***************************
// Solution to Exercise 5-4: Pick one of the followings
typedef std::vector<Student_info> Student_group;
// typedef std::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 Student_group.h accordingly (one-liner change).

// ********************* AMEND THIS ***************************
// Solution to Exercise 5-4: Pick one of the followings
// typedef std::vector<Student_info> Student_group;
typedef std::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)

Conclusion

Overall this is a very good exercise to train our ability to be more “generalise” about writing codes. e..g reduce duplication. It has been suggested by the Author that this exercise builds the grounds for the C++ template topic later on in the book.

Reference

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

C++, Programming

Accelerated C++ Solution to Exercise 5-3

August 27, 2014 Johnny 1 Comment

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:

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.
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.
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.
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).
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
extract_fails_v3.h
extract_fails_v3.cpp
extract_fails_v4.h
extract_fails_v4.cpp
grade.h
grade.cpp
median.h
median.cpp
Student_info.h
Student_info.cpp

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

C++, Programming

Accelerated C++ Solution to Exercise 5-2

August 27, 2014 Johnny 2 Comments

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:

Have a pair of start and end time-stamps just before and after the extract_fails function.
Compute the duration by taking the time difference between the end and start time.
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:

Make a copy of the entire project as per Solution to Exercise 5-0 (Part 1/3).
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.
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

C++, Programming

Accelerated C++ Solution to Exercise 5-1

August 26, 2014 Johnny 6 Comments

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.

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

The outer for loop iterates through the lines in vector<string> article.
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:

Create a new Permuted_index object.
Fill in the 6 properties for the newly created Permuted_index object.
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:

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.

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:

Create the vector<string> container and populate with the requirement elements.
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

main.cpp
frame.cpp
hcat.cpp
Permuted_index.cpp
read_lines.cpp
split.cpp
vcout.cpp

Header File List

frame.h
hcat.h
Permuted_index.h
read_lines.h
split.h
vcout.h

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

C++, Programming

Accelerated C++ Solution to Exercise 5-0

August 17, 2014 Johnny

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

C++, Programming

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

August 17, 2014 Johnny

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

User to create a paragraph by providing multiple lines of input, via the console window.
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.
A function called vcout may be used to display a vector<string> container in the form of a paragraph via the console window.
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.
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.
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.
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.
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).

this is an
example
to
illustrate
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

August 2014
M	T	W	T	F	S	S
« Jul				Sep »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31