Part 1 due: 11:00 PM Saturday, May 3
Part 2 due: 11:00 PM Wednesday, May 7
Go through the following sections of the class zyBook, doing the Participation Activities and Challenge Activities. We will be looking at whether you have ever successfully completed them; it does not matter how many attempts you make before a successful completion (or how many attempts you make after a successful completion if you want to experiment).
Advice: Don't put off doing Part 1, since the sooner you complete Part 1, the more time you'll have for Part 2.
As you gain experience with arrays, you'll discover that many applications do the same kinds of things with them (e.g., find where an item is in an array, or check whether two arrays differ). You'll find that it's helpful to have a library of useful functions that manipulate arrays. (For our purposes now, a library is a collection of functions that developers can call instead of having to write them themselves. For a library to be most useful, the functions in it should be related and organized around a central theme. For example, a screen graphics library might have functions that allow you to draw shapes like lines and circles on the screen, move them around, fill them with color, etc. In this view, the Standard C++ library is really a collection of libraries: a string library, a math library, an input/output library, and much more.)
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 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 to be part of the array, starting from the beginning. For example, in
string people[5] = { "keir", "olaf", "narendra", "claudia", "donald" };
int i = locateOccurrence(people, 3, "donald"); // should return -1 (not found)
even though the array has 5 elements, we're telling the function that only the first 3 have values we're interested in for this call; 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 (and thus
we won't test for) is when the caller of the function says to examine
more items in the array than it actually has. For example, in
this situation, it is impossible for the function
locateOccurrence to detect that the caller is lying by telling the
function that it can safely access more elements of the
people array than that array was declared to have:
string people[5] = { "keir", "olaf", "narendra", "claudia", "donald" };
int i = locateOccurrence(people, 25, "bongbong"); // Bad call of function, but
// your locateOccurrence implementation doesn't have to try to check
// for this, because there is no way it can do so.
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 on the platforms you're likely using, if you see every upper case letter comparing less than every lower case letter, don't be surprised. The FAQ has a note about string comparisons.
Here are the functions you must implement:
int countOccurrences(const string a[], int n, string target);
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
"olaf" to be equal to "OlAf". Here's an example:
string d[9] = {
"giorgia", "donald", "bola", "bola", "jinping", "jinping", "jinping", "bola", "bola"
};
int i = countOccurrences(d, 9, "bola"); // returns 4
int j = countOccurrences(d, 5, "jinping"); // returns 1
int k = countOccurrences(d, 9, "luiz"); // returns 0
int locateOccurrence(const string a[], int n, string target);
target; if there is more than one such string, return the
smallest position number of such a matching string. Return −1 if
there is no such string. As noted above, case matters: Do not consider
"OLaf" to be equal to "oLAf". Here's an example:
string d[9] = {
"giorgia", "donald", "bola", "bola", "jinping", "jinping", "jinping", "bola", "bola"
};
int m = locateOccurrence(d, 9, "jinping"); // returns 4
int p = locateOccurrence(d, 4, "jinping"); // returns -1 (no "jinping" in first 4)
bool locateSequence(const string a[], int n, string target, int& begin, int& end);
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 (instead of −1). Here's an example:
string d[9] = {
"giorgia", "donald", "bola", "bola", "jinping", "jinping", "jinping", "bola", "bola"
};
int b;
int e;
bool b1 = locateSequence(d, 9, "bola", b, e); // returns true and
// sets b to 2 and e to 3
bool b2 = locateSequence(d, 9, "donald", b, e); // returns true and
// sets b to 1 and e to 1
bool b3 = locateSequence(d, 9, "narendra", b, e); // returns false and
// leaves b and e unchanged
int locateMin(const string a[], int n);
string people[5] = { "keir", "olaf", "narendra", "claudia", "donald" };
int q = locateMin(people, 5); // returns 3, since claudia is <= every
// string in the array
int moveToBack(string a[], int n, int pos);
pos by copying all elements after
it one place to the left. Put the value that was thus eliminated into the last
position of the array that the function knows about. Return the original
position of the item that was moved to the end. Here's an example:
string people[5] = { "keir", "olaf", "narendra", "claudia", "donald" };
int r = moveToBack(people, 4, 1); // returns 1
// people now contains: "keir" "narendra" "claudia" "olaf" "donald"
// the function knew about only 4 elements
int moveToFront(string a[], int n, int pos);
pos by copying all elements before
it one place to the right. Put the value 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] = { "keir", "olaf", "narendra", "claudia", "donald" };
int s = moveToFront(people, 5, 2); // returns 2
// people now contains: "narendra" "keir" "olaf" "claudia" "donald"
int locateMismatch(const string a1[], int n1, const string a2[], int n2);
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 whichever value of
n1 and n2 is less than or equal to the other.
Here's an example:
string people[5] = { "keir", "olaf", "narendra", "claudia", "donald" };
string leaders[6] = { "keir", "olaf", "giorgia", "claudia", "donald", "narendra" };
int r = locateMismatch(people, 5, leaders, 6); // returns 2
int s = locateMismatch(people, 2, leaders, 1); // returns 1
int eliminateDuplicates(string a[], int n);
a,
retain only one item of that sequence. Suppose we call the number of all
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] = {
"giorgia", "donald", "bola", "bola", "jinping", "jinping", "jinping", "bola", "bola"
};
int p = eliminateDuplicates(d, 9); // returns 5
// d[0] through d[4] now contain "giorgia" "donald" "bola" "jinping" "bola"
// We no longer care what strings are in d[5] and beyond.
bool contains(const string a1[], int n1, const string a2[], int n2);
n2 elements of a2 appear in
a1, in the same order (though not necessarily consecutively),
then return true. Return false if a1 does not so contain
a2. (Consider a sequence of 0 elements to be contained in
any sequence, even one also with 0 elements.) Return false (instead of
−1) if this function is passed any bad arguments. Here's an example:
string big[10] = { "claudia", "keir", "bola", "jinping", "donald", "bola" };
string little1[10] = { "keir", "jinping", "donald" };
bool u1 = contains(big, 6, little1, 3); // returns true
string little2[10] = { "bola", "keir" };
bool u2 = contains(big, 6, little2, 2); // returns false
string little3[10] = { "keir", "bola", "bola" };
bool u3 = contains(big, 6, little3, 3); // returns true
string little4[10] = { "keir", "keir", "bola" };
bool u4 = contains(big, 6, little4, 3); // returns false
bool u5 = contains(big, 6, little4, 0); // returns true
int meld(const string a1[], int n1, const string a2[], int n2,
string result[], int max);
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] = { "bola", "claudia", "claudia", "jinping", "narendra" };
string y[4] = { "claudia", "giorgia", "keir", "olaf" };
string z[20];
int n = meld(x, 5, y, 4, z, 20); // returns 9
// z has bola claudia claudia claudia giorgia jinping keir narendra olaf
int divide(string a[], int n, string divider);
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 no such elements. Here's an example:
string wl[6] = { "keir", "bola", "narendra", "claudia", "olaf", "donald" };
int x = divide(wl, 6, "jinping"); // returns 3
// wl must now be
// "donald" "bola" "claudia" "olaf" "narendra" "keir"
// or "bola" "claudia" "donald" "keir" "olaf" "narendra"
// or one of several other orderings.
// All elements < "jinping" (i.e., "bola", "claudia", and "donald")
// come before all others
// All elements > "jinping" (i.e., "narendra" "olaf", and "keir")
// come after all others
string wl2[4] = { "donald", "olaf", "bola", "keir" };
int y = divide(wl2, 4, "keir"); // returns 2
// wl2 must now be either
// "donald" "bola" "keir" "olaf"
// or "bola" "donald" "keir" "olaf"
// All elements < "keir" (i.e., "bola" and "donald") come
// before all others.
// All elements > "keir" (i.e., "olaf") come after all others.
For each of the functions moveToBack, moveToFront,
eliminateDuplicates, meld, and divide,
if the function is correctly implemented, you will earn one bonus point for
that function if it does its job without creating any additional array.
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.
Your implementations must not use any global variables whose values may be changed during execution.
Your program must build successfully under both g31 and either Visual C++ or clang++.
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] = { "giorgia", "claudia", "keir" };
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 <iostream>
#include <string>
#include <cassert>
using namespace std;
int main()
{
string h[7] = { "luiz", "olaf", "keir", "bola", "", "claudia", "keir" };
assert(countOccurrences(h, 7, "keir") == 2);
assert(countOccurrences(h, 7, "") == 1);
assert(countOccurrences(h, 7, "giorgia") == 0);
assert(countOccurrences(h, 0, "keir") == 0);
assert(locateOccurrence(h, 7, "keir") == 2);
assert(locateOccurrence(h, 2, "keir") == -1);
int bg;
int en;
assert(locateSequence(h, 7, "bola", bg, en) && bg == 3 && en == 3);
string g[4] = { "luiz", "olaf", "bola", "claudia" };
assert(locateMin(g, 4) == 2);
assert(locateMismatch(h, 4, g, 4) == 2);
assert(contains(h, 7, g, 4));
assert(moveToBack(g, 4, 1) == 1 && g[1] == "bola" && g[3] == "olaf");
string f[4] = { "claudia", "bola", "olaf", "mark" };
assert(moveToFront(f, 4, 2) == 2 && f[0] == "olaf" && f[2] == "bola");
string e[5] = { "claudia", "claudia", "claudia", "olaf", "olaf" };
assert(eliminateDuplicates(e, 5) == 2 && e[1] == "olaf");
string x[4] = { "jinping", "jinping", "narendra", "olaf" };
string y[4] = { "bola", "claudia", "jinping", "keir" };
string z[10];
assert(meld(x, 4, y, 4, z, 10) == 8 && z[5] == "keir");
assert(divide(h, 7, "keir") == 3);
cout << "All tests succeeded" << endl;
}
The reason for the one line of output at the end is to ensure that you can distinguish the situation of all tests succeeding from the case where one test silently crashes the program.
Make sure that if you were to replace your main routine with the one above, your program would build successfully under both g31 and either Visual C++ or clang++. (This means that even if you haven't figured out how to implement some of the required functions, you must still have some kind of implementation for each of them, even if such a stub implementation does nothing more than immediately return, say, 42.) If the program built with that main routine happens to run successfully, you'll probably get a pretty good correctness score.
You won't turn anything in through the CS 31 web site for Part 1; the zyBook system notes your successful completion of the PAs and CAs. For Part 2, turn in a zip file containing these two files and nothing more:
A text file named array.cpp that contains the source code for your C++ program. Your source code should have helpful comments that explain any non-obvious code. If you chose to write additional functions, make sure they are in this file.
How nice! Your report this time doesn't have to contain any design documentation.
By Tuesday, May 7, there will be a link on the class webpage that will enable you to turn in your zip file electronically. Turn in the file by the due time above.