#ifndef prototype1_src_l1_5_codegen_rbtree_set_map_template_inst_h
#define prototype1_src_l1_5_codegen_rbtree_set_map_template_inst_h

#include "all_set_map_templ_util_inst.h"

NODISCARD VecU8 codegen_rbtree__node_struct_name(map_instantiation_op op){
    return (op.V.len > 0) ? VecU8_fmt("RBTreeNode_KVP%sTo%s", op.K, op.V) : VecU8_fmt("RBTreeNode_%s", op.K);
}

NODISCARD VecU8 codegen_rbtree__node_structure(map_instantiation_op op){
    map_instantiation_op_fix(&op);
    VecU8 node_g = codegen_rbtree__node_struct_name(op);
    SpanU8 node = VecU8_to_span(&node_g);
    VecU8 res =  VecU8_fmt(
        "typedef struct {\n"
        SPACE "RBTreeNode base;\n"
        SPACE "%s key;\n"           /* op.K*/
        "%v"                          /* "" / op.V value; */
        "} %s;\n\n",                /* node */
        op.K, op.V.len > 0 ? VecU8_fmt(SPACE "%s value;\n", op.V) : vcstr(""),
        node);
    VecU8_drop(node_g);
    return res;
}


NODISCARD VecU8 codegen_rbtree_map__exp_passing_cur_key(map_instantiation_op op){
    return VecU8_fmt("%s" "((%v*)cur)->key", op.k_integer ? cstr("") : cstr("&"), codegen_rbtree__node_struct_name(op));
}

