#include <lib/algo/avl_tree.h>
#include <lib/monad.h>

#include <stddef.h>
#include <stdio.h>

// Get the height of an AVL node
uint8_t get_height(struct AVLNode* node)
{
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

// Get the Maximum Height between two
uint8_t max_height(uint8_t a, uint8_t b)
{
  return (a > b) ? a : b;
}

// Get the balance factor of a node
ssize_t get_balance_factor(struct AVLNode* node)
{
  if (node == NULL) {
    return 0;
  }
  return get_height(node->left) - get_height(node->right);
}

// Rotate an AVL node right
struct AVLNode* right_rotate(struct AVLNode* parent)
{
  struct AVLNode* child1 = parent->left;
  struct AVLNode* child2 = child1->right;

  child1->right = parent;
  parent->left = child2;

  parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1;
  child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1;
  return child1;
}

// Rotate an AVL node left
struct AVLNode* left_rotate(struct AVLNode* parent)
{
  struct AVLNode* child1 = parent->right;
  struct AVLNode* child2 = child1->left;

  child1->left = parent;
  parent->right = child2;

  parent->height = max_height(get_height(parent->left), get_height(parent->right)) + 1;
  child1->height = max_height(get_height(child1->left), get_height(child1->right)) + 1;
  return child1;
}

// In-order traversal print pointer
void print_in_order(struct AVLNode* root)
{
  if (root != NULL) {
    print_in_order(root->left);
    printf("%p ", root->data);
    print_in_order(root->right);
  }
}

// Free avl tree nodes starting at root
void free_avl_tree(struct AVLNode* root)
{
  if (root != NULL) {
    free_avl_tree(root->left);
    free_avl_tree(root->right);
    free(root);
  }
}

// Free avl tree and their data starting at root
void free_avl_tree_nodes(struct AVLNode* root)
{
  if (root != NULL) {
    free_avl_tree_nodes(root->left);
    free_avl_tree_nodes(root->right);
    if (root->data != NULL) {
      free(root->data);
    }
    free(root);
  }
}