#ifndef AVL_TREE_HPP_INCLUDED
#define AVL_TREE_HPP_INCLUDED

#include <algorithm>

#include "exceptions.hpp"


//
// AVL fa osztály
// DEFINÍCIÓ
//
template<class T>
class avl_tree
{
   // Belső csúcs struktúra
   struct node
   {
       node *parent;
       node *left, *right;
       int height;
       T key;

       node(const T& k, node *p)
           : parent(p), left(0), right(0), height(1), key(k) {}
   };

   // Adattag
   node *root;

   // Felszabadító függvény
   void _destroy(node *x);

   // Segédfüggvények
   node *_min(node *x) const;
   node *_max(node *x) const;
   node *_next(node *x) const;
   node *_prev(node *x) const;

   size_t _size(node *x) const;

   // Kiegyensúlyozásért felelős függvények
   int _get_height(node *x) const
   {
       return (x == 0) ? 0 : x->height;
   }

   void _update_height(node *x)
   {
       x->height = std::max(_get_height(x->left), _get_height(x->right)) + 1;
   }

   void _rotate_left(node *x);
   void _rotate_right(node *x);

   void _rebalance(node *x);

   // Ellenőrző segédfüggvény
   void _validate_avl(node *x) const;

public:
   // Konstruktor és destruktor
   avl_tree() : root(0) {}
   ~avl_tree()
   {
       _destroy(root);
   }

   // Másoló konstruktor és operátor egyelőre nincs implementálva
   avl_tree(const avl_tree& t)
   {
       throw copy_not_implemented();
   }
   avl_tree& operator=(const avl_tree& t)
   {
       throw copy_not_implemented();
   }

   // Alapműveletek
   size_t size() const
   {
       return _size(root);
   }

   bool find(const T& k) const;
   void insert(const T& k);
   void remove(const T& k);

   // Ellenőrző függvény
   void validate() const;
};

//
// AVL fa osztály
// FÜGGVÉNYIMPLEMENTÁCIÓK
//

// Rekurzívan felszabadítja a csúcsokat.
// A destruktor hívja meg a gyökérre.
template<class T>
void avl_tree<T>::_destroy(node *x)
{
   if (x != 0)
   {
       _destroy(x->left);
       _destroy(x->right);
       delete x;
   }
}

// Visszaadja az x gyökerű részfa legkisebb értékű csúcsát.
// Előfeltétel: x != nil
template<class T>
typename avl_tree<T>::node *avl_tree<T>::_min(node *x) const
{
   while (x->left != 0)
       x = x->left;
   return x;
}

// Visszaadja az x gyökerű részfa legnagyobb értékű csúcsát.
// Előfeltétel: x != nil
template<class T>
typename avl_tree<T>::node *avl_tree<T>::_max(node *x) const
{
   while (x->right != 0)
       x = x->right;
   return x;
}

// Visszaadja a fából az x csúcs rákövetkezőjét,
// vagy nil-t, ha x az legnagyobb kulcsú elem.
// Előfeltétel: x != nil
template<class T>
typename avl_tree<T>::node *avl_tree<T>::_next(node *x) const
{
   if (x->right != 0)
       return _min(x->right);

   node *y = x->parent;
   while (y!=0 && x==y->right)
   {
       x = y;
       y = y->parent;
   }
   return y;
}

// Visszaadja a fából az x csúcs megelőzőjét,
// vagy nil-t, ha x az legkisebb kulcsú elem.
// Előfeltétel: x != nil
template<class T>
typename avl_tree<T>::node *avl_tree<T>::_prev(node *x) const
{
   if (x->left != 0)
       return _max(x->left);

   node *y = x->parent;
   while (y!=0 && x==y->left)
   {
       x = y;
       y = y->parent;
   }
   return y;
}

// Rekurzívan meghatározza, és visszaadja
// az x gyökerű részfa elemeinek számát.
// Megjegyzés: üres fára is működik -> 0-t ad vissza
template<class T>
size_t avl_tree<T>::_size(node *x) const
{
   if (x == 0)
       return 0;
   else
       return _size(x->left) + _size(x->right) + 1;
}

// Balra forgatás ...
// az x csúcs körül, illetve más szóhasználattal
// az x csúcs és a jobb gyereke közötti él mentén.
template<class T>
void avl_tree<T>::_rotate_left(node *x)
{
   node *y = x->right;
   if (y == 0)
       throw internal_error();

   x->right = y->left;

   if (y->left != 0)
       y->left->parent = x;

   y->parent = x->parent;

   if (x->parent != 0)
   {
       if (x == x->parent->left)
       {
           x->parent->left = y;
       }
       else
       {
           x->parent->right = y;
       }
   }
   else
   {
       root = y;
   }

   x->parent = y;
   y->left = x;
}
// Jobbra forgatás ...
// az x csúcs körül, illetve más szóhasználattal
// az x csúcs és a bal gyereke közötti él mentén.
template<class T>
void avl_tree<T>::_rotate_right(node *x)
{
node *y = x->left;
   if (y == 0)
       throw internal_error();
   x->left = y->right;

   if(y->right != 0)
   y->right->parent = x;

   y->parent = x->parent;

   if(x->parent != 0)
   {
       if (x = x->parent->left)
       {
           x->parent->left = y;
       }
       else
       {
           x->parent->right = y;
       }
   }
   else
   {
       root = y;
   }

   x->parent = y;
   y->right = x;
}

