Tag Archives: Scientific Programming

Accelerated C++ Solution to Exercise 7-9

Exercise 7-9

(difficult) The implementation of nrand in S7.4.4/135 will not work for arguments greater than RAND_MAX. Usually, this restriction is no problem, because RAND_MAX is often the largest possible integer anyway. Nevertheless, there are implementations under which RAND_MAX is much smaller than the largest possible integer. For example, it is not uncommon for RAND_MAX to be 32767 (2^15 -1) and the largest possible integer to be 2147483647 (2^31 -1). Reimplement nrand so that it works well for all values of n.

Solution

This exercise is great – it gives us the chance to create and understand an algorithm that generate random number beyond RAND_MAX (the largest default C++ random number that can be “reached” by the rand() function) whilst ensuring even probability distribution of that random number (i.e. the number “10” having the same chance of getting picked as the number “234”, etc.).

Andrew and Barbara (the authors) provided the original code for this exercise on GitHub here back in year 2000. I took the liberty to read through it with the aim of understanding and making sense of the solution. After 3 evenings of sketching diagrams in my notepad (and getting stuck multiple times), I eventually understood the underlying principle / concepts, and managed to come up with an algorithm built on the authors’ original solution (with slight differences).

In this post I shall illustrate the derivation and implementation of the algorithm (which I can actually visualise). I use PowerPoint to draw out some diagrams to aid visualising the algorithms. I would like to express my sincerest thanks to Andrew and Barbara for this very wonderful exercise.

What Will Our nrand() Do?

We are going to create a function nrand() that returns a random integer, given the asymmetric range [0, randomOutcomeLimit).

e.g. if randomOutcomeLimit is 4, then the randomOutcome may be either 0, 1, 2, 3 – each with an equal (25%) chance of getting picked.

Terminologies

Before going any further, I believe it is a good idea to define some core variables / terminologies.

  • randomDriver: this is essentially rand(). The C++ default (seeding) random number that span within the asymmetric range [0, randomDriverLimit). We use randomDriver to “drive” (or compute) the eventual randomOutcome.
  • randomDriverLimit: this is RAND_MAX + 1. i.e. “one-above” the maximum possible randomDriver value.
  • randomOutcome: this is the random number that gets returned. It spans within the symmetric range [0, randomOutcomeLimit). The algorithm ensures that every single randomOutcome has the same probability of getting randomly selected. The randomOutcome is “driven” (or determined) by the randomDriver.
  • randomOutcomeLimit: “one-above” the maximum possible randomOutcome value.
  • bucketSize: this is “the glue” between randomDriver and randomOutcome. Think of it as the ratio between the two. To enable us to translate a randomDriver into a randomOutcome (and vice versa).
  • remainder: this is used in the computation of randomOutcome. Only relevant for the case whhen randomOutcomeLimit > randomDriverLimit.

Note: in the “pseudo diagrams” that I have drawn up in PowerPoint, I shall use RD to represent randomDriver, and RO to represent randomOutcome.

Algorithm

The algorithm for nrand() will cater for two scenarios:

  • Case 1: when randomOutcomeLimit <= randomDriverLimit
  • Case 2: when randomOutcomeLimit > randomDriverLimit

It may be easier if I display the complete nrand.cpp code here now, and walk through in more details afterwards.

The nrand.cpp Code

#include <cmath>         // ceil
#include <cstdlib>       // rand, RAND_MAX, srand
#include <stdexcept>     // domain_error

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

// Asymmetric ranges:
//   randomOutcome: [0, randomOutcomeLimit)
//   randomDriver:  [0, randomDriverLimit)

int nrand(int randomOutcomeLimit) {

  if (randomOutcomeLimit <= 0)
    throw domain_error("Argument to nrand is out of range");

  int randomOutcome;
  int randomDriverLimit = RAND_MAX + 1;

  if (randomOutcomeLimit <= randomDriverLimit) {
    const int bucketSize = randomDriverLimit / randomOutcomeLimit;

    do {
      int bucket = rand() / bucketSize;
      randomOutcome = bucket;
    } while (randomOutcome >= randomOutcomeLimit);

  } else {
    const int bucketSize = ceil(randomOutcomeLimit / randomDriverLimit);

    do {
      int bucket = nrand(randomDriverLimit);
      int remainder = nrand(bucketSize);
      randomOutcome = (bucket * bucketSize) + remainder;
    } while (randomOutcome >= randomOutcomeLimit);
  }
  return randomOutcome;
}
 

Case 1: when randomOutcomeLimit <= randomDriverLimit


  if (randomOutcomeLimit <= randomDriverLimit) {
    const int bucketSize = randomDriverLimit / randomOutcomeLimit;

    do {
      int bucket = rand() / bucketSize;
      randomOutcome = bucket;
    } while (randomOutcome >= randomOutcomeLimit);

  } 

Since the values of randomOutcomeLimit and randomDriverLimit are pre-defined, we compute our bucketSize by taking the ratio between the two. We use the randomDriverlimit as the numerator (and randomDriverLimit as the denominator) to ensure this ratio is a non-fraction. Think of bucketSize as: “The number of randomDrivers per randomOutcome”. 10 randomDrivers per randomOutcome makes sense. 0.5 randomDrivers per randomOutcome does not.

Note that the equation automatically “round-down” the ratio to the integer (instead of “round-up”). This is to ensure every single randomOutcome to have the same probability of being picked.

To illustrate this, assume we have randomDriverLimit = 5 (i.e. RAND_MAX = 4. i.e. randomDriver may be 0, 1, 2, 3.), and randomOutcomeLimit = 2 (i.e. randomOutcome maybe 0 and 1).

Compute bucketSize With “Round-down” (desirable)

In the case of computing bucketSize using “round-down”, the probability distribution of randomOutcome is even. This is what we want in a random number generator.

acpp7p9_Pic1a

Compute bucketSize With “Round-up” (Un-desirable)

In the case of computing bucketSize using “round-up”, the probability distribution of randomOutcome is non-even. This is what we DO NOT want in a random number generator.

acpp7p9_Pic1b

Further Visualisation

To visualise randomDriver, randomDriverLimit, randomOutcome, randomOutcomeLimit, bucket, and bucketSize all in one go, I have put together some PowerPoint diagrams here which I believe will speak for themselves without the need of much further (wordy) explanations! I assume a fixed randomDriverLimit of 21, and vary the randomOutcomeLimit for illustrations.

Visualise: randomDriverLimit of 21, randomOutcomeLimit = 2.

acpp7p9_Pic2a

Visualise: randomDriverLimit of 21, randomOutcomeLimit = 3.

acpp7p9_Pic2b

Visualise: randomDriverLimit of 21, randomOutcomeLimit = 4.

acpp7p9_Pic3a

Visualise: randomDriverLimit of 21, randomOutcomeLimit = 5.

acpp7p9_Pic3b

Visualise: randomDriverLimit of 21, randomOutcomeLimit = 6.

acpp7p9_Pic4a

Visualise: randomDriverLimit of 21, randomOutcomeLimit = 7.

acpp7p9_Pic4b

Visualise: randomDriverLimit of 21, randomOutcomeLimit = 11.

acpp7p9_Pic5a

Case 2: when randomOutcomeLimit > randomDriverLimit

  } else {
    const int bucketSize = ceil(randomOutcomeLimit / randomDriverLimit);

    do {
      int bucket = nrand(randomDriverLimit);
      int remainder = nrand(bucketSize);
      randomOutcome = (bucket * bucketSize) + remainder;
    } while (randomOutcome >= randomOutcomeLimit);
  }

