Your assignment is to produce a library that provides functions for many common manipulations of arrays of strings. For example, one function will find where a string occurs in an unordered array of strings. Another will change the order of strings in an array. For each function you must write, this specification will tell you its interface (what parameters it takes, what it returns, and what it must do). It's up to you to decide on the implementation (how it will do it).

The source file you turn in will contain all the functions and a main routine. You can have the main routine do whatever you want, because we will rename it to something harmless, never call it, and append our own main routine to your file. Our main routine will thoroughly test your functions. You'll probably want your main routine to do the same. If you wish, you may write functions in addition to those required here. We will not directly call any such additional functions. If you wish, your implementation of a function required here may call other functions required here.

The program you turn in must build successfully, and during execution, no function (other than main) may read anything from cin or write anything to cout. If you want to print things out for debugging purposes, write to cerrinstead of cout. When we test your program, we will cause everything written to cerr to be discarded instead we will never see that output, so you may leave those debugging output statements in your program if you wish.

All of the functions you must write take at least two parameters: an array of strings, and the number of items the function will consider in the array, starting from the beginning. For example, in

string folks[8] = { "samwell", "jon", "margaery", "daenerys", "tyrion", "sansa", "jaime", "cersei" }; int i = locate(folks, 5, "cersei"); // should return -1 (not found) 

even though the array has 8 elements, only the first 5 had values we were interested in for this call to the function; the function must not examine the others.

Notwithstanding each function's behavior described below, all functions that return an int must return 1 if they are passed any bad arguments (e.g. a negative array size, or a position that would require looking at the contents of an element past the last element we're interested in). Unless otherwise noted, passing 0 to the function as the array size is not itself an error; it merely indicates the function should examine no elements of the array.

The one error your function implementations don't have to handle, because they can't, is when the caller of the function lies and says the array is bigger than it really is. For example, in this situation, the function locate can't possibly know that the caller is lying about the number of interesting items in the array:

string people[5] = { "samwell", "jon", "margaery", "daenerys", "tyrion" }; int i = locate(people, 25, "cersei"); // Bad call of function, but // your locate implementation doesn't have to check for // this, because it can't. 

To make your life easier, whenever this specification talks about strings being equal or about one string being less than or greater than another, the case of letters matters. This means that you can simply use comparison operators like == or < to compare strings. Because of the character collating sequence, all upper case letters come before all lower case letters, so don't be surprised. The FAQ has a note about string comparisons.

Here are the functions you must implement:

int enumerate(const string a[], int n, string target);

Return the number of strings in the array that are equal to target. [Of course, in this and other functions, if n is negative, the paragraph above that starts "Notwithstanding" trumps this by requiring that the function return 1. Also, in the description of this function and the others, when we say "the array", we mean the n elements that the function is aware of.] As noted above, case matters: Do not consider "jon" to be equal to "JoN".

int locate(const string a[], int n, string target);

Return the position of the first string in the array that is equal to target. Return 1 if there is no such string. As noted above, case matters: Do not consider "jOn" to be equal to "Jon".

bool locateSequence(const string a[], int n, string target, int& begin, int& end);

Find the earliest occurrence in a of one or more consecutive strings that are equal to target; set begin to the position of the first occurrence of target, set end to the last occurrence of target in that earliest consecutive sequence, and return true. If n is negative or if no string in a is equal to target, leave begin and end unchanged and return false. Here's an example:

string d[9] = { "jon", "daenerys", "samwell", "samwell", "margaery", "margaery", "margaery", "samwell", "samwell" }; int b; int e; bool b1 = locateSequence(d, 9, "samwell", b, e); // returns true and // sets b to 2 and e to 3 bool b2 = locateSequence(d, 9, "daenerys", b, e); // returns true and // sets b to 1 and e to 1 bool b3 = locateSequence(d, 9, "cersei", b, e); // returns false and // leaves b and e unchanged 

int locationOfMin(const string a[], int n);

