exam

//set.tpp
template<typename T>
set<T>::set(): head(NULL)
{
}

template<typename T>
set<T>::set(const set<T>& other): head(other.head->clone())
{
}

template<typename T>
template<typename FwdIter>
set<T>::set(FwdIter start, FwdIter end) : head(NULL)
{
    for (FwdIter it = start; it != end; ++it)
        insert(*it);
}

template<typename T>
set<T>& set<T>::operator=(set<T> other)
{
    swap(other);
    return *this;
}

template<typename T>
void set<T>::swap(set<T>& other)
{
    std::swap(head, other->head);
}

template<typename T>
typename set<T>::iterator set<T>::find(const T& elem) const
{
    if (head == NULL)
        return end();
    return set<T>::iterator(head->find(elem));
}

template<typename T>
void set<T>::insert(const T& elem)
{
    if (head == NULL)
        head = new node<T>(elem);
    else
        head->insert(elem);
}

template<typename T>
void set<T>::erase(const T& elem)
{
    if (head == NULL)
        return;
    node<T>* found = head->find(elem);
    if (!found)
        return;
    else
    {
        bool need_fix = (head == found);
        node<int>*tmp = details::node_erase(found);
        if (need_fix)
            head = tmp;
    }
}

template<typename T>
set<T>::~set()
{
    delete head;
}

template<typename T>
typename set<T>::iterator set<T>::begin() const
{
    if (head == NULL)
        return end();
    else
        return set::iterator(head->find_smallest());
}

template<typename T>
typename set<T>::iterator set<T>::end() const
{
    return set::iterator(NULL);
}




//set_iterator.tpp
template<typename T>
set<T>::iterator::iterator(): p(NULL)
{
}

template<typename T>
set<T>::iterator::iterator(details::node<T>* b): p(b)
{
}

template<typename T>
typename set<T>::iterator& set<T>::iterator::operator++()
{
    if (p->right)
    {
        p = p->right->find_smallest();
    }
    else if (p->parent && p->parent->left == p)
    {
        p = p->parent;
    }
    else
    {
        p = NULL;
    }
    return *this;
}

template<typename T>
typename set<T>::iterator set<T>::iterator::operator++(int)
{
    set<T>::iterator old = *this;
    ++(*this);
    return old;
}

template<typename T>
T& set<T>::iterator::operator*()
{
    if (p != NULL)
        return p->data;
    else
        throw std::runtime_error("trying to dereference end iterator");
}

template<typename T>
bool set<T>::iterator::operator!=(const iterator &it) const
{
    return (p != it.p);
}

template<typename T>
bool set<T>::iterator::operator==(const iterator &it) const
{
    return !(*this != it);
}




//set_node.tpp
namespace details
{

template<typename T>
class node
{
public:
    node(): left(NULL), right(NULL), parent(NULL), data(0)
    {
    }
    node(const T& d): left(NULL), right(NULL), parent(NULL), data(d)
    {
    }
    node* clone() const
    {
        node* new_node = new node(data);
        if (left)
        {
            new_node->left = left->clone();
            new_node->left->parent = new_node;
        }
        if (right)
        {
            new_node->right = right->clone();
            new_node->right->parent = new_node;
        }
        return new_node;
    }
    node* find(const T& b)
    {
        if (b == data)
            return this;
        if (b < data)
        {
            if (left)
                return left->find(b);
            else
                return NULL;
        }
        else //b > data
        {
            if (right)
                return right->find(b);
            else
                return NULL;
        }
    }
    int children_count() const
    {
        int c = 0;
        if (left != NULL)
            c++;
        if (right != NULL)
            c++;
        return c;
    }
    node* onechild()
    {
        if (left)
            return left;
        else
            return right;
    }
    bool is_left_child() const
    {
        return (this->parent->left == this);
    }
    bool is_right_child() const
    {
        return !is_left_child();
    }
    node* find_greatest()
    {
        node* current = this;
        while (current->right)
            current = current->right;
        return current;
    }
    node* find_smallest()
    {
        node* current = this;
        while (current->left)
            current = current->left;
        return current;
    }
    void insert(const T& b)
    {
        if (b == data)
            return;
        if (b > data)
        {
            if (right)
                right->insert(b);
            else
            {
                right = new node<T>(b);
                right->parent = this;
            }
        }
        else
        {
            if (left)
                left->insert(b);
            else
            {
                left = new node<T>(b);
                left->parent = this;
            }
        }
    }
    ~node()
    {
        if (left)
        {
            delete left;
            left = NULL;
        }
        if (right)
        {
            delete right;
            right = NULL;
        }
    }
    template<typename T>
    friend node* node_remove(node*);
    node* left;
    node* right;
    node* parent;
    T data;
};

template<typename T>
node<T>* node_erase(node<T>* rem)
{
    if (rem->children_count() == 0)
    {
        if (rem->parent)
        {
            if (rem->is_left_child())
                rem->parent->left = NULL;
            else
                rem->parent->right = NULL;
        }
        delete rem;
        return NULL;
    }
    else if (rem->children_count() == 1)
    {
        node<T>* ret = rem->onechild();
        if (rem->parent)
        {
            rem->onechild()->parent = rem->parent;
            if (rem->is_left_child())
                rem->parent->left = rem->onechild();
            else
                rem->parent->right = rem->onechild();
        }
        else
        {
            rem->onechild()->parent = NULL;
        }
        rem->left = NULL;
        rem->right = NULL;
        delete rem;
        return ret;
    }
    else //2 children
    {
        node<T>* replace = rem->left->find_greatest();
        std::swap(rem->data, replace->data);
        node_erase(replace);
        return rem;
    }
}

}




