/*
  @author Rohit Gupta
*/

#include <linux/avltree.h>
#include <linux/module.h>

static void left_avl_rotate(struct avl_node*nd,struct avl_root *root)
{
  struct avl_node*node=nd;
  struct avl_node*A = node->avl_right;
  struct avl_node*B = A->avl_left;
  A->avl_left = node;
  A->avl_parent = node->avl_parent;
  if(A->avl_parent==NULL)
    root->avl_node = A;
  else if(node == node->avl_parent->avl_left)
    A->avl_parent->avl_left = A;
  else
    A->avl_parent->avl_right = A;
  node->avl_parent = A; 
  node->avl_right = B;
  if(B!=NULL)
  B->avl_parent = node;
}

static void right_avl_rotate(struct avl_node*nd,struct avl_root *root)
{
  struct avl_node * node = nd;
  struct avl_node*A = node->avl_left;
  struct avl_node*B = A->avl_right;
  A->avl_right = node;
  A->avl_parent = node->avl_parent;
  if(A->avl_parent==NULL)
  root->avl_node = A;
  else if(node==A->avl_parent->avl_left)
    A->avl_parent->avl_left = A;
   else
   A->avl_parent->avl_right = A;
  node->avl_parent = A; 
  node->avl_left = B;
  if(B!=NULL)
  B->avl_parent = node;
}


void insert_avl_node(struct avl_node*node, struct avl_root *root)
{
    struct avl_node* B;

    /*Adjust balance factor that are affected after the insertion*/
    B=node;
    do
    {
      if((B->avl_parent)->avl_left==B)
      {
        B=B->avl_parent;
        B->balf-=1;
      }
      else
      {
        B=B->avl_parent;
        B->balf++;
      }
    }while(B->balf!=0 && B->balf<=1 && B->balf>=-1 && B!=root->avl_node);
    /*Balance factor adjustment ends here*/


    /*Balance the nodes if avl rule violated*/
    if(B->balf > 1) //Case 1 (++)
    {
      if((B->avl_right)->balf == 1) //case 1.1 (++ -> +)
      {
        /*
        Adjust balance factors so that the new balance factors for the nodes
        are the one generated after rotation. Perform rotation after this step.
        */
        B->balf = 0;
        (B->avl_right)->balf=0;
        /*rotate*/
        left_avl_rotate(B,root);
      }
      else if((B->avl_right)->balf==-1)  //case 1.1 (++ -> -)
      {
        struct avl_node * temp = (B->avl_right)->avl_left;
        /*
        Adjust balance factors so that the new balance factors for the nodes
        are the one generated after rotation. Perform rotation after this step.
          */
        if(temp->balf ==1)
        {
          (B->avl_right)->balf=0;
          B->balf = -1;
        }
        else if(temp->balf == -1)
        {
          B->balf = 0;
          (B->avl_right)->balf = 1;
        }
        else if(temp->balf == 0)
        {
          B->balf = 0;
          (B->avl_right)->balf = 0;
        }
        temp->balf = 0;
        /*rotate*/
        right_avl_rotate((B->avl_right),root);
        left_avl_rotate(B,root);
      }
    }
    else if(B->balf < -1)  //Case 2 (--)
    {
      if((B->avl_left)->balf == -1) //case 2.1 (-- -> -)
      {
        /*
        Adjust balance factors so that the new balance factors for the nodes
        are the one generated after rotation. Perform rotation after this step.
          */
        B->balf = 0;
        (B->avl_left)->balf = 0;
        /*Rotate*/
        right_avl_rotate(B,root);
      }
      else if((B->avl_left)->balf==1)  //case 2.2 (-- -> +)
      {
        struct avl_node * temp = (B->avl_left)->avl_right;
        /*
        Adjust balance factors so that the new balance factors for the nodes
        are the one generated after rotation. Perform rotation after this step.
          */
        if(temp->balf ==1)
        {
          B->balf=0;
          (B->avl_left)->balf = -1;
        }
        else if(temp->balf == -1)
        {
          B->balf = -1;
          (B->avl_left)->balf = 0;
        }
        else if(temp->balf == 0)
        {
          B->balf = 0;
          (B->avl_left)->balf = 0;
        }
        temp->balf = 0;
        /*Rotate*/
        left_avl_rotate((B->avl_left),root);
        right_avl_rotate(B,root);
      }
    }
  }