void codegen_append_rbtree_map__structure_and_simplest_methods(
    VecU8* res, map_instantiation_op op, SpanU8 set, SpanU8 TT
    ){
    VecU8_append_vec(res, VecU8_fmt(
        "typedef struct {\n"
        SPACE "RBTreeNode* root;\n"
        SPACE "RBTreeNode* NIL;\n"
        "%v"                             /* "" / guest field */
        "} %s;\n\n",
        op.guest_data_T.len == 0 ? vcstr("") : VecU8_fmt("%s guest;\n", op.guest_data_T),
        set));

    VecU8_append_vec(res, VecU8_fmt(
        "NODISCARD %s %s_new(" "%v" ") {\n"                           /* set, set, "" / GT guest */
        /* Only color field initialization is important (should be 0) */
        SPACE "RBTreeNode* NIL = (RBTreeNode*)safe_calloc(1, sizeof(RBTreeNode));\n"
        SPACE "return (%s){.root = NIL, .NIL = NIL" "%s" "};\n"              /* set, "" / , .guest = guest */
        "}\n\n",
        set, set, op.guest_data_T.len == 0 ? vcstr("") : VecU8_fmt("%s guest", op.guest_data_T),
        set, op.guest_data_T.len == 0 ? cstr("") : cstr(", .guest = guest")));

    // todo: figure out mutability restrictions crrp later
    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_min(const %s* self) {\n"                              /* TT, set, set */
        SPACE "if (self->root == self->NIL)\n"
        SPACE SPACE "return NULL;\n"
        SPACE "return (RBTreeNode_%s*)RBTreeNode_minimum_in_subtree(self->root, self->NIL);\n"  /* TT */
        "}\n\n", TT, set, set, TT));

    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_max(const %s* self) {\n"                              /* TT, set, set */
        SPACE "if (self->root == self->NIL)\n"
        SPACE SPACE "return NULL;\n"
        SPACE "return (RBTreeNode_%s*)RBTreeNode_maximum_in_subtree(self->root, self->NIL);\n"  /* TT */
        "}\n\n", TT, set, set, TT));

    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_next(const %s* self, RBTreeNode_%s* x){\n"                 /* TT, set, set, TT */
        SPACE "return (RBTreeNode_%s *)RBTreeNode_find_next((RBTreeNode*)x, self->NIL);\n"   /* TT */
        "}\n\n", TT, set, set, TT, TT));

    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_prev(const %s* self, RBTreeNode_%s* x){\n"                  /* TT, set, set, TT */
        SPACE "return (RBTreeNode_%s *)RBTreeNode_find_prev((RBTreeNode*)x, self->NIL);\n"    /* TT */
        "}\n\n", TT, set, set, TT, TT));

    /* Here we read and write something to ->left, ->right field of NIL sentinel node.
     * These fields are correct pointers (NULL), so everything is ok */
    VecU8_append_vec(res, VecU8_fmt(
        "void %s_drop(%s self){\n"                      /* set, set */
        SPACE "RBTreeNode* cur = self.root;\n"
        SPACE "while (cur != self.NIL){\n"
        SPACE SPACE "if (cur->left != self.NIL) {\n"
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE "} else if (cur->right != self.NIL) {\n"
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE "} else {\n"
                            /* This is actually safe, although cur->parent may be self.NIL */
        SPACE SPACE SPACE "if (cur->parent->left == cur)\n"
        SPACE SPACE SPACE SPACE "cur->parent->left = self.NIL;\n"
        SPACE SPACE SPACE "else"
        SPACE SPACE SPACE SPACE "cur->parent->right = self.NIL;\n"
        SPACE SPACE SPACE "RBTreeNode* parent = cur->parent;\n"
        "%v"         /* "" / tabulation op.K_drop((RBTreeNode_TT*)cur->key */
        "%v"         /* "" / tabulation op.V_drop((RBTreeNode_TT*)cur->value */
        SPACE SPACE SPACE "free((void*)cur);\n"
        SPACE SPACE SPACE "cur = parent;\n"
        SPACE SPACE "}\n"
        SPACE "}\n"
        SPACE "free(self.NIL);\n"
        "}\n\n", set, set,
        op.k_primitive ? vcstr("") : VecU8_fmt(SPACE SPACE SPACE "%s_drop(((RBTreeNode_%s*)cur)->key);\n", op.K, TT),
        op.v_primitive ? vcstr("") : VecU8_fmt(SPACE SPACE SPACE "%s_drop(((RBTreeNode_%s*)cur)->value);\n", op.V, TT)
        ));

    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find(const %s* self, %v key) {\n"               /* TT, set, set, taking_ref_k_argument */
        SPACE "RBTreeNode* cur = self->root;\n"
        SPACE "while (cur != self->NIL) {\n"
        SPACE SPACE "if (%v) {\n"  /* key < cur->key */
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE "} else if (%v) {\n"  /* cur->key < key */
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE "} else {\n"
        SPACE SPACE SPACE "return (RBTreeNode_%s*)cur;\n"               /* TT */
        SPACE SPACE "}\n"
        SPACE "}\n"
        SPACE "return NULL;\n"
        "}\n\n",
        TT, set, set, codegen_rbtree_map__taking_ref_k_argument(op),
        codegen_rbtree_map__less(op, vcstr("key"), codegen_rbtree_map__exp_passing_cur_key(op)),
        codegen_rbtree_map__less(op, codegen_rbtree_map__exp_passing_cur_key(op), vcstr("key")),
        TT));

    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_max_less(const %s* self, %v key) {\n"       /* TT, set, set, taking_ref_t_argument */
        SPACE "RBTreeNode_%s* last_less = NULL;\n"                          /* TT */
        SPACE "RBTreeNode* cur = self->root;\n"
        SPACE "while (cur != self->NIL) {\n"
        SPACE SPACE "if (%v) {\n"      /* key < cur->key */
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE "} else if (%v) {\n"       /* cur->key < key */
        SPACE SPACE SPACE "last_less = (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE "} else {\n"
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE SPACE "if (cur == self->NIL)\n"
        SPACE SPACE SPACE SPACE "return last_less;\n"
        SPACE SPACE SPACE "while (cur->right != self->NIL)\n"
        SPACE SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE SPACE "return (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE "}\n"
        SPACE "}\n"
        SPACE "return last_less;\n"
        "}\n\n",
        TT, set, set, codegen_rbtree_map__taking_ref_k_argument(op), TT,
        codegen_rbtree_map__less(op, vcstr("key"), codegen_rbtree_map__exp_passing_cur_key(op)),
        codegen_rbtree_map__less(op, codegen_rbtree_map__exp_passing_cur_key(op), vcstr("key")),
        TT, TT));

    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_max_less_or_eq(const %s* self, %v key) {\n"    /* TT, set, set, taking_ref_t_argument */
        SPACE "RBTreeNode_%s* last_less = NULL;\n"                          /* TT */
        SPACE "RBTreeNode* cur = self->root;\n"
        SPACE "while (cur != self->NIL) {\n"
        SPACE SPACE "if (%v) {\n"      /* key < cur->key */
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE "} else if (%v) {\n"       /* cur->key < key */
        SPACE SPACE SPACE "last_less = (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE "} else {\n"
        SPACE SPACE SPACE "return (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE "}\n"
        SPACE "}\n"
        SPACE "return last_less;\n"
        "}\n\n",
        TT, set, set, codegen_rbtree_map__taking_ref_k_argument(op), TT,
        codegen_rbtree_map__less(op, vcstr("key"), codegen_rbtree_map__exp_passing_cur_key(op)),
        codegen_rbtree_map__less(op, codegen_rbtree_map__exp_passing_cur_key(op), vcstr("key")),
        TT, TT));

    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_min_grtr(const %s* self, %v key) {\n"       /* TT, set, set, taking_ref_t_argument */
        SPACE "RBTreeNode_%s* last_grtr = NULL;\n"                          /* TT */
        SPACE "RBTreeNode* cur = self->root;\n"
        SPACE "while (cur != self->NIL) {\n"
        SPACE SPACE "if (%v) {\n"      /* key < cur->key */
        SPACE SPACE SPACE "last_grtr = (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE "} else if (%v) {\n"       /* cur->key < key */
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE "} else {\n"
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE SPACE "if (cur == self->NIL)\n"
        SPACE SPACE SPACE SPACE "return last_grtr;\n"
        SPACE SPACE SPACE "while (cur->left != self->NIL)\n"
        SPACE SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE SPACE "return (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE "}\n"
        SPACE "}\n"
        SPACE "return last_grtr;\n"
        "}\n\n",
        TT, set, set, codegen_rbtree_map__taking_ref_k_argument(op), TT,
        codegen_rbtree_map__less(op, vcstr("key"), codegen_rbtree_map__exp_passing_cur_key(op)),
        TT,
        codegen_rbtree_map__less(op, codegen_rbtree_map__exp_passing_cur_key(op), vcstr("key")),
        TT));


    VecU8_append_vec(res, VecU8_fmt(
        "RBTreeNode_%s* %s_find_min_grtr_or_eq(const %s* self, %v key) {\n"    /* TT, set, set, taking_ref_t_argument */
        SPACE "RBTreeNode_%s* last_grtr = NULL;\n"                          /* TT */
        SPACE "RBTreeNode* cur = self->root;\n"
        SPACE "while (cur != self->NIL) {\n"
        SPACE SPACE "if (%v) {\n"      /* key < cur->key */
        SPACE SPACE SPACE "last_grtr = (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE "} else if (%v) {\n"       /* cur->key < key */
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE "} else {\n"
        SPACE SPACE SPACE "return (RBTreeNode_%s*)cur;\n"                /* TT */
        SPACE SPACE "}\n"
        SPACE "}\n"
        SPACE "return last_grtr;\n"
        "}\n\n",
        TT, set, set, codegen_rbtree_map__taking_ref_k_argument(op), TT,
        codegen_rbtree_map__less(op, vcstr("key"), codegen_rbtree_map__exp_passing_cur_key(op)),
        TT,
        codegen_rbtree_map__less(op, codegen_rbtree_map__exp_passing_cur_key(op), vcstr("key")),
        TT));

    // todo: implement it like i deed in BufRBTree
    VecU8_append_vec(res, VecU8_fmt(
        /* This method is unsafe. Arguments key, value will be taken if 0 is returned,
         * or left on their place if not-0 is returned */
        "/* UNSAFE */\n"
        "NODISCARD RBTreeNode_%s* %s_try_insert(%s* self, %v) {\n"                 /* TT, set, set, taking_t_argument */
        SPACE "RBTreeNode** surprising = &self->root;\n"
        SPACE "RBTreeNode* prev = self->NIL;\n"
        SPACE "RBTreeNode* cur = self->root;\n"
        SPACE "while (cur != self->NIL){\n"
        SPACE SPACE "prev = cur;\n"
        SPACE SPACE "if (%v) {\n"         /* key < cur->key */
        SPACE SPACE SPACE "surprising = &cur->left;\n"
        SPACE SPACE SPACE "cur = cur->left;\n"
        SPACE SPACE "} else if (%v) {\n"    /* cur->key < key */
        SPACE SPACE SPACE "surprising = &cur->right;\n"
        SPACE SPACE SPACE "cur = cur->right;\n"
        SPACE SPACE "} else {\n"
        SPACE SPACE SPACE "return (RBTreeNode_%s *)cur;\n"                      /* TT */
        SPACE SPACE "}\n"
        SPACE "}\n"
        SPACE "RBTreeNode_%s* new_node = (RBTreeNode_%s *)safe_malloc(sizeof(RBTreeNode_%s));\n"  /* TT, TT, TT */
        SPACE "*new_node = (RBTreeNode_%s){ .base.parent = prev,\n"                                /* TT */
        SPACE SPACE ".base.left = self->NIL, .base.right = self->NIL, .base.color = RBTREE_RED,\n"
        SPACE SPACE ".key = key" "%s" "};\n"                                             /* "" / ,.value = value */
        SPACE "*surprising = (RBTreeNode*)new_node;\n"
        SPACE "RBTree_fix_after_insert(&self->root, self->NIL, (RBTreeNode*)new_node);\n"
        SPACE "return NULL;\n"
        "}\n\n",
        TT, set, set, codegen_rbtree_map__taking_t_argument(op),
        codegen_rbtree_map__less(op, codegen_rbtree_map__exp_passing_key_val(op), codegen_rbtree_map__exp_passing_cur_key(op)),
        codegen_rbtree_map__less(op, codegen_rbtree_map__exp_passing_cur_key(op), codegen_rbtree_map__exp_passing_key_val(op)),
        TT,
        TT, TT, TT,
        TT, op.V.len == 0 ? cstr("") : cstr(", .value = value")));

    VecU8_append_vec(res, VecU8_fmt(
        "bool %s_insert(%s* self, %v){\n"                                          /* set, set, taking_t_argument */
        SPACE "RBTreeNode_%s* col = %s_try_insert(self, key" "%s" ");\n"           /* TT, set, "" /, value */
        SPACE "if (col == NULL)\n"
        SPACE SPACE "return true;\n"
        "%v" "%v"                     /* "" / dropping key, "" / dropping value */
        SPACE "return false;\n"
        "}\n\n",
        set, set, codegen_rbtree_map__taking_t_argument(op),
        TT, set, op.V.len > 0 ? cstr(", value") : cstr(""),
        op.k_primitive ? vcstr("") : VecU8_fmt(SPACE "%s_drop(key);\n", op.K),
        op.v_primitive ? vcstr("") : VecU8_fmt(SPACE "%s_drop(value);\n", op.V)));

    VecU8_append_vec(res, VecU8_fmt(
        "void %s_erase_by_iter(%s* self, RBTreeNode_%s* it) {\n"            /* set, set, TT */
        SPACE "assert(it != NULL);\n"
        "%v"                                                                /* "" / op.K_drop(it->key) */
        "%v"                                                                /* "" / op.V_drop(it->value) */
        SPACE "RBTree_erase_empty_by_iter(&self->root, self->NIL, (RBTreeNode*)it);\n"
        SPACE "free(it);\n"
        "}\n\n",
        set, set, TT,
        op.k_primitive ? vcstr("") : VecU8_fmt(SPACE "%s_drop(it->key);\n", op.K),
        op.v_primitive ? vcstr("") : VecU8_fmt(SPACE "%s_drop(it->value);\n", op.V)));

    VecU8_append_vec(res, VecU8_fmt(
        "bool %s_erase(%s* self, %v key) {\n"               /* set, set, taking_ref_k_argument */
        SPACE "RBTreeNode_%s* v = %s_find(self, key);\n"    /* TT, set */
        SPACE "if (v == NULL)\n"
        SPACE SPACE "return false;\n"
        SPACE "%s_erase_by_iter(self, v);\n"                 /* set */
        SPACE "return true;\n"
        "}\n\n",
        set, set, codegen_rbtree_map__taking_ref_k_argument(op),
        TT, set, set));
}


