In C++

Implement the Map ADT in a file Map.h as shown below.

// Map.h #ifndef MAP_H_ #define MAP_H_ #include "Pair.h" #include "MapSet.h" // must have insert that returns iterator!!! using namespace std; template  class Map { public: Map() {} void printMap() { typename Set>::iterator itr = themap.begin(); for (; itr != themap.end(); ++itr) { cout << (*itr).getKey() << ":" << (*itr).getValue() << endl; } return; } V & operator [](K index) { typename Set >::iterator here; Pair probe(index, V()); here = themap.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) {} K& getKey() { return key; } V& getValue() { return value; } bool operator == (const Pair& rhs) const { return key == rhs.key; } bool operator != (const Pair& rhs) const { return key != rhs.key; } bool operator < (const Pair& rhs) const { return key < rhs.key; } bool operator > (const Pair& rhs) const { return key > rhs.key; } private: K key; V value; }; #endif 

// MapSet.h #ifndef SET_H #define SET_H #include  #include  #include  using namespace std; template  class Set { public: Set( ) : root{ nullptr } { } ~Set( ) { makeEmpty(); } bool isEmpty( ) const { return root == nullptr; } 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 << "Empty tree" << endl; else print( root ); } void makeEmpty( ) { makeEmpty( root ); } void remove( const C & x ) { remove( x, root ); } private: struct BinaryNode { C element; BinaryNode* left; BinaryNode* right; BinaryNode( const C & theElement, BinaryNode* lt, BinaryNode* rt ) : element{ theElement }, left{ lt }, right{ rt } { } }; BinaryNode* root; public: class iterator { public: iterator() : current(nullptr) {} // for map.h iterator(BinaryNode* p) : current(p) {} C & operator *() { return current->element; } // prefix iterator & operator++() { if (current == nullptr) return *this; if (current->right != nullptr) { current = current->right; while (current->left != nullptr) { antes.push(current); current = current->left; } } else { if (!antes.empty()) { current = antes.top(); antes.pop(); } else current = nullptr; } return *this; } iterator operator++(int) { iterator old = *this; ++(*this); return old; } bool operator ==(const iterator & rhs) const { return current == rhs.current; } bool operator !=(const iterator & rhs) const { return !(*this == rhs); } private: BinaryNode * current; stack antes; iterator(BinaryNode* p, stack st) : current{p}, antes{st} {} friend class Set; }; iterator begin() { BinaryNode* lmost = root; stack nstack; while (lmost->left != nullptr) { nstack.push(lmost); lmost = lmost->left; } return iterator(lmost,nstack); } iterator end() { stack emptystack; return iterator(nullptr, emptystack); } // for map.h, change void to iterator  iterator insert(const C & x) { return insert( x, root ); } private: // Internal method to find the smallest item in a subtree t. // Return node containing the smallest item. BinaryNode* findMin( BinaryNode* t ) const { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } // 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 ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } void print( BinaryNode* t) const { if( t != nullptr ) { print( t->left); cout << t->element << " - "; print( t->right); } } void makeEmpty( BinaryNode* & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } // Internal method to insert into a subtree. // x is the item to insert. // t is the node that roots the subtree. // Set the new root of the subtree.  iterator insert( const C & x, BinaryNode* & t ) { if( t == nullptr ) { t = new BinaryNode{ x, nullptr, nullptr }; return iterator(t); } else if( x < t->element ) return insert( x, t->left ); else if( t->element < x ) return insert( x, t->right ); else return iterator(t); // Duplicate; do nothing } // Internal method to remove from a subtree. // x is the item to remove. // t is the node that roots the subtree. // Set the new root of the subtree. void remove( const C & x, BinaryNode* & t ) { if( t == nullptr ) return; // Item not found; do nothing if( x < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinaryNode* oldNode = t; if ( t->left == nullptr ) t = t->right; else t = t->left; delete oldNode; } } }; #endif 

Program your own file lab09.cpp in which your main() function will test the new data structure. The main() function,

• Declare an instance of Map Map studentDB; suitable to hold student information, that is, student id (key) and student name (value).
• Prompt user to enter a sequence of student information, insert these pairs into the data structure (the entered student ids should NOT be in sorted order).
• Call the printMap() member function to print out the pairs in studentDB.
• Prompt user to enter a student id, and change the student name as the user input name. Print out the pairs in studentDB.
• Prompt user to enter a student id, and remove this pair from studentDB. Print out the pairs in studentDB.

• Add a public function insert in Map.h, which add a new pair in themap.

 void insert(Pair newpair) { // add your code }

• Prompt user to enter a sequence of student information, insert these pairs into studentDB by calling insert member function.
• Call the printMap() member function to print out the pairs in studentDB.
• Call insert function defined in Map.h to add more student information in studentDB. And then print out the pairs in studentDB

The expected result:

using index operator to insert new pair: Student ID? 1006 Student Name? Jim Student ID? 1004 Student Name? Alice Student ID? 1008 Student Name? Fred Student ID? 1005 Student Name? Mary Student ID? 1001 Student Name? Tom Student ID? 0 Content of my basket: 1001:Tom 1004:Alice 1005:Mary 1006:Jim 1008:Fred Change which one? 1006 ... to what? Bill 1001:Tom 1004:Alice 1005:Mary 1006:Bill 1008:Fred Remove which one? 1005 1001:Tom 1004:Alice 1006:Bill 1008:Fred

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