We compute bucketSize in a similar manner as Case 1, except that we use “round-up” (i.e. using the “ceil” function in C++) instead of “round-down”. We also ensure a non-fraction bucketSize (as explained in Case 1), by putting randomOutcomeLimit as the numerator, and randomDriverLimit as the denominator. Think of bucketSize as: “The number of randomOutcome per randomDriver”. 10 randomOutcomes per randomRandomDriver makes sense. 0.5 randomOutcome per randomRandomDriver does not.

We use “round-up” in the computation of the bucketSize to ensure the entire range of randomDriver can “cover” the entire range of randomOutcome. I can illustrate this point easily via some diagrams as followings.

In addition, we use nrand recursively downstream. Unfortunately I am not able to explain this bit in words. I would however recommend to look at the diagrams in the following section – looking at these diagrams have helped in understanding how the remaining steps hang together. I hope you may be able to figure this out for yourself too! (use the diagrams!).

Compute bucketSize With “Round-down” (un-desirable)

acpp7p9_Pic6a

Compute bucketSize With “Round-up” (desirable)

acpp7p9_Pic6b

Further Visualisation

To visualise randomDriver, randomDriverLimit, randomOutcome, randomOutcomeLimit, bucket, and bucketSize all in one go, I have put together some PowerPoint diagrams here which I believe will speak for themselves without the need of much further (wordy) explanations! I assume a fixed randomDriverLimit of 2, and vary the randomOutcomeLimit for illustrations.

Visualise: randomDriverLimit of 2, randomOutcomeLimit = 5.

acpp7p9_Pic7a

Visualise: randomDriverLimit of 2, randomOutcomeLimit = 6.

acpp7p9_Pic7b

Visualise: randomDriverLimit of 2, randomOutcomeLimit = 7.

acpp7p9_Pic7c

Visualise: randomDriverLimit of 3, randomOutcomeLimit = 5.

acpp7p9_Pic8a

Visualise: randomDriverLimit of 3, randomOutcomeLimit = 6.

acpp7p9_Pic8b

Visualise: randomDriverLimit of 3, randomOutcomeLimit = 7.

acpp7p9_Pic8c

The Project

To wrap up the entire projects I shall document the C++ header and source files here. The nrand algorithm aims to generate random numbers within the range [0, randomOutcomeLimit) in an even probability distribution – i.e. each random outcome has the same chance of being picked.

Source File List

Header File List

Source Files

main.cpp

#include <iostream>    // std::cout, std::cin, std::endl
#include <cstdlib>     // RAND_MAX, srand
#include <ctime>       // std::time
#include "nrand.h"     // nrand

using std::cout;
using std::cin;
using std::endl;
using std::srand;
using std::time;

int main()
{
  // Uncomment this line to see new randomness every time the job is run.
  srand(time(NULL));

  // Generate random numbers within the range [0, n)
  const int n = 999999999;  // try n = 10, and n = 3276700
  const int numbersPerLine = 5;

  // Display the limits
  cout << "randomOutcomeLimit: " << n << endl;
  cout << "randomDriverLimit: " << (RAND_MAX + 1) << endl;

  // Display the randomOutcomes
  for (int i = 0; i != 100; ++i) {
    if (i == 0)
      cout << nrand(n);
    else {
      cout << ", " << nrand(n);

    // start a new line
    if (i != 0 && (i+1) % numbersPerLine == 0)
      cout << endl;
    }
  }
  return 0;
}

nrand.cpp

#include <cmath>         // ceil
#include <cstdlib>       // rand, RAND_MAX, srand
#include <stdexcept>     // domain_error

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

// Asymmetric ranges:
//   randomOutcome: [0, randomOutcomeLimit)
//   randomDriver:  [0, randomDriverLimit)

int nrand(int randomOutcomeLimit) {

  if (randomOutcomeLimit <= 0)
    throw domain_error("Argument to nrand is out of range");

  int randomOutcome;
  int randomDriverLimit = RAND_MAX + 1;

  if (randomOutcomeLimit <= randomDriverLimit) {
    const int bucketSize = randomDriverLimit / randomOutcomeLimit;

    do {
      int bucket = rand() / bucketSize;
      randomOutcome = bucket;
    } while (randomOutcome >= randomOutcomeLimit);

  } else {
    const int bucketSize = ceil(randomOutcomeLimit / randomDriverLimit);

    do {
      int bucket = nrand(randomDriverLimit);
      int remainder = nrand(bucketSize);
      randomOutcome = (bucket * bucketSize) + remainder;
    } while (randomOutcome >= randomOutcomeLimit);
  }
  return randomOutcome;
}

Header Files

nrand.h

#ifndef GUARD_NRAND_H
#define GUARD_NRAND_H

// nrand.h

int nrand(int);

#endif // GUARD_NRAND_H

Test Result

Test Case 1: when randomOutcomeLimit > randomDriverLimit

Set randomOutcomeLimit (i.e. the “n” in the main program) = 10. (randomDriverLimit on my Windows Vista System is 32768. i.e. RAND_MAX = 32767).

randomOutcomeLimit: 10
randomDriverLimit: 32768
0, 7, 3, 4, 5
, 2, 3, 5, 7, 8
, 5, 1, 0, 9, 1
, 0, 1, 2, 5, 3
, 1, 3, 5, 9, 1
, 8, 4, 8, 8, 8
, 2, 6, 8, 1, 4
, 5, 4, 5, 7, 4
, 7, 5, 1, 2, 0
, 5, 7, 3, 6, 9
, 8, 6, 5, 6, 4
, 4, 3, 2, 2, 5
, 9, 3, 0, 2, 7
, 8, 8, 1, 7, 1
, 4, 2, 3, 0, 0
, 8, 1, 2, 5, 9
, 4, 2, 5, 9, 9
, 7, 4, 3, 0, 4
, 9, 5, 6, 8, 0
, 4, 1, 6, 5, 2

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

Test Case 2: when randomOutcomeLimit <= randomDriverLimit

Set randomOutcomeLimit (i.e. the “n” in the main program) = 999999999. (randomDriverLimit on my Windows Vista System is 32768. i.e. RAND_MAX = 32767).

randomOutcomeLimit: 999999999
randomDriverLimit: 32768
40716497, 545497019, 401935189, 573265717, 87747530
, 675712555, 451019252, 549144813, 442862664, 914580320
, 3346215, 284749221, 212065917, 568356864, 979714558
, 544197549, 418473188, 720009720, 433822531, 424721581
, 541414236, 257758341, 608087599, 83473957, 984179693
, 492106188, 331214530, 521536020, 935375395, 580651497
, 195237728, 664468742, 414572965, 645131011, 682450472
, 477285531, 969901982, 319040147, 723433358, 897986272
, 120072600, 13688281, 426975024, 332152250, 774858930
, 85086071, 749114164, 49610236, 923599508, 602891952
, 599691044, 621946048, 156375628, 885810442, 918023686
, 135602107, 449128117, 661074165, 86314758, 699792585
, 461395423, 916830653, 398552621, 933505532, 326772882
, 142535635, 570358869, 573805944, 391791222, 527897950
, 942405333, 383272295, 777643889, 483575430, 421364976
, 808711544, 623226506, 83231569, 970354625, 918738412
, 272996097, 134992162, 663575905, 719215842, 172551438
, 345021838, 170806050, 154762077, 794127443, 949285447
, 81891829, 62877966, 418973269, 343240040, 888728945
, 627644733, 808847443, 814885588, 628243461, 188955197

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

Reference

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

