/*
 * AVLtree.cpp
 *
 *  Created on: 30.11.2012
 *      Author: trifon
 */

#include "tree.cpp"

template <typename K, typename V>
struct AVLNode
{
	K key;
	V value;
	int balance;
};

template <typename K, typename V>
ostream& operator<<(ostream& os, AVLNode<K, V> const& avlnode)
{
	os << '[' << avlnode.key << ',' << avlnode.value << ',';
	return os << avlnode.balance << ']';
}

template <typename K=int, typename V=int>
class AVLTree : public BinTree<AVLNode<K, V> >
{
	typedef AVLNode<K, V> T;

private:
	void createTree(T const&, BinTree<T >&, BinTree<T >& ) {}

	void rotateLeft(node<T>*& n)
	{
		node<T>* x = n;
		node<T>* y = x->right;
		x->right = y->left;
		y->left = x;
		n = y;
		if (y->inf.balance <= 0)
			x->inf.balance--;
		else
			x->inf.balance -= y->inf.balance + 1;
		if (x->inf.balance >= 0)
			y->inf.balance--;
		else
			y->inf.balance += x->inf.balance - 1;
	}

	void rotateRight(node<T>*& n)
	{
		node<T>* y = n;
		node<T>* x = y->left;
		y->left = x->right;
		x->right = y;
		n = x;
		if (x->inf.balance >= 0)
			y->inf.balance++;
		else
			y->inf.balance -= x->inf.balance - 1;
		if (y->inf.balance <= 0)
			x->inf.balance++;
		else
			x->inf.balance += y->inf.balance + 1;
	}

public:
	V* search(K const& key) const {
		BinTreeIterator<T> it = this->iterator();
		while (it && (*it).key != key)
		{
			if (key < (*it).key)
				it = ++it;
			else
				it = it++;
		}
		if (!it)
			return NULL;
		return &(*it).value;
	}

private:
	// 1, ако височината на дървото се е увеличила с 1
	// 0, ако височината на дървото не се е увеличила въпреки вмъкването
	// -1, ако елементът не е могъл да бъде вмъкнат
	int insertNode(node<T>*& n, K const& key, V const& value)
	{
		if (n == NULL)
		{
			n = new node<T>;
			n->left = n->right = NULL;
			n->inf.key = key;
			n->inf.value = value;
			n->inf.balance = 0;
			return 1;
		}
		if (n->inf.key == key)
			return -1;
		int res;
		if (key < n->inf.key)
		{
			// ще вмъкваме отляво
			res = insertNode(n->left, key, value);
			if (res == -1)
				return -1;
			if (res > 0)
			{
				n->inf.balance--;
				res = 0;
				if (n->inf.balance == -1)
					res = 1;
				else
					if (n->inf.balance == -2)
					{
						if (n->left->inf.balance == 1)
							rotateLeft(n->left);
						rotateRight(n);
					}
			}
		}
		else
		// key > n->inf.key
		{
			// ще вмъкваме отдясно
			res = insertNode(n->right, key, value);
			if (res == -1)
				return -1;
			if (res > 0)
			{
				n->inf.balance++;
				res = 0;
				if (n->inf.balance == 1)
					res = 1;
				else
					if (n->inf.balance == 2)
					{
						if (n->right->inf.balance == -1)
							rotateRight(n->right);
						rotateLeft(n);
					}
			}
		}
		return res;
	}

public:
	bool insert(K const& key, V const& value)
	{
		return insertNode(this->root, key, value) >= 0;
	}

private:
	// 1, ако височината на дървото се е намалила с 1
	// 0, ако височината на дървото не се е намалила въпреки изтриването
	// -1, ако елементът не е могъл да бъде изтрит
	int remove(node<T>*& n, K const& key)
	{
		// TODO
		return -1;
	}

public:
	bool remove(K const& key)
	{
		return remove(this->root, key) >= 0;
	}
};