#ifndef INC_LIB_ALGO_AVL_TREE_H
#define INC_LIB_ALGO_AVL_TREE_H

#include <lib/bool.h>
#include <lib/monad.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/types.h>

#define AvlHeight_t uint8_t

typedef bool_t (*AvlComparator)(void*, void*);

typedef struct AVLNode {
  void* data;
  AvlComparator compare;
  struct AVLNode* left;
  struct AVLNode* right;
  AvlHeight_t height;
} AVLNode;

// Get the height of an AVL node
AvlHeight_t get_height(AVLNode* node);

// Get the Maximum Height between two
AvlHeight_t max_height(AvlHeight_t a, AvlHeight_t b);

// Get the balance factor of a node
ssize_t get_balance_factor(AVLNode* node);

// Rotate an AVL node right
AVLNode* right_rotate(AVLNode* parent);

// Rotate an AVL node left
AVLNode* left_rotate(AVLNode* parent);

// Create AVL node
AVLNode* create_avl_node(void* data, AvlComparator compare);

// Insert data into AVL tree
Result avl_insert(AVLNode* node, void* data, AvlComparator compare);

// In-order traversal print pointer
void print_in_order(AVLNode* root);

// Free avl tree nodes starting at root
void free_avl_tree(AVLNode* root);

// Free avl tree and their data starting at root
void free_avl_tree_nodes(AVLNode* root);

#endif