#ifndef PROTOTYPE1_SRC_L1_5_CORE_RB_TREE_NODE_H
#define PROTOTYPE1_SRC_L1_5_CORE_RB_TREE_NODE_H

#include "../../l1/core/util.h"

typedef enum {
    RBTree_black = 0,
    RBTree_red = 1,
} RBTreeColor;

typedef struct {
    size_t left;
    size_t right;
    size_t parent;
    /* 0 is black, 1 is red */
    RBTreeColor color;
} BufRBTreeNode;

#include "../../../gen/l1/eve/embassy_l1_5/VecBufRBTreeNode.h"

void BufRBTree_left_rotate(BufRBTreeNode* tree, U64* root, U64 x){
    assert(x != 0);
    U64 y = tree[x].right;
    assert(y != 0);
    tree[x].right = tree[y].left;
    if (tree[x].right != 0)
        tree[tree[x].right].parent = x;

    tree[y].parent = tree[x].parent;
    if (tree[y].parent == 0) {
        *root = y;
    } else if (x == tree[tree[x].parent].left) {
        tree[tree[x].parent].left = y;
    } else {
        tree[tree[x].parent].right = y;
    }
    tree[x].parent = y;
    tree[y].left = x;
}

void BufRBTree_right_rotate(BufRBTreeNode* tree, U64* root, U64 x){
    assert(x != 0);
    U64 y = tree[x].left;
    assert(y != 0);
    tree[x].left = tree[y].right;
    if (tree[x].left != 0)
        tree[tree[x].left].parent = x;

    tree[y].parent = tree[x].parent;
    if (tree[y].parent == 0) {
        *root = y;
    } else if (x == tree[tree[x].parent].right) {
        tree[tree[x].parent].right = y;
    } else {
        tree[tree[x].parent].left = y;
    }
    tree[x].parent = y;
    tree[y].right = x;
}

/* Helper function. Called in automatically generated code */
void BufRBTree_fix_after_insert(BufRBTreeNode* tree, U64* root, U64 me){
    assert(me);
    while (true) {
        U64 mom = tree[me].parent;
        if (mom == 0)
            break;
        if (tree[mom].color == RBTree_black)
            return;
        U64 grandma = tree[mom].parent;
        U64 aunt = tree[grandma].left == mom ? tree[grandma].right : tree[grandma].left;
        assert(aunt != mom);
        if (tree[aunt].color == RBTree_red) {
            /* Easy case */
            tree[mom].color = RBTree_black;
            tree[aunt].color = RBTree_black;
            tree[grandma].color = RBTree_red;
            me = grandma;
        } else if (tree[grandma].left == mom) {
            /* Hard case: firstborn orientation */
            if (tree[mom].right == me) {
                BufRBTree_left_rotate(tree, root, mom);
                tree[me].color = RBTree_black;
            } else {
                tree[mom].color = RBTree_black;
            }
            BufRBTree_right_rotate(tree, root, grandma);
            tree[grandma].color = RBTree_red;
            return;
        } else {
            /* Hard case: benjamin orientation */
            if (tree[mom].left == me) {
                BufRBTree_right_rotate(tree, root, mom);
                tree[me].color = RBTree_black;
            } else {
                tree[mom].color = RBTree_black;
            }
            BufRBTree_left_rotate(tree, root, grandma);
            tree[grandma].color = RBTree_red;
            return;
        }
    }
    assert(*root == me);
    tree[me].color = RBTree_black;
}

/* fr index will be forgotten. to fields will be overwritten (all fields replaced by fr's values)
 * If you need the old values of `to` position, you better save them on stack */
void BufRBTree_steal_neighbours(BufRBTreeNode* tree, U64* root, U64 fr, U64 to){
    if (tree[fr].parent == 0)
        *root = to;
    else if (tree[tree[fr].parent].left == fr)
        tree[tree[fr].parent].left = to;
    else
        tree[tree[fr].parent].right = to;
    tree[tree[fr].left].parent = to;
    tree[tree[fr].right].parent = to;
    tree[to] = tree[fr];
}

/* helper function (used in _erase, _find_min methods). It is assumed that s is not null.
 * Guaranteed to return no-null
 */
U64 BufRBTree_minimum_in_subtree(const BufRBTreeNode* tree, U64 s){
    assert(s != 0);
    while (tree[s].left != 0)
        s = tree[s].left;
    return s;
}

/* helper function (used in _find_max, _find_prev methods). It is assumed that s is not null.
 * Guaranteed to return no-null
 */
U64 BufRBTree_maximum_in_subtree(const BufRBTreeNode* tree, U64 s){
    assert(s != 0);
    while (tree[s].right != 0)
        s = tree[s].right;
    return s;
}