EXPORT_SYMBOL(insert_avl_node);

void delete_avl_node(struct avl_node *node, struct avl_root *root)
{
  struct avl_node *temp = node,*temp1=NULL,*temp2=NULL,*B=NULL,*A=NULL;
  register int tbalf;
  if(temp->avl_left!=NULL && temp->avl_right!=NULL) 
  /*here the node has both valid children..
  therefore adjustment of the node, that is to be deleted, is done. Pointers manipulated*/
  {
    temp = temp->avl_right;
    while(temp->avl_left!=NULL) temp = temp->avl_left;

    if(temp == node->avl_right)
    {
      temp1 = node->avl_parent;
      temp2 = node->avl_left;

      node->avl_right = temp->avl_right;
      if(node->avl_right) node->avl_right->avl_parent = node;
      node->avl_left = temp->avl_left;
      if(node->avl_left) node->avl_left->avl_parent = node;

      node->avl_parent = temp;

      temp->avl_left = temp2;
      if(temp2)temp2->avl_parent = temp;
      temp->avl_right = node;
      temp->avl_parent = temp1;

      if(temp->avl_parent && temp->avl_parent->avl_right == node) 
        temp->avl_parent->avl_right = temp;
      else if(temp->avl_parent)
         temp->avl_parent->avl_left = temp;
       else root->avl_node = temp;

      tbalf = temp->balf;
      temp->balf = node->balf;
      node->balf = tbalf;
       temp = node; //
    }

    else
    {
      temp1 = node->avl_left;
      temp2 = node->avl_right;
      B=node->avl_parent;

      node->avl_right = temp->avl_right;
      if(node->avl_right) node->avl_right->avl_parent = node;
      node->avl_left = temp->avl_left;
      if(node->avl_left) node->avl_left->avl_parent = node;
      node->avl_parent = temp->avl_parent;
      node->avl_parent->avl_left = node;

      temp->avl_left = temp1;
      if(temp1) temp1->avl_parent = temp;
      temp->avl_right = temp2;
      if(temp2) temp2->avl_parent = temp;

      temp->avl_parent = B;
      if(B && B->avl_right == node) B->avl_right = temp;
      else if(B) B->avl_left = temp;
      else root->avl_node = temp;

      tbalf = temp->balf;
      temp->balf = node->balf;
      node->balf = tbalf;
       temp = node; //
    }
  }

  temp1=NULL;temp2=NULL;B=NULL;

  if(temp->avl_left != NULL)
   temp1 = temp->avl_left;
  else
   temp1 = temp->avl_right;

   if(temp1!=NULL)
    temp1->avl_parent = temp->avl_parent;

  if(temp->avl_parent == NULL) //case: Deletion of root.. No change required
   root->avl_node = temp1;         //Entire avl_node's height decreases.. Terminate here. CH
  else
  {
    temp2=temp;
    while(temp2->avl_parent)
    {
      if((temp2->avl_parent)->balf == 0) //case: No balancing required. CH
      {
        if(temp2 == (temp2->avl_parent)->avl_left) (temp2->avl_parent)->balf++;
        else (temp2->avl_parent)->balf--;
        break;
      }

      else if((temp2->avl_parent)->balf == 1 && temp2==(temp2->avl_parent)->avl_right)//CH
      {
        (temp2->avl_parent)->balf = 0; //Case: No rotation.. Only change in bal factor
        temp2 = temp2->avl_parent;
      }

      else if((temp2->avl_parent)->balf == -1 && temp2==(temp2->avl_parent)->avl_left)//CH
      {
        (temp2->avl_parent)->balf = 0; //Case: No rotation.. Only change in bal factor
        temp2 = temp2->avl_parent;
      }

      else if((temp2->avl_parent)->balf == 1 && temp2==(temp2->avl_parent)->avl_left)
      {
         B=temp2->avl_parent;
         B->balf++;
         if((B->avl_right)->balf == 1) //case 1.1 (++ -> +) //CH
         {

          //Adjust balance factors so that the new balance factors for the nodes
          //are the one generated after rotation. Perform rotation after this step.

          B->balf = 0;
          (B->avl_right)->balf=0;
          //rotate
          temp2=B->avl_right;//In case of left rotate.. The node which takes position of B
          left_avl_rotate(B,root);
         }
         else if((B->avl_right)->balf==-1)  //case 1.2 (++ -> -) //CH
         {
           A = (B->avl_right)->avl_left;

           //Adjust balance factors so that the new balance factors for the nodes
           //are the one generated after rotation. Perform rotation after this step.

           if(A->balf ==1)
           {
             (B->avl_right)->balf=0;
             B->balf = -1;
           }
           else if(A->balf == -1)
           {
             B->balf = 0;
             (B->avl_right)->balf = 1;
           }
           else if(A->balf == 0)
           {
             B->balf = 0;
             (B->avl_right)->balf = 0;
           }
           A->balf = 0;
           //rotate
           right_avl_rotate((B->avl_right),root);
           temp2 = B->avl_right;// In case of left rotate.. The node which takes position of B
           left_avl_rotate(B,root);
        }
        else //CH
        {
          //Adjustment of Balance Factor required here.
          B->balf -= 1;
          B->avl_right->balf -= 1;
          left_avl_rotate(B,root);
          break;
        }
      }

      else if((temp2->avl_parent)->balf == -1 && temp2==(temp2->avl_parent)->avl_right)
      {
          B=temp2->avl_parent;
          B->balf--;
          if((B->avl_left)->balf == -1) //case 2.1 (-- -> -) //CH
          {

           // Adjust balance factors so that the new balance factors for the nodes
           // are the one generated after rotation. Perform rotation after this step.

            B->balf = 0;
            (B->avl_left)->balf = 0;
            //Rotate
            temp2 = B->avl_left; //In the case of right roatate.. The node which takes position of B
            right_avl_rotate(B,root);
          }
          else if((B->avl_left)->balf==1)  //case 2.2 (-- -> +) //CH
          {
            A = (B->avl_left)->avl_right;

            //Adjust balance factors so that the new balance factors for the nodes
            //are the one generated after rotation. Perform rotation after this step.

            if(A->balf ==1)
            {
              B->balf=0;
              (B->avl_left)->balf = -1;
            }
            else if(A->balf == -1)
            {
              B->balf = -1;
              (B->avl_left)->balf = 0;
            }
            else if(A->balf == 0)
            {
              B->balf = 0;
              (B->avl_left)->balf = 0;
            }
            A->balf = 0;
            //Rotate
            left_avl_rotate((B->avl_left),root);
            temp2 = B->avl_left;//In the case of right roatate.. The node which takes position of B
            right_avl_rotate(B,root);
          }
          else //CH
          {
            //Adjustment of balance factor required here.
            B->balf += 1;
            B->avl_left->balf += 1;
            right_avl_rotate(B,root);
            break;
          }
      }
    }
    //Delete the node...
    if(temp == (temp->avl_parent)->avl_left)
     (temp->avl_parent)->avl_left = temp1;
    else
     (temp->avl_parent)->avl_right = temp1;
  }
}
EXPORT_SYMBOL(delete_avl_node);

