CSCI 330 Lab: Set

Complete the implementation of the mynode, my_set and my_set_iterator template classes as defined below, so that they run correctly with the test code test_my_set.cpp.

#ifndef MY_NODE_H
#define MY_NODE_H

// my_node.h

template <class T> class my_set;
template <class T> class my_set_iterator;

template <class T>
class my_node
{
public:
   my_node( const T & x, 
           my_node * parent, 
           my_node * left_child, 
           my_node * right_child);

   unsigned int size() const;
   unsigned int count(const T & x) const;
   my_node * find(const T & x);
   my_node * insert(const T & x, unsigned int & size);

protected:
   T x;
   my_node * parent;
   my_node * left_child;
   my_node * right_child;

friend class my_set<T>;
friend class my_set_iterator<T>;
};

#endif

---

#ifndef MY_SET_H
#define MY_SET_H

// my_set.h -- implemented as a binary search tree with inorder traversal

#include "my_node.h"

template <class T> class my_set_iterator;

template <class T>
class my_set
{
public:
   typedef my_set_iterator<T> iterator;
   my_set();

   bool empty() const;
   unsigned int size() const;

   iterator insert(const T & x);
   void erase(iterator it);
   unsigned int erase(const T & x);
      // Remove the value x from the set.
      // Return 1 if the value was found and removed;
      // return 0 otherwise.
   unsigned int count(const T & x) const;
   iterator find(const T & x) const; 
   iterator begin() const;
   iterator end() const;

protected:
   my_node<T> * remove(my_node<T> * n, T v);
   my_node<T> * root;
   unsigned int my_size;
};

template <class T>
class my_set_iterator
{
public:
   my_set_iterator();
   my_set_iterator(my_node<T> * n);

   bool operator==(my_set_iterator it) const;
   bool operator!=(my_set_iterator it) const;
   my_set_iterator & operator++();  // inorder traversal, pre-increment
   my_set_iterator operator++(int);  // inorder traversal, post-increment
   T & operator*();

protected:
   my_node<T> * n;

   friend class my_set<T>;
};

#endif

---

// test_my_set.cpp

#include <iostream>
#include <string>
#include <set>
#include <cassert>
#include "my_set.h"

using namespace std;

int main(char *args[])
{
   //#define SET set
   #define SET my_set

   SET<int> s;

   assert(s.size() == 0);
   assert(s.empty());

   s.insert(10);

   SET<int>::iterator it = s.begin();
   assert(*it == 10);

   s.insert(6);
   s.insert(6);

   assert(s.count(6) == 1);
   assert(s.count(10) == 1);
   assert(s.count(12) == 0);

   it = s.begin();
   assert(*it == 6);
   ++it;
   assert(*it == 10);
   ++it;
   assert(it == s.end());

   s.insert(7);
   s.insert(9);
   s.insert(9);
   s.insert(8);
   s.insert(11);
   it = s.begin();
   assert(*it == 6);
   ++it;
   assert(*it == 7);
   ++it;
   assert(*it == 8);
   ++it;
   assert(*it == 9);
   ++it;
   assert(*it == 10);
   ++it;
   assert(*it == 11);

   SET<int> s2;
   s2.insert(3);
   s2.insert(7);
   s2.insert(-1);
   s2.insert(16);
   s2.insert(11);
   s2.insert(4);

   it = s2.find(3);
   assert(*it == 3);
   it = s2.find(888);
   assert(it == s2.end());

   s2.erase(7);
   it = s2.begin();
   assert(*it == -1);
   ++it;
   assert(*it == 3);
   ++it;
   assert(*it == 4);
   ++it;
   assert(*it == 11);
   ++it;
   assert(*it == 16);
   ++it;
   assert(it == s2.end());

   s2.erase(16);
   it = s2.begin();
   assert(*it == -1);
   ++it;
   assert(*it == 3);
   ++it;
   assert(*it == 4);
   ++it;
   assert(*it == 11);
   ++it;
   assert(it == s2.end());

   s2.erase(3);
   it = s2.begin();
   assert(*it == -1);
   ++it;
   assert(*it == 4);
   ++it;
   assert(*it == 11);
   ++it;
   assert(it == s2.end());

   s2.erase(11);
   it = s2.begin();
   assert(*it == -1);
   ++it;
   assert(*it == 4);
   ++it;
   assert(it == s2.end());

   s2.erase(-1);
   it = s2.begin();
   assert(*it == 4);
   ++it;
   assert(it == s2.end());

   s2.erase(4);
   it = s2.begin();
   assert(it == s2.end());

   cout << "All tests passed." << endl;
}