#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 Allocate* allocate) {
    allocate->size = sizeof(struct Node);
    allocator(context);

    stack_push(context->code_stack, &context->next);

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

        goto meta(context, Replace);
    }
}

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

__code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
    stack_push(context->node_stack, &newNode);

    *newNode = *oldNode;

    if (result == 0) {
        stack_pop(context->node_stack, &tree->current);
        newNode->value = context->data[Node]->node.value;

        goto meta(context, Balance1);
    } else if (result == 1) {
        tree->current = oldNode->right;
        newNode->right = context->heap;
    } else {
        tree->current = oldNode->left;
        newNode->left = context->heap;
    }

    allocator(context);

    if (tree->current == 0) {
        stack_pop(context->node_stack, &tree->current);
        goto meta(context, Insert);
    } else {
        compare(context, tree, tree->current->key, context->data[Node]->node.key);
        
        goto meta(context, Replace);
    }
}

__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 balance1(struct Context* context, struct Node* current) {
    if (current->right != 0)
        if (current->right->color == Red) {
            context->next = Balance2;

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

    goto meta(context, Balance2);
}

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

__code balance2(struct Context* context, struct Node* current) {
    if (current->left != 0)
        if (current->left->left != 0)
            if (current->left->color == Red && current->left->left->color == Red) {
                context->next = Balance3;

                stack_push(context->code_stack, &context->next);
                goto meta(context, RotateR);
            }
                
    goto meta(context, Balance3);
}

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

__code balance3(struct Context* context, struct Node* current){
    if (current->right != 0 && current->left != 0)
        if (current->right->color == Red && current->left->color == Red) {
            context->next = FixUp;

            stack_push(context->code_stack, &context->next);
            goto meta(context, ColorFlip);
        }
    
    goto meta(context, FixUp);    
}

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

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

    if (tree->root == 0) {
        tree->current = newNode;
        goto meta(context, SetRoot);
    }
    
    goto meta(context, Balance1);
}

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

__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
    struct Node* tmp = node->right;
    node->right = tmp->left;
    tmp->left = node;
    tmp->color = node->color;
    node->color = Red;
    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;
    node->left = tmp->right;
    tmp->right = node;
    tmp->color = node->color;
    node->color = Red;
    context->data[Tree]->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 colorFlip(struct Context* context, struct Node* node) {
    node->color ^= 1;

    if (node->left != 0)
        node->left->color ^= 1;

    if (node->right != 0)
        node->right->color ^= 1;

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

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

__code fixUp(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
    node->key = newNode->key;
    tree->prev = newNode;
    
    if (stack_pop(context->node_stack, &tree->current) == 0) {
        compare(context, tree, tree->current->key, node->key);
        goto meta(context, ChangeRef);
    }

    goto meta(context, SetRoot);
}

__code fixUp_stub(struct Context* context) {
    goto fixUp(context, &context->data[Tree]->tree, &context->data[Node]->node, context->data[Tree]->tree.current);
}

__code setRoot(struct Context* context, struct Tree* tree, struct Node* node) {
    tree->root = node;
    tree->root->color = Black;
    tree->current = 0;
    
    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}    

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

__code changeReference(struct Context* context, struct Tree* tree, struct Node* node, int result) {
    if (result == 1) {
        node->right = tree->prev;
    } else if (result == -1) {
        node->left = tree->prev;
    } else {
        perror("bad status");
    }
    
    goto meta(context, Balance1);
}

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

__code get(struct Context* context, struct Tree* tree, struct Node* node) {
    tree->current = (tree->current == 0)? tree->root : tree->current;

    compare(context, tree, tree->current->key, node->key);
    
    if (tree->result == 0) {
        goto meta(context, context->next);
    } else if (tree->result == 1) {
        tree->current = tree->current->right;
    } else {
        tree->current = tree->current->left;
    }
        
    if (tree->current == 0)
        goto meta(context, context->next);
        
    goto meta(context, Get);
}

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

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

    stack_push(context->code_stack, &context->next);

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

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

__code replaceNode_d1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
    *newNode = *oldNode;
    tree->current = newNode;
    
    if (tree->result == -1) {
        if (tree->current->left != 0) {

            if (tree->current->left->left != 0)
                if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
                    context->next = MoveRedL1;
                    
                    stack_push(context->code_stack, &context->next);
                    goto meta(context, ColorFlip);
                }
            
            stack_push(context->node_stack, &tree->current);

            tree->current->left = context->heap;
            tree->current = oldNode->left;

            allocator(context);
            compare(context, tree, tree->current->key, context->data[Node]->node.key);

            goto meta(context, Replace_d1);
        }
    } else {
        if (tree->current->left != 0)
            if (tree->current->left->color == Red) {
                allocator(context);
                context->data[context->dataNum]->node = *tree->current->left;
                tree->current->left = &context->data[context->dataNum]->node;

                context->next = Replace_d2;
                stack_push(context->code_stack, &context->next);

                goto meta(context, RotateR);
            }

        goto meta(context, Replace_d2);
    }
}

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

__code replaceNode_d2(struct Context* context, struct Tree* tree) {
    compare(context, tree, tree->current->key, context->data[Node]->node.key);
    
    if (tree->result == 0 && tree->current->right == 0) {
        stack_pop(context->node_stack, &tree->current);

        compare(context, tree, tree->current->key, context->data[Node]->node.key);
        
        if (tree->result == 1) {
            tree->current->right = 0;
        } else {
            tree->current->left = 0;
        }

        goto meta(context, Balance1);
    }

    goto meta(context, Replace_d3);
}

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

