Assignment 2 Double Trouble

CS 32 Project 2
CS 32 Programming Assignment 2 Double Trouble
Homework 1 gave you extensive experience with the Map type using both arrays and dynamicallyallocated arrays. In this project, you will re-write the implementation of the Map type to employ a doubly-linked list rather than an array. You must not use arrays. You will also implement a couple of algorithms that operate on maps. Implement Map yet again Consider the Map interface from problem 2 of Homework 1: typedefTheTypeOfTheKeysGoesHereKeyType; typedefTheTypeOfTheValuesGoesHereValueType; classMap { public: Map(); boolempty()const; intsize()const; boolinsert(constKeyType&key,constValueType&value); boolupdate(constKeyType&key,constValueType&value); boolinsertOrUpdate(constKeyType&key,constValueType&value); boolerase(constKeyType&key); boolcontains(constKeyType&key)const; boolget(constKeyType&key,ValueType&value)const; boolget(inti,KeyType&key,ValueType&value)const; voidswap(Map&other); }; In problem 3 of Homework 1, you implemented this interface using an array. For this project, implement this Map interface using a doubly-linked list. (You must not use the listclass template from the C++ library.) For the array implementation of problem 3 of Homework 1, since you declared no destructor, copy constructor, or assignment operator, the compiler wrote them for you, and they did the right thing. For this linked list implementation, if you let the compiler write the destructor, copy constructor, and assignment operator, they will do the wrong thing, so you will have to declare and implement these public member functions as well: Destructor When a Map is destroyed, the nodes in the linked list must be deallocated. Copy constructor When a brand new Map is created as a copy of an existing Map, enough new nodes must be allocated to hold a duplicate of the original list. https://www.coursehero.com/file/13887121/CS-32-Project-2-Winter-2016/ Assignment operator This study resource was shared via CourseHero.com 3/12/2016 CS 32 Project 2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Projects/2/spec.html 2/7 When an existing Map (the left-hand side) is assigned the value of another Map (the righthand side), the result must be that the left-hand side object is a duplicate of the right-hand side object, with no memory leak of list nodes (i.e. no list node from the old value of the lefthand side should be still allocated yet inaccessible). Notice that there is now no a priori limit on the maximum number of key/value pairs in the Map (so insertOrUpdateshould always return true). Also, as in Homework 1, if a Map has a size of n, then the values of the first parameter to the three-parameter form of getfor which that function retrieves a key and a value and returns true are 0, 1, 2, ..., n-1; for other values, it returns false without setting its second and third parameters. Another requirement is that as in Problem 5 of Homework 1, the number of statement executions when swapping two maps must be the same no matter how many key/value pairs are in the maps. Implement some map algorithms Using only the public interface of Map, implement the following two functions. (Notice that they are non-member functions; they are not members of Map or any other class.) boolcombine(constMap&m1,constMap&m2,Map&result); When this function returns, resultmust consist of pairs determined by these rules: If a key appears in exactly one of m1and m2, then resultmust contain a pair consisting of that key and its corresponding value. If a key appears in both m1and m2, with the same corresponding value in both, then resultmust contain a pair with that key and value. When this function returns, resultmust contain no pairs other than those required by these rules. (You must not assume resultis empty when it is passed in to this function; it might not be.) If there exists a key that appears in both m1and m2, but with different corresponding values, then this function returns false; if there is no key like this, the function returns true. Even if the function returns false, resultmust be constituted as defined by the above rules. For example, suppose a Map maps strings to doubles. If m1consists of the three pairs (in any order) "Fred" 123 "Ethel" 456 "Lucy" 789 and m2consists of (in any order) "Lucy" 789 "Ricky" 321 then no matter what value it had before, resultmust end up as a map consisting of (in any order) "Fred" 123 "Ricky" 321 "Lucy" 789 "Ethel" 456 and combinemust return true. If instead, m1were as before, and m2consisted of "Lucy" 654 "Ricky" 321 https://www.coursehero.com/file/13887121/CS-32-Project-2-Winter-2016/ This study resource was shared via CourseHero.com 3/12/2016 CS 32 Project 2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Projects/2/spec.html 3/7 then no matter what value it had before, resultmust end up as a map consisting of (in any order) "Fred" 123 "Ricky" 321 "Ethel" 456 and combinemust return false. voidsubtract(constMap&m1,constMap&m2,Map&result); When this function returns, resultmust contain a copy of all the pairs in m1whose keys don't appear in m2; it must not contain any other pairs. (You must not assume resultis empty when it is passed in to this function; it may not be.) For example, if m1consists of the three pairs (in any order) "Fred" 123 "Ethel" 456 "Lucy" 789 and m2consists of (in any order) "Lucy" 789 "Ricky" 321 "Ethel" 654 then no matter what value it had before, resultmust end up as a map consisting of "Fred" 123 If English is not your native language, make extra sure you spell the name of this function correctly: it's subtract, not substract. Be sure these functions behave correctly in the face of aliasing: What if m1and resultrefer to the same Map, for example? Other Requirements Regardless of how much work you put into the assignment, your program will receive a zero for correctness if you violate these requirements: Your class definition, declarations for the two required non-member functions, and the implementations of any functions you choose to inline must be in a file named Map.h, which must have appropriate include guards. The implementations of the functions you declared in Map.hthat you did not inline must be in a file named Map.cpp. Neither of those files may have a main routine (unless it's commented out). You may use a separate file for the main routine to test your Map class; you won't turn in that separate file. Except to add a destructor, copy constructor, assignment operator, and dumpfunction (described below), you must not add functions to, delete functions from, or change the public interface of the Map class. You must not declare any additional struct/class outside the Map class, and you must not declare any public struct/class inside the Map class. You may add whatever private data members and private member functions you like, and you may declare private structs/classes inside the Map class if you like. The source files you submit for this project must not contain the word friendor the character [(open square bracket). You must not use any global variables whose values may be changed during execution. If you wish, you may add a public member function with the signature voiddump()const. The intent of this function is that for your own testing purposes, you can call it to print https://www.coursehero.com/file/13887121/CS-32-Project-2-Winter-2016/ This study resource was shared via CourseHero.com 3/12/2016 CS 32 Project 2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Projects/2/spec.html 4/7 information about the map; we will never call it. You do not have to add this function if you don't want to, but if you do add it, it must not make any changes to the map; if we were to replace your implementation of this function with one that simply returned immediately, your code must still work correctly. The dumpfunction must not write to cout, but it's allowed to write to cerr. Map.cppmust not contain the word stringor double. (Map.hmay contain them only in the typedef statements, and must contain #includeif a typedef statement contains the word string.) Your code must build successfully (under both Visual C++ and either clang++ or g++) if linked with a file that contains a main routine. You must have an implementation for every member function of Map, as well as the nonmember functions combineand subtract. Even if you can't get a function implemented correctly, it must have an implementation that at least builds successfully. For example, if you don't have time to correctly implement Map::eraseor subtract, say, here are implementations that meet this requirement in that they at least build successfully: boolMap::erase(constKeyType&value) { returnfalse; //notcorrect,butatleastthiscompiles } voidsubtract(constMap&m1,constMap&m2,Map&result) { //doesnothing;notcorrect,butatleastthiscompiles } You've probably met this requirement if the following file compiles and links with your code. (This uses magic beyond the scope of CS 32.) #include"Map.h" #include #defineCHECKTYPE(f,t){autop=(t)(f);(void)p;} static_assert(std::is_default_constructible::value, "Mapmustbedefault-constructible."); static_assert(std::is_copy_constructible::value, "Mapmustbecopy-constructible."); voidThisFunctionWillNeverBeCalled() { CHECKTYPE(&Map::operator=, Map&(Map::*)(constMap&)); CHECKTYPE(&Map::empty, bool(Map::*)()const); CHECKTYPE(&Map::size, int (Map::*)()const); CHECKTYPE(&Map::insert, bool(Map::*)(constKeyType&,constValueType&)); CHECKTYPE(&Map::update, bool(Map::*)(constKeyType&,constValueType&)); CHECKTYPE(&Map::insertOrUpdate,bool(Map::*)(constKeyType&,constValueType&)); CHECKTYPE(&Map::erase, bool(Map::*)(constKeyType&)); https://www.coursehero.com/file/13887121/CS-32-Project-2-Winter-2016/ This study resource was shared via CourseHero.com 3/12/2016 CS 32 Project 2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Projects/2/spec.html 5/7 CHECKTYPE(&Map::contains, bool(Map::*)(constKeyType&)const); CHECKTYPE(&Map::get, bool(Map::*)(constKeyType&,ValueType&)const); CHECKTYPE(&Map::get, bool(Map::*)(int,KeyType&,ValueType&)const); CHECKTYPE(&Map::swap, void(Map::*)(Map&)); CHECKTYPE(combine, bool(*)(constMap&,constMap&,Map&)); CHECKTYPE(subtract,void(*)(constMap&,constMap&,Map&)); } intmain() {} If you add #includeto Map.h, have Map's typedefs define KeyTypeas std::string and ValueTypeas double, and link your code to a file containing #include"Map.h" #include #include #include usingnamespacestd; voidtest() { Mapm; assert(m.insert("Fred",123)); assert(m.insert("Ethel",456)); assert(m.size()==2); doubled=42; assert(m.get("Fred",d) && d==123); d=42; strings1; assert(m.get(0,s1,d) && ((s1=="Fred" && d==123) || (s1=="Ethel" && d==456))); strings2; assert(m.get(1,s2,d) && s1!=s2 && ((s2=="Fred" && d==123) || (s2=="Ethel" && d==456))); } intmain() { test(); cout<<"Passedalltests"<<endl; } the linking must succeed. When the resulting executable is run, it must write Passedall teststo coutand nothing else to cout. If we successfully do the above, then make no changes to Map.hother than to change the typedefs for Map so that KeyTypespecifies intand ValueTypespecifies std::string, recompile Map.cpp, and link it to a file containing https://www.coursehero.com/file/13887121/CS-32-Project-2-Winter-2016/ This study resource was shared via CourseHero.com 3/12/2016 CS 32 Project 2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Projects/2/spec.html 6/7 #include"Map.h" #include #include #include usingnamespacestd; voidtest() { Mapm; assert(m.insert(123,"Fred")); assert(m.insert(456,"Ethel")); assert(m.size()==2); strings; assert(m.get(123,s) && s=="Fred"); s=""; inti1; assert(m.get(0,i1,s) && ((i1==123 && s=="Fred") || (i1==456 && s=="Ethel"))); inti2; assert(m.get(1,i2,s) && i1!=i2 && ((i2==123 && s=="Fred") || (i2==456 && s=="Ethel"))); } intmain() { test(); cout<<"Passedalltests"<<endl; } the linking must succeed. When the resulting executable is run, it must write Passedall teststo coutand nothing else to cout. During execution, if a client performs actions whose behavior is defined by this spec, your program must not perform any undefined actions, such as dereferencing a null or uninitialized pointer. Your code in Map.hand Map.cppmust not read anything from cinand must not write anything whatsoever to cout. If you want to print things out for debugging purposes, write to cerrinstead of cout. cerris the standard error destination; items written to it by default go to the screen. When we test your program, we will cause everything written to cerrto be discarded instead — we will never see that output, so you may leave those debugging output statements in your program if you wish. Turn it in By Monday, January 25, there will be a link on the class webpage that will enable you to turn in your source files and report. You will turn in a zip file containing these three files: Map.h. When you turn in this file, the typedefs must specify std::stringas the KeyTypeand doubleas the ValueType. https://www.coursehero.com/file/13887121/CS-32-Project-2-Winter-2016/ This study resource was shared via CourseHero.com 3/12/2016 CS 32 Project 2, Winter 2016 http://web.cs.ucla.edu/classes/winter16/cs32/Projects/2/spec.html 7/7 Map.cpp. Function implementations should be appropriately commented to guide a reader of the code. report.docor report.docx(in Microsoft Word format) or report.txt(an ordinary text file) that contains: a description of the design of your doubly-linked list implementation. (A couple of sentences will probably suffice, perhaps with a picture of a typical Map and an empty Map. Is the list circular? Does it have a dummy node? What's in your list nodes? Are they in any particular order?) pseudocode for non-trivial algorithms (e.g., Map::eraseand subtract). a list of test cases that would thoroughly test the functions. Be sure to indicate the purpose of the tests. For example, here's the beginning of a presentation in the form of code: The tests were performed on a map from strings to doubles //defaultconstructor Mapm; //Foranemptymap: assert(m.size()==0); //testsize assert(m.empty()); //testempty assert(!m.erase("Ricky")); //nothingtoerase Even if you do not correctly implement all the functions, you must still list test cases that would test them. Don't lose points by thinking "Well, I didn't implement this function, so I won't bother saying how I would have tested it if I had implemented it."