NODISCARD VecU8 get_name_of_rbtree_set_structure(set_instantiation_op op){
    if (op.alternative_comp_set_name_embed.len > 0)
        return VecU8_fmt("RBTreeBy%s_Set%s", op.alternative_comp_set_name_embed, op.T);
    return VecU8_fmt("RBTree_Set%s", op.T);
}

NODISCARD VecU8 generate_rbtree_Set_template_instantiation(set_instantiation_op op, bool generate_node_struct){
    set_instantiation_op_fix(&op);
    map_instantiation_op map_op = {
        .K = op.T, .k_integer = op.t_integer, .k_primitive = op.t_primitive, .k_clonable = op.t_clonable,
        .V = cstr(""), .v_primitive = true, .v_clonable = true,
        .alternative_comp_map_name_embed = op.alternative_comp_set_name_embed, .alternative_less = op.alternative_less,
        .guest_data_T = op.guest_data_T
    };

    VecU8 res = VecU8_new();
    VecU8 set_g = get_name_of_rbtree_set_structure(op);
    if (generate_node_struct)
        VecU8_append_vec(&res, codegen_rbtree__node_structure(map_op));
    codegen_append_rbtree_map__structure_and_simplest_methods(&res, map_op, VecU8_to_span(&set_g), op.T);
    VecU8_drop(set_g);
    return res;
}

