Exercise 1: Implement the Map ADT in a file Map.h as shown below /7 Map.h #ifndef MAP H #define MAP H #include #include "Pair.h" "MapSet.h" // must have insert that returns iterator!!! using namespace std; template class Map public: Map () fh void printMap () typename Set>::iterator itr-themap.begin(); for ( ; itr != themap . end(); ++itr) cout >: :iterator here; Pair probe (index, V()) herethemap.insert (probe) return (*here).getValue) void remove (K & key) Pair probe (key); themap.remove (probe); return; private: Set > themap; #endif Map.h includes two header files Pair.h and Mapset.h which are defined as below // Pair.h #ifndef PAIR H #define PAIR-H- using namespace std; template class Pair public: Pair) Pair(K thekey) :key(thekey) Pair(K thekey, V theval):key (thekey), value (theval) Ch K& getKey () return key; v& getValue() return value bool operator(const Pair& rhs) const return keyrhs.key; bool operator - (const Pair& rhs) const return keyrhs.key; bool operator (const Pair& rhs) const return key > rhs.key private: K key; V value; li #end if // MapSet.h #ifndef SET H #de fine SETH - #include #include #include using namespace std; template class Set public: Set( rootf nullptr -Set() makeEmpty(); bool isEmpty const return rootnullptr; const c& findMin const assert(isEmpty()); return findMin( root )->element; const C & findMax) const assert(isEmpty)); return findMax( root )->element; bool contains ( const C&x const return contains( x, root; void print() const if( isEmpty cout current (p) C & operator *() return current->element; // prefix iterator & operator++) if (current nullptr) return *this if (current->right 1- nullptr) currentcurrent->right; while (current->left !- nullptr) antes.push (current) currentcurrent->left; else if (lantes.empty)) current-antes.top (); antes.pop) else current - nullptr; return *this; iterator operator++(int) private: // Internal method to find the smallest item in a subtree t. // Return node containing the smallest item. BinaryNode* findMin BinaryNode* t const if( tnullptr) if( t->left nullptr) return findMin( t->left return nullptr; return t; // Internal method to find the largest item in a subtree t. // Return node containing the largest item BinaryNode* findMax( BinaryNode* t const if( t != nullptr ) while ( t->right != nullptr ) t -t->right; return t; // Internal method to test if an item is in a subtree. / x is item to search for. // t is the node that roots the subtree. bool contains ( const C & x, BinaryNode * t ) const if( t -nullptr) else ifx element) else if( t->element left return contains( x, t->right); return true; // Match void print( BinaryNode* t) const if( t != nullptr ) print( t->left) cout elementright); void makeEmpty BinaryNode* & t ) if( t !- nullptr) makeEmpty( t->left); makeEmpty( t->right ); delete t; t-nullptr; using insert function to insert new pair: Student ID? 1009 Student Name? Fred Student ID? 1005 Student Name? David 1001:Tom 1004:Alice 1005:David 1006:Bill 1008:Fred 1009:Fred Exercise 1: Implement the Map ADT in a file Map.h as shown below /7 Map.h #ifndef MAP H #define MAP H #include #include "Pair.h" "MapSet.h" // must have insert that returns iterator!!! using namespace std; template class Map public: Map () fh void printMap () typename Set>::iterator itr-themap.begin(); for ( ; itr != themap . end(); ++itr) cout >: :iterator here; Pair probe (index, V()) herethemap.insert (probe) return (*here).getValue) void remove (K & key) Pair probe (key); themap.remove (probe); return; private: Set > themap; #endif Map.h includes two header files Pair.h and Mapset.h which are defined as below // Pair.h #ifndef PAIR H #define PAIR-H- using namespace std; template class Pair public: Pair) Pair(K thekey) :key(thekey) Pair(K thekey, V theval):key (thekey), value (theval) Ch K& getKey () return key; v& getValue() return value bool operator(const Pair& rhs) const return keyrhs.key; bool operator - (const Pair& rhs) const return keyrhs.key; bool operator (const Pair& rhs) const return key > rhs.key private: K key; V value; li #end if // MapSet.h #ifndef SET H #de fine SETH - #include #include #include using namespace std; template class Set public: Set( rootf nullptr -Set() makeEmpty(); bool isEmpty const return rootnullptr; const c& findMin const assert(isEmpty()); return findMin( root )->element; const C & findMax) const assert(isEmpty)); return findMax( root )->element; bool contains ( const C&x const return contains( x, root; void print() const if( isEmpty cout current (p) C & operator *() return current->element; // prefix iterator & operator++) if (current nullptr) return *this if (current->right 1- nullptr) currentcurrent->right; while (current->left !- nullptr) antes.push (current) currentcurrent->left; else if (lantes.empty)) current-antes.top (); antes.pop) else current - nullptr; return *this; iterator operator++(int) private: // Internal method to find the smallest item in a subtree t. // Return node containing the smallest item. BinaryNode* findMin BinaryNode* t const if( tnullptr) if( t->left nullptr) return findMin( t->left return nullptr; return t; // Internal method to find the largest item in a subtree t. // Return node containing the largest item BinaryNode* findMax( BinaryNode* t const if( t != nullptr ) while ( t->right != nullptr ) t -t->right; return t; // Internal method to test if an item is in a subtree. / x is item to search for. // t is the node that roots the subtree. bool contains ( const C & x, BinaryNode * t ) const if( t -nullptr) else ifx element) else if( t->element left return contains( x, t->right); return true; // Match void print( BinaryNode* t) const if( t != nullptr ) print( t->left) cout elementright); void makeEmpty BinaryNode* & t ) if( t !- nullptr) makeEmpty( t->left); makeEmpty( t->right ); delete t; t-nullptr; using insert function to insert new pair: Student ID? 1009 Student Name? Fred Student ID? 1005 Student Name? David 1001:Tom 1004:Alice 1005:David 1006:Bill 1008:Fred 1009:Fred