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.

C++ 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 cerr instead 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", "howard123", "jon" }; bool b = hasDuplicates( folks, 5 ); // should return true and not inspect the last three elements... 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 any of the others.

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 find 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" }; bool b = hasDuplicates(people, 25 ); // Bad driver code call // your 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 by that result. The FAQ has a note about string comparisons.

Your task

Here are the functions you must implement:

int locateMaximum( const string array[ ], int n ); Return the index of the largest item found in the array or -1 if n <= 0. For example, for the array people[ 5 ] shown above, locateMaximum( people, 5 ) should return the value 4, corresponding to the index of "tyrion". If there are multiple duplicate maximum values, please return the smallest index that has this maximum value. The maximum value is determined by its dictionary-sorted order which is what < and > use in C++ to determine true and false.

bool hasDuplicates( const string array[ ], int n ); If there is a value that is repeatedly found in the array, return true otherwise false or if n <= 0 return false. For example, for the array people[ 5 ] shown above, hasDuplicates( people, 5 ) should return false. For the array people[ 5 ] shown above, hasDuplicates( people, 0 ) should return false because the empty array indeed has no duplicates either. For the array folks[ 8 ] shown above, hasDuplicates( folks, 8 ) should return true.

int countSs( const string array[ ], int n ); Return the number of 's' or 'S' characters found inside each of the elements of the passed array or if n <= 0 return -1. For example, for the array people[ 5 ] shown above, countSs( people, 5 ) should return 2.

int shiftLeft( string array[ ], int n, int amount, string placeholderToFillEmpties ); Adjust the items found in the array, shifting each value to the left by amount parameter, filling the resulting first amount elements of the array with the placeholder parameter and returning the number of times the placeholder value has been used after all the shifting has been performed. For example, for the array people[5] shown above, shiftLeft( people, 5, 3, "foo" ) should return 3 and adjust the array to have the value { "daenerys", "tyrion", "foo", "foo", "foo" }; If n <= 0, return 0 because no shifting will have been performed at all. If amount exceeds n, return n since all of the original element will have been stomped over by this function.

bool isInDecreasingOrder( const string array[ ], int n ); If every value in the array is smaller than the one that precedes it, return true otherwise false or if n <= 0 return false . For example, for the array people[ 5 ] shown above, isInDecreasingOrder( people, 5 ) should return false. For example, for the array people[ 5 ] shown above, isInDecreasingOrder( people, 2 ) should return true.

bool matchingValuesTogether( const string array[ ], int n ); If all the duplicated values found in the array are located one right after the other, return true otherwise false. If you don't find any duplicated values at all, then return true since you never found any values violating this together principle. If n <=0, return false. For example, for the array people[ 5 ] shown above, matchingValuesTogether( people, 5 ) should return true. For the array folks[ 8 ], matchingValuesTogether( folks, 8 ) should return false because the two "jon" values are not located in the array in contiguously located elements, one right after the other.

int divide( string array[ ], 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. (Yes, there might be numerous correct rearrangements that are valid.) Return the position of the first element that, after the rearrangement, is not < divider, or 0 if there are none.

Programming Guidelines

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 

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 a[6] = { "alpha", "beta", "gamma", "gamma", "beta", "delta" };

assert(hasDuplicates(a, 3 ) == false); assert(hasDuplicates(a, 6 ) == true);

cout << "All tests succeeded" << endl; return( 0 );

 }