Accelerated C++ Solution to Exercise 5-1

Exercise 5-1

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

The quick brown fox
jumped over the fence

the output would be

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

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

Step 1

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

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

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

Step 2

Sort the rotations.

Step 3

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

Solution

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

What is a Permuted Index Page?

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

Ok. Assume we have the following “article”:

Acpp5p1WikiKwic1

A Permuted Index Page may look like this:

Acpp5p1WikiKwic2

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

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

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

Acpp5p1WikiKwic3

What may our Permuted Index Page look like?

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

The quick brown fox
jumped over the fence

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

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

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

Acpp5p1pic30

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

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

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

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

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

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

C++ Algorithm and Implementation Strategy

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

The High Level Main Program

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

int main()
{

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

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

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

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

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

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

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

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

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

    // visualise the output
    vcout(Permuted_index_collection4);

    return 0;
}

Program Logic Step-by-step (in Pictures)

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

Read the Input Article

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

Acpp5p1pic5

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

The read function looks like this:

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

    return ret;
}

Create Permuted Index Objects

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

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

Acpp5p1pic6

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

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

Acpp5p1pic7

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

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

Acpp5p1pic8

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

Acpp5p1pic31

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

vector<string>::size_type birth_id

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

vector<string>::size_type line_number

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

vector<string> line_elements

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

vector<string>::size_type position_in_line

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

vector<string> rotated_line_elements

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

string rotated_line

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

Populate the Permuted Index Collection Container

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

There are two for loops.

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

Acpp5p1pic32

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

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

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

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

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

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

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

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

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

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

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

This is what the rotate_line_element function looks like.

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

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

    return ret;
}

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

Permuted_index object 0

Acpp5p1pic9

Permuted_index object 1

Acpp5p1pic10

Permuted_index object 2

Acpp5p1pic11

Permuted_index object 3

Acpp5p1pic12

Permuted_index object 4

Acpp5p1pic13

Permuted_index object 5

Acpp5p1pic14

Permuted_index object 6

Acpp5p1pic15

Permuted_index object 7

Acpp5p1pic16

Sort the Permuted Index Objects

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

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

Acpp5p1pic17

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

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

This is what the function sort_permuted_index_collection looks like

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

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

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

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

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

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

The vector<Permuted_index> container now looks like this:

Acpp5p1pic19

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

Create the “Four Blocks”

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

Acpp5p1pic18

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

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

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

To create each block, we do two things:

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

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

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

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

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

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

    return ret;
}

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

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

Acpp5p1pic20

Acpp5p1pic21

This is what the function get_left_hand_side looks like:

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

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

Acpp5p1pic22

Acpp5p1pic23

This is what the function get_right_hand_side looks like:

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

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

Acpp5p1pic24

Acpp5p1pic25

This is what the function get_line_numbers looks like:

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

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

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

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

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

Acpp5p1pic26

Acpp5p1pic27

This is what the function get_word_numbers looks like:

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

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

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

Horizontal Concatenate the “Four Blocks”

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

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

Acpp5p1pic28

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

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

Display the Permuted Index Page

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

// visualise the output
vcout(Permuted_index_collection4);

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

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

Acpp5p1pic29

And this is it!

The Complete Project

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

Acpp5p1MgntTree

Source File List

Header File List

Source Files

main.cpp

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

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

int main()
{

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

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

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

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

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

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

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

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

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

    // visualise the output
    vcout(Permuted_index_collection4);

    return 0;
}

frame.cpp

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

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

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

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

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

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

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

    return ret;
}

hcat.cpp

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

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

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

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

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

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

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

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

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

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

    return ret;
}

Permuted_index.cpp

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

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

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

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

    return ret;
}

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

    return ret;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

read_lines.cpp

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

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

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

    return ret;
}

split.cpp

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

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

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

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

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

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

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

vcout.cpp

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

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

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

Header Files

frame.h

#ifndef GUARD_FRAME_H
#define GUARD_FRAME_H

#include <string>
#include <vector>

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

#endif // GUARD_FRAME_H

hcat.h

#ifndef GUARD_HCAT_H
#define GUARD_HCAT_H

#include <string>
#include <vector>

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

#endif // GUARD_HCAT_H

Permuted_index.h

#ifndef GUARD_PERMUTED_INDEX_H
#define GUARD_PERMUTED_INDEX_H

#include <string>
#include <vector>

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

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

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

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

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

#endif // GUARD_PERMUTED_INDEX_H

read_lines.h

#ifndef GUARD_READ_LINES_H
#define GUARD_READ_LINES_H

#include <string>
#include <vector>

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

#endif // GUARD_READ_LINES_H

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

#include <vector>
#include <string>

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

#endif // GUARD_SPLIT_H

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

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

#endif // GUARD_VCOUT_H

Test Program

This summarises my program test input and output.

Test 1  – The quick brown fox

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

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

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

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

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

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

Reference

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

Accelerated C++ Solution to Exercise 3-3

Exercise 3-3

Write a program to count how many times each distinct word appears in its output.

Solution


Note: Viktor has kindly pointed out the fact that I have mis-read the question as “How many distinct words are there” (instead of how many times each distinct word appears). The solution below therefore, does not actually under the question above!!! (If I have time I may redo the question – otherwise please just ignore my solution below!!!)


My solution is a result of combining the knowledge gained from Solution to Exercise 2-8 (on recursive operations between element v[i] and v[i+1]) and Solution to Exercise 3-2 (on manipulating vector).

The solution strategy:

  • Ask user to provide the list of words so we can append the string elements to a vector, v.
  • Compute the size of vector, N.
  • If vector size is 0, the number of distinct words is also 0.
  • If vector size is 1, the number of distinct words is also 1.
  • If vector size is 2 or above, we apply an algorithm to identify and count the distinct words. (To be explained further below).

The algorithm (for the case of vector size of 2 or above) is described as followings:

  1. We sort the vector v in non-descending order.
  2. We initialise the index A to 0, and index B to 1. These indices will be used for comparing adjacent elements within the vector (to check for distinctive elements).
  3. We also initialise the distinct element count figure ND to 1 – we know that we have at least 1 distinct word.
  4. We perform N-1 number of comparisons between the adjacent elements v[A] and v[B]. (e.g. if there are 10 elements, we can only compare 9 sets of adjacent elements).
  5. During each comparison step, if v[B] is not the same as v[A], it implies that v[B] is a newly discovered distinct word. We increment ND.
  6. Note: if v[B] is the same as v[A], it implies v[B] is a repeated word. We do nothing in that case, as we are only interested in discovering new distinct words.
  7. We then increment the indices A and B by 1 for the next comparisons. i.e. we first compare v[0] and v[1], then v[1] and v[2], then v[2] and v[3], etc…
  8. We display the final value of ND – this is the number of distinct words computed.

Putting this all together, we have our full program.

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

using std::cin;             // <iostream>
using std::cout;            // <iostream>
using std::endl;            // <iostream>
using std::sort;            // <algorithm>
using std::string;          // <string>
using std::vector;          // <string>