struct avl_node* avl_next(struct avl_node *node)
{
  if(node->avl_right!=NULL)
  {
    node = node->avl_right;
    while(node->avl_left !=NULL) node = node->avl_left;
   return node;
  }
  else
  {
    struct avl_node*y = node->avl_parent;
    while(y!=NULL && node == y->avl_right)
    {
      node = y;
      y = y->avl_parent;
    }
    return y;
  }
}
EXPORT_SYMBOL(avl_next);

struct avl_node* avl_prev(struct avl_node *node)
{
  if(node->avl_left!=NULL)
  {
    node = node->avl_left;
    while(node->avl_right !=NULL) node = node->avl_right;
   return node;
  }
  else
  {
    struct avl_node*y = node->avl_parent;
    while(y!=NULL && node == y->avl_left)
    {
      node = y;
      y = y->avl_parent;
    }
    return y;
  }
}
EXPORT_SYMBOL(avl_prev);

struct avl_node *avl_first(struct avl_root *root)
{
  struct avl_node *n;
  n = root->avl_node;
  if (!n)
  return NULL;
  while (n->avl_left)
  n = n->avl_left;
  return n;
}
EXPORT_SYMBOL(avl_first);

struct avl_node *avl_last(struct avl_root *root)
{
  struct avl_node *n;
  n = root->avl_node;
  if (!n)
  return NULL;
  while (n->avl_right)
  n = n->avl_right;
  return n;
}
EXPORT_SYMBOL(avl_last);