void generate_rbtree_Set_templ_inst_eve_header(SpanU8 layer, SpanU8 bonus_ns, set_instantiation_op op, bool generate_node_struct) {
    generate_SOME_templ_inst_eve_header(layer, bonus_ns,
        generate_rbtree_Set_template_instantiation(op, generate_node_struct), get_name_of_rbtree_set_structure(op));
}

void generate_rbtree_Set_templ_inst_guarded_header(
    SpanU8 layer, SpanU8 bonus_ns, SpanU8 dependencies, set_instantiation_op op, bool generate_node_struct
    ){
    VecU8 all_dependencies = VecU8_fmt("%v%s",
        codegen_include_relative_to_root(bonus_ns, cstr("src/l1_5/core/rb_tree_node.h")), dependencies);
    generate_SOME_templ_inst_guarded_header(layer, bonus_ns, all_dependencies,
        generate_rbtree_Set_template_instantiation(op, generate_node_struct), get_name_of_rbtree_set_structure(op));
}


/* Don't forget to do the map stuff, Set is not enough */

NODISCARD VecU8 get_name_of_rbtree_map_structure(map_instantiation_op op){
    if (op.alternative_comp_map_name_embed.len > 0)
        return VecU8_fmt("RBTreeBy%s_Map%sTo%s", op.alternative_comp_map_name_embed, op.K, op.V);
    return VecU8_fmt("RBTree_Map%sTo%s", op.K, op.V);
}