int main()
{
    // display header message
    cout << "***************************************************************\n"
            "*** This program computes number of unique words            ***\n"
            "***************************************************************\n";
    cout << endl;

    // ask for a list of numbers and store the list as a vector
    cout << "Enter a list of words one by one: ";
    vector<string> v;
    string x;
    while (cin >> x)
        v.push_back(x);    // append new input to the vector

    cout << endl;

    // define and compute core vector variables
    typedef vector<string>::size_type vecSize;   // define a type for vector size related variables
    vecSize N = v.size();            // number of elements in the vector
    vecSize numLoops = N - 1;        // number of (comparison) operators required
    vecSize ND;                      // number of distinct words

    // Check vector size, action accordingly
    if (N ==0 )
    {
        ND = 0;
        cout << "Number of distinct words = " << ND << endl;
        return 0;
    }

    else if (N ==1 )
    {
        ND = 1;
        cout << "Number of distinct words = " << ND << endl;
        return 0;
    }

    else
    {
        // sort the vector;
        sort(v.begin(),v.end());

        // display some results to console window
        cout << "Vector size (number of words entered): " << N << endl;
        cout << endl;
        cout << "Display the sorted (non-descending) distinct words below." << endl;
        cout << v[0] << endl;

        // declare new variables
        vecSize A = 0;     // vector index
        vecSize B = 1;     // vector index
        ND = 1;            // number of distinct words

        // Loop through the vector, compute ND, and identify the distinct words
        for (vecSize i = 0; i != numLoops; ++i)
        {
            if (v[B] != v[A])
            {
                ++ND;
                cout << v[B] << endl;  // display any newly discovered distinct words
            }
            ++A;
            ++B;
        }
        // Display final distinct word count
        cout << endl;
        cout << "Number of distinct elements (words): " << ND << endl;
    }
    return 0;

}

Result

Below shows the results of the 3 sets of test:

  • N = 0
  • N=1
  • N>=2

The results also reveal that fact that the sorting elements of a vector is case-sensitive. e.g. the string John (beginning with upper case) is different to john (all lower case).

N = 0

***************************************************************
*** This program computes number of unique words            ***
***************************************************************

Enter a list of words one by one: ^Z

Number of distinct words = 0

N = 1

***************************************************************
*** This program computes number of unique words            ***
***************************************************************

Enter a list of words one by one: Johnny
^Z

Number of distinct words = 1

N >= 2

*** This program computes number of unique words            ***
***************************************************************

Enter a list of words one by one: john
peter
pete
johnny
john
John
^Z

Vector size (number of words entered): 6

Display the sorted (non-descending) distinct words below.
John
john
johnny
pete
peter

Number of distinct elements (words): 5

Reference

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

Accelerated C++ Solution to Exercise 3-2

Exercise 3-2

Write a program to compute and print the quartiles (that is, the quarter of the numbers with the largest values, the next highest quarter, and so on) of a set of integers.

Solution

According to this Wikipedia page, for discrete distributions, there is no universal agreement on selecting the quartiles values – there are 3 major computing methods.

I will apply Method 1 in my solution which has the following definitions:

  1. Use the median to divide the ordered data set into two halves. Do not include the median in either half.
  2. The lower quartile value is the median of the lower half of the data. The upper quartile value is the median of the upper half of the data.

This rule is employed by the TI-83 calculator boxplot and “1-Var Stats” functions (according to Wikipedia)

It is also very important to note that there are two types of medians:

  • Datum median – the middle data point of an ordered vector.
  • Non-datum median – the mean of the middle two data points of an ordered dataset.

Datum vs Non-datum

The computation of the lower quartile, median, and upper quartile can be either a datum or non-datum. It depends on the dataset dataset pattern which I shall expand on more shortly.

The 6 distinctive dataset patterns

After  3 hours of sketching and iterations, I am pleased to say that I have found “the dataset pattern” which I believe is consistent for all types of input datasets, and robust to implement. I summarise this pattern in the following table:

ID Pattern Condition  Quartiles (Q1, Q2, Q3)
1 NULL dataset N = 0 (Cannot compute)
2 1 Number only N = 1 Quartiles all resolve to that 1 number provided.
3 Datum Profile [0 0 0] N % 4 == 0 Datum Profile 000
4 Datum Profile [0 1 0] N % 4 == 1 Datum Profile 010
5 Datum Profile [1 0 1] N % 4 == 2   Datum Profile 101
6 Datum Profile [1 1 1] N % 4 == 3  Datum Profile 111

Note

  • I use Q1, Q2, and Q3 to denote Quartile 1, 2, and 3. (i.e. end of quarter 1, 2, and 3)
  • If the dataset is empty (Null), it is not possible to compute the quartiles for that dataset.
  • If the dataset contains only 1 number, it is quite natural to assume that there is no variation (or no range). i.e. all quartiles correspond to that number.
  • If there are at least 2 numbers provided, the pattern is determined by the Datum Profile [Q1 Q2 Q3]. There are four possible types of Datum Profiles: [0 0 0], [0 1 0], [1 0 1], and [1 1 1].
  • For example, a datum profile of [1 0 1] means: lower quartile is a datum, median is a non-datum, upper quartile is a datum. i.e. 1 represents datum. 0 represents non-datum.
  • N is the total number of elements within the dataset.
  • The % (percent) sign is used to compute remainder. e.g. N % 4 gives the remainder of N divided by 4.

Nomenclature

I use the following short-form letters to make the formula easier to understand, and program easier to code.

Symbol Meaning
v Represents the vector. e.g. v[M] resolves the value of the element locating at index M of the vector v.
N Number of elements of the vector (i.e. the input dataset)
ML An index value for computing the lower quartile. (Think Median of the Lower-halve).
M An index value for computing the median.
MU An index value for computing the upper quartile. (Think Median of the Upper-halve).
ml The computed value of lower quartile.
m The computed value of median
mu The computed value of upper quartile.

Solution Strategy

At a high level, this is what the program should do:

  • Read the list of numbers from the user and store in a vector.
  • Pattern 1: If vector contains no elements (i.e. NULL), output an error message (mentioning the program requires at least 1 number to compute quartiles), then exit the program peacefully.
  • Pattern 2: If vector contains just 1 number, output a message saying that all quartiles values are the same as that number provided, then exit the program peacefully.
  • Sort the vector so it become non-descending – this is required for the median computation.
  • Determine whether the dataset belongs to pattern 3, 4, 5, or 6, execute the corresponding algorithms, display the quartile summary at the end.

Before walking through this solution strategy I think it is worth expand a bit more on how I derive the algorithms for pattern 3, 4, 5, and 6 in the first place.

Derivation of Algorithms

Pattern 1 (null dataset) and patter 2 (1 number only) are very straight forward and have already been explained above. So I’m not going to expand further on these first two patterns.

Pattern 3, 4, 5 and 6, however, are much more interesting in comparison. These patterns require a bit more intelligence to solve – so I will focus on these one-by-one and summarise this at the end.

 The Repeating Cycles

The first thing that I did in terms of trying to spot a pattern was to sketch out around a number vectors with sizes ranging from N=2 to N=11 (could have been more but the patter had become quite obvious at that point!), circle out the datum profile, and hope to see some sort of pattern. Through the exercise I observed that the datum profile changes every time I increase N by 1. I also observed the profile change follows a cycle of 4 increments. e.g. the profile is the same at N=2, N=6, N=10, etc…. The following table is that “sketch” that I produced which led me to the discovery of algorithms.

N N % 4  Profile Sketch
2  2  [101] Acpp3p2N2
3 3  [111] Acpp3p2N3
4  0  [000] Acpp3p2N4
5 1  [010] Acpp3p2N5
6 2  [101] Acpp3p2N6
7 3  [111] Acpp3p2N7
8 0  [000] Acpp3p2N8
9 1  [010]  Acpp3p2N9
 10 2  [101]  Acpp3p2N10
11 3  [111]  Acpp3p2N11

The pattern can therefore be summarised as follows:

Pattern ID Datum Profile N % 4
3 [000] 0
4 [010] 1
5 [101] 2
6 [111] 3

