#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