#ifndef AVL_TREE_H
#define AVL_TREE_H

#include "../sys/sizes.h"

typedef struct avl_tree_node_t__ {
	i8                       balance_factor;
	struct avl_tree_node_t__ *parent;
	struct avl_tree_node_t__ *left;
	struct avl_tree_node_t__ *right;
	void                     *value;
} avl_tree_node_t;

/** DOC
 * @type typename
 * @name avl_tree_t
 *
 * @member avl_tree_node_t *root
 * @member u64             size
 * @member u8(*compare)(void*, void*)
 *
 * @description
 * This type describes the head of an `avl_tree_t`
 * It contains its `size` and holds its `root`.
 * Additionally it holds the `compare` function
 * which is used for having a custom order of elements.
 * To use the normal order for an `avl_tree_t` just holding
 * integers use the `<type>_compare` functions given by this header.
 */
typedef struct {
	avl_tree_node_t *root;
	u64 size;
	i8(*compare)(void*, void*);
	u8 free_value;
} avl_tree_t;

avl_tree_t *new_avl_tree(i8(*compare)(void*, void*), u8 free_value);
void       free_avl_tree(avl_tree_t *tree);
void       *avl_tree_search(avl_tree_t *tree, void *value);
void       avl_tree_insert(avl_tree_t *tree, void *value);
void       avl_tree_remove(avl_tree_t *tree, void *value);

i8 u8_compare(void*, void*);
i8 i8_compare(void*, void*);
i8 u16_compare(void*, void*);
i8 i16_compare(void*, void*);
i8 u32_compare(void*, void*);
i8 i32_compare(void*, void*);
i8 u64_compare(void*, void*);
i8 i64_compare(void*, void*);

#endif