namespace tiit {
	template <typename T>
	struct Node {
		Node(int v, Node<T>* p) :parent(p), value(v) {}

		T value;
		Node* left;
		Node* right;
		Node* parent;

	};

	template <typename T>
	class set {
	private:

		class iterator {
		private:
			Node<T>* pointer;
		public:
			iterator() {
				pointer = nullptr;
			}
			iterator(Node<T>* node) {
				pointer = node;
			}
			iterator(const iterator& it) {
				pointer = it.pointer;
			}

			iterator& operator=(const iterator& it) {
				pointer = it.pointer;
				return *this;
			}

			bool operator==(const iterator& it) const {
				return pointer == it.pointer;
			}

			bool operator!=(const iterator& it) const {
				return pointer != it.pointer;
			}
			iterator& operator++() {
				if (pointer->right) {
					pointer = pointer->right;
					while (pointer->left) {
						pointer = pointer->left;
					}
				}
				else {
					Node<T>* before;
					do {
						before = pointer;
						pointer = pointer->parent;
					} while (pointer && before == pointer->right);
				}
				return *this;
			}
			iterator& operator++(int) {
				iterator old(*this);
				++(*this);
				return old;
			}

			iterator& operator--() {
				if (pointer->left) {
					pointer = pointer->left;
					while (pointer->right) {
						pointer = pointer->right;
					}
				}
				else {
					Node* before;
					do {
						before = pointer;
						pointer = pointer->parent;
					} while (pointer && before == pointer->left);
				}
				return *this;
			}

			iterator operator--(int) {
				iterator old(*this);
				--(*this);
				return old;
			}



			T& operator*() const {
				return pointer->value;
			}


		};


		Node<T>* insert_private(Node<T>* node, const T& value);
		bool empty_private(Node<T>* node) {
			return node == nullptr ? true : false;
		}
		Node<T>* remove_min(Node<T>* node) {
			Node<T>* current = node;
			while (current->left != nullptr) {
				current = current->left;
			}
			return current;
		}

		Node<T>* remove(Node<T>* node, const  T& value);

	public:
		set() {
			this->node_ = nullptr;
		}
		~set() {
			while (!this->empty()) {
				this->node_ = remove(this->node_, this->node_->value);
			}
		}

		template<typename It>
		set(It begin, It end) {
			for (auto it = begin; it != end; it++) {
				insert(*it);
			}
		}
		void remove_element(const T& value) {
			remove(this->node_, value);
		}
		set(const set& tr) {
			*this = tr;
		}
		void insert(const T& value) {
			node_ = insert_private(node_, value);
		}
		iterator min_element()const  {
			Node<T>* leftest = node_;
			while (leftest->left) {
				leftest = leftest->left;
			}
			return iterator(leftest);
		}
		iterator max_element() const  {
			Node<T>* rightest = node_;
			while (rightest->right) {
				rightest = rightest->right;
			}
			return iterator(rightest);
		}
		iterator begin() {
			return min_element();
		}
		iterator begin() const {
			return min_element();
		}
		iterator end() {
			return ++max_element();
		}
		iterator end() const  {
			return ++max_element();
		}

		bool empty() {
			return empty_private(this->node_);
		}


		size_t size() const {
			return	size_;
		}
		bool operator<(const set& rhs) const  {
			if (this->size() != rhs.size()) {
				return this->size_ < rhs.size() ?true : false;
			}
			auto it1 = this->begin();
			auto it2 = rhs.begin();
			for (int i = 0; i < size_; i++) {
				return *it1 < *it2;
			}
		}
		bool operator>(const set& rhs) const {
			if (this->size() != rhs.size()) {
				return this->size_ > rhs.size() ? true : false;
			}
			auto it1 = this->begin();
			auto it2 = rhs.begin();
			for (int i = 0; i < size_; i++) {
				return *it1 > *it2;
			}
		}

	private:
		Node<T>* node_;
		size_t size_;
	};

	template<typename T>
	inline Node<T>* set<T>::insert_private(Node<T>* node, const T & value)
	{
		Node<T>** current = &node;
		Node<T>* parent = nullptr;
		while (*current != nullptr) {
			parent = *current;
			if (value < (*current)->value) {
				current = &(*current)->left;
			}
			else if (value > (*current)->value) {
				current = &(*current)->right;
			}
			else {
				return node;
			}
		}
		*current = new Node<T>(value, parent);
		(*current)->left = nullptr;
		(*current)->right = nullptr;
		size_++;
		return node;
	}

	template<typename T>
	inline Node<T>* set<T>::remove(Node<T>* node, const T & value)
	{
		if (node == nullptr) {
			return node;
		}
		if (value < node->value) {
			node->left = remove(node->left, value);
		}
		else if (value > node->value) {
			node->right = remove(node->right, value);
		}
		else {
			size_--;
			if (node->left == nullptr && node->right == nullptr) {
				Node<T>* temp = node;
				node = nullptr;
				delete temp;
			}
			else if (node->left == nullptr) {
				Node<T>* temp = node->right;
				*node = *temp;
				delete temp;

			}
			else if (node->right == nullptr) {
				Node<T>* temp = node->left;
				*node = *temp;
				delete temp;
			}
			else {
				Node<T>* temp = remove_min(node->right);
				node->value = temp->value;
				node->right = remove(node->right, temp->value);
			}
		}
	}

}