/*
 * avl_tree.cpp
 *
 *  Created on: 19.12.2013
 *      Author: trifon
 */

#include "ordered_tree.cpp"

template <typename U>
struct AVLElement {
	U data;
	int balance;

	AVLElement(U const& _data = U(), int _balance = 0) :
		data(_data), balance(_balance) {}

	bool operator==(AVLElement const& avle) const {
		return data == avle.data;
	}
	bool operator<(AVLElement const& avle) const {
		return data < avle.data;
	}
	bool operator!=(AVLElement const& avle) const {
		return !(*this == avle);
	}
	bool operator<=(AVLElement const& avle) const {
		return *this == avle || *this < avle;
	}
	bool operator>(AVLElement const& avle) const {
			return !(*this <= avle);
	}
	bool operator>=(AVLElement const& avle) const {
			return !(*this < avle);
	}
};

template <typename U>
ostream& operator<<(ostream& os, AVLElement<U> const& avle) {
	return os << avle.data;
}

template <typename U>
class AVLTree : public OrderedTree<AVLElement<U> > {
private:
	typedef AVLElement<U> AVL;

	void rotateLeft(node<AVL>*& n) {
		node<AVL>* old = n;
		n = n->right;
		old->right = n->left;
		n->left = old;

		node<AVL>* x = old, *y = n;
		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<AVL>*& n) {
		node<AVL>* old = n;
		n = n->left;
		old->left = n->right;
		n->right = old;

		node<AVL>* x = n, *y = old;
		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;

	}

	/**
	 * -1, при грешка (т.е. елементът го има)
	 * 0, ако е вмъкнато успешно, но нямаме промяна
	 * във височината, заради пребалансиране
	 * 1, ако е вмъкнато успешно, но ИМАМЕ промяна
	 * във височината с 1
	 */
	// O(log n)
	int insertNode(node<AVL>*& n, U const& x) {
		if (n == NULL) {
			/*
			 * AVLElement<U> avle(x)
			 * n = new node(avle);
			 */
			n = new node<AVLElement<U> >(x);
			return 1;
		}
		if (n->inf.data == x)
			return -1;
		if (x < n->inf.data) {
			// ще вмъкваме в лявото поддърво
			int result = insertNode(n->left, x);
			if (result == 1) {
				n->inf.balance--;
				if (n->inf.balance == -2) {
					// ще трябва да въртим надясно
					// около корена
					// Но първо! да проверим дали
					// лявото е с баланс 1
					if (n->left->inf.balance == 1)
						// първо завъртаме лявото поддърво
						// наляво
						rotateLeft(n->left);
					rotateRight(n);
					// балансирахме дървото и височината,
					// която беше се увеличила с 1, сега се
					// върна до старата си стойност, затова:
					result = 0;
				}
			}
			return result;
		} else {
			// ще вмъкваме в дясното поддърво
			int result = insertNode(n->right, x);
			if (result == 1) {
				n->inf.balance++;
				if (n->inf.balance == 2) {
					// ще трябва да въртим наляво
					// около корена
					// Но първо! да проверим дали
					// дясното е с баланс -1
					if (n->right->inf.balance == -1)
						// първо завъртаме дясното поддърво
						// надясно
						rotateRight(n->right);
					rotateLeft(n);
					// балансирахме дървото и височината,
					// която беше се увеличила с 1, сега се
					// върна до старата си стойност, затова:
					result = 0;
				}
			}
			return result;
		}
	}

	/**
	 * -1, при грешка (т.е. елементът го има)
	 * 0, ако е изтрит успешно, но нямаме промяна
	 * във височината, заради пребалансиране
	 * 1, ако е изтрит успешно, но ИМАМЕ промяна
	 * във височината с 1
	 */
	// O(log n)
	int removeNode(node<AVL>*& n, U const& x) {
		return -1;
	}


public:

	// O(log n)
	U* search(U const& x) const {
		AVL avle(x);
		BinaryTreeIterator<AVL> it =
				OrderedTree<AVL>::search(avle);
		if (!it)
			return NULL;
		return &((*it).data);
	}

	bool insert(U const& x) {
		return insertNode(this->rootNode, x) >= 0;
	}

	bool remove(U const& x) {
		return removeNode(this->rootNode, x) >= 0;
	}
};