#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include <cstddef>

namespace ecci
{

template <typename DataType>
class BinarySearchTree
{
  private:
	struct Node
	{
		Node* parent;
		DataType data;
		Node* left;
		Node* right;

	  public:
		explicit Node(const DataType& data, Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr)
			: parent(parent), data(data), left(left), right(right)
		{
		}
	};

  private:
	Node* root;
	size_t count;

  public:
	class Iterator
	{
	   private:
		Node* node;

	   public:
		explicit Iterator(Node* node)
			: node(node)
		{
		}

		inline bool operator!=(const Iterator& other) const
		{
			return this->node != other.node;
		}

		DataType& operator*()
		{
			return node->data;
		}

		Iterator& operator++()
		{
			if ( node != nullptr )
			{
				if ( node->right )
				{
					node = minimum(node->right);
					return *this;
				}
				while ( node->parent != nullptr && node->parent->right == node )
				{
					node = node->parent;
					if ( node->parent == nullptr )
					{
						node = nullptr;
						return *this;
					}
				}
				if ( node->parent != nullptr && node->parent->left == node )
				{
					node = node->parent;
					return *this;
				}
				node = nullptr;
				return *this;
			}
			return *this;
		}
	};

	Iterator begin() { return Iterator(minimum(root)); }

	Iterator end() { return Iterator(nullptr); }

  public:
	BinarySearchTree() : root(nullptr), count(0)
	{
	}

	bool insert(const DataType& data)
	{
		if ( root == nullptr )
			root = new Node(data);
		else
		{
			Node* current = root;
			while ( current != nullptr )
			{
				if ( data < current->data )
				{
					if ( current->left == nullptr )
					{
						if ( ( current->left = new Node(data, current) ) == nullptr )
							return false;
						break;
					}
					else
						current = current->left;
				}
				else
				{
					if ( current->right == nullptr )
					{
						if ( ( current->right = new Node(data, current) ) == nullptr )
							return false;
						break;
					}
					else
						current = current->right;
				}
			}
		}

		++count;
		return true;
	}

  private:
	static Node* minimum(Node* node)
	{
		if ( node == nullptr )
			return nullptr;
		Node* current = node;
		while ( current->left )
			current = current->left;
		return current;
	}

};

} // namespace ecci

#endif // BINARYSEARCHTREE_H