// Az újrakiegyensúlyozó függvény
// ** Az AVL fa lelke **
//
// Miután a módosító műveletet (beszúrást vagy törlést) a bináris keresőfáknál
// tanult módon végrehajtottuk, ezt a függvényt kell meghívni a beszúrt, illetve
// az eltávolítottuk csúcs szülőjére, hogy a fában felfelé haladva frissítse a
// magasságinformációkat, és szükség esetén forgatásokkal helyreállítsa az AVL
// fa tulajdonságait.
//
// Pontos előfeltételek:
// x nil, vagy
// x mindkét részfája érvényes, kiegyensúlyozott AVL fa helyes magasságértékekkel
// (üres részfa is helyes AVL fa)
template<class T>
void avl_tree<T>::_rebalance(node *x)
{

}

// Lekérdezi, hogy található-e k kulcs a fában.
// Igazat ad vissza, ha található.
template<class T>
bool avl_tree<T>::find(const T& k) const
{
   node *x = root;
   while (x!=0 && !(k==x->key))
       if (k < x->key)
           x = x->left;
       else
           x = x->right;
   return x;
}

// Beszúrja a k értéket a fába.
// Ha már van k érték a fában, akkor nem csinál semmit.
template<class T>
void avl_tree<T>::insert(const T& k)
{
   // Keresés
   node *y = 0;
   node *x = root;
   while (x!=0 && !(k==x->key))
   {
       y = x;
       if (k < x->key)
           x = x->left;
       else
           x = x->right;
   }

   // Ha van már ilyen kulcsú elem a fában, úgy nincs dolgunk.
   if (x != 0)
       return;

   // Új csúcs létrehozása és bekötése
   x = new node(k, y);
   if (y == 0)
       root = x;
   else if (x->key < y->key)
       y->left = x;
   else
       y->right = x;

   // Beszúrás utáni kiegyensúlyozás
   _rebalance(y);
}

// Eltávolítja a k értéket a fából.
// Ha nem volt k érték a fában, akkor nem csinál semmit.
template<class T>
void avl_tree<T>::remove(const T& k)
{
   // Keresés
   node *z = root;
   while (z!=0 && !(k==z->key))
       if (k < z->key)
           z = z->left;
       else
           z = z->right;

   // Ha nincs ilyen kulcsú elem a fában, úgy nincs dolgunk.
   if (z == 0)
       return;

   // Csúcs kivágása a fából és felszabadítás
   node *y;
   if (z->left==0 || z->right==0)
       y = z;
   else
       y = _next(z);

   node *w = y->parent;

   node *x;
   if (y->left != 0)
       x = y->left;
   else
       x = y->right;

   if (x != 0)
       x->parent = y->parent;
   if (y->parent == 0)
       root = x;
   else if (y == y->parent->left)
       y->parent->left = x;
   else
       y->parent->right = x;

   if (y != z)
       z->key = y->key;
   delete y;

   // Törlés utáni kiegyensúlyozás
   _rebalance(w);
}

// Rekurzív segédfüggvény a validate() függvényhez
// Ellenőrzi, hogy az x gyökerű fára teljesülnek-e az AVL tulajdonságok.
template<class T>
void avl_tree<T>::_validate_avl(node *x) const
{
   if (x != 0)
   {
       _validate_avl(x->left);
       _validate_avl(x->right);

       if (x->height != std::max(_get_height(x->left), _get_height(x->right))+1)
           throw invalid_avl_tree();

       if (std::abs(_get_height(x->left) - _get_height(x->right)) > 1)
           throw invalid_avl_tree();
   }
}

// Ez a függvény a debuggolást segíti.
// Ellenőrzi, hogy a gyökérből elérhető fa érvényes
// bináris keresőfa, illetve érvényes AVL fa-e.
template<class T>
void avl_tree<T>::validate() const
{
   // Keresőfa tulajdonság ellenőrzése bejárással
   if (root != 0)
   {
       node *x = _min(root);
       T prev = x->key;
       x = _next(x);
       while (x)
       {
           if (prev >= x->key)
               throw invalid_binary_search_tree();
           prev = x->key;
           x = _next(x);
       }
   }

   // AVL fa tulajdonság ellenőrzése
   _validate_avl(root);
}


#endif // AVL_TREE_HPP_INCLUDED