We now have this core table, let’s derive the equations.

Equations and Examples

These diagrams summarise the equations, examples, and code implementations for each of the four datum patterns.

Profile [000] – Equations and Examples

Profile 000 Equations

Profile 000 Equations

Profile 000 Equations

Profile [010] – Equations and Examples

Profile 010 Equations

Profile 010 Equations

Acpp3p2Pic5b

Profile [101] – Equations and Examples

Acpp3p2Pic6

Acpp3p2Pic7

Acpp3p2Pic8a

Acpp3p2Pic8b

Profile [111] – Equations and Examples

Acpp3p2Pic9

Acpp3p2Pic10

Acpp3p2Pic11a

Acpp3p2Pic11b

 The Program

Now that we have our algorithms, let’s put everything together into a final program. I am purely using the skeleton program from chapter 3 of the book (which has an in-depth explanation of the various components). I merely implement the algorithms into this skeleton program, with some extra enhancements for user-friendly output.

#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <string>
#include <vector>

using std::cin;             // <iostream>
using std::cout;            // <iostream>
using std::endl;            // <iostream>
using std::setprecision;    // <iomanip>
using std::sort;            // <algorithm>
using std::streamsize;      // <ios>
using std::string;          // <string>
using std::vector;          // <string>

int main()
{
    // display header message
    cout << "***************************************************************\n"
            "*** This program computes quartiles given a list of numbers ***\n"
            "***************************************************************\n";
    cout << endl;

    // ask for a list of numbers and store the list as a vector
    cout << "Enter all a list of numbers: ";
    vector<double> v;
    double x;
    while (cin >> x)
        v.push_back(x);

    // check vector size and action accordingly
    cout << endl;
    typedef vector<double>::size_type vecSize;
    vecSize N = v.size();
    if (N ==0 )
    {
        cout << "You must enter some numbers! " << endl;
        return 1;
    }

    else if (N ==1 )
    {
        cout << " Only 1 number supplied. Q1, Q2, and Q3 all equate to " << v[0] << endl;
        return 0;
    }

    else
    {
        // sort the homework grades;
        sort(v.begin(),v.end());
    }

    // declare new variables
    vecSize NMod4 = (N % 4);  // identification of 1 of the 4 known datum distribution profiles
    string datumDistr = "";   // datum distribution profile
    vecSize M, ML, MU;        // core vector indices for quartile computation
    double m, ml, mu;         // quartile values are store here

    // compute quartiles for the 4 known patterns
    if ( NMod4 == 0 )
    {
        // Q1-Q3 datum distribution: [0 0 0]
        datumDistr = "[0 0 0]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML;

        // grab quartile values
        ml= (v[ML] + v[ML-1]) / 2;     // datum: 0
        m = (v[M] + v[M-1]) / 2;       // datum: 0
        mu = (v[MU] + v[MU-1]) / 2;    // datum: 0
    }

    else if ( NMod4 == 1 )
    {
        // Q1-Q3 datum distribution: [0 1 0]
        datumDistr = "[0 1 0]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML + 1;

        // grab quartile values
        datumDistr = "[0 0 0]";
        ml= (v[ML] + v[ML-1]) / 2;      // datum: 0
        m = v[M];                       // datum: 1
        mu = (v[MU] + v[MU-1]) / 2;     // datum: 0
    }

    else if ( NMod4 == 2 )
    {
        // Q1-Q3 datum distribution: [1 0 1]
        datumDistr = "[1 0 1]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML;

        // grab quartile values
        ml= v[ML];                    // datum: 1
        m = (v[M] + v[M-1]) / 2;     // datum: 0
        mu = v[MU];                   // datum: 1
    }

    else if ( NMod4 == 3 )
    {
        // Q1-Q3 datum distribution: [1 1 1]
        datumDistr = "[1 1 1]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML + 1;

        // grab quartile values
        ml= v[ML];                    // datum: 1
        m = v[M];                     // datum: 0
        mu = v[MU];                   // datum: 1
    }

    else
    {
        cout << "Unknown pattern discovered - new algorithm may be required.";
    }

    // Display results
    streamsize prec = cout.precision();
    cout << "Display the sorted (non-descending) vector below." << endl;
    cout << "Index: Number" << endl;
    for (vecSize i = 0; i !=  N; ++i)
    {
        cout << i << ": " << v[i] << endl;
    }
    cout << endl;
    cout << "Vector size: " << N << endl;
    cout << "Datum Distribution: " << datumDistr << endl;
    cout << setprecision(3) << endl
         << " Q1: " << ml << endl
         << " Q2: " << m << endl
         << " Q3: " << mu << endl
         << setprecision(prec);
}

Result

i’m going to run the program a number of times – each with different input dataset. (e.g. incrementing N by 1, try out the Wikipedia example and compare, etc.)

N = 0

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: ^Z

You must enter some numbers!

Process returned 1 (0x1)   execution time : 9.804 s

N = 1

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 5
^Z

 Only 1 number supplied. Q1, Q2, and Q3 all equate to 5

Process returned 0 (0x0)   execution time : 8.430 s

N = 2

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 10
20
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 10
1: 20

Vector size: 2
Datum Distribution: [1 0 1]

 Q1: 10
 Q2: 15
 Q3: 20

N = 3

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 10
20
30
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 10
1: 20
2: 30

Vector size: 3
Datum Distribution: [1 1 1]

 Q1: 10
 Q2: 20
 Q3: 30

N = 4

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 6
2
4
9
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 2
1: 4
2: 6
3: 9

Vector size: 4
Datum Distribution: [0 0 0]

 Q1: 3
 Q2: 5
 Q3: 7.5

N = 5

Enter all a list of numbers: 9
4
20
39
44
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 4
1: 9
2: 20
3: 39
4: 44

Vector size: 5
Datum Distribution: [0 0 0]

 Q1: 6.5
 Q2: 20
 Q3: 41.5

Wikipedia example (even size vector)

The results match!

**************************************************************
*** This program computes quartiles given a list of numbers **
**************************************************************

Enter all a list of numbers: 41
39
15
7
36
40
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 7
1: 15
2: 36
3: 39
4: 40
5: 41

Vector size: 6
Datum Distribution: [1 0 1]

 Q1: 15
 Q2: 37.5
 Q3: 40

Wikipedia example (odd size vector)

The results match!

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 49
43
41
39
15
6
7
36
40
42
47
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 6
1: 7
2: 15
3: 36
4: 39
5: 40
6: 41
7: 42
8: 43
9: 47
10: 49

Vector size: 11
Datum Distribution: [1 1 1]

 Q1: 15
 Q2: 40
 Q3: 43

Reference

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

Accelerated C++ Solution to Exercise 2-8

Exercise 2-8

Write a program to generate the product of the numbers in the range [1,10).

Solution

The question asks as to compute the product of the numbers within the asymmetric range [1,10). In other words, the product of numbers within the range of 1 to 10, excluding 10. i.e.

1 x 2 x 3 ... x 7 x 8 x 9

Observation: this is the same as 9 factorial (9!). This is the same logic as computing n factorial.

Here outlines my solution strategy at the top level.

Solution Strategy