NODISCARD VecU8 generate_rbtree_Map_template_instantiation(map_instantiation_op op, bool generate_node_struct){
    map_instantiation_op_fix(&op);

    VecU8 res = VecU8_new();
    VecU8 map_g = get_name_of_rbtree_map_structure(op);
    SpanU8 map = VecU8_to_span(&map_g);
    VecU8 kvp_g = VecU8_fmt("KVP%sTo%s", op.K, op.V);
    SpanU8 kvp = VecU8_to_span(&kvp_g);

    if (generate_node_struct)
        VecU8_append_vec(&res, codegen_rbtree__node_structure(op));
    codegen_append_rbtree_map__structure_and_simplest_methods(&res, op, map, kvp);

    if (op.pop_substitute) {
        VecU8_append_vec(&res, VecU8_fmt(
            "%s" "Option%s %s_pop_substitute(%s* self, %s key, %s value) {\n"      /* "" / NODISCARD , op.V, map, map, op.K, op.V */
            /* Using unsafe method with conditional ownership transfer */
            SPACE "RBTreeNode_%s* col = %s_try_insert(self, key, value);\n"        /* kvp, map */
            SPACE "if (col == NULL) {\n"
            SPACE SPACE "return None_%s();\n"                                      /* op.V */
            SPACE "} else {\n"
            "%v"                     /* "" / dropping col->key */
            SPACE SPACE "%s saved = col->value;\n"                                 /* op.V */
            SPACE SPACE "col->key = key;\n"
            SPACE SPACE "col->value = value;\n"
            SPACE SPACE "return Some_%s(saved);\n"                                 /* op.V */
            SPACE "}\n"
            "}\n\n",
            op.v_primitive ? cstr("") : cstr("NODISCARD "), op.V, map, map, op.K, op.V,
            kvp, map, op.V,
            op.k_primitive ? vcstr("") : VecU8_fmt(SPACE SPACE"%s_drop(col->key);\n", op.K),
            op.V, op.V));
    }
    if (!op.v_primitive) {
        VecU8_append_vec(&res, VecU8_fmt(
            "bool %s_erase_substitute(%s* self, %s key, %s value) {\n"            /* map, map, op.K, op.V */
            SPACE "RBTreeNode_%s* col = %s_try_insert(self, key, value);\n"       /* kvp, map */
            SPACE "if (col == NULL)\n"
            SPACE SPACE "return true;\n"
            "%v" "%v"                               /* "" / op.K_drop(col->key), "" / op.V_drop(col->value) */
            SPACE "col->key = key;\n"
            SPACE "col->value = value;\n"
            SPACE "return false;\n"
            "}\n\n",
            map, map, op.K, op.V, kvp, map,
            op.k_primitive ? vcstr("") : VecU8_fmt(SPACE "%s_drop(col->key);\n", op.K),
            op.v_primitive ? vcstr("") : VecU8_fmt(SPACE "%s_drop(col->value);\n", op.V)));
    }

    if (op.pop){
        // todo: write _pop_by_it

        // todo: rewrite pop using _pop_by_it
        VecU8_append_vec(&res, VecU8_fmt(
            "Option%s %s_pop(%s* self, %v key) {\n"                           /* op.V, map, map, taking_ref_k_argument */
            SPACE "RBTreeNode_%s* v = %s_find(self, key);\n"                  /* kvp, map */
            SPACE "if (v == NULL)\n"
            SPACE SPACE "return None_%s();\n"                                 /* op.V */
            "%v"                                                              /* "" / op.K_drop(v->key) */
            "%s saved = v->value;\n"                                               /* op.V */
            SPACE "RBTree_erase_empty_by_iter(&self->root, self->NIL, (RBTreeNode*)v);\n"
            SPACE "free(v);\n"
            SPACE "return Some_%s(saved);\n"                                          /* op.V */
            "}\n\n",
            op.V, map, map, codegen_rbtree_map__taking_ref_k_argument(op),
            kvp, map, op.V,
            op.k_primitive ? vcstr("") : VecU8_fmt(SPACE "%s_drop(v->key);\n", op.K),
            op.V, op.V));
    }
    // todo: write generator for methods _at and _mat

    return res;
}

void generate_rbtree_Map_templ_inst_eve_header(SpanU8 layer, SpanU8 bonus_ns, map_instantiation_op op, bool generate_node_struct) {
    generate_SOME_templ_inst_eve_header(layer, bonus_ns,
        generate_rbtree_Map_template_instantiation(op, generate_node_struct), get_name_of_rbtree_map_structure(op));
}

void generate_rbtree_Map_templ_inst_guarded_header(
    SpanU8 layer, SpanU8 bonus_ns, SpanU8 dependencies, map_instantiation_op op, bool generate_node_struct
    ){
    VecU8 all_dependencies = VecU8_fmt("%v%s",
        codegen_include_relative_to_root(bonus_ns, cstr("src/l1_5/core/rb_tree_node.h")), dependencies);
    generate_SOME_templ_inst_guarded_header(layer, bonus_ns, all_dependencies,
        generate_rbtree_Map_template_instantiation(op, generate_node_struct), get_name_of_rbtree_map_structure(op));
}


#endif
