#ifndef _ALV_TREE_H
#define _ALV_TREE_H
#define Max(a,b) (((a)>(b))?(a):(b))
#include <iostream>

template<class T>
class AVLTree
{
 struct _TreeNode;
 typedef struct _TreeNode TreeNode;
 struct _TreeNode
 {
  T data;
  int height;
  TreeNode* left;
  TreeNode* right;
 };

private:
 TreeNode *root;
public:
 AVLTree()
 {
  this->root=NULL;
 }

 ~AVLTree()
 {
  this->MakeEmpty(this->root);
 }

 int GeiHeight()
 {
  return this->GetHeightUtil(this->root);
 }

 void Insert(T data)
 {
  this->root=this->InsertUtil(this->root,data);
 }
 
 void Delete(T data)
 {
  this->root=this->DeleteUtil(this->root,data);
 }

 void Print()
 {
  /*if(root!=NULL)
  {
   std::cout<<"The root node is: "<<root->data<<std::endl;
  }*/
  for(int level=0;;level++)
  {
   if(this->PrintUtil(this->root,level)==0)
   {
    break;
   }
   std::cout<<std::endl;
  }
 }

private:
 TreeNode *InsertUtil(TreeNode *_root,T data)
 {
  if(_root==NULL)
  {
   _root=new TreeNode();
   _root->data=data;
   _root->left=0;
   _root->right=0;
   _root->height=0;
  }
  if(data>_root->data)
  {
   _root->right=this->InsertUtil(_root->right,data);
   if(GetHeightUtil(_root->right)-GetHeightUtil(_root->left)==2)
   {
    if(data>_root->right->data)
    {
     _root=this->SingleRotateWithRight(_root);
    }
    else
    {
     _root=this->DoubleRotateWithRight(_root);
    }
   }
  }
  else if(data<_root->data)
  {
   _root->left=this->InsertUtil(_root->left,data);
   if(GetHeightUtil(_root->left)-GetHeightUtil(_root->right)==2)
   {
    if(data<_root->left->data)
    {
     _root=this->SingleRotateWithLeft(_root);
    }
    else
    {
     _root=this->DoubleRotateWithLeft(_root);
    }
   }
  }
  _root->height=Max(GetHeightUtil(_root->left),GetHeightUtil(_root->right))+1;
  return _root;
 }

 TreeNode *DeleteUtil(TreeNode *_root,T data)
 {
  if(_root==NULL)
  {
   return _root;
  }
  else if(_root->data==data
   &&_root->left==NULL
   &&_root->right==NULL)
  {
   delete _root;
   return NULL;
  }
  else if(_root->data==data
   &&_root->left!=NULL
   &&_root->right==NULL)
  {
   TreeNode* tmpNode=_root->left;
   delete _root;
   tmpNode->height=this->RecalculateHeight(tmpNode);
   return tmpNode;
  }
  else if(_root->data==data
   &&_root->left==NULL
   &&_root->right!=NULL)
  {
   TreeNode *tmpNode=_root->right;
   delete _root;
   tmpNode->height=this->RecalculateHeight(tmpNode);
   return tmpNode;
  }
  else
  {
   if(data==_root->data)
   {
    TreeNode *tmpNode,*parentNode;
    tmpNode=_root->right->right;
    parentNode=_root->right;
    if(tmpNode!=NULL)
    {
     while(tmpNode->right!=NULL)
     {
      parentNode->height-=1;
      parentNode=tmpNode;
      tmpNode=tmpNode->right;
     }
     parentNode->right=NULL;
     _root->data=tmpNode->data;
     delete tmpNode;
    }
    else
    {
     _root=parentNode;
    }
    _root->height=this->RecalculateHeight(_root);
    //TreeNode *tmpNode=this->FindMax(_root->right);
    //_root->data=tmpNode->data;
    if(GetHeightUtil(_root->left)-GetHeightUtil(_root->right)==2)
    {
     if(_root->left->left!=NULL)
     {
      _root=this->SingleRotateWithLeft(_root);
     }
     else if(_root->left->right!=NULL)
     {
      _root=this->DoubleRotateWithLeft(_root);
     }
    }
   }
   else
   if(data>_root->data)
   {
    _root->right=this->DeleteUtil(_root->right,data);
    _root->height=this->RecalculateHeight(_root);
    if(GetHeightUtil(_root->left)-GetHeightUtil(_root->right)==2)
    {
     if(_root->left->left!=NULL)
     {
      _root=this->SingleRotateWithLeft(_root);
     }
     else if(_root->left->right!=NULL)
     {
      _root=this->DoubleRotateWithLeft(_root);
     }
    }
   }
   else
   {
    _root->left=this->DeleteUtil(_root->left,data);
    _root->height=this->RecalculateHeight(_root);
    if(GetHeightUtil(_root->right)-GetHeightUtil(_root->left)==2)
    {
     if(_root->right->right!=NULL)
     {
      _root=this->SingleRotateWithRight(_root);
     }
     else if(_root->right->left!=NULL)
     {
      _root=this->DoubleRotateWithRight(_root);
     }
    }
   }
  }
  //_root->height=this->RecalculateHeight(_root);
  return _root;
 }

