#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

#include "Global.h"
#include <cstddef>
#include <iostream>

template <typename DataType>
class less
{
  public:
	bool operator()(const DataType& a, const DataType& b) const
	{
		return a < b ? a : b;
	}
};

template <typename DataType, typename Comparator = less<DataType> >
class BinarySearchTree
{
  private:
	class Node
	{
	  friend class BinarySearchTree;
	  private:
		DataType data;
		Node* parent;
		Node* left;
		Node* right;

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

		~Node()
		{
			delete left;
			delete right;
		}
	};

  private:
	Node* root;
	size_t elementCount;

  public:
	BinarySearchTree() : root(null), elementCount(0) { }
	~BinarySearchTree() { delete root; }
	inline size_t count() const { return elementCount; }
	/// @return true if the value was successfully inserted in the tree,
	/// false if not enough memory
	bool insert(const DataType& value)
	{
		Comparator comp;
		Node **node = &root, *parent = null;
		for ( ; *node; node = comp(value, (*node)->data) ? &(*node)->left : &(*node)->right )
			parent = *node;

		*node = new Node(value, parent);
		return *node ? ++elementCount : 0;
	}
	void clear()
	{
		delete root;
		root = null;
		elementCount = 0;
	}

	void print() const
	{
		print(root);
	}


  private:
	void print(Node* node) const
	{
		if ( ! node ) return;
		print(node->left);
		std::cout << node->data << ' ';
		print(node->right);
	}

	static Node* minimum(Node* node)
	{
		while ( node && node->left )
			node = node->left;
		return node;
	}

	static Node* findNextNode(Node* node)
	{
		if ( node->right )
			return minimum(node->right);

		while ( node->parent && node->parent->right == node )
		{
			node = node->parent;
			if ( ! node->parent ) return null;
		}

		if ( node->parent && node->parent->left == node )
			node = node->parent;

		return node;
	}

  public:
	class ConstIterator
	{
	  private:
		Node* ptr;
	  public:
		explicit ConstIterator(Node* ptr) : ptr(ptr) { }
		inline const DataType& operator*() const { return ptr->data; }
		inline bool operator==(const ConstIterator& other) const { return ptr == other.ptr; }
		inline bool operator!=(const ConstIterator& other) const { return ptr != other.ptr; }
		ConstIterator& operator++()
		{
			return moveToNextNode();
		}
		ConstIterator operator++(int)
		{
			ConstIterator result = *this;
			moveToNextNode();
			return result;
		}
	  private:
		ConstIterator& moveToNextNode()
		{
			if ( ! ptr ) return *this;
			Node* next = BinarySearchTree::findNextNode(ptr);
			ptr = ptr == next ? (Node*)null : next;
			return *this;
		}
	};

	ConstIterator begin() const
	{
		return ConstIterator( minimum(root) );
	}

	ConstIterator end() const { return ConstIterator(null); }
};

#endif // BINARYSEARCHTREE_H