The following is a declaration of a function that takes a string and returns true if a particular property of that string is true, and false otherwise. (Such a function is called a predicate.)

 bool somePredicate(string s); 

Here is an example of an implementation of the predicate s is empty:

 bool somePredicate(string s) { return s.empty(); } 

Here is an example of an implementation of the predicate s contains exactly 10 digits:

 bool somePredicate(string s) { int nDigits = 0; for (int k = 0; k != s.size(); k++) { if (isdigit(s[k])) nDigits++; } return nDigits == 10; } 

Here are five functions, with descriptions of what they are supposed to do. They are incorrectly implemented. The first four take an array of strings and the number of strings to examine in the array; the last takes two arrays of strings and the number of strings to examine in each:

 // Return false if the somePredicate function returns false for at // least one of the array elements; return true otherwise. bool allTrue(const string a[], int n) { return false; // This is not always correct. } // Return the number of elements in the array for which the // somePredicate function returns false. int countFalse(const string a[], int n) { return -999; // This is incorrect. } // Return the subscript of the first element in the array for which // the somePredicate function returns false. If there is no such // element, return -1. int firstFalse(const string a[], int n) { return -999; // This is incorrect. } // Return the subscript of the least string in the array (i.e., // the smallest subscript m such that a[m] <= a[k] for all // k from 0 to n-1). If the array has no elements to examine, // return -1. int indexOfLeast(const string a[], int n) { return -999; // This is incorrect. } // If all n2 elements of a2 appear in the n1 element array a1, in // the same order (though not necessarily consecutively), then // return true; otherwise (i.e., if the array a1 does not include // a2 as a not-necessarily-contiguous subsequence), return false. // (Of course, if a2 is empty (i.e., n2 is 0), return true.) // For example, if a1 is the 7 element array // "stan" "kyle" "cartman" "kenny" "kyle" "cartman" "butters" // then the function should return true if a2 is // "kyle" "kenny" "butters" // or // "kyle" "cartman" "cartman" // and it should return false if a2 is // "kyle" "butters" "kenny" // or // "stan" "kenny" "kenny" bool includes(const string a1[], int n1, const string a2[], int n2) { return false; // This is not always correct. } 

Your implementations of those first three functions must call the function named somePredicate where appropriate instead of hardcoding a particular expression like a[k].empty() or a[k].size() == 42. (When you test your code, we don't care what predicate you have the function named somePredicate implement: s.empty() or s.size() == 42 or whatever, is fine.)

Replace the incorrect implementations of these functions with correct ones that use recursion in a useful way; your solution must not use the keywords while, for, or goto. You must not use global variables or variables declared with the keyword static, and you must not modify the function parameter lists. You must not use any references or pointers as parameters except for the parameters representing arrays. (Remember that a function parameter x declared T x[] for any type T means exactly the same thing as if it had been declared T* x.) If any of the parameters n, n1, or n2 is negative, act as if it were zero.

Here is an example of an implementation of allTrue that does not satisfy these requirements because it doesn't use recursion and it uses the keyword for:

 bool allTrue(const string a[], int n) { for (int k = 0; k < n; k++) { if ( ! somePredicate(a[k])) return false; } return true; } 

You will not receive full credit if the allTrue, countFalse, or firstFalse functions cause each value somePredicate returns to be examined more than once. Consider all operations that a function performs that compares two strings (e.g. <=, ==, etc.). You will not receive full credit if for nonnegative n, the indexOfLeast function causes operations like these to be performed more than n times, or the includes function causes them to be performed more than n1 times. For example, this non-recursive (and thus unacceptable for this problem) implementation of indexOfLeast performs a <= comparison of two strings many, many more than n times, which is also unacceptable:

 int indexOfLeast(const string a[], int n) { for (int k1 = 0; k1 < n; k1++) { int k2; for (k2 = 0; k2 < n && a[k1] <= a[k2]; k2++) ; if (k2 == n) return k1; } return -1; } 

Each of these functions can be implemented in a way that meets the spec without calling any of the other four functions. (If you implement a function so that it does call one of the other functions, then it will probably not meet the limit stated in the previous paragraph.)

For this part of the homework, you will turn in one file named linear.cpp that contains the five functions and nothing more: no #include directives, no using namespace std;, no implementation of somePredicate and no main routine. (Our test framework will precede the functions with appropriate #include directives and using statement and our own implementation of a function named somePredicate that takes a string and returns a bool.)