#include <stdio.h>

#include "llrbContext.h"
#include "origin_cs.h"

extern void allocator(struct Context* context);
extern void compare(struct Context* context, struct Tree* tree, int key1, int key2);

extern int num;

__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) {
    allocate->size = sizeof(struct Node);
    allocator(context);
    
    stack_push(context->code_stack, &context->next);

    tree->root = &context->data[context->dataNum]->node;
    
    if (root) {
        tree->current = root;
        compare(context, tree, tree->current->key, context->data[Node]->node.key);

        goto meta(context, Replace);
    }

    goto meta(context, Insert);
}

__code put_stub(struct Context* context) {
    goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate);
}

__code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
    *newNode = *oldNode;

    if (result == EQ) {
        newNode->value = context->data[Node]->node.value;

        stack_pop(context->code_stack, &context->next);
        goto meta(context, context->next);
    } else if (result == GT) {
        tree->current = oldNode->right;
        newNode->right = context->heap;
    } else {
        tree->current = oldNode->left;
        newNode->left = context->heap;
    }

    allocator(context);

    if (tree->current) {
        tree->current->parent = newNode;
        compare(context, tree, tree->current->key, context->data[Node]->node.key);
        goto meta(context, Replace);
    }
    
    tree->current = newNode;
    goto meta(context, Insert);
}

__code replaceNode_stub(struct Context* context) {
    goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
}

__code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
    node->color = Red;
    *newNode = *node;
    newNode->parent = tree->current;
    
    tree->current = newNode;

    goto meta(context, InsertCase1);
}

__code insertNode_stub(struct Context* context) {
    goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
}

__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
    if (current->parent)
        goto meta(context, InsertCase2);

    tree->root->color = Black;
    tree->current = 0;

    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}

__code insert1_stub(struct Context* context) {
    goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}

__code insertCase2(struct Context* context, struct Node* current) {
    if (current->parent->color == Black) {
        stack_pop(context->code_stack, &context->next);
        goto meta(context, context->next);
    }
    
    goto meta(context, InsertCase3);
}

__code insert2_stub(struct Context* context) {
    goto insertCase2(context, context->data[Tree]->tree.current);
}

__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
    struct Node* uncle;
    struct Node* grandparent = current->parent->parent;

    if (grandparent->left == current->parent)
        uncle = grandparent->right;
    else
        uncle = grandparent->left;

    if (uncle && (uncle->color == Red)) {
        current->parent->color = Black;
        uncle->color = Black;
        grandparent->color = Red;
        tree->current = grandparent;
        goto meta(context, InsertCase1);
    }

    goto meta(context, InsertCase4);
}

__code insert3_stub(struct Context* context) {
    goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}

__code insertCase4(struct Context* context, struct Node* current) {
    struct Node* grandparent = current->parent->parent;

    if ((current == current->parent->right) && (current->parent == grandparent->left)) {
        context->next = InsertCase4_1;

        stack_push(context->code_stack, &context->next);
        goto meta(context, RotateL);
    } else if ((current == current->parent->left) && (current->parent == grandparent->right)) {
        context->next = InsertCase4_2;
        
        stack_push(context->code_stack, &context->next);
        goto meta(context, RotateR);
    }

    goto meta(context, InsertCase5);
}

__code insert4_stub(struct Context* context) {
    goto insertCase4(context, context->data[Tree]->tree.current);
}

__code insertCase4_1(struct Context* context, struct Tree* tree) {
    tree->current = tree->current->left;
    goto meta(context, InsertCase5);
}

__code insert4_1_stub(struct Context* context) {
    goto insertCase4_1(context, &context->data[Tree]->tree);
}   

__code insertCase4_2(struct Context* context, struct Tree* tree) {
    tree->current = tree->current->right;
    goto meta(context, InsertCase5);
}

__code insert4_2_stub(struct Context* context) {
    goto insertCase4_2(context, &context->data[Tree]->tree);
}   

__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
    current->parent->color = Black;
    current->parent->parent->color = Red;

    tree->current = current->parent->parent;

    context->next = InsertCase5_1;
    stack_push(context->code_stack, &context->next);
    
    if ((current == current->parent->left) && (current->parent == current->parent->parent->left))
        goto meta(context, RotateR);
    else
        goto meta(context, RotateL);
}

__code insert5_stub(struct Context* context) {
    goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}

__code insertCase5_1(struct Context* context, struct Tree* tree) {
    tree->current = NULL;

    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}

__code insert5_1_stub(struct Context* context) {
    goto insertCase5_1(context, &context->data[context->dataNum]->tree);
}