//set.hpp
#include <iterator>
#include <vector>
#include <fstream>
#include <sstream>
#include <stdexcept>

#include "set_node.tpp"

template<typename T>
class set
{
public:
    class iterator;
    set();
    set(const set&);
    template <typename FwdIter>
    set(FwdIter start, FwdIter end);
    set& operator=(set );
    void swap(set&);
    void insert(const T&);
    void erase(const T&);
    iterator find(const T&) const;
    iterator begin() const;
    iterator end() const;
    ~set();
private:
    details::node<T>* head;
};

template<typename T>
class set<T>::iterator
{
    friend set<T>;
public:
    iterator();
    iterator& operator++();
    iterator operator++(int );
    T& operator*();
    bool operator!=(const iterator &it) const;
    bool operator==(const iterator &it) const;
private:
    iterator(details::node<T>* b);
    details::node<T>* p;
};

#include "set.tpp"
#include "set_iterator.tpp"





//main.cpp
#define BOOST_TEST_MAIN

#include <iostream>
#include <set>
#include <ctime>
using std::cout;
using std::endl;

#include <boost/test/unit_test.hpp>

#include "set.hpp"
using namespace details;

void vector_random_fill(std::vector<int> &v, int modulo)
{
    for (size_t i = 0; i < v.size(); i++)
        v[i] = rand() % modulo;
}

BOOST_AUTO_TEST_SUITE( set_test )

BOOST_AUTO_TEST_CASE( set_constructor )
{
    //empty
    set<int> s;
    BOOST_CHECK(s.find(0) == s.end());

    //sequence constructor
    const int size = 100;
    const int mod = 40;
    std::vector<int> v(size);
    vector_random_fill(v, mod);
    set<int> s2(v.begin(), v.end());
    for (size_t i = 0; i < size; i++)
        BOOST_CHECK(s2.find(v[i]) != s.end());
}

BOOST_AUTO_TEST_CASE( set_insert_simple )
{
    set<int> s;
    s.insert(1);
    BOOST_CHECK(s.find(1) != s.end());
    BOOST_CHECK(s.find(100500) == s.end());
    s.insert(2);
    s.insert(-10);
    s.insert(239);
    BOOST_CHECK(s.find(239) != s.end());
    BOOST_CHECK(s.find(2) != s.end());
}

BOOST_AUTO_TEST_CASE( set_erase_simple )
{
    set<int> s;
    s.erase(1);
    s.insert(1);
    s.insert(2);
    s.insert(-10);
    s.insert(100500);
    s.insert(0);
    s.erase(1);
    BOOST_CHECK(s.find(1) == s.end());
    s.erase(100500);
    s.erase(2);
    s.erase(-10);
    s.erase(0);
    BOOST_CHECK(s.find(1) == s.end());
}

BOOST_AUTO_TEST_CASE( test_complex )
{
    using std::vector;
    using std::rand;


    int randseed = static_cast<int>(std::time(0) % 10000);
    srand(randseed);
    cout << "randseed is " << randseed << endl;
    const size_t size = 100;
    const int mod = 20;

    set<int> a;
    std::set<int> b;

    vector<int> inserts(rand() % size);
    vector<int> erases(rand() % size);
    vector<int> tests(size);
    vector_random_fill(inserts, mod);
    vector_random_fill(erases, mod);
    vector_random_fill(tests, mod);

    for (size_t i = 0, j = 0; i < inserts.size() || j < erases.size(); )
    {
        if (rand() % 2 == 0 && i < inserts.size())
        {
            a.insert(inserts[i]);
            b.insert(inserts[i]);
            i++;
        }
        else if (j < erases.size())
        {
            a.erase(erases[j]);
            b.erase(erases[j]);
            j++;
        }
        for (size_t k = 0; k < tests.size(); k++)
        {
            bool b1 = (a.find(tests[k]) != a.end());
            bool b2 = (b.find(tests[k]) != b.end());
            BOOST_CHECK(b1 == b2);
        }
    }
}

BOOST_AUTO_TEST_SUITE_END()



BOOST_AUTO_TEST_SUITE( iterator_tests )

BOOST_AUTO_TEST_CASE( iterators )
{
    //empty constructor
    set<int>::iterator it;
    //empty iterator dereference check
    BOOST_CHECK_THROW(*it, std::runtime_error);

    const int size = 50;
    //big test
    std::vector<int> v(20);
    vector_random_fill(v, size);
    set<int> s(v.begin(), v.end());
    set<int> s2;
    for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
        s2.insert(*it);

    set<int>::iterator sit = s.begin();
    set<int>::iterator s2it = s2.begin();
    for (set<int>::iterator sit = s.begin(); sit != s.end(); ++sit)
    {
        BOOST_CHECK(*sit == *s2it);
        s2it++;//postincrement test
    }


    //empty set iterating
    set<int> se;
    for (set<int>::iterator it = se.begin(); it != se.end(); ++it)
        cout << *it << " ";
}

BOOST_AUTO_TEST_SUITE_END()