Descriptions:

  • Fact: the product of 3 x 4 x 5 (ascending syntax) is the same as 5 x 4 x 3 (descending syntax). So for simplicity, we restrict ourself by only writing in an ascending syntax. i.e. use [3,6), and avoid [5,1) . This is the same as making the assumption of n >= m.
  • Fact: Case 1, if (n-m)=0, e.g. the asymmetric range is [3,3), this is equivalent of saying the range is between 3 and 3 (excluding 3). Because this range is null, the product is also null (zero). No loops required.
  • Fact: Case 2, if (n-m)=1, e.g. the asymmetric range is [3,4), this is equivalent of saying the range is between 3 and 4 (excluding 4). The range is therefore just the number 3 (i.e. m). Likewise, the product is also 3 (i.e. m). No loops required.
  • Fact: Case 3, if (n-m)>=1, e.g. the asymmetric range is [3,7), this is equivalent of saying the range is between 3 and 7 (excluding 7). i.e. we are looking for the product of 3 x 4 x 5 x 6. To compute this we must use loops. The main focus of this post is case 3.

Case 3 Solution Strategy

After spending an entire Sunday afternoon on this question, I eventually spotted a pattern which I believe is consistent and can be leveraged in the forming of our algorithm. To demonstrate this pattern, I have put together some diagrams in PowerPoint and presented as snapshot images below. For clarity, we are going to focus on this particular (arbitrary) asymmetric range as our core example: [3, 7).

Solution Strategy

 

Observations:

  • The number of elements is always (n-m). there are 4 elements in this case.
  • The number of loops required is always (n-m-1). We need 3 loops in this case. (numLoops = 3).
  • The number of loops required also equals to the number of (multiplication) operator.
  • Knowing the number of loops required enable us to form the loop invariant i [0,numLoops).

Now, let’s try and observe more patterns – what happens at each loop? (See diagram below)

Solution Strategy

Observations:

  • 4 major variables are required.
  • The integer invariant i that controls whether the loop is to go ahead or terminate.
  • The integer variable a – the lower number of the product (a x b).
  • The integer variable b – the higher number of the product (a x b).
  • The integer variable c – the product of (a x b).
  • At the beginning of the very first loop, initialise values of a and b.
  • At the end of each loop, the re-initialise values of a and b.

The final product of [m,n) is the value of c at the end of the very last loop.

For completeness, let’s do a drill down into the loops in greater depth. Bear in mind that for [3,7), the numLoops is n-m-1=3. We need 3 loops. The loop go ahead if the invariant i has not reached numLoops – it starts at 0 (zero), and get increment by 1 at end of each loop.

Invariant i = 0 (Loop)

Solution Strategy

Invariant i = 1 (Loop)

Solution Strategy

Invariant i = 2 (Loop)

Solution Strategy

Invariant i = 3 (No Loop)

Solution Strategy

At the end of the loop, output the final result. The product of the numbers within the asymmetric range [m,n) is the value of c at the end of the very last loop. The following table summarises this looping process.

Invariant i a b c
0 3 4 12
1 12 5 60
2 60 6 360

Full Program

We should now have all the fundamentals in the making of our program. This is my version of the program. (There are many ways to do this however!)

#include <iostream>
using namespace std;
int main()
{
    cout << "***********************************************************\n"
         << "*** This program computes the product of the numbers    ***\n"
         << "*** in the asymmetric range [m,n).                      ***\n"
         << "*** (Limitation: please ensure m is not larger than n)  ***\n"
         << "*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***\n"
         << "***********************************************************";
    cout << endl;

    // Ask user to supply the startNumber
    cout << "Enter m: ";
    int m;
    cin >> m;

    // Ask user to supply the endNumber
    cout << "Enter n: ";
    int n;
    cin >> n;

    // Algorithm to compute the product of numbers within the asymmetric range [m,n)
    const int startNumber = m ;
    const int endNumber = n;
    const int numElements = endNumber - startNumber;
    const int numLoops = numElements - 1;
    int c;
    if (numElements == 0)
        {c = 0;}
    else if (numElements == 1)
        {c = startNumber;}
    else
    {
        int a = startNumber;
        int b = startNumber + 1;

        cout << " i, a, b, c " << endl;
        for (int i = 0; i != numLoops; ++i)
        {
            c = a * b;
            cout << i << ", " << a << ", " << b << ", " << c << endl;
            a = c;
            ++b;
        }
    }
    cout << "Asymmetric range: [" << startNumber << "," << endNumber << ")" << endl;
    cout << "Number of elements: " << numElements << endl;
    cout << "Number of loops required: " << numLoops << endl;
    cout << "Product of numbers within the asymmetric range = " << c << endl;
    return 0;
}

Result

