PROGRAMMING BAG DICTIONARY ASSIGNMENT INSTRUCTIONS OVERVIEW Implement a dictionary using a Bag7Project 4.7 in the text (modied) INSTRUC'ONS Use the bag ADT provided to create an array-based implementation for bags. Then use your bag to implement the dictionary ADT provided you. This means you have to implement your dictionary using the bag functions. Test your bag and dictionary implementations with the bagtestmain.cpp le provided for you. If you are not able to fully implement all the functions of the dictionary and/or bag, you may modify the tests in bagtestmain.cpp to only exercise those functions you were able to complete You will only get credit for those methods you test and display, so be sure you don't leave any out. Also, do not add any public functions to your bag and dictionary implementations beyond those specied in the ADTs, though you may add private functions if you want. Put the following les into a zip le named studentgnamegBaggAssignment and submit them to Canvas: -ABag.h // Your bag-array implementation which must inherit the Bag class - BDictionary.h must inherit the // Your Dictionary-bag implementation which // Dictionary class - bagtestmain.cpp // The test driver I have provided for you - bagADT.h // The bag ADTI gave you 7 it should be unchanged - dictionaryADT.h // The dictionaryADT I gave you 7 it should be unchanged -kvpair.h // The kvpair class I gave you 7 it should be unchanged - Screen Shots // Word document with screen shot(s) and integrity statements showing // all of your program's output. Approachdoc // This is a Word document where you explain how you implemented tested each required function // your solution and how you 7 Any other .cpp and/or .h les that comprise your project (I need all the .cpp and .h les used in your project). - Your_dictionary.exe //Your executable le.**\" **" If you completed your assignment using Visual Studios you must use Visual Studios 2017 and submit your entire VS project directory Note: If your ABag does not inherit Bag and/or BDictionary does not inherit Dictionary, you will not receive any credit for your work If you use the templates provided (ABagih and BDictionaryih) the inheritance is already done for you. Your test program must exercise every function of the dictionary. For any function whose functionality is not obvious you must explain in your Word document how your test output demonstrates that function. Reach out to your professor if you have questions. Rubrics (For the 70% Content Portion) Program must run in order to get any points. By \"run\" this means that you must at least get one or more of the bag methods working (and your program must demonstrate that functionality). Tips for Success 0 Start by working on your \"Approach\" rst. Once you are satised with your approach, then start building your program incrementally. Start with the bag and increment one feature at a time (you'll have to stub out the features the ADT requires that you are not ready to implement yet) starting with the constructors and then working your Way down the feature list using common sense to gure out which features need to be implemented rst. Try your bag out with the various parameter combinations I want you to test with ( and ), When you are satised the bag is working then move on to the dictionary, again implementing and testing rnction by function I Don't wait until the last minute, You'll nd that many of your problems you will solve while you are away from your computer and have a chance to think about the error you are seeing. This takes time. Note: KVpair, which uses the = operator for comparing the key values, will only accept objects that have also implemented the = operator, This class has been tested with the following types: 0 string 0 int It specically does not work with the Int type (at least not in the version of C++ I am working with). Debugging Your Code A big part of this assignment is debugging your code, so do not expect your instructor to do this for you, Having completed the pre-requisite courses for this class, you should already have some experience nding coding errors and xing them. This class will give you plenty of opportunities to further rene those skills and you can only do that by wrestling with the problem, Here are some debugging tips: 0 Build a little, test a little, Don't write all your code before you start debugging it. Break your work into logical chunks that can be compiled and debugged and build them one at a time. For this project, I would start by building the Bag class and implementing the addItem() function first. Once I get that function working properly, thenI would move on to another Bag function. The idea is you build and test a function one function at a time. That way, if you run into an error, you know Where to look. - Learn to use the debugger if you haven't already. The debugger allows you to step through your code one step and a time and see what happens in memory while you're doing it. When students come to me with problems, I rst try to isolate where the problem is logically based on what the program is doing and then I use the debugger to nd the actual fault. 0 Be willing to walk away from your computer and give your mind a rest. I nd that the solution to a problem often comes to me while I am doing something else. I have never regretted stepping away from my computer to let the problem \"percolate\" in my mind, but I have oen regretted not doing this, This is one of the reasons you should never wait till the last minute to start working on your program; by doing that you are not giving yourself the time to walk away, ABag.h + X Project 1 (Global Scope) * File: ABag . h * Author: Prof Terri Sipantzi JOUIDWNA You may use this template to implement your ABag. * #ifndef ABAG_H #define ABAG_H 10 11 #include "book.h" 12 #include "bagADT.h" 13 14 template 15 Eclass ABag : public Bag { 16 public: 17 // constructors/destructor 18 19 // bag methods: addItem, remove, operator+=, size, etc. 20 21 private: 22 E *data; / / an array of items 23 int used; // number of items the data array currently holds 24 int capacity; / / the number of items the bag can hold (size of array) 25 26 27 #endif /* ABAG_H */ 28 29bagADT.h + X ABag.h Project1 (Global Scope) 10 * / 11 12 #ifndef BAGADT_H 13 #define BAGADT_H 14 15 #include 16 #include "book.h" 17 18 template 19 aclass Bag { 20 public: 21 Bag () {} / / base constructor 22 virtual ~Bag() {} / / base destructor 23 24 // Insert a new item into the bag -- return false if fails and true if 25 // successful 26 virtual bool addItem(const E& item) = 0; 27 28 // Looks for 'item' in the bag and if found updates 'item' with the 29 / / bag value and returns true. Otherwise 'item' is left unchanged 30 // and the method returns false. 31 virtual bool remove(E& item) = 0; 32 33 // Removes the top record from the bag, puts it in returnValue, and 34 // returns true if the bag is not empty. If the bag is empty the 35 // function returns false and returnValue remains unchanged. 36 virtual bool removeTop(E& returnValue) = 0; 37 38 // Finds the record using returnValue and if the record is found updates 39 // returnValue based on the contents of the bag and returns true. If the 40 // record is not found the function returns false. Works just like remove() 41 // except that the found record is not removed from the bag. 42 virtual bool find(E& returnValue) const = 0; 43 44 // Inspect the top of the bag. If the bag is empty return 45 // false and leave 'item' unchanged; otherwise, return true and update 46 // 'item' with the contents of the bag. 47 virtual bool inspectTop(E& item) const = 0; 48 49 // empties the bag 50 virtual void emptyBag ( ) = 0; 51 52 / / use the += operator to add an item to the bag 53 virtual bool operator+=(const E& addend) = 0; 54 55 // get the size of the bag 56 virtual int size() const = 0; 57 58 / / get the capacity of the bag 59 virtual int bagCapacity( ) const = 0; 60 61 62 63 64 #endif /* BAGADT_H */ 65 66BDictionary.h + X bagADT.h ABag.h Project 1 (Global Scope) 1 3/* N * File: BDictionary.h -- implement a dictionary use an array-based bag 3 * Author: Prof Terri Sipantzi * * You may use this template to implement your Dictionary * 00 #ifndef BDICTIONARY_H 9 #define BDICTIONARY_H 10 11 #include "ABag.h" 12 #include "dictionaryADT. h" 13 #include "kvpair.h" 14 15 template 16 class BDictionary : public Dictionary { 17 public: 18 // constructors/destructor 19 20 / / methods: clear, insert, remove, removeAny, find, size, etc. 21 22 private: 23 E / /Pointer to a ABag object. You'll need to instantiate the bag in your constructor: 24 // dictionary = new ABag >(size) or something similar depending on how 25 / / you've implemented your ABag constructor(s). 26 //This pointer gives you access to the bag which stores your data and provides the 27 / /functions you need to build your dictionary. 28 ABag >* dictionary; 29 30 31 32 #endif /* BDICTIONARY_H */ 33 34book.h + X BDictionary.h bagADT.h ABag.h (Global Scope) Project1 7 // used for the software examples. 8 9 // First, include all the standard headers that we need 10 -#ifndef BOOK_H 11 #define BOOK_H 12 13 #include 14 #include // Used by timing functions 17 18 / / Now all the standard names that we use 19 using std: : cout. 20 using std: : endl; 21 using std: :string; 22 using std: : ostream; 23 24 const int defaultsize = 10; // Default size 25 26 // Return true iff "x" is even 27 inline bool EVEN(int x) { return (x % 2) == 0; } 28 29 / / Return true iff "x" is odd 30 inline bool ODD(int x) { return (x % 2) != 0; } 31 32 =/ / Assert: If "val" is false, print a message and terminate 33 / / the program 34 void Assert (bool val, string s) { 35 if (!val) { // Assertion failed -- close the program 36 cout key( ); } 106 107 #endif / /end of BOOK_HdictionaryADT.h + X book.h BDictionary.h bagADT.h ABag.h Project1 Global 1 V/ From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, IDWN // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. =#ifndef DICTIONARYADT_H #define DICTIONARYADT_H 9 // The Dictionary abstract class. 10 template 11 aclass Dictionary { 12 public: 13 Dictionary ( ) {} / / Default constructor 14 virtual ~Dictionary() {} // Base destructor 15 16 / Reinitialize dictionary 17 virtual void clear() = 0; 18 19 // Insert a record 20 // k: The key for the record being inserted. 21 // e: The record being inserted. 22 // Return true if insert is successful and false otherwise 23 virtual bool insert(const Key& k, const E& e) = 0; 24 25 // Looks for a record using the key and if found does the following: 26 // - updates the E& rtnVal 27 // - removes the record from the dictionary 28 // - returns true 29 // If the record is not found the function returns false. 30 virtual bool remove (const Key& k, E& rtnVal) = 0; 31 32 // Takes an arbitrary record from the dictionary and does the following: 33 // - updates the E& returnValue 34 // - removes the record from the dictionary 35 // - returns true 36 // If the dictionary is empty the function returns false. 37 virtual bool removeAny(E& returnValue) = 0; 38 39 // Looks for a record using the key and if found does the following: 40 // - updates the E& returnValue 41 // - returns true 42 // If the record is not found the function returns false. 43 virtual bool find (const Key& k, E& returnValue) const = 0; 44 45 / Return the number of records in the dictionary. 46 virtual int size() = 0; 47 48 49 #endifkvpair.h # x dictionaryADT.h book.h BDictionary.h bagADT.h ABag.h Project1 1 =/ / From the software distribution accompanying the textbook IN / / "A Practical Introduction to Data Structures and Algorithm Analysis, / / Third Edition (C++)" by Clifford A. Shaffer. 4 // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. 5 6 #ifndef KVPAIR_H 7 #define KVPAIR_H 8 9 9// Container for a key-value pair 10 / / Key object must be an object for which the == operator is defined. 11 // For example, int and string will work since they both have == defined, 12 / / but Int will not work since it does not have == defined. 13 template 14 aclass KVpair { 15 private: 16 Key k; 17 E e; 18 public: 19 / Constructors 20 KVpair () {} 21 KVpair (Key kval, E eval) 22 23 k = kval; e = eval; 24 25 KVpair (const KVpair& o) // Copy constructor 26 27 k = o.k; e = o.e; 28 29 30 void operator =(const KVpair& o) // Assignment operator 31 32 k = o.k; e = o.e; 33 34 35 bool operator==(const KVpair& o) const { -0-0 36 if (o.k = = k) { 37 return true; 38 39 return false; 40 41 42 // Data member access functions 43 Key key () { return k; } 44 void setkey(Key ink) { k = ink; } 45 E value() { return e; } 46 47 48 49 #endif