__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
    struct Node* tmp = node->right;

    if (node->parent) {
        if (node == node->parent->left)
            node->parent->left = tmp;
        else
            node->parent->right = tmp;
    } else {
        tree->root = tmp;
    }

    if (tmp)
        tmp->parent = node->parent;
    
    node->right = tmp->left;

    if (tmp->left)
        tmp->left->parent = node;

    tmp->left = node;
    node->parent = tmp;
    tree->current = tmp;
    
    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}
    
__code rotateLeft_stub(struct Context* context) {
    goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
}

__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
    struct Node* tmp = node->left;

    if (node->parent) {
        if (node == node->parent->left)
            node->parent->left = tmp;
        else
            node->parent->right = tmp;
    } else {
        tree->root = tmp;
    }

    if (tmp)
        tmp->parent = node->parent;

    node->left = tmp->right;

    if (tmp->right)
        tmp->right->parent = node;
    
    tmp->right = node;
    node->parent = tmp;
    tree->current = tmp;
    
    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}

__code rotateRight_stub(struct Context* context) {
    goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
}

__code get(struct Context* context, struct Tree* tree) {
    if (tree->root) {
        tree->current = tree->root;

        goto meta(context, Search);
    }

    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}

__code get_stub(struct Context* context) {
    goto get(context, &context->data[Tree]->tree);
}

__code search(struct Context* context, struct Tree* tree, struct Node* node) {
    compare(context, tree, tree->current->key, node->key);
    
    if (tree->result == EQ) {
        *node = *tree->current;
        
        goto meta(context, context->next);
    } else if (tree->result == GT) {
        tree->current = tree->current->right;
    } else {
        tree->current = tree->current->left;
    }
        
    if (tree->current)
        goto meta(context, Search);

    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}

__code search_stub(struct Context* context) {
    goto search(context, &context->data[Tree]->tree, &context->data[Node]->node);
}

__code delete(struct Context* context, struct Tree* tree) {
    if (tree->root) {
        stack_push(context->code_stack, &context->next);
        context->next = Delete1;
        goto meta(context, Get);
    }

    goto meta(context, context->next);
}

__code delete_stub(struct Context* context) {
    goto delete(context, &context->data[Tree]->tree);
}

__code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
    allocate->size = sizeof(struct Node);
    allocator(context);
    
    struct Node* root = tree->root;

    tree->root = &context->data[context->dataNum]->node;
    tree->current = root;

    compare(context, tree, tree->current->key, context->data[Node]->node.key);
    
    goto meta(context, Replace_d1);
}

__code delete1_stub(struct Context* context) {
    goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
}

__code delete2(struct Context* context, struct Node* current) {
    if (current->color == Black) {
        struct Node* child = current->right == NULL ? current->left : current->right;
        current->color = child == NULL ? Black : child->color;

        goto meta(context, DeleteCase1);
    }

    goto meta(context, Delete3);
}

__code delete2_stub(struct Context* context) {
    goto delete2(context, context->data[Tree]->tree.current);
}

__code delete3(struct Context* context, struct Tree* tree, struct Node* current) {
    struct Node* tmp = current->right == NULL ? current->left : current->right;

    if (current->parent) {
        if (current == current->parent->left)
            current->parent->left = tmp;
        else
            current->parent->right = tmp;
    } else {
        tree->root = tmp;
    }

    if (tmp)
        tmp->parent = current->parent;

    if (current->parent == NULL && tmp)
        tmp->color = Black;

    current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL);

    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}

__code delete3_stub(struct Context* context) {
    goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}

__code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
    *newNode = *oldNode;

    if (result == EQ)
        goto meta(context, Replace_d2);
    else if (result == GT)
        tree->current = newNode->right;
    else
        tree->current = newNode->left;

    tree->current->parent = newNode;
    
    if (tree->current->left == NULL && tree->current->right == NULL)
        goto meta(context, Delete2);
    
    if (result == GT)
        newNode->right = context->heap;
    else if (result == LT)
        newNode->left = context->heap;
    
    allocator(context);
    
    compare(context, tree, tree->current->key, context->data[Node]->node.key);
    
    goto meta(context, Replace_d1);
}

__code replaceNodeForDelete1_stub(struct Context* context) {
    goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
}

__code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) {
    if (tree->current->left && tree->current->right) {
        newNode->left->parent = newNode;
        tree->current = newNode->left;
        newNode->left = context->heap;
        tree->deleted = newNode;

        allocator(context);
        tree->current->parent = newNode;
        
        goto meta(context, FindMax1);
    }

    goto meta(context, Delete2);
}

__code replaceNodeForDelete2_stub(struct Context* context) {
    goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node);
}

__code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
    *newNode = *oldNode;

    if (newNode->right)
        goto meta(context, FindMax2);
    
    tree->deleted->key = newNode->key;
    tree->deleted->value = newNode->value;

    tree->current = newNode;

    goto meta(context, Delete2);
}