__code replaceNode_d3(struct Context* context, struct Tree* tree) {
    if (tree->current->right != 0) {
        if (tree->current->right->left != 0)
            if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
                context->next = MoveRedR1;
                stack_push(context->code_stack, &context->next);

                goto meta(context, ColorFlip);
            }

        goto meta(context, Replace_d4);
    }
}

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

__code replaceNode_d4(struct Context* context, struct Tree* tree, struct Node* node) {
    stack_push(context->node_stack, &tree->current);

    if (tree->result == 0) {
        tree->current = node->right;
        goto meta(context, FindMin);
    } else {
        struct Node* next = node->right;
        tree->current->right = context->heap;
        tree->current = next;
        
        allocator(context);

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

        goto meta(context, Replace_d1);
    }
}

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

__code moveRedLeft1(struct Context* context, struct Tree* tree, struct Node* node) {
    if (tree->current->right != 0)
        if (tree->current->right->left != 0)
            if (tree->current->right->left->color == Red) {
                allocator(context);
                context->data[context->dataNum]->node = *node->right;
                node->right = &context->data[context->dataNum]->node;
                
                allocator(context);
                context->data[context->dataNum]->node = *node->right->left;
                node->right->left = &context->data[context->dataNum]->node;
                
                stack_push(context->node_stack, &tree->current);
                tree->current = node->right;
                
                context->next = MoveRedL2;
                stack_push(context->code_stack, &context->next);
                
                goto meta(context, RotateR);
            }

    stack_pop(context->code_stack, &context->next);
    if (context->next == DeleteMin2)
        goto meta(context, context->next);

    stack_push(context->code_stack, &context->next);
    stack_push(context->node_stack, &tree->current);
    
    struct Node* next = node->left;
    tree->current->left = context->heap;
    tree->current = next;
    
    allocator(context);
    compare(context, tree, tree->current->key, context->data[Node]->node.key);
    
    goto meta(context, Replace_d1);
}

__code moveRedLeft1_stub(struct Context* context) {
    goto moveRedLeft1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
}
 
__code moveRedLeft2(struct Context* context, struct Tree* tree) {
    stack_pop(context->node_stack, &tree->current);

    context->next = MoveRedL3;
    stack_push(context->code_stack, &context->next);

    context->next = ColorFlip;
    stack_push(context->code_stack, &context->next);

    goto meta(context, RotateL);
}

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

__code moveRedLeft3(struct Context* context, struct Tree* tree) {
    stack_pop(context->code_stack, &context->next);
    if (context->next == DeleteMin2)
        goto meta(context, context->next);

    stack_push(context->code_stack, &context->next);
    stack_push(context->node_stack, &tree->current);

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

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

__code moveRedRight1(struct Context* context, struct Tree* tree, struct Node* node) {
    if (tree->current->left != 0)
        if (tree->current->left->left != 0)
            if (tree->current->left->left->color == Red) {
                allocator(context);
                context->data[context->dataNum]->node = *node->left;
                node->left = &context->data[context->dataNum]->node;
                
                context->next = MoveRedR2;
                stack_push(context->code_stack, &context->next);

                context->next = ColorFlip;
                stack_push(context->code_stack, &context->next);
                
                goto meta(context, RotateR);
            }

    goto meta(context, Replace_d4);
}

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

__code moveRedRight2(struct Context* context, struct Tree* tree) {
    stack_push(context->node_stack, &tree->current);
    tree->current = tree->current->right;
    
    compare(context, tree, tree->current->key, context->data[Node]->node.key);
    
    goto meta(context, Replace_d1);
}

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

__code findMin(struct Context* context, struct Tree* tree, struct Node* tmp) {
    if (tree->current->left == 0) {
        tmp->key = tree->current->key;
        tmp->value = tree->current->value;
            
        stack_pop(context->node_stack, &tree->current);

        tree->current->key = tmp->key;
        tree->current->value = tmp->value;

        stack_push(context->node_stack, &tree->current);

        struct Node* next = tree->current->right;

        tree->current->right = context->heap;
        tree->current = next;

        allocator(context);

        goto meta(context, DeleteMin1);
    } else {
        tree->current = tree->current->left;

        goto meta(context, FindMin);
    }
}

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

__code deleteMin1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
    *newNode = *oldNode;
    tree->current = newNode;

    if (tree->current->left == 0) {
        struct Node* node = tree->current;

        stack_pop(context->node_stack, &tree->current);
        
        compare(context, tree, tree->current->key, node->key);

        if (tree->result == -1) {
            tree->current->left = 0;
        } else {
            tree->current->right = 0;
        }
        
        goto meta(context, Balance1);
    }

    if (tree->current->left != 0)
        if (tree->current->left->left != 0)
            if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
                context->next = DeleteMin2;
                stack_push(context->code_stack, &context->next);

                context->next = MoveRedL1;
                stack_push(context->code_stack, &context->next);
                
                goto meta(context, ColorFlip);
            }

    goto meta(context, DeleteMin2);
}

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

__code deleteMin2(struct Context* context, struct Tree* tree, struct Node* node) {
    stack_push(context->node_stack, &tree->current);
    tree->current->left = context->heap;
    tree->current = node->left;

    allocator(context);
    goto meta(context, DeleteMin1);
}

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