The program is meant to be robust and be able to deal with any asymmetric range [m,n) as long as (n>=m). Case 1-3 are mainly for prove of concepts. Case 4 is the solution to the question (find product of numbers within the range [1,10).

  • Case 1 – when (n-m)=0. e.g. [3,3)
  • Case 2 – when (n-m)=1. e.g. [3,4)
  • Case 3 – when (n-m)>1. e.g. [3,7)
  • Case 4 – when (n-m)>1. e.g. [1,10)

Case 1 – Asymmetric Range [3,3)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 3
Asymmetric range: [3,3)
Number of elements: 0
Number of loops required: 0
Product of numbers within the asymmetric range = 0

Case 2 – Asymmetric Range [3,4)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 4
Asymmetric range: [3,4)
Number of elements: 1
Number of loops required: 0
Product of numbers within the asymmetric range = 3

Case 3 – Asymmetric Range [3,7)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 7
 i, a, b, c
0, 3, 4, 12
1, 12, 5, 60
2, 60, 6, 360
Asymmetric range: [3,7)
Number of elements: 4
Number of loops required: 3
Product of numbers within the asymmetric range = 360

Case 4- Asymmetric Range [1,10)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 1
Enter n: 10
 i, a, b, c
0, 1, 2, 2
1, 2, 3, 6
2, 6, 4, 24
3, 24, 5, 120
4, 120, 6, 720
5, 720, 7, 5040
6, 5040, 8, 40320
7, 40320, 9, 362880
Asymmetric range: [1,10)
Number of elements: 9
Number of loops required: 8
Product of numbers within the asymmetric range = 362880

Compute the N factorial

Note that this program may also be used as a skeleton program for computing factorial. e.g. 5! = 1 x 2 x 3 x 4 x 5. In other words, to compute n! this is effectively the same as computing the internal product of the numbers within the asymmetric range (0, n+1).

Conclusion

The product of the numbers within the asymmetric range [0,10) is 362880, as computed by the program (and verified by calculators). This program might also be used as a skeleton program for computing factorial.

Reference

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

Accelerated C++ Solution to Exercise 2-5

Exercise 2-5

Write the set of “*” characters so that they form a square, a rectangle, and a triangle.

Solution

This is a fun one! To make this an even more interesting problem to solve, I’m going to add one more requirement – hollow and solid shapes. This diagram outlines my solution strategy:

Solution Stategy

In this post I will:

  • Walk through the solution strategy step-by-step, with explanation of the code snippets that I have created using logics.
  • Put all the snippets together and form one complete program.
  • Run the complete program and record the results – seeing is believing!

I will start from step one of my solution strategy.

1 – Choose Shape Type

Shape Type

The program first asks the user to select the int inputShapeType 1 (Square), 2 (Rectangle), or 3 (Triangle). This is stored as the const int shapeType which has global scope. I’ve also added a for loop for the extra effect that, in the case that the user type in a number outside the selected range (e.g. 9), the program would keep re-asking the question until the user eventually type in the valid range of 1, 2, or 3. Note that if we really want we could add extra controls such as preventing the user from entering letters (instead of numbers). But for the sake of this exercise.

        // ask for the Shape Type
        int inputShapeType;
        for (int keepAsking = 1; keepAsking == 1; )
        {
            cout << "Select the Shape Type." << endl;
            cout << "  (1) - Square " << endl;
            cout << "  (2) - Rectangle " << endl;
            cout << "  (3) - Triangle " << endl;
            cout << "Shape Type (enter 1/2/3): ";
            cin >> inputShapeType;

            // Make sure the user input is within range. If not, ask again!
            if (inputShapeType == 1 || inputShapeType == 2 || inputShapeType == 3)
                {keepAsking = 0;}
        }
        const int shapeType = inputShapeType;

2 – Define Shape Height

Shape Height

We ask the user to supply the desirable height (in number of columns). This integer height is stored as a int const numRows and has global scope.

        // ask for the shape height
        cout << "Enter Shape Height: ";
        int shapeHeight;
        cin >> shapeHeight;

        // set the total number of rows to write (as a constant)
        int const numRows = shapeHeight;    

3 – Define or Compute Shape Width

Shape Width

  • If the shape is a square, the width is computed as the same as height.
  • If the shape is a rectangle, the user will need to explicitly supply the width (in number of columns).
  • If the shape is a triangle, the width is computed as: width = (2*numRows)-1.

We store the width as const string:size_type numCols.

        // Only need to ask for a width if the shape is a a rectangle
        // For square and triangle, the width is computed instead.
        int shapeWidth;
        if (shapeType == 2)
        {
            // ask for the shape width
            cout << "Enter Shape Width: ";
            cin >> shapeWidth;
        }

        // compute the number of columns to write (as a constant) based on shape type
        int finalShapeWidth;
        if (shapeType == 1)
            {finalShapeWidth = shapeHeight; }    // Compute square width
        else if (shapeType == 2)
            {finalShapeWidth = shapeWidth; }     // Define rectangle width
        else
           {finalShapeWidth = (2*numRows)-1; }   // Compute triangle width
        const string::size_type numCols = finalShapeWidth; // define constant here  

4 – Choose Fill Style (Hollow / Solid)

Fill Style

To make the problem more interesting I have added the option to either output a hollow or solid shape. We ask user to choose option 1 (Hollow), or 2 (Solid) and store the value as int inputFillStyle. We eventually store this value as a const int fillSyle. Depending on the shapeType and fillStyle we may apply different algorithm accordingly later on.

        // ask for the Shape Fill Style
        int inputFillStyle;
        for (int keepAsking = 1; keepAsking == 1; )
        {
            cout << "Select Fill Style." << endl;
            cout << "  (1) - Hollow " << endl;
            cout << "  (2) - Solid " << endl;
            cout << "Select Fill Style (enter 1/2): ";
            cin >> inputFillStyle;

            // Make sure the user input is within range. If not, ask again!
            if (inputFillStyle == 1 || inputFillStyle == 2)
                {keepAsking = 0;}
        }
        const int fillStyle = inputFillStyle;

5 – Apply Algorithms

Algo Loop

All algorithms follow the same “looping” procedure. We have two loops (like in the previous exercises):

  • a for loop with the invariant r (increment of 1), and an asymmetric range of [0, numRows). Denote this as r[0,numRows].
  • a nested while loop with the invariant c, and an asymmetric range of [0, numCols). Denote this as c[0,numCols].

Just to refresh memory, asymmetric range of [0,numRows) means the range is betwen 0 and numRows, and excludeding numRows from the range. The looping procedure looks like this:

// invariant: we have written r rows so far
for ( int r = 0; r != numRows; ++r )
{
    string::size_type c = 0;

    // invariant: we have written c characters so far in the current row
    while ( c != numCols)
    {       

        // Algorithms go here (where the invariant c gets incremented accordingly)

     }
 }      

Rectangle (and Square) Algorithm

Algo Rectangle

If rectangle and square, use the solid/hollow rectangle algorithm (as square is a form of rectangle).

                // If Square or Rectangle Option
                if (shapeType == 1 or shapeType == 2)
                {
                    // hollow option
                    if (fillStyle == 1)
                    {
                        // Are we at the exact position to output asterisk (border)?
                        if (
                               ( c == 0 )                    // the left edge
                            || ( c == numCols-1)        // the right edge
                            || ( r == 0 )                     // the top edge
                            || ( r == numRows-1)       // or the bottom edge
                           )
                        { cout << "*"; ++c; }
                        else
                        { cout << ' '; ++c; }
                    }

                    // If solid option
                    else if (fillStyle == 2)
                    { cout << "*"; ++c; } 
                }

Triangle Algorithm

Algo Triangles

If triangle, use the solid/hollow triangle algorithm.

                // If Triangle Option
                if (shapeType == 3)
                {
                     // If Triangle hollow option
                    if (fillStyle == 1)
                    {
                        // Are we at the exact position to output asterisk (border)?
                        if (
                               ( c == ((numCols-1)/2)-r )  // the triangle left edge
                            || ( c == ((numCols-1)/2)+r )  // or the triangle right edge
                            || ( r == numRows-1)           // or the triangle bottom edge
                           )
                        { cout << "*"; ++c; }
                        else
                        { cout << ' '; ++c; }
                    }

                    // If triangle solid option
                    else if (fillStyle == 2)
                    {
                        // Are we at the exact position to output asterisk (solid fill)?
                        if (
                               ( c >= ((numCols-1)/2)-r )  // between the triangle left edge
                            && ( c <= ((numCols-1)/2)+r )  // and the triangle right edge
                           )
                        { cout << "*"; ++c; }
                        else
                        { cout << ' '; ++c; }
                    }
                }

6 – Extras

To make the problem more robust I have also added the following features:

A banner at the top to make the console output prettier.

        cout << endl;
        cout << "*********************************" << endl;
        cout << "*** The Shape Making Program  ***" << endl;
        cout << "*********************************" << endl;
        cout << endl;

Display the height and width values for clarification.

        // display the shape specification
        cout << endl;
        cout << "Height = " << numRows << " rows." << endl;
        cout << "Width = " << numCols << " columns." << endl;
        cout << endl;

At the end of the program, offer the user an option to re-start the program (from the top) by entering the y button on the keyboard (whereas entering any other keys will cause the program to terminate peacefully). To do this, we wrap the entire main program with a while loop.

int main()
{

    string tryAgain = "y";
    while (tryAgain == "y")
    {

        // The core program components go here

        // at the end of the program we ask user if he would like to re-run program
        // depending on the user input then this program may either re-run or terminate
        cout << "Again? (y/n): ";
        cin >> tryAgain;
    }
    return 0;
}

}
[/code]

The Complete Program

Putting this all together, we now have our complete program.

#include <iostream>
#include <string>

// say what standard-library names we use
using std::cin; using std::endl;
using std::cout; using std::string;

