#ifndef Map_h
#define Map_h

#include <cstddef>

namespace ecci
{

template <class DataType>
struct Less
{
	inline bool operator()(const DataType& v1, const DataType& v2)
	{
		return v1 < v2;
	}
};

template <class DataType>
struct Greater
{
	inline bool operator()(const DataType& v1, const DataType& v2)
	{
		return v1 > v2;
	}
};

template <typename Key, typename Value, typename Comparator = Less<Key>>
class Map
{
  private:
	struct Node
	{
		Key key;
		Value value;
		Node* parent;
		Node* left;
		Node* right;

		Node(const Key& key, const Value& value, Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr)
			: key(key)
			, value(value)
			, parent(parent)
			, left(left)
			, right(right)
		{
		}
	};

  private:
	Node* root;
	size_t count;

  public:
	Map() : root(nullptr) , count(0) { }
	inline bool isEmpty() const { return root == nullptr; }
	void insert(const Key& key, const Value& value)
	{
		if ( isEmpty() )
			root = new Node(key, value);
		else
		{
			Node* current = root;
			bool inserted = false;
			while ( ! inserted )
			{
				Comparator comparator;
				if ( comparator(key, current->key) )
				{
					// left
					if ( current->left == nullptr )
						inserted = current->left = new Node(key, value, current);
					else
						current = current->left;
				}
				else
				{
					// right
					if ( current->right == nullptr )
						inserted = current->right = new Node(key, value, current);
					else
						current = current->right;
				}
			}
		}

		++count;
	}


  public:
	class ConstIterator
	{
	  private:
		Node* node;

	  public:
		explicit ConstIterator(Node* node = nullptr) : node(node) { }
		inline bool operator==(const ConstIterator& other) const { return node == other.node; }
		inline bool operator!=(const ConstIterator& other) const { return ! (*this == other); }
		inline const Key& getKey() const { return node->key; }
		inline const Value& getValue() const { return node->value; }
		ConstIterator& operator++()
		{
			if ( node )
				node = Map::findNextNode(node);
			return *this;
		}
	};

	ConstIterator constBegin() const { return ConstIterator( minimum(root) ); }
	ConstIterator constEnd() const { return ConstIterator(nullptr); }

  private:
	static Node* findNextNode(Node* node)
	{
		Node* original = node;

		// The next node must be greater than this and should be in the right subtree
		if ( node->right )
			return minimum(node->right);

		// This node does not have a right subtree, if this node is the right child of its parent
		// this is the greatest child of the parent. Climb to the parent, and repeat this if the
		// parent is also the last child of the grand parent, and so on
		while ( node->parent && node->parent->right == node )
		{
			node = node->parent;

			// We climbed, if we reached the root by the right side, we are at the greatest node
			// and there are not a next node, stop here
			if ( node->parent == nullptr )
				return nullptr;
		}

		// If this node is the left child of its parent, the next node is its parent
		if ( node->parent && node->parent->left == node )
			node = node->parent;

		// If we do not find a next node, stop traversing the tree
		return original == node ? nullptr : node;
	}

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

} // namespace ecci

#endif // Map_h