CSE250 Assignment 7 Answer Key Fall 2011 (1)~Translate the following code into iterator notation. One important point is that the "string" class has a constructor that takes two iterators denoting a substring of another string as arguments. (18 pts.) /** True if switching 2 adjacent unequal letters in x leaves y. CODE SKETCH---DOES NOT COMPILE (owing to need for const_iterator etc.) */ bool transpose(const string& x, const string& y) { if (x.length() != y.length()) { return false; } //x.size() is more general // else //int xlenm1 = x.length() - 1; string::iterator xlast = --(x.end()) //x.rbegin() should work, does it? string::iterator xitr = x.begin(); //really string::const_iterator xitr string::iterator yitr = y.begin(); //LOOP INV: keeps lockstep with xitr while (xitr != xlast) { //last item can't be first of two //for (int i = 0; i < xlenm1; i++) { //if (x[i] != y[i]) { //mismatch, so moment-of-truth is now if ((*xitr) != (*yitr)) { /*--------------------------------------------------- if (x[i] == y[i+1] && x[i+1] == y[i] && x[i] != x[i+1] && x.substr(i+2) == y.substr(i+2)) { return true; } else { return false; } ----------------------------------------------------*/ string::iterator xitrp1 = xitr+1; //needs RandomAccessIterator string::iterator yitrp1 = yitr+1; return ((*xitr) == (*yitrp1) && (*xitrp1) == (*yitr) && (*xitr) != (*yitr) //forces letters to be unequal && string(xitr+2,x.end()) == string(yitr+2, y.end()) ); } //else ++xitr; ++yitr; //easy to forget to do this! } //control here means x == y return false; } As written the code uses a RandomAccessIterator, so the compiler will give one. We also used the "--" operation to define xlast; using x.rbegin() instead would also have required a BidirectionalIterator. But in fact the code *can* be written to use a ForwardIterator only. The following is less clear and a bit less efficient, but you would have to use it if, say, you were using a singly linked list to manage gene sequencing rather than vector on account of all the splicing going on, and were studying mutations that transpose two genes. string::iterator xitr = x.begin(); //really string::const_iterator xitr string::iterator yitr = y.begin(); //LOOP INV: keeps lockstep with xitr string::iterator xpre = xitr++; //INV: xitr always 1 ahead of xpre string::iterator ypre = yitr++; //INV: ditto for ypre and yitr while (xitr != x.end()) { //last item can't be first of two if ((*xpre) != (*ypre)) { string::iterator xprep1 = xitr++; //doable by ForwardIterator string::iterator yprep1 = yitr++; //now ypre,yprep1,yitr in a row return ((*xpre) == (*yprep1) && (*xprep1) == (*ypre) && (*xpre) != (*ypre) //forces letters to be unequal && string(xitr,x.end()) == string(yitr, y.end()) ); //note that ^^^^ and yitr changed their meanings from prev code } xpre = xitr++; //advances both iterators while maintaining INVs. ypre = yitr++; //ditto } //control here means x == y return false; (2)~Write code to find the index $j$ into an array "cont" that maximizes the value f(cont[j]) for some given numerical function f. If there are multiple such $j$, return the least one. Then translate your code into iterator notation, returning an iterator pointing to that element. What is the least category of iterator needed for this task? (12 + 9 = 21 pts.) [Note that this is an abstraction of the Assignment~6 task of finding the greatest number of words in a phrase, except now you are asked to identify a phrase that gives it. For 9 pts.\ extra credit, write this code as a "higher-order function" taking f as a parameter.] Show answer with indexing: size_t fmax(const Container& cont){ size_t i = 0; size_t j = 0; //INV: j indexes max f(a) for elements a seen thus far. while (i != cont.size()) { if f(cont[j]) < f(cont[i]) { j = i; } i++; } return j; } Container::iterator fmax(const Container& cont){ //OK Container::iterator iitr; Container::iterator jitr = cont.begin(); //INV: max value seen so far while(iitr != cont.end()) { if (f(*jitr) < f(*iitr)) { //REQ: Arg type of Container has operator< jitr = iitr; } ++iitr; } return jitr; } -----------------Technote on extra credit------------------------------ With the function f as a variable rather than a given, this should have a template at least for the argument type of the container, and customarily for the container itself and the function f to boot! template Container::iterator fmax(const Container& cont, double f(ARG a)) { [iterator code as above] } Fully generic, even passing in function via template not parameter! I prefer keeping ARG, but you could get rid of it. template //REQ: FUNC()(a) computes f(a) CONT::iterator fmax(const CONT& cont) { CONT::iterator iitr; CONT::iterator jitr = cont.begin(); //INV: max value seen so far while(iitr != cont.end()) { if (FUNC()(*jitr) < FUNC()(*iitr)) { //REQ: ARG type of Container has operator< jitr = iitr; } ++iitr; } return jitr; } (3)~Write iterator code to merge two containers "cont1" and "cont2", creating a third container "cont3". Your "REQ" is that both "cont1" and "cont2" are sorted according to a "lessThan" method in non-decreasing order, and this must be an "ENS" for "cont3". A particular case of what this means is that for any iterator "it" into "cont1" that is in a valid position (i.e., pointing to a real element not a dummy node, which entails that "cont1" is nonempty), the following is true: (*(cont.begin())).lessThan(*it) || (*(cont.begin())) == (*it) Here we are assuming that the client type "I" (same as "Item_Type" in the text) has a value-equality operator that together with "lessThan" obeys trichotomy. Note also that we are allowing the container to have multiple copies of items that compare equal (later we will say that their /keys/ compare equal), though by the sortedness requirement, all such elements must be consecutive within any of the sorted containers. Again say what is the least category you need: ForwardIterator? BidirectionalIterator? RandomAccessIterator? Your code should have the header void merge(const Container& cont1, const Container& cont2, Container& cont3) and can assume that the call-by-reference parameter "cont3" has methods like "push_back" that you need. (21 points) Answer (OK, many people got the need for const_iterator so I'll use it): /** REQ: cont1 and cont2 are sorted in non-decreasing order. REQ: OK to require that cont3 be initially empty. ENS: cont3 includes the elements of cont1 and cont2 sorted in nondec. order INV: any and all elements of cont3 are <= both *itr1 and *itr2. (If "cont3" is initially nonempty but INV is true even for the begin iterators---translation: if every element of cont3 is <= every element of cont1 and cont2---then it is OK to begin thusly with cont3 nonempty.) Does not destroy inputs---copies their items instead. */ void merge(const Container& cont1, const Container& cont2, Container& cont3) { Container::const_iterator itr1 = cont1.begin(); Container::const_iterator itr2 = cont2.begin(); while (itr1 != cont1.end() && itr2 != cont2.end()) { if ((*itr1).lessThan(*itr2)) { cont3.push_back(*itr1++); //or cont3.insert(*itr1++,cont3.end()); } else { cont3.push_back(*itr2++); //note use of walk-and-chew-gum idiom. } } //control here means one of the iterators has touched the end, so now //we just append the rest of the other container to the output. //[With a linked list we could "splice" this in one go, but with a general //container we still have to append the items one-at-a-time.] if (itr1 == cont1.end()) { while (itr2 != cont2.end()) { cont3.push_back(*itr2++); } } else { while (itr1 != cont1.end()) { cont3.push_back(*itr1++); } } } A ForwardIterator is enough! The gist is that MergeSort is an algorithm than can be performed well even with linked lists. \bigskip (4)~Write iterator code to perform binary search on a nonempty container "cont" sorted in non-descending order (like the last problem). Use iterators "right" and "left", and obey the following header and INV: /**Return iterator itr to first element such that !((*itr).lessThan(item)), end() if none. */ iterator binsearch(const I& item) { ... } //INV: *left is <= item is < *right (or right==end()) Again, do you need a random-access iterator? (24 pts., for 84 total on the set) Answer (assuming this is in code where "cont" is also visible---you could add "cont" as a parameter or suppose this is a method of the container class): /**Return iterator itr to first element such that !((*itr).lessThan(item)), end() if none. INV: *left is <= item is < *right (or right==end()) */ iterator binsearch(const I& item) { iterator left = begin(); //or Container::iterator = cont.begin(); if (left == end() || item.lessThan(*itr)) { return left; //correct in both cases //else---we have *left <= item. iterator right = end(); //so INV holds, and also right > left while (right != left+1) { iterator mid = (right + left)/2; //legal with RandomAccessIterator if (item.lessThan(*mid)) { right = mid; //INV still holds since lessThan is strict } else { left = mid; } } //no infinite loop since right >= left+2 ==> mid strictly in-between. if (item.lessThan(*left)) { return left; } else { return end(); //item is > maximum } } (end of key---quiz answers were already e-mailed)