Set.h

#ifndef SET_H #define SET_H

#include #include #include using namespace std;

template class Set { public: Set( ) : root{ nullptr } { }

~Set( ) { makeEmpty(); }

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 ); }

bool isEmpty( ) const { return root == nullptr; }

void printSet( ) const { if( isEmpty( ) ) cout << "Empty set" << endl; else printSet( root ); }

void makeEmpty( ) { makeEmpty( root ); }

void insert( const C & x ) { insert( x, 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: // // add nested class iterator here // class iterator { public: iterator() : current(nullptr) {}

C & operator *() { return current->element; }

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: // 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.

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); } void insert( const C & x, BinaryNode* & t ) { if( t == nullptr ) t = new BinaryNode{ x, nullptr, nullptr }; else if( x < t->element ) insert( x, t->left ); else if( t->element < x ) insert( x, t->right ); else ; // 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; t = ( t->left != nullptr ) ? t->left : t->right; delete oldNode; } }

// 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 makeEmpty( BinaryNode* & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; }

void printSet( BinaryNode* t) const { if( t != nullptr ) { printSet( t->left); cout << t->element << " - "; printSet( t->right); } } }; #endif

program your own file lab08.cpp in which your main() function will test the new data structure.

• The main function is contained in the file lab08.cpp.
• Declare an instance of Set suitable to hold integer values.
• Prompt user to enter a random sequence of integer values, insert these values into the data structure (the entered values should NOT be in sorted order).
• Call the printSet() member function in order to print out the values in your set.
• Prompt user to enter a random sequence of integer values, remove these values from your set. Print out the reduced set.
• use iterator to print the element values in your set. Compile and run your program, and see what you get.

The expected result:

insert the values (stop when entering 0): 10 5 20 3 22 6 18 7 9 13 15 4 2 1 19 30 8 0 print the values: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 13 - 15 - 18 - 19 - 20 - 22 - 30 - remove the values (stop when entering 0): 1 11 2 12 3 13 0 print the values: 4 - 5 - 6 - 7 - 8 - 9 - 10 - 15 - 18 - 19 - 20 - 22 - 30 - Print the element values using iterator: 4, 5, 6, 7, 8, 9, 10, 15, 18, 19, 20, 22, 30,