Quiz #1: Using the ICS46 Template Library ICS-46 Fall 2019 When working on this quiz, recall the rules stated on the Academic Integrity statement that you signed. You can download/unzip the q1helper project folder (available for Friday, on the Weekly Schedule link) in which to write/test/debug your code. Submit your completed q1solution.hpp file online by Thursday, 11:30pm. I will post my solutions to EEE reachable via the Solutions link on Friday morning. Use the Array implementations from courselib for all the Data Types specified in the problem statements below. IMPORTANT: Submit code that compiles correctly under Clang. If any function bodies do not compile, replace them with code that compiles, even if it does nothing/is wrong. We cannot run GoogleTests on non-compiling code; you must meet with a TA/Reader to have non-compiling code graded in person, and we will deduct points. 1. (4 pts) Define the following two templated functions: (a) Define the templated void function swap, which takes an ArrayMap and two keys, and swaps the values associated with the keys in the ArrayMap. Assume (don”t check) that both keys are always contained in the ArrayMap. You may not use std::swap: it trivializes the problem. Grading: 1 pt. correctness, 1 pt. for a one-statement solution. Hint: Look at all the operators and methods for ArrayMap. (b) Define the templated void function values_set_to_queue, which takes a first ArrayMap whose values are ArraySets and a second empty ArrayMap whose values are ArrayQueues and fills in the second ArrayMap with the same key/value mappings as the first (leaving the first ArrayMap intact). The second ArrayMap will consist of every key in the first ArrayMap, but associated with it is an ArrayQueue of all the same elements that are in the ArraySet it is associated with in the first ArrayMap. Grading: 1 pt. correctness, 1 pt. for a two-statement solution. 2. (3 pts) Define a follows function that takes one argument: a std:string that is one word; it returns a map whose keys are every letter in the word that is followed by another letter, and whose values are a set of the letters that directly follows that letter in the word. For example, calling follows(“bookkeeper”) returns the result map[b->set[o],o->set[o,k],k->set[k,e],e->set[e,p,r],p->set[e]] Of course, the map/set values may appear in any order when printed. Problems 3-4: Suppose that political parties wanted to store a database containing basic information about voters by their zipcode. We will represent this information in a map whose keys specify a zipcode (int). Associated with each zipcode key is another map whose keys specify a party (a political party, a str); associated with each party key is the number of registered voters of that party in the zipcode (int that is non-negative). For example. a simple database might be as follows (note: the keys could appear in any order!) db = map[1->map[d->15,i->15,r->15], 2->map[d->12,r->8], 3->map[d->10,i->30,l->20,r->22], 4->map[d->30,l->20,r->30], 5->map[i->15,l->15,r->15] ] I have printed this map in an easy to read form. C++ prints maps on one line, and can print their key/values in any order, because maps are not ordered. Assume that any distinct str can represent a political party: in the example above, “d” could be democrat, “i” could be independent, “l” could be libertarian, “r” could be republican (and there might be others). 3. (14 pts) Define the following three functions that each take a database in the form above as an argument. Each returns a queue of values in a certain order: use a priority queue to put these values in the right order and then create a queue with the values in that order. You may not use vectors/sorting in these functions. You might have to construct other temporary data structures to solve the problems. My solutions were at or under a dozen lines each (not a requirement, but think twice if your solutions are a lot longer), some using typedefs. (a) The by_diversity function returns a queue of pairs (whose first values are zipcodes and whose second values are different number of parties in that zipcode) whose values are decreasing by the number of parties; if two zipcodes have the same number of parties, these tuples should appear in increasing numerical order by zipcode. For example, if db is the database above, calling by_diversity(db) would return queue[pair[3,4],pair[1,3],pair[4,3],pair[5,3],pair[2,2]]:rear. (b) The by_size function returns a queue of zipcodes whose values are decreasing by the number of registered voters in that zipcode; if the number of registered voters in two different zipcodes are the same, these zipcodes should appear in increasing numerical order by zipcode. For example, if db is the database above, calling by_size(db) would return the queue[3,4,1,5,2]:rear: zipcode 3 has 82 registered votes, zipcode 4 has 80, zipcode 1 has 45, zipcode 5 has 45, and zipcode 2 has 20. (c) The by_party function returns a queue of parties whose values are decreasing by the number of registered voters in that party, summed over all zipcodes; if the number of registered voters in two different parties are the same, these parties should appear in increasing alphabetical order. For example, if db is the database above, calling by_size(db) would return queue[“r”,”d”,”i”,”l”]:rear: there are 90 registered republicans, 67 registered democrats, 60 registered independents, and 55 registered liberals. 4. (4 pts) Define the registrations_by_state function with two arguments: (a) a database in the form of the one above and (b) a map whose keys are str (states) each associated with a set of int (zipcodes in that state). This function returns an outer map associating a str (state) with an inner map that associates a str (party) with an int (the number of registered voters for that party for that state, over all zipcodes). For example, calling party_view using the database above and map[CA->set[1,3],WA->set[2,4,5]]as the zipcode map, would return the map map[CA->map[d->25,i->45,r->37,l->20],WA->map[d->42,r->53,l->35,i->15]] If a state in the map has no zipcodes in the database, it should not appear in the returned map. Hint: I wrote only 6 lines of code (not a requirement, but think twice if your solution is a lot longer) consisting of a triply-nested for loop to build a map that contains all the required information.