void BufRBTree_fix_after_delete(BufRBTreeNode* tree, U64* root, U64 me){
    assert(tree[*root].parent == 0);
    while (me != *root && tree[me].color == RBTree_black) {
        U64 mom = tree[me].parent;
        if (me == tree[mom].left) { /* We are on the left */
            U64 sister = tree[mom].right;
            if (tree[sister].color == RBTree_red) { /* Case 1 */
                tree[mom].color = RBTree_red;
                tree[sister].color = RBTree_black;
                BufRBTree_left_rotate(tree, root, mom);
                /* Reassignation required */
                sister = tree[mom].right;
            }
            /* Cases 2,3,4 (every instance of red-black tree has an itchy substring in source code containing 2,3,4) */
            assert(sister != 0);
            U64 nephew_firstborn = tree[sister].left;
            U64 nephew_benjamin = tree[sister].right;
            if (tree[nephew_firstborn].color == RBTree_black && tree[nephew_benjamin].color == RBTree_black) {
                /* Case 2 */
                tree[sister].color = RBTree_red;
                me = mom;
                continue;
            }
            /* Cases 3,4 */
            if (tree[nephew_benjamin].color == RBTree_black) {
                /* Case 3 */
                tree[nephew_firstborn].color = RBTree_black;
                tree[sister].color = RBTree_red;
                BufRBTree_right_rotate(tree, root, sister);
                /* Reassignation required */
                nephew_benjamin = sister;
                sister = nephew_firstborn;
                nephew_firstborn = tree[sister].left;
            }
            /* Case 4 */
            tree[sister].color = tree[mom].color;
            tree[mom].color = RBTree_black;
            tree[nephew_benjamin].color = RBTree_black;
            BufRBTree_left_rotate(tree, root, mom);
            me = *root;
        } else if (me == tree[mom].right) { /* We are on the right */
            U64 sister = tree[mom].left;
            if (tree[sister].color == RBTree_red) { /* Case 1 */
                tree[mom].color = RBTree_red;
                tree[sister].color = RBTree_black;
                BufRBTree_right_rotate(tree, root, mom);
                /* Reassignation required */
                sister = tree[mom].left;
            }
            /* Cases 2,3,4 (every instance of red-black tree has an itchy substring in source code containing 2,3,4) */
            assert(sister != 0);
            U64 nephew_firstborn = tree[sister].left;
            U64 nephew_benjamin = tree[sister].right;
            if (tree[nephew_firstborn].color == RBTree_black && tree[nephew_benjamin].color == RBTree_black) {
                /* Case 2 */
                tree[sister].color = RBTree_red;
                me = mom;
                continue;
            }
            /* Cases 3,4 */
            if (tree[nephew_firstborn].color == RBTree_black) {
                /* Case 3 */
                tree[nephew_benjamin].color = RBTree_black;
                tree[sister].color = RBTree_red;
                BufRBTree_left_rotate(tree, root, sister);
                /* Reassignation required */
                nephew_firstborn = sister;
                sister = nephew_benjamin;
                nephew_benjamin = tree[sister].right;
            }
            /* Case 4 */
            tree[sister].color = tree[mom].color;
            tree[mom].color = RBTree_black;
            tree[nephew_firstborn].color = RBTree_black;
            BufRBTree_right_rotate(tree, root, mom);
            me = *root;
        }
    }
    tree[me].color = RBTree_black;
}

/* UNSAFE. Use when you dropped the symbol that is about to be deleted. Does not shrink the el vector,
 * do it yourself */
void BufRBTree_empty_index_erase(VecBufRBTreeNode* tree, U64* root, U64 z) {
    assert(z != 0 && z < tree->len);
    U64 y = (tree->buf[z].left == 0 || tree->buf[z].right == 0) ? z : BufRBTree_minimum_in_subtree(tree->buf, tree->buf[z].right);
    U64 x = tree->buf[y].left != 0 ? tree->buf[y].left : tree->buf[y].right;
    assert(x != y && x != z);
    U64 x_adopter = tree->buf[y].parent;
    tree->buf[x].parent = x_adopter;
    if (x_adopter == 0)
        *root = x;
    else if (tree->buf[x_adopter].left == y)
        tree->buf[x_adopter].left = x;
    else
        tree->buf[x_adopter].right = x;
    RBTreeColor y_org_clr = tree->buf[y].color;
    if (z != y) {
        BufRBTree_steal_neighbours(tree->buf, root, z, y);
        if (x_adopter == z)
            x_adopter = y;
    }
    U64 L = tree->len - 1;
    if (L != z) {
        BufRBTree_steal_neighbours(tree->buf, root, L, z);
        if (L == x)
            x = z;
        else if (L == x_adopter)
            x_adopter = z;
    }
    tree->buf[x].parent = x_adopter;
    tree->len--;
    if (y_org_clr == RBTree_black)
        BufRBTree_fix_after_delete(tree->buf, root, x);
    // self->el.buf[z-1] = self->el.buf[L-1];
    // self->el.len--;

}

#endif
