#pragma once
#include <cassert>
#include <deque>
#include <iostream>
#include <algorithm>
#include <string>
/*
COPY OPERATOR/CONSTR-problems with destructor???
NO CONST RVALUE
NO RVALUE FUNCT
NO MOVE OPERATOR
NO CONST ITERS
NO OVERLOADING OPERATORS
NEED BALANCING
PROBLEMS WITH STL FUNCTIONS?
*/

namespace tiit {
	template <typename T>
	struct Node {
		Node(T v, Node* 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<T>* 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>* get_pointer() const {
				return pointer;
			}

		};


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

		void clear(Node<T>* node) {
			if (node) {
				clear(node->left);
				clear(node->right);
				delete node;
				size_--;
			}
		}
		Node<T>* find_node(const T& value) {
			Node<T>** current = &node_;
			while (*current != nullptr) {
				if (value < (*current)->value) {
					current = &(*current)->left;
				}
				else if (value > (*current)->value) {
					current = &(*current)->right;
				}
				else {
					return *current;
				}
			}
			return nullptr;
		}



	public:
		set() {
			this->node_ = nullptr;
		}
		~set() {
			clear(node_);
			node_ = nullptr;

		}
		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);
		}
		void insert(const T& value) {
			node_ = insert_private(node_, value);
		}

		void delete_node(const T& value) {
			Node<T>* node = find_node(value);
			Node<T>* node_par = node->parent;
			if (node_par->parent == nullptr && node_par->left == node) {
				clear(node);
				node_par->left = nullptr;
			}
			else if(node_par->parent == nullptr && node_par->right==node) {
				node_par->right = nullptr;
			}
			else {
				node_par->parent->left = nullptr;
				node_par->parent->right = nullptr;
			}

		}

		iterator min_element() {
			Node<T>* leftest = node_;
			while (leftest->left) {
				leftest = leftest->left;
			}
			return iterator(leftest);
		}
		iterator min_element() const {
			Node<T>* leftest = node_;
			while (leftest->left) {
				leftest = leftest->left;
			}
			return iterator(leftest);
		}
		iterator max_element() {
			Node<T>* rightest = node_;
			while (rightest->right) {
				rightest = rightest->right;
			}
			return iterator(rightest);
		}
		iterator max_element() const {
			Node<T>* rightest = node_;
			while (rightest->right) {
				rightest = rightest->right;
			}
			return iterator(rightest);
		}
		iterator begin() {
			return min_element();
		}
		iterator end() {
			return ++max_element();
		}
		iterator rbegin() {
			return max_element();
		}
		iterator rend() {
			return --min_element();
		}
		iterator begin() const {
			return min_element();
		}
		iterator end() const {
			return ++max_element();
		}

		iterator find(const T& value) {
			Node<T>* node = node_;
			while (node) {
				if (value < node->value) {
					node = node->left;
				}
				else if (value > node->value) {
					node = node->right;
				}
				else {
					return iterator(node);
				}
			}
			return end();
		}

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


		size_t size() {
			return	size_;
		}

		size_t count_lists() {
			size_t result = 0;
				for (auto x = begin(); x != end();x++) {
				if (x.get_pointer()->left == nullptr && x.get_pointer()->right == nullptr) {
					result++;
				}
			}
			return result;
		}


		void erase(iterator iter) {
			auto it = iter.get_pointer();
			if (it == nullptr) {
				throw std::invalid_argument("no element");
			}
			if (it->left == nullptr && it->right == nullptr) {
				if (it->parent->left == it) {
					it->parent->left = nullptr;
				}
				if(it->parent->right == it) {
					it->parent->right = nullptr;
				}
				Node<T>* temp = it;
				it = nullptr;
				delete  temp;
				size_;
				return;
			}
			if (it->left == nullptr && it->right!=nullptr) {
				if (it->parent->left == it) {
					it->parent->left = it->right;
					it->right->parent = it->parent;
				}
				else if (it->parent->right == it) {
					it->parent->right = it->right;
					it->right->parent = it->parent;
				}
				Node<T>* temp = it;
				it = nullptr;
				delete  temp;
				size_;
				return;
			}
			if (it->left != nullptr && it->right == nullptr) {
				if (it->parent->left == it) {
					it->parent->left = it->left;
					it->left->parent = it->parent;
				}
				else if (it->parent->right == it) {
					it->parent->right = it->left;
					it->left->parent = it->parent;
				}
				Node<T>* temp = it;
				it = nullptr;
				delete  temp;
				size_;
				return;
			}
			if (it->left != nullptr && it->right != nullptr) {
				Node<T>* min=(++iter).get_pointer();
				it->value = min->value;
				erase(iterator(min));

			}
		}

		void PrintTree() {
			PrintTree_(node_, 0);
		}

		private:
		void PrintTree_(Node<T>* node,int level) {
			std::string str=" ";
			if (node) {
				PrintTree_(node->left, level + 1);
				for (int i = 0; i < level; i++) { str = str + " "; }
					str += std::to_string(node->value);
					std::cout << str<<std::endl;
				PrintTree_(node->right, level + 1);
			}
		}


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

}