Return the position of a string in the array such that that string is <= every string in the array. If there is more than one such string, return the smallest position of such a string. Return 1 if the array has no elements. Here's an example:

string people[5] = { "samwell", "jon", "margaery", "daenerys", "tyrion" }; int j = locationOfMin(people, 5); // returns 3, since daenerys is earliest // in alphabetic order 

int moveToEnd(string a[], int n, int pos);

Eliminate the item at position pos by copying all elements after it one place to the left. Put the item that was thus eliminated into the last position of the array. Return the original position of the item that was moved to the end. Here's an example:

string people[5] = { "samwell", "jon", "margaery", "daenerys", "tyrion" }; int j = moveToEnd(people, 5, 1); // returns 1 // people now contains: "samwell" "margaery" "daenerys" "tyrion" "jon" 

int moveToBeginning(string a[], int n, int pos);

Eliminate the item at position pos by copying all elements before it one place to the right. Put the item that was thus eliminated into the first position of the array. Return the original position of the item that was moved to the beginning. Here's an example:

string people[5] = { "samwell", "jon", "margaery", "daenerys", "tyrion" }; int j = moveToBeginning(people, 5, 2); // returns 2 // people now contains: "margaery" "samwell" "jon" "daenerys" "tyrion" 

int locateDifference(const string a1[], int n1, const string a2[], int n2);

Return the position of the first corresponding elements of a1 and a2 that are not equal. n1 is the number of interesting elements in a1, and n2 is the number of interesting elements in a2. If the arrays are equal up to the point where one or both runs out, return the smaller of n1 and n2. Here's an example:

string cast[5] = { "samwell", "jon", "margaery", "daenerys", "tyrion" }; string roles[4] = { "samwell", "jon", "sansa", "jaime" }; int k = locateDifference(cast, 5, roles, 4); // returns 2 int m = locateDifference(cast, 2, roles, 1); // returns 1 

int eliminateDups(string a[], int n);

For every sequence of consecutive identical items in a, retain only one item of that sequence. Suppose we call the number of retained items r. Then when this functions returns, elements 0 through r-1 of a must contain the retained items (in the same relative order they were in originally), and the remaining elements may have whatever values you want. Return the number of retained items. Here's an example:

string d[9] = { "jon", "daenerys", "samwell", "samwell", "margaery", "margaery", "margaery", "samwell", "samwell" }; int p = eliminateDups(d, 9); // returns 5 // d[0] through d[4] now contain "jon" "daenerys" "samwell" "margaery" "samwell" // We no longer care what strings are in d[5] and beyond. 

bool subsequence(const string a1[], int n1, const string a2[], int n2);

If all n2 elements of a2 appear in a1, in the same order (though not necessarily consecutively), then return true. Return false if a1 does not contain a2 as a subsequence. (Of course, the empty sequence is a subsequence of any sequence.) Return false (instead of 1) if this function is passed any bad arguments. Here's an example:

string big[10] = { "samwell", "jon", "margaery", "daenerys", "tyrion", "margaery" }; string little1[10] = { "jon", "daenerys", "tyrion" }; bool b1 = subsequence(big, 6, little1, 3); // returns true string little2[10] = { "margaery", "jon" }; bool b2 = subsequence(big, 6, little2, 2); // returns false string little3[10] = { "jon", "margaery", "margaery" }; bool b3 = subsequence(big, 6, little3, 3); // returns true string little4[10] = { "jon", "jon", "margaery" }; bool b4 = subsequence(big, 6, little4, 3); // returns false 

int makeMerger(const string a1[], int n1, const string a2[], int n2, string result[], int max);

If a1 has n1 elements in nondecreasing order, and a2 has n2 elements in nondecreasing order, place in result all the elements of a1 and a2, arranged in nondecreasing order, and return the number of elements so placed. Return 1 if the result would have more than max elements or if a1 and/or a2 are not in nondecreasing order. (Note: nondecreasing order means that no item is > the one that follows it.) Here's an example:

string x[5] = { "cersei", "jon", "margaery", "samwell", "sansa" }; string y[4] = { "daenerys", "jon", "jon", "tyrion" }; string z[20]; int n = makeMerger(x, 5, y, 4, z, 20); // returns 9 // z has cersei daenerys jon jon jon margaery samwell sansa tyrion 

int divide(string a[], int n, string divider);

Rearrange the elements of the array so that all the elements whose value is < divider come before all the other elements, and all the elements whose value is > divider come after all the other elements. Return the position of the first element that, after the rearrangement, is not < divider, or n if there are none. Here's an example:

string f[6] = { "cersei", "margaery", "sansa", "daenerys", "tyrion", "jon" }; int r = divide(f, 6, "samwell"); // returns 4 // f might now be // "cersei" "margaery" "jon" "daenerys" "tyrion" "sansa" // or "jon" "daenerys" "margaery" "cersei" "sansa" "tyrion" // or several other orderings. // The first 4 elements are < "samwell"; the last 2 aren't. string g[4] = { "samwell", "margaery", "tyrion", "jon" }; int s = divide(g, 4, "margaery"); // returns 1 // g must now be either // "jon" "margaery" "samwell" "tyrion" // or "jon" "margaery" "tyrion" "samwell" // All elements < "margaery" (i.e., "jon") come before all others. // All elements > "margaery" (i.e., "tyrion" and "samwell") come // after all others. 

Your program must not use any function templates from the algorithms portion of the Standard C++ library. If you don't know what the previous sentence is talking about, you have nothing to worry about. If you do know, and you violate this requirement, you will be required to take an oral examination to test your understanding of the concepts and architecture of the STL.

Your implementations must not use any global variables whose values may be changed during execution.

Your program must build successfully under both Visual C++ and either clang++ or g++.

The correctness of your program must not depend on undefined program behavior. Your program could not, for example, assume anything about t's value in the following, or even whether or not the program crashes:

 int main() { string s[3] = { "samwell", "jon", "tyrion" }; string t = s[3]; // position 3 is out of range  

As with Project 3, a nice way to test your functions is to use the assert facility from the standard library. As an example, here's a very incomplete set of tests for Project 4:

#include  #include  #include  using namespace std; 

int main() { string h[7] = { "samwell", "jon", "margaery", "daenerys", "", "tyrion", "margaery" }; assert(enumerate(h, 7, "margaery") == 2); assert(enumerate(h, 7, "") == 1); assert(enumerate(h, 7, "sansa") == 0); assert(enumerate(h, 0, "margaery") == 0); assert(locate(h, 7, "margaery") == 2); assert(locate(h, 2, "margaery") == -1); int bg; int en; assert(locateSequence(h, 7, "daenerys", bg, en) && bg == 3 && en == 3); string g[4] = { "samwell", "jon", "daenerys", "tyrion" }; assert(locationOfMin(g, 4) == 2); assert(locateDifference(h, 4, g, 4) == 2); assert(subsequence(h, 7, g, 4)); assert(moveToEnd(g, 4, 1) == 1 && g[1] == "daenerys" && g[3] == "jon"); string f[4] = { "daenerys", "tyrion", "margaery", "jon" }; assert(moveToBeginning(f, 4, 2) == 2 && f[0] == "margaery" && f[2] == "tyrion"); string e[5] = { "daenerys", "daenerys", "daenerys", "margaery", "margaery" }; assert(eliminateDups(e, 5) == 2 && e[1] == "margaery"); string x[4] = { "cersei", "jon", "jon", "sansa" }; string y[4] = { "daenerys", "jon", "margaery", "tyrion" }; string z[10]; assert(makeMerger(x, 4, y, 4, z, 10) == 8 && z[5] == "margaery"); assert(divide(h, 7, "margaery") == 3); cout << "All tests succeeded" << endl; }