#ifndef DICTIONARY_DICTIONARY_H
#define DICTIONARY_DICTIONARY_H

#include "CustomExceptions.h"

template <typename key, typename info>
class Dictionary {
	struct node {
		key id;
		info data;
		node* leftChild;
		node* rightChild;
		node(const key& key, const info& info) : id(key), data(info), leftChild(nullptr), rightChild(nullptr) {};
	} *root;
	node* insert(node* newNode, const key& newKey, const info& newInfo) {
		if (!newNode) {
			node* add = nullptr;
			try {
				add = new node(newKey, newInfo);
			}
			catch (std::wrong_alloc&ba) {
				std::cout << std::endl << "Allocation memory failure." << std::endl;
				throw;
			}
			return add;
		}
		if (newKey > newNode->id) {
			newNode->rightChild = insert(newNode->rightChild, newKey, newInfo);
		}
		else if (newKey < newNode->id) {
			newNode->leftChild = insert(newNode->leftChild, newKey, newInfo);
		}
		else if (newKey == newNode->id) {
			newNode->data = newInfo;
			return newNode;
		}
		return balance(newNode);
	}

	node* LeftLeftRotation(node* parent)
	{
		node* temp;
		temp = parent->leftChild;
		parent->leftChild = temp->rightChild;
		temp->rightChild = parent;
		return temp;
	}

	node* LeftRightRotation(node* parent)
	{
		node* temp;
		temp = parent->leftChild;
		parent->leftChild = RightRightRotation(temp);
		return LeftLeftRotation(parent);
	}

	node* RightLeftRotation(node* parent)
	{
		node* temp;
		temp = parent->rightChild;
		parent->rightChild = LeftLeftRotation(temp);
		return RightRightRotation(parent);
	}

	node* RightRightRotation(node* parent)
	{
		node* temp;
		temp = parent->rightChild;
		parent->rightChild = temp->leftChild;
		temp->leftChild = parent;
		return temp;
	}

	node* balance(node* n) {
		int balanceFactor = difference(n);
		if (balanceFactor > 1)
		{
			if (difference(n->leftChild) > 0)
				n = LeftLeftRotation(n);
			else
				n = LeftRightRotation(n);
		}
		else if (balanceFactor < -1)
		{
			if (difference(n->rightChild) > 0)
				n = RightLeftRotation(n);
			else
				n = RightRightRotation(n);
		}
		return n;
	}
	node* findMinimum(node* n) {
		if (!n) {
			return nullptr;
		}
		return n->leftChild ? findMinimum(n->leftChild) : n;
	}
	node* detachMinimum(node* n) {
		if (!n) {
			return nullptr;
		}
		if (!n->leftChild) {
			return n->rightChild;
		}
		n->leftChild = detachMinimum(n->leftChild);
		return balance(n);
	}
	node* remove(node* n, const key& Key) {
		if (!n) {
			throw notExistingKeyUsed();
		}
		if (Key < n->id) {
			n->leftChild = remove(n->leftChild, Key);
		}
		else if (Key > n->id) {
			n->rightChild = remove(n->rightChild, Key);
		}
		else {
			node* ln = n->leftChild;
			node* rn = n->rightChild;
			delete n;
			if (!rn) {
				return ln;
			}
			node* minimal = findMinimum(rn);
			minimal->rightChild = detachMinimum(rn);
			minimal->leftChild = ln;
			return balance(minimal);
		}
		return balance(n);
	}
	node* copy(node* n) {
		if (!n) {
			return nullptr;
		}
		node* temp = new node(n->id, n->data);
		temp->leftChild = copy(n->leftChild);
		temp->rightChild = copy(n->rightChild);
		return temp;
	}

	node* exist(node* n, const key& k) const {
		if (!n) {
			throw notExistingKeyUsed();
		}
		else {
			if (n->id == k) {
				return n;
			}
			else if (k < n->id) {
				return exist(n->leftChild, k);
			}
			else if (k > n->id) {
				return exist(n->rightChild, k);
			}
			else {
				throw notExistingKeyUsed();
			}
		}
	}
	void graph(node* n, int level) {
		if (!n) {
			std::cout << std::endl;
			return;
		}
		int i;
		graph(n->rightChild, level + 1);
		for (i = 0; i < level; ++i) {
			std::cout << '\t';
		}
		std::cout << n->id << '[' << n->data << ']' << std::endl;
		graph(n->leftChild, level + 1);
	}
	void clear(node* n) {
		if (!n) {
			return;
		}
		clear(n->leftChild);
		clear(n->rightChild);
		delete n;
	}
	void printInOrder(std::ostream& os, node* n) const {
		if (!n) {
			return;
		}
		printInOrder(os, n->leftChild);
		os << n->id << "/" << n->data << " ";
		printInOrder(os, n->rightChild);
	}
	int difference(node* n) {
		int leftHeight = height(n->leftChild);
		int rightHeight = height(n->rightChild);
		int balanceFactor = leftHeight - rightHeight;
		return balanceFactor;
	}

	int height(node* n) {
		int h = 0;
		if (n != nullptr)
		{
			int leftHeight = height(n->leftChild);
			int rightHeight = height(n->rightChild);
			int max_height = (leftHeight < rightHeight) ? rightHeight : leftHeight;
			h = max_height + 1;
		}
		return h;
	}
public:
	Dictionary() : root(nullptr) {};
	~Dictionary() {
		clear(root);
	}
	Dictionary(const Dictionary<key, info>& src) {
		root = copy(src.root);
	}
	Dictionary<key, info>& operator=(const Dictionary<key, info>& src) {
		if (this == &src) {
			return *this;
		}
		clear(root);
		if (src.root) {
			root = copy(src.root);
		}
		return *this;
	}
	const info& operator[](const key& k) const {
		node* index = nullptr;
		try {
			index = exist(root, k);
		}
		catch (notExistingKeyUsed& n) {
			std::cout << std::endl << n.what() << std::endl;
			throw;
		}
		return index->data;

	}
	friend std::ostream& operator<<(std::ostream& output, const Dictionary<key, info>& src) {
		src.printInOrder(output, src.root);
		return output;
	}
	void insert(const key& newKey, const info& newInfo) {
		if (!root) {
			root = new node(newKey, newInfo);
		}
		else {
			root = insert(root, newKey, newInfo);
		}
	}
	void remove(const key& key) {
		try
		{
			root = remove(root, key);
		}
		catch (notExistingKeyUsed& e)
		{
			std::cout << e.what() << std::endl;
			throw;
		}
	}
	void graph() {
		if (root) {
			graph(root, 1);
		}
		else {
			std::cerr << std::endl << "The tree is empty" << std::endl;
		}
	}
	void clear() {
		clear(root);
	}
	bool exist(const key& k) const {
		try {
			exist(root, k);
		}
		catch (notExistingKeyUsed& n) {
			return false;
		}
		return true;
	}
};
#endif //DICTIONARY_DICTIONARY_H