C++ programming

Summary: searching text files for (key, value) pairs, e.g. movies and their total revenue.

Google collects all sorts of interesting data: what words appear most frequently in searches? What web sites are most commonly searched using Alexa? What are the most popular baby names? For example, the data file "words-by-freq.txt" ranks the English words used most commonly in searches. Here's the start of the file:

5627187200 the

3395006400 of

2994418400 and

2595609600 to

.

.

.

# #

The words are listed by rank, so "the" is the most frequently searched word with a frequency of "5627187200". The 2nd most frequently searched word is "of", with a frequency of "3395006400", and so on. The file ends with # and #.

The first input is the filename, and the remaining inputs are keys to search for. The keys are followed by #, which stops the program. Here's the correct output given this input sequence:

**Starting**

File: 'words-by-freq.txt'

# of entries: 8000

Top-ranked: (the, 5627187200)

>>Found key: headache

Value= 633224

Rank= 8000

>>Found key: the

Value= 5627187200

Rank= 1

>>Not found: C++

>>Found key: meanwhile

Value= 1692630

Rank= 4152

**End**

The file contains 8000 (key, value) pairs, and the top-ranked (first) pair is (the, 5627187200). The program was then asked to search for "headache", then "the", then "C++", and finally "meanwhile". If the key was found, the corresponding value and rank was output.

The tests cases involve 3 input files: "alexa-by-freq.txt", "baby-names-by-freq.txt", and "words-by-freq.txt"

Here are the functions you need to write, which are declared in "search.cpp". Note that the functions are "returning" values via additional reference parameters. You can read more about reference parameters in section 6.11, but in short all you need to know is that inside the function you need to assign values to the reference parameters, and the value you assign is the value that is "returned". In the case of GetFileStats, you need to assign to firstKey and firstValue. In the case of SearchForKey, you need to assign to value and rank.

/*search.cpp*/

#include

#include

#include

#include

using namespace std;

//

// GetFileStats

//

// Returns the # of (key, value) pairs in the given file. Also returns the first (key, value)

// pair via the parameters firstKey and firstValue.

//

// NOTE: it is assumed the file contains at least one (key, value) pair, in this format:

//

// value key

// value key

// value key

// # #

//

// where value and key are one word strings (or numbers that will be input as strings).

// If the file cannot be opened, the program will be exited.

//

int GetFileStats(string filename, string& firstKey, string& firstValue)

{

//

// Initialize return value / parameters:

//

firstKey = "?";

firstValue = "?";

int N = 0;

//

// TODO: open and read the (key, value) pairs from the file. The goal is

// to simply count how many pairs there are and return this value N. Also,

// we need to return the first (key, value) pair via the firstKey and

// firstValue parameters; just assign to the parameters to "return" the

// values. Don't forget to close the file when you're done.

//

return N;

}

//

// SearchForKey

//

// Opens the given file, searches for the given key, and if found, returns true; if the

// key is not found then false is returned.

//

// If the key is found, the value will be returned via the "value" parameter; likewise

// the rank will be returned via the "rank" parameter. The rank is simply the line #

// where the (key, value) pair was found: 1 for first line, 2 for second line, etc.

// If the key is not found, value and rank should be ignored.

//

// NOTE: it is assumed the file contains at least one (key, value) pair, in this format:

//

// value key

// value key

// value key

// # #

//

// where value and key are one word strings (or numbers that will be input as strings).

// If the file cannot be opened, the program will be exited.

//

bool SearchForKey(string filename, string key, string& value, int& rank)

{

//

// initialize return value / parameters:

//

value = "<>";

rank = 0;

bool found = false; // not found:

//

// TODO: search for the key, and if found, we want to return the associated value.

// But we also need to return the "rank" via the rank parameter; the rank is the

// line number where the (key, value) appears: 1 for first line, 2 for second

// line, and so on. Finally, return true if key was found, false if not.

//

// Don't forget to close the file when you're done.

//

return found;

}

This is the main.ccp you do not edit.

/*main.cpp*/

#include

#include

#include

#include

using namespace std;

//

// function declarations:

//

int GetFileStats(string filename, string& firstKey, string& firstValue);

bool SearchForKey(string filename, string key, string& value, int& rank);

int main()

{

string filename;

cin >> filename;

cout << "**Starting**" << endl;

cout << "File: '" << filename << "'" << endl;

cout << endl;

//

// First, let's get some statistics about the data file:

//

int N, rank;

string key, value;

bool found;

N = GetFileStats(filename, key, value);

cout << "# of entries: " << N << endl;

cout << "Top-ranked: (" << key << ", " << value << ")" << endl;

cout << endl;

//

// Now let's input keys from the keyboard and look for them in the file:

//

cin >> key;

while (key != "#")

{

found = SearchForKey(filename, key, value, rank);

if (found == true)

{

cout << ">>Found key: " << key << endl;

cout << " Value= " << value << endl;

cout << " Rank= " << rank << endl;

}

else // not found:

{

cout << ">>Not found: " << key << endl;

}

cin >> key;

}

cout << endl;

cout << "**End**" << endl;

return 0;

}