int main()
{
    // at the end of the program we ask user if he would like to re-run program
    // depending on the user input then this program may either re-run or terminate
    string tryAgain = "y";
    while (tryAgain == "y")

    {
        cout << endl;
        cout << "*********************************" << endl;
        cout << "*** The Shape Making Program  ***" << endl;
        cout << "*********************************" << endl;
        cout << endl;

        // ask for the Shape Type
        int shapeType;
        for (int keepAsking = 1; keepAsking == 1; )
        {
            cout << "Select the Shape Type." << endl;
            cout << "  (1) - Square " << endl;
            cout << "  (2) - Rectangle " << endl;
            cout << "  (3) - Triangle " << endl;
            cout << "Shape Type (enter 1/2/3): ";
            cin >> shapeType;

            // Make sure the user input is within range. If not, ask again!
            if (shapeType == 1 || shapeType == 2 || shapeType == 3)
                {keepAsking = 0;}
        }

        // ask for the shape height
        cout << "Enter Shape Height: ";
        int shapeHeight;
        cin >> shapeHeight;

        // set the total number of rows to write (as a constant)
        int const numRows = shapeHeight;        

        // Only need to ask for a width if the shape is a a rectangle
        // For square and triangle, the width is computed instead.
        int shapeWidth;
        if (shapeType == 2)
        {
            // ask for the shape width
            cout << "Enter Shape Width: ";
            cin >> shapeWidth;
        }

        // compute the number of columns to write (as a constant) based on shape type
        int finalShapeWidth;
        if (shapeType == 1)
            {finalShapeWidth = shapeHeight; }    // Compute square width
        else if (shapeType == 2)
            {finalShapeWidth = shapeWidth; }     // Define rectangle width
        else
           {finalShapeWidth = (2*numRows)-1; }   // Compute triangle width
        const string::size_type numCols = finalShapeWidth; // define constant here      


        // ask for the Shape Fill Style
        int fillStyle;
        for (int keepAsking = 1; keepAsking == 1; )
        {
            cout << "Select Fill Style." << endl;
            cout << "  (1) - Hollow " << endl;
            cout << "  (2) - Solid " << endl;
            cout << "Select Fill Style (enter 1/2): ";
            cin >> fillStyle;

            // Make sure the user input is within range. If not, ask again!
            if (fillStyle == 1 || fillStyle == 2)
                {keepAsking = 0;}
        }

        // display the shape specification
        cout << endl;
        cout << "Height = " << numRows << " rows." << endl;
        cout << "Width = " << numCols << " columns." << endl;
        cout << endl;

        // invariant: we have written r rows so far
        for ( int r = 0; r != numRows; ++r )
        {
            string::size_type c = 0;

            // invariant: we have written c characters so far in the current row
            while ( c != numCols)
            {
                // If Square or Rectangle Option
                if (shapeType == 1 or shapeType == 2)
                {
                    // hollow option
                    if (fillStyle == 1)
                    {
                        // Are we at the exact position to output asterisk (border)?
                        if (
                               ( c == 0 )              // the left edge
                            || ( c == numCols-1)       // the right edge
                            || ( r == 0 )              // the top edge
                            || ( r == numRows-1)       // or the bottom edge
                           )
                        { cout << "*"; ++c; }
                        else
                        { cout << ' '; ++c; }
                    }

                    // If solid option
                    else if (fillStyle == 2)
                    { cout << "*"; ++c; }
                }

                // If Triangle Option
                if (shapeType == 3)
                {
                     // Triangle hollow option
                    if (fillStyle == 1)
                    {
                        // Are we at the exact position to output asterisk (border)?
                        if (
                               ( c == ((numCols-1)/2)-r )  // the triangle left edge
                            || ( c == ((numCols-1)/2)+r )  // or the triangle right edge
                            || ( r == numRows-1)           // or the triangle bottom edge
                           )
                        { cout << "*"; ++c; }
                        else
                        { cout << ' '; ++c; }
                    }

                    // If triangle solid option
                    else if (fillStyle == 2)
                    {
                        // Are we at the exact position to output asterisk (solid fill)?
                        if (
                               ( c >= ((numCols-1)/2)-r )  // between the triangle left edge
                            && ( c <= ((numCols-1)/2)+r )  // and the triangle right edge
                           )
                        { cout << "*"; ++c; }
                        else
                        { cout << ' '; ++c; }
                    }
                }
            }
            cout << endl;
        }

        // ask user if he would like to start the program again
        cout << "Again? (y/n): ";
        cin >> tryAgain;
    }
    return 0;
}

Result

*********************************
*** The Shape Making Program  ***
*********************************

Select the Shape Type.
  (1) - Square
  (2) - Rectangle
  (3) - Triangle
Shape Type (enter 1/2/3): 1
Enter Shape Height: 5
Select Fill Style.
  (1) - Hollow
  (2) - Solid
Select Fill Style (enter 1/2): 1

Height = 5 rows.
Width = 5 columns.

*****
*   *
*   *
*   *
*****
Again? (y/n): y

*********************************
*** The Shape Making Program  ***
*********************************

Select the Shape Type.
  (1) - Square
  (2) - Rectangle
  (3) - Triangle
Shape Type (enter 1/2/3): 1
Enter Shape Height: 5
Select Fill Style.
  (1) - Hollow
  (2) - Solid
Select Fill Style (enter 1/2): 2

Height = 5 rows.
Width = 5 columns.

*****
*****
*****
*****
*****
Again? (y/n): y

*********************************
*** The Shape Making Program  ***
*********************************

Select the Shape Type.
  (1) - Square
  (2) - Rectangle
  (3) - Triangle
Shape Type (enter 1/2/3): 2
Enter Shape Height: 5
Enter Shape Width: 10
Select Fill Style.
  (1) - Hollow
  (2) - Solid
Select Fill Style (enter 1/2): 1

Height = 5 rows.
Width = 10 columns.

**********
*        *
*        *
*        *
**********
Again? (y/n): y

*********************************
*** The Shape Making Program  ***
*********************************

Select the Shape Type.
  (1) - Square
  (2) - Rectangle
  (3) - Triangle
Shape Type (enter 1/2/3): 2
Enter Shape Height: 5
Enter Shape Width: 10
Select Fill Style.
  (1) - Hollow
  (2) - Solid
Select Fill Style (enter 1/2): 2

Height = 5 rows.
Width = 10 columns.

**********
**********
**********
**********
**********
Again? (y/n): y

*********************************
*** The Shape Making Program  ***
*********************************

Select the Shape Type.
  (1) - Square
  (2) - Rectangle
  (3) - Triangle
Shape Type (enter 1/2/3): 3
Enter Shape Height: 5
Select Fill Style.
  (1) - Hollow
  (2) - Solid
Select Fill Style (enter 1/2): 1

Height = 5 rows.
Width = 9 columns.

    *
   * *
  *   *
 *     *
*********
Again? (y/n): y

*********************************
*** The Shape Making Program  ***
*********************************

Select the Shape Type.
  (1) - Square
  (2) - Rectangle
  (3) - Triangle
Shape Type (enter 1/2/3): 3
Enter Shape Height: 5
Select Fill Style.
  (1) - Hollow
  (2) - Solid
Select Fill Style (enter 1/2): 2

Height = 5 rows.
Width = 9 columns.

    *
   ***
  *****
 *******
*********
Again? (y/n): n

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

Remarks

This (procedural) program works fine when the problem is fairly simple. When things get more complicated (e.g. if we are asked to produce hundreds or even thousands of different types of shapes, a procedural code might become harder and harder to write and maintain. In that case, I wonder if an object-orientated approach may help simplifying this? Something to come back to in future I guess. i.e. to rewrite the above program in an object oriented manner.

Reference

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

My solutions to the book Accelerated C++ (A. Koenig and B. Moo)

C++ is one of the most popular programming languages used in the scientific programming area. So I’ve decided to have a go learning it.

I’ve been recommended to start with this book called Accelerated C++ by Andrew Koenig and Barbara E. Moo (Published in 2000 by Addison Wesley). The book is very compacted (~300 pages) and is said to be suitable for beginner. The tag line is “Practical Programming by Example” – teaching only the bits and pieces that are required to solve most of the problems.

The book contains 17 chapters. At the end of each chapter is a list of problems to solve. As part of my learning I shall have a go solving these and post my solutions and feedback via posts.

It’s just learning.