Exercise 7-8

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

Solution

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

This is the solution strategy:

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

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

… is replaced by this (using find_urls)….

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

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

The Project

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

Source File List

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

Header File List

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

Source Files

main.cpp

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

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

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

int main() { 

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

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

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

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

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

    ++line_it;

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

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

  }

  return 0; 
} 

find_urls.cpp

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

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

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

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

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

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

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

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

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

not_url_char.cpp

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

using std::string;

bool not_url_char(char c) { 

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

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

}

split.cpp

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

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

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

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

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

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

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

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

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

  // Re-initialize
  i = j;

  } 

  return ret; 

}

url_beg.cpp

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

using std::string;

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

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

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

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

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

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

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

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

  } 

  return e; 

}

url_end.cpp

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

using std::string;

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

xref.cpp

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

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

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

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

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

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

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

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

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


  }

  return ret; 
}

Header Files

find_urls.h

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

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

#endif // GUARD_FIND_URLS_H

not_url_char.h

#ifndef GUARD_NOT_URL_CHAR_H
#define GUARD_NOT_URL_CHAR_H

bool not_url_char(char);

#endif // GUARD_NOT_URL_CHAR_H

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

#include <vector>
#include <string>

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

#endif // GUARD_SPLIT_H

url_beg.h

#ifndef GUARD_URL_BEG_H

#define GUARD_URL_BEG_H

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

#endif // GUARD_URL_BEG_H

url_end.h

#ifndef GUARD_URL_END_H

#define GUARD_URL_END_H

#include <string>

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

#endif // GUARD_URL_END_H

xref.h

#ifndef GUARD_XREF_H

#define GUARD_XREF_H

// xref.h

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

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

#endif // GUARD_XREF_H

Test Result

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

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

Reference

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

Exercise 7-7

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

Solution

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

For instance…

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

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

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

This is the original snippet within the main function:

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

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

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

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

Surprisingly simple.

The Project

Simply…

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

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

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

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

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

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

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

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

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

  return 0;
}

Test Result

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

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

Reference

Exercise 7-6

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

Solution

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

In the followings, I shall:

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

The Project

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

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

Newer Version Souce and Header Files

This summarises the newer version source and header files.

gen_aux.h

#ifndef GUARD_GEN_AUX_H
#define GUARD_GEN_AUX_H

// gen_aux.h

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

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

#endif // GUARD_GEN_AUX_H

gen_aux.cpp

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

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

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

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

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

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

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

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

gen_sentence.cpp

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

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

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

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

  return sentence;
}

Test Result

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

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

Understanding the concept

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

the large brown dog sits wherever it wants

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

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

Recall that this is the input grammar table:

The gen_sentence and gen_aux can give the following output values:

Some Notes To This Example

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

tokens non-empty?

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

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

const string& token

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

string token = tokens.back();

Is token bracketed?

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

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

const Rule& r

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

vector<string>& sentence

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

(Updated) vector<string>& tokens

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

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

Summary

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

Reference