Question
In C++ Implement the Map ADT in a file Map.cpp as shown below. // Map.cpp #ifndef MAP_H_ #define MAP_H_ #include Pair.cpp #include MapSet.cpp // must
In C++
Implement the Map ADT in a file Map.cpp as shown below. // Map.cpp #ifndef MAP_H_ #define MAP_H_ #include "Pair.cpp" #include "MapSet.cpp" // must have insert that returns iterator!!! using namespace std; template
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.cpp #ifndef SET_H #define SET_H #include
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; CSE 2020 Lab 10 Maps maps.html[1/11/21, 12:45:54 PM] }
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 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; } CSE 2020 Lab 10 Maps maps.html[1/11/21, 12:45:54 PM] 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.cpp, 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 the pointer to the 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 the pointer to the 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. CSE 2020 Lab 10 Maps maps.html[1/11/21, 12:45:54 PM] // x is item to search for. // t is the pointer to the root of 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 item into a subtree. // x is the item to insert. // t is the pointer to the root of 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 pointer to the root of 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; CSE 2020 Lab 10 Maps maps.html[1/11/21, 12:45:54 PM] delete oldNode; } } }; #endif Program your own file lab10.cpp in which your main() function will test the Map class. The main() function, Declares an instance of Map Map
outcome
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 student database: 1001:Tom 1004:Alice 1005:Mary 1006:Jim 1008:Fred Who you want to know? 1005 The corresponding name is: Mary 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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started