__code findMax1_stub(struct Context* context) {
    goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
}
    

__code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
    *newNode = *oldNode;

    if (newNode->right->right) {
        tree->current = newNode->right;
        newNode->right = context->heap;

        allocator(context);
        tree->current->parent = newNode;
        
        goto meta(context, FindMax2);
    }

    tree->deleted->key = newNode->right->key;
    tree->deleted->value = newNode->right->value;

    tree->current = newNode;
    
    goto meta(context, Delete2);
}
    
__code findMax2_stub(struct Context* context) {
    goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
}

__code deleteCase1(struct Context* context, struct Node* current) {
    if (current->parent)
        goto meta(context, DeleteCase2);

    goto meta(context, Delete3);
}

__code deleteCase1_stub(struct Context* context) {
    goto deleteCase1(context, context->data[Tree]->tree.current);
}

__code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) {
    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
    
    if ((sibling == NULL ? Black : sibling->color) == Red) {
        current->parent->color = Red;
        sibling->color = Black;

        current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap);
        allocator(context);
        context->data[context->dataNum]->node = *sibling;
        
        tree->current = current->parent;
        
        context->next = DeleteCase3;
        stack_push(context->code_stack, &context->next);

        if (current == current->parent->left)
            goto meta(context, RotateL);
        else
            goto meta(context, RotateR);
    }

    goto meta(context, DeleteCase3);
}

__code deleteCase2_stub(struct Context* context) {
    goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}

__code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) {
    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
    
    if (current->parent->color == Black &&
        (sibling == NULL ? Black : sibling->color) == Black &&
        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
        sibling->color = Red;

        tree->current = current->parent;
        goto meta(context, DeleteCase1);
    }

    goto meta(context, DeleteCase4);
}

__code deleteCase3_stub(struct Context* context) {
    goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}

__code deleteCase4(struct Context* context, struct Node* current) {
    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
    
    if (current->parent->color == Red &&
        (sibling == NULL ? Black : sibling->color) == Black &&
        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
        sibling->color = Red;
        current->parent->color = Black;

        goto meta(context, Delete3);
    }

    goto meta(context, DeleteCase5);
}

__code deleteCase4_stub(struct Context* context) {
    goto deleteCase4(context, context->data[Tree]->tree.current);
}

__code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) {
    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
    sibling->parent = current->parent;
    
    if (current == current->parent->left &&
        (sibling == NULL ? Black : sibling->color) == Black &&
        (sibling->left == NULL ? Black : sibling->left->color) == Red &&
        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
        sibling->color = Red;
        sibling->left->color = Black;
        
        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
        allocator(context);
        struct Node* tmp = &context->data[context->dataNum]->node;
        *tmp = *sibling;
        tmp->parent = current;
        
        tmp->left = context->heap;
        allocator(context);
        context->data[context->dataNum]->node = *sibling->left;
        context->data[context->dataNum]->node.parent = tmp;

        tree->current = tmp;
        
        context->next = DeleteCase6;
        stack_push(context->code_stack, &context->next);

        goto meta(context, RotateR);
    } else if (current == current->parent->right &&
               (sibling == NULL ? Black : sibling->color) == Black &&
               (sibling->left == NULL ? Black : sibling->left->color) == Black &&
               (sibling->right == NULL ? Black : sibling->right->color) == Red) {
        sibling->color = Red;
        sibling->right->color = Black;

        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
        allocator(context);
        struct Node* tmp = &context->data[context->dataNum]->node;
        *tmp = *sibling;
        tmp->parent = current;

        tmp->right = context->heap;
        allocator(context);
        context->data[context->dataNum]->node = *sibling->right;
        context->data[context->dataNum]->node.parent = tmp;

        tree->current = tmp;

        context->next = DeleteCase6;
        stack_push(context->code_stack, &context->next);
        goto meta(context, RotateL);
    }

    goto meta(context, DeleteCase6);
}

__code deleteCase5_stub(struct Context* context) {
    goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}

__code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) {
    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;

    sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
    allocator(context);
    struct Node* tmp = &context->data[context->dataNum]->node;
    *tmp = *sibling;
    tmp->parent = current;

    tmp->color = current->parent->color;
    current->parent->color = Black;
    
    context->next = Delete3;
    stack_push(context->code_stack, &context->next);
    
    if (current == current->parent->left) {
        tmp->right->color = Black;
        tree->current = current->parent;

        goto meta(context, RotateL);
    } else {
        tmp->left->color = Black;
        tree->current = current->parent;

        goto meta(context, RotateR);
    }
}

__code deleteCase6_stub(struct Context* context) {
    goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}