#ifndef MAP_H
#define MAP_H

#include <cassert>
#include <cstddef>

#define DISABLE_COPY(Class) \
	Class(const Class& other) = delete; \
	Class(Class&& other) = delete; \
	Class& operator=(const Class& other) = delete; \
	Class& operator=(Class&& other) = delete


namespace ecci
{

template <typename KeyType>
struct LessThan
{
	inline bool operator()(const KeyType& key1, const KeyType& key2) const
	{
		return key1 < key2;
	}
};

template <typename KeyType>
struct GreaterThan
{
	inline bool operator()(const KeyType& key1, const KeyType& key2) const
	{
		return key1 > key2;
	}
};

template <typename KeyType, typename ValueType, typename Comparator = LessThan<KeyType>>
class Map
{
  private:
	struct Node
	{
	  public:
		KeyType key;
		ValueType value;
		Node* parent;
		Node* left;
		Node* right;
		// ecci::Array<Node*> children; // n-ary tree

	  public:
		explicit Node(const KeyType& key = KeyType(), const ValueType& value = ValueType(),
			Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr )
		: key{key}
		, value{value}
		, parent{parent}
		, left{left}
		, right{right}
		{
		}

		DISABLE_COPY(Node);
//		Node(const Node& other) = delete; // = default
//		Node(Node&& other) = delete;
//		Node& operator=(const Node& other) = delete;
//		Node& operator=(Node&& other) = delete;

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

  private:
	size_t count;
	Node* root;

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

	DISABLE_COPY(Map);

	~Map()
	{
		delete root;
	}

	inline bool isEmpty() const
	{
		return this->root == nullptr;
	}

	inline size_t getCount() const
	{
		return this->count;
	}

	ValueType& operator[](const KeyType& key)
	{
//		Node* node = this->find(key);
//		if ( node == nullptr )
		Node* node = insert(key, ValueType());
		assert(node);
		return node->value;
	}
/*
	const ValueType& operator[](const KeyType& key) const
	{
		Node* node = this->find(key);
		assert(node);
		return node->value;
	}
*/
  public:
	class ConstIterator
	{
	  private:
		Node* current;

	  public:
		explicit ConstIterator(Node* current = nullptr)
			: current{current}
		{
		}

		ConstIterator(const ConstIterator& other) = default;
		ConstIterator(ConstIterator&& other) = default;
		~ConstIterator() = default;
		ConstIterator& operator=(const ConstIterator& other) = default;
		ConstIterator& operator=(ConstIterator&& other) = default;

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

		ConstIterator& operator++()
		{
			this->current = Map::findNextNode(this->current);
			return *this;
		}

		inline const KeyType& getKey() const
		{
			return this->current->key;
		}

		inline const ValueType& getValue() const
		{
			return this->current->value;
		}
	};

  public:
	ConstIterator constBegin() const
	{
		return ConstIterator( this->minimum(this->root) );
	}

	ConstIterator constEnd() const
	{
		return ConstIterator(nullptr);
	}

  private:
	Node* insert(const KeyType& key, const ValueType& value)
	{
		++this->count;
		if ( this->isEmpty() )
			return this->root = new Node(key, value);

		Node* current = this->root;
		while ( true )
		{
			Comparator comp;
			if ( comp(key, current->key) )
			{
				if ( current->left )
					current = current->left;
				else
					return current->left = new Node(key, value, current);
			}
			else if ( comp(current->key, key) )
			{
				if ( current->right )
					current = current->right;
				else
					return current->right = new Node(key, value, current);
			}
			else
			{
				--this->count;
				return current;
			}
		}

		assert(false);
		return nullptr;
	}

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

	static Node* findNextNode(Node* current)
	{
//		std::cerr << "findNextNode(Node* current)\n";
		Node* original = current;

		if ( current->right )
			return minimum(current->right);

		while ( current->parent && current == current->parent->right )
		{
			current = current->parent;
			if ( current->parent == nullptr )
				return nullptr;
		}

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

		return current == original ? nullptr : current;
	}
};

}


#endif // MAP_H