#include "avl_tree.h"

/* helper function to calculate balance factor */
int balance(avl_node *right, avl_node *left) {
  if(left == NULL && right == NULL)
    return 0;
  if(left == NULL)
    return right->height;
  if(right == NULL)
    return 0 - left->height;
  return right->height - left->height;
}

/*
 * Adds the character array into the AVL tree.  You will NOT malloc out 
 * data for the character array.  Simply store a reference to it.  Returns
 * the root of the tree after the add.  
 *
 * To create a new avl_tree you will simply add to a null tree.
 * Example:
 *  avl_tree *root = avl_add(NULL,"hello");
 */
avl_node *avl_add(avl_node *head,const char *data) {
  if(head == NULL) {
    if((head = malloc(sizeof(avl_node)))==NULL)
      DPRINTF((stderr,"malloc error in avl_add\n"));
    head->data = data;
    head->height = 1;
    head->left = NULL;
    head->right = NULL;
    return head;
  }
  if(strcmp(data,head->data) < 0)
    head->left = avl_add(head->left,data);
  if(strcmp(data,head->data) > 0)
    head->right = avl_add(head->right,data);
  if(head->left != NULL && head->left->height >= head->height)
    head->height = head->left->height + 1;
  if(head->right != NULL && head->right->height >= head->height)
    head->height = head->right->height + 1;
  if(balance(head->right,head->left) > 1) {
    if(balance(head->right->right,head->right->left) > 0)
      head = avl_left_rotate(head);
    else
      head = avl_right_left_rotate(head);
  }
  else if(balance(head->right,head->left) < -1) {
    if(balance(head->left->right,head->left->left) < 0)
      head = avl_right_rotate(head);
    else
      head = avl_left_right_rotate(head);
  }
  return head;
}

/*
 * Determines whether or not the avl tree contains the specified char*.  If
 * it does not it will return 0.  If it does it will return 1.
 */
int avl_has(avl_node *curr,const char *data) {
  if(curr == NULL)
    return 0;
  if(strcmp(curr->data,data) == 0)
    return 1;
  else
    return avl_has(curr->left,data) + avl_has(curr->right,data);
}

/* 
 * Delete a string from the avl tree.  The tree will remain balanced after 
 * this operation.  If the char* is not in the tree the structure should 
 * remain unchanged
 *
 * *** NOTE *** 
 * This function is optional.  No credit will be gained or lost as a 
 * result of coding this function.  It is fairly difficult when you can 
 * only consider the balance factor stored in the nodes.  However we 
 * encourage you to try it.  If you do not wish to code this function, 
 * just have it return the value passed in. 
 * ************
 */
avl_node *avl_delete(avl_node *root,const char *data) {
  return root;
}

/*
 * Performs a left rotation on the root node that is passed in and returns 
 * the new root node for the subtree.
 */
avl_node *avl_left_rotate(avl_node *head) {
  avl_node *tmp1 = head->right;
  avl_node *tmp2 = head->right->left;
  head->right->left = head;
  head->right = tmp2;
  head = tmp1;
  if(head->left->left != NULL)
    head->left->height = head->left->left->height + 1;
  if(head->left->right != NULL && head->left->right->height >= head->left->height)
    head->left->height = head->left->right->height + 1;
  head->height = head->left->height + 1;
  if(head->right->height >= head->height)
    head->height = head->right->height + 1;
  return head;
}

/*
 * Performs a right rotation on the root node that is passed in and returns
 * the new root node for the subtree.  This function must update the 
 * balance factors for the nodes involved.  
 */
avl_node *avl_right_rotate(avl_node *head) {
  avl_node *tmp1 = head->left;
  avl_node *tmp2 = head->left->right;
  head->left->right = head;
  head->left = tmp2;
  head = tmp1;
  if(head->right->right != NULL)
    head->right->height = head->right->right->height + 1;
  if(head->right->left != NULL && head->right->left->height >= head->right->height)
    head->right->height = head->right->left->height + 1;
  head->height = head->right->height + 1;
  if(head->left->height >= head->height)
    head->height = head->left->height + 1;
  return head;
}

/*
 * Performs a left right rotation on the root node that is passed in and 
 * returns the new root node for the subtree.  This function must update
 * the balance factor of the nodes involved.  
 */
avl_node *avl_left_right_rotate(avl_node *head) {
  head->left = avl_left_rotate(head->left);
  head = avl_right_rotate(head);
  return head;
}

/*
 * Performs a right left rotation on the root node that is passed in and 
 * returns the new root node for the subtree.  This function must update
 * the balance factor of the nodes involved. 
 */
avl_node *avl_right_left_rotate(avl_node *head) {
  head->right = avl_right_rotate(head->right);
  head = avl_left_rotate(head);
  return head;
}

/*
 * Frees all nodes in the avl tree and sets the node passed in to NULL
 */
void avl_free(avl_node** curr) {
  if(curr != NULL && *curr != NULL) {
    avl_free(&(*curr)->right);
    avl_free(&(*curr)->left);
    free(*curr);
    *curr = NULL;
  }
}

#ifdef DEBUG
int main() {
  avl_node *root = avl_add(NULL,"1");
  printf("%s\n",root->data);
  root = avl_add(root,"2");
  printf("%s\n",root->data);
  root = avl_add(root,"3");
  printf("%s\n",root->data);
  return 0;
}
#endif