 void MakeEmpty(TreeNode *_root)
 {
  if(_root==NULL)
  {
   return;
  }
  else
  {
   MakeEmpty(_root->left);
   MakeEmpty(_root->right);
   delete _root;
  }
 }

 int GetHeightUtil(TreeNode *_root)
 {
  /*if(_root==NULL|| (_root->left==NULL && _root->right==NULL))
  {
   return 0;
  }
  else
  {
   return 1+GetHeightUtil(_root->left)+GetHeightUtil(_root->right);
  }*/
  if(_root==NULL)
  {
   return -1;
  }
  else
  {
   return _root->height;
  }
 }

 int PrintUtil(TreeNode *node, int level)
 {
  if(node==NULL||level<0)
  {
   return 0;
  }
  else
  {
   if(level==0)
   {
    std::cout<<node->data<<" ";
    return 1;
   }
   return PrintUtil(node->left,level-1)+PrintUtil(node->right,level-1);
  }
 }

 TreeNode *SingleRotateWithLeft(TreeNode *node)
 {
  TreeNode *tmpNode=node->left;
  node->left=tmpNode->right;
  tmpNode->right=node;
  node->height=Max(GetHeightUtil(node->left),GetHeightUtil(node->right))+1;
  tmpNode->height=Max(GetHeightUtil(tmpNode->left),GetHeightUtil(tmpNode->right))+1;
  return tmpNode;
 }

 TreeNode*SingleRotateWithRight(TreeNode *node)
 {
  TreeNode *tmpNode=node->right;
  node->right=tmpNode->left;
  tmpNode->left=node;
  node->height=Max(GetHeightUtil(node->left),GetHeightUtil(node->right))+1;
  tmpNode->height=Max(GetHeightUtil(tmpNode->left),GetHeightUtil(tmpNode->right))+1;
  return tmpNode;
 }

 TreeNode* DoubleRotateWithLeft(TreeNode *node)
 {
  node->left=this->SingleRotateWithRight(node->left);
  return this->SingleRotateWithLeft(node);
 }

 TreeNode* DoubleRotateWithRight(TreeNode *node)
 {
  node->right=this->SingleRotateWithLeft(node->right);
  return this->SingleRotateWithRight(node);
 }

 TreeNode* FindMax(TreeNode *node)
 {
  //T maxData;
  while(node!=NULL&&node->right!=NULL)
  {
   node=node->right;
  }
  //maxData=node->data;
  return node;
 }

 int RecalculateHeight(TreeNode *node)
 {
  if(node==NULL)
  {
   return -1;
  }
  else
  {
   node->height=Max(RecalculateHeight(node->left),RecalculateHeight(node->right))+1;
   return node->height;
  }
 }
};

#endif