/*
 * KPL tree
 */

#pragma once

// tree_duplicate is a linked stack
#define KPL_TREE_HEADER(STRUCT_NAME) \
    struct STRUCT_NAME *tree_left, *tree_right, *tree_duplicate; \
    int32_t tree_height

/*
 * Recursive AVL saves 8 bytes per object (no need for parent pointer) and keeps the insertion and finding simple
 */
typedef struct _kpl_tree_node {
    KPL_TREE_HEADER(_kpl_tree_node);
} kpl_tree_node;

typedef enum : int32_t {
   KPL_TREE_TREE_HEIGHT_INIT = 1
} kpl_tree_enum;

/*
 * -1 search left, 1 search right, 0 found
 */
typedef int32_t kpl_tree_node_compare_fn(const void *node_a, const void *node_b);

typedef void kpl_tree_node_free_fn(void *node);

/*
 * KPL needs tree with insertion and find operations, deletion is not needed, all nodes are freed on tree free
 */
typedef struct {
    kpl_tree_node *root_node;
    kpl_tree_node_compare_fn *node_compare_fn;
    kpl_tree_node_free_fn *node_free_fn;
} kpl_tree;

#define KPL_TREE_INIT_STATIC(COMPARE_FN, FREE_FN) \
    (kpl_tree) { .root_node = NULL, .node_compare_fn = COMPARE_FN, .node_free_fn = FREE_FN }

inline void kpl_tree_init(kpl_tree *tree, kpl_tree_node_compare_fn node_compare_fn,
    kpl_tree_node_free_fn node_free_fn) {
    tree->root_node = NULL;
    tree->node_compare_fn = node_compare_fn;
    tree->node_free_fn = node_free_fn;
}

void kpl_tree_free(kpl_tree *tree);

/*
 * *find is stack allocated
 * NULL for not found
 */
void *kpl_tree_find(kpl_tree *tree, const void *find_node);

/*
 * *insert is heap allocated
 * All inserts succeed, duplicates are added to *tree_duplicate
 */
void kpl_tree_insert(kpl_tree *tree, void *insert_node);