#include <iostream>  #include <cstdio>  #include <cstdlib>  #define BOOST_TEST_MODULE Link  #define BOOST_TEST_MAIN  #include <boost/test/unit_test.hpp>    struct node {  	int value;  	node* left;  	node* right;  	node* parent;  	node (int value, node* left, node* right, node* parent)  		: value(value),  		  left(left),  	      right(right),  	      parent(parent)  	{}  };    node* minimum(node* v) {  	if (v -> left == nullptr) {  		return v;  	}  	else {  		return minimum(v -> left);  	}  }    node* maximum(node* v) {  	if (v -> right == nullptr) {  		return v;  	}  	else {  		return maximum(v -> right);  	}  }    node* next(node* v) {  	if (v -> right != nullptr) {  		return minimum(v -> right);  	}	  	node* y = v -> parent;  	while (y != nullptr && v == y -> right) {  		v = y;  		y = y -> parent;  	}  	return y;  }    node const* next(node const* v) {  	if (v -> right != nullptr) {  		return minimum(v -> right);  	}	  	node const* y = v -> parent;  	while (y != nullptr && v == y -> right) {  		v = y;  		y = y -> parent;  	}  	return y;  }    node* previous(node* v) {  	if (v -> left != nullptr) {  		return maximum(v -> left);  	}  	node* y = v -> parent;  	while (y != nullptr &&  v == y -> left) {  		v = y;  		y = y -> parent;  	}  	return y;  }    node const* previous(node const* v) {  	if (v -> left != nullptr) {  		return maximum(v -> left);  	}  	node* y = v -> parent;  	while (y != nullptr &&  v == y -> left) {  		v = y;  		y = y -> parent;  	}  	return y;  }    struct iterator {  	node* it;  	  	iterator ()   		:it(nullptr)  	{}    	iterator(node* it)   	   : it(it)  	{}  	  	iterator& iterator::operator++() {  	  *this = next(it);  	  return *this;  	}  	  	iterator iterator::operator++(int) {  	    iterator *tmp = new iterator(it);          ++(*this);          return *tmp;  	}  	  	iterator& iterator::operator--() {  	   *this = previous(it);  	   return *this;  	}  	  	iterator iterator::operator--(int) {  	    iterator *tmp = new iterator(it);          --(*this);          return *tmp;  	}  	  	int& iterator::operator*() const {  		return it -> value;    	}  	  	bool iterator::operator == (iterator const& it_1) const {  		return (this -> it == it_1.it);  	}  	  	bool iterator::operator != (iterator const&it_1) const {  		return (this -> it != it_1.it);  	}    };    struct constIterator {  	node const* it;        	constIterator()   		: it(nullptr)  	{}    	constIterator(node const* it)   		: it(it)  	{}    	constIterator(iterator thing)   	   : it((node const*)thing.it)      {}  	  	constIterator& constIterator::operator++() {  		*this = next(it);  		return *this;  	}  	  	constIterator constIterator::operator++(int) {  	    constIterator *tmp = new constIterator(it);          ++(*this);          return *tmp;  	}      	constIterator& constIterator::operator--() {  	   *this = previous(it);  	   return *this;  	}  	  	constIterator constIterator::operator--(int) {  	    constIterator *tmp = new constIterator(it);          --(*this);          return *tmp;  	}  	  	const int& constIterator::operator*() const {  		return it -> value;    	}  	  	bool constIterator::operator==(constIterator const& it_1) const {  		return (this -> it == it_1.it);  	}  	  	bool constIterator::operator!=(constIterator const&it_1)const {  		return (this -> it != it_1.it);  	}  };     struct set {  	  	int size;  	node* root;  	set (int size, node* root)   		: size(size),  		  root(root)   	{}    	set(set const& c) {  	    constIterator it = c.begin();  		this -> size = 0;  		this -> root = nullptr;  		for (constIterator it = c.begin(); this -> size != c.size; it++) {  			this -> insert(*it);  		}  	}  	  	void insert_1(node* v, int x) {  		if (v == nullptr) {  			node* tmp = new node(x, nullptr, nullptr, nullptr);  			size++;  			root = tmp;  			return;  		}    		if (x >= v -> value) {  			if (v -> right != nullptr) {  				insert_1(v -> right, x);	  			}  			else {  			  size++;  			  node* tmp = new node(x, nullptr, nullptr, v);  			  v -> right = tmp;  			}  		}   		else {  			if (v -> left != nullptr) {  				insert_1(v -> left, x);  			}  			else {  				size++;  				node* tmp = new node(x, nullptr, nullptr, v);  				v -> left = tmp;  			}  		}  	}  	void insert(int x) {  	   insert_1(this -> root, x);  	}  	  	void erase(iterator v) {  		node* y;  		node* x;  		if (size == 0) {  			printf("The tree has size = 0\n");  			return;  		}  		if (v.it -> left != nullptr && v.it -> right != nullptr) {  			size--;  			y = next(v.it);  			x = nullptr;  			if (y != root) {  				if (y == y -> parent -> left) {  					y -> parent -> left = nullptr;   				}  				else {  					y -> parent -> right = nullptr;   				}  			}  			v.it -> value = y -> value;  		}  		else {  			if (v.it -> left != nullptr || v.it -> right != nullptr) {  				y = v.it;  				if (y -> left != nullptr) {  					x = y -> left;   				}  				else {  					x = y -> right;  				}    			}  			else {  				y = v.it;  				x = nullptr;  			}  		}	  		if (x != nullptr) {  			x -> parent = y -> parent;  		}  		if (y -> parent == nullptr) {  			root = x;  		}  		else {  			if (y == y -> parent -> left) {  				y -> parent -> left = x;  			}  			else {  				y -> parent -> right = x;  			}  		}  		delete y;  	}    	node* find_1(node* v, int x) {  		if (v == nullptr || v -> value == x) {  			return v;  		}  		if (x >= v -> value) {  			find_1(v -> right, x);  		}  		else {  			find_1(v -> left, x);  		}  	}  	iterator find(int x) {  		iterator v;  		v.it = find_1(root, x);  		return v;  	}    	iterator const& begin() const {  	    iterator it(minimum(root));  		return it;  	}    	iterator const& end() const {  	    iterator it(maximum(root));  		return it;  	}    	void deleteTree(node* v) {  		size = 0;  		if (v == nullptr) {  			delete v;  		}  		else {  			deleteTree(v -> left);  			deleteTree(v -> right);  			delete v;  		}  	}  	void deleteTree() {  		deleteTree(root);  		root = nullptr;  	}    	set& operator=(set const& c) {  		deleteTree(this -> root);  		this -> size = 0;  		this -> root = nullptr;  		for (constIterator it = c.begin(); this -> size != c.size; it++) {  			this -> insert(*it);  		}  		return *this;  	}    	void printTree_1(node* v, int level) {  		if (v == nullptr) {  			return;  		}  		printTree_1(v -> left, level + 1);  		for (int i = 1; i<=level; i++) {  			printf(".");  		}  		std::cout << v -> value << std::endl;  		printTree_1(v -> right, level + 1);  	}  	void printTree() {  		printTree_1(root, 0);  	}  	  	void print(iterator v) {  		printf("%d\n", *v);  	}  };    // SET TESTS  BOOST_AUTO_TEST_CASE(insert){  	set a(0, nullptr);  	a.insert(1);  	BOOST_CHECK_EQUAL(a.begin().it -> value, 1);  }    BOOST_AUTO_TEST_CASE(deleteElement) {  	set a(0, nullptr);  	a.insert(1);  	a.insert(5);  	a.insert(3);  	a.erase(a.find(1));  	BOOST_CHECK_EQUAL(a.find(1) == nullptr, true);  	a.erase(a.find(3));  	BOOST_CHECK_EQUAL(a.find(3) == nullptr, true);  	a.erase(a.find(5));  	BOOST_CHECK_EQUAL(a.find(5) == nullptr, true);  }    BOOST_AUTO_TEST_CASE(findElements){  	set a(0, nullptr);  	for (int i = 0; i<=10; i++) {  		a.insert(i);  	}  	for (int i = 0; i<=10; i++) {  		BOOST_CHECK_EQUAL(*a.find(i) == i, true);  	}  	BOOST_CHECK_EQUAL(a.find(11) == nullptr, true);  	BOOST_CHECK_EQUAL(a.find(-1) == nullptr, true);  	BOOST_CHECK_EQUAL(a.find(100500) == nullptr, true);  	  }    BOOST_AUTO_TEST_CASE(deleteTree){  	set a(0, nullptr);  	for (int i = 0; i<=10; i++) {  		a.insert(i);  	}  	a.deleteTree();  	BOOST_CHECK_EQUAL(a.size == 0, true);  	for (int i = 0; i<=10; i++) {  		BOOST_CHECK_EQUAL(a.find(i) == nullptr, true);  	}  }     BOOST_AUTO_TEST_CASE(assignmentSet){  	set a(0, nullptr);  	set b(0, nullptr);  	  	for (int i = 0; i<=10; i++) {  		a.insert(i);  	}  	b = a;  	BOOST_CHECK_EQUAL(a.size == b.size, true);  	  	iterator ita = a.begin();  	iterator itb = b.begin();  	iterator finish = a.end();  	while (ita != finish) {  		BOOST_CHECK_EQUAL(*ita == *itb, true);  		ita++;  		itb++;  	}  	ita = a.end();  	itb = b.end();  	BOOST_CHECK_EQUAL(*ita == *ita, true);  }    BOOST_AUTO_TEST_CASE(assignmentSets){  	set a(0, nullptr);  	set b(0, nullptr);  	set c(0, nullptr);  	  	for (int i = 0; i<=10; i++) {  		a.insert(i);  	}  	c = b = a;  	BOOST_CHECK_EQUAL(a.size == b.size, true);  	BOOST_CHECK_EQUAL(b.size == c.size, true);  	iterator ita = a.begin();  	iterator itb = b.begin();  	iterator itc = c.begin();  	iterator finish = a.end();  	while (ita != finish) {  		BOOST_CHECK_EQUAL(*ita == *itb, true);  		BOOST_CHECK_EQUAL(*itb == *itc, true);  		ita++;  		itb++;  		itc++;  	}  	ita = a.end();  	itb = b.end();  	itc = c.end();  	BOOST_CHECK_EQUAL(*ita == *itb, true);  	BOOST_CHECK_EQUAL(*itb == *itc, true);  }    // ITERATOR TESTS  BOOST_AUTO_TEST_CASE(iteratorBegin) {  	set a(0, nullptr);  	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.begin();  	BOOST_CHECK_EQUAL(*it == 0, true);  	for (int i = -10; i <= -1; i++) {  		a.insert(i);   	}  	it = a.begin();  	BOOST_CHECK_EQUAL(*it == -10, true);  }    BOOST_AUTO_TEST_CASE(iteratorEnd) {  	set a(0, nullptr);  	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.end();  	BOOST_CHECK_EQUAL(*it == 10, true);  	for (int i = 20; i >= 11; i--) {  		a.insert(i);   	}  	it = a.end();  	BOOST_CHECK_EQUAL(*it == 20, true);  }    BOOST_AUTO_TEST_CASE(operatorEqual) {  	set a(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}    	iterator it(a.find(3));  	iterator it1(a.find(3));  	BOOST_CHECK_EQUAL(it == it1, true);  }    BOOST_AUTO_TEST_CASE(operatorNotEqual) {  	set a(0, nullptr);  	set b(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   		b.insert(i);   	}    	iterator it = a.find(3);  	iterator it1 = a.find(5);  	BOOST_CHECK_EQUAL(it != it1, true);  	it = a.find(3);  	it1 = b.find(3);  	BOOST_CHECK_EQUAL(it != it1, true);  }    BOOST_AUTO_TEST_CASE(printIteratorWithStar) {  	set a(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.begin();  	BOOST_CHECK_EQUAL(*it == 0, true);  	it = a.end();  	BOOST_CHECK_EQUAL(*it == 10, true);  	it = a.find(7);  	BOOST_CHECK_EQUAL(*it == 7, true);  }    BOOST_AUTO_TEST_CASE(printIteratorWithoutStar) {  	set a(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.begin();  	BOOST_CHECK_EQUAL(it.it -> value == 0, true);  	it = a.end();  	BOOST_CHECK_EQUAL(it.it -> value == 10, true);  	it = a.find(7);  	BOOST_CHECK_EQUAL(it.it -> value == 7, true);  }    BOOST_AUTO_TEST_CASE(iteratorPlusPlus) {  	set a(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.begin();  	BOOST_CHECK_EQUAL(*it == 0, true);  	for (int i = 1; i<=10; i++) {  		it++;  		BOOST_CHECK_EQUAL(*it == i, true);  	}  }    BOOST_AUTO_TEST_CASE(plusPlusIterator) {  	set a(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.begin();  	BOOST_CHECK_EQUAL(*it == 0, true);  	for (int i = 1; i<=10; i++) {  		++it;  		BOOST_CHECK_EQUAL(*it == i, true);  	}  }    BOOST_AUTO_TEST_CASE(iteratorMinusMinus) {  	set a(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.end();  	BOOST_CHECK_EQUAL(*it == 10, true);  	for (int i = 9; i>=0; i--) {  		it--;  		BOOST_CHECK_EQUAL(*it == i, true);  	}  }    BOOST_AUTO_TEST_CASE(minusMinusIterator) {  	set a(0, nullptr);    	for (int i = 0; i <= 10; i++) {  		a.insert(i);   	}  	iterator it = a.end();  	BOOST_CHECK_EQUAL(*it == 10, true);  	for (int i = 9; i>=0; i--) {  		--it;  		BOOST_CHECK_EQUAL(*it == i, true);  	}  }