#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) {
        newNode->color = Black;
        tree->root = newNode;
        tree->current = 0;

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

    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;
    node->left->color ^= 1;
    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);
    }
    
    newNode->color = Black;
    tree->root = newNode;
    tree->current = 0;
    
    stack_pop(context->code_stack, &context->next);
    goto meta(context, context->next);
}    

__code fixUp_stub(struct Context* context) {
    goto fixUp(context, &context->data[Tree]->tree, &context->data[Node]->node, 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_d);
}

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

__code replaceNode_d(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)
                    goto meta(context, MoveRedL);
        
        stack_push(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_d);
    } 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;
                
                // roatate right
                struct Node* tmp = tree->current->left;
                tree->current->left = tmp->right;
                tmp->right = tree->current;
                tmp->color = tree->current->color;
                tree->current->color = Red;
                tree->current = tmp;
            }

        if (tree->result == 0 && tree->current->right == 0) {
            stack_pop(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;
            }

            if (tree->current->right != 0)
                if (tree->current->right->color == Red)
                    goto meta(context, RotateL);
            
            if (tree->current->left != 0)
                if (tree->current->left->left != 0)
                    if (tree->current->left->color == Red && tree->current->left->left->color == Red)
                        goto meta(context, RotateR);
            
            goto meta(context, FixUp);
        }
            

        if (tree->current->right != 0) {
            if (tree->right->left != 0) {
                if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
                    goto meta(context, MoveRedR);
                }
            }

            stack_push(node_stack, &tree->current);
        
            tree->current->right = context->heap;
            tree->current = oldNode->right;
            
            allocator(context);

            goto(context, Replace_d);

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

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

__code moveRedLeft(struct Context* context, struct Node* node) {
    // color flip
    node->color ^= 1;
    node->left->color ^= 1;
    node->right->color ^= 1;

    if (tree->current->right != 0)
        if (tree->current->right->left != 0)
            if (tree->current->right->left == 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;

                // rotate right
                struct Node* tmp = node->right->left;
                node->right->left = tmp->right;
                tmp->right = node->right;
                tmp->color = node->right->color;
                node->right->color = Red;
                node->right = tmp;

                // rotate left
                tmp = node->right;
                node->right = tmp->left;
                tmp->left = node;
                tmp->color = node->color;
                node->color = Red;

                // color flip
                node->color ^= 1;
                node->left->color ^= 1;
                node->right->color ^= 1;

                tree->current = tmp;
            }

    stack_push(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_d);
}

__code moveRedRight(struct Context* context, struct Node* node) {
    // color flip
    node->color ^= 1;
    node->left->color ^= 1;
    node->right->color ^= 1;

    if (tree->current->left != 0)
        if (tree->current->left->left != 0)
            if (tree->current->left->left == Red) {
                allocator(context);
                *context->data[context->dataNum]->node = *node->left;
                node->left = context->data[context->dataNum]->node;
                
                // rotate right
                struct Node* tmp = node->left;
                node->left = tmp->right;
                tmp->right = node;
                tmp->color = node->color;
                node->color = Red;

                // color flip
                node->color ^= 1;
                node->left->color ^= 1;
                node->right->color ^= 1;

                tree->current = tmp;
            }
    
    stack_push(node_stack, &tree->current);
    
    tree->current->right = context->heap;
    tree->prev = tree->current;
    tree->current = oldNode->right;
    
    allocator(context);
    if (tree->result = 0) {
        goto meta(context, DeleteMin);
    } else {
        compare(context, tree, tree->current->key, context->data[Node]->node.key);
        
        goto meta(context, Replace_d);
    }
}

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

__code deleteMin(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
    stack_push(node_stack, &newNode);
    
    *newNode = *oldNode;
    tree->current = newNode;

    if (tree->current->left == 0) {
        newNode->left = 0;

        if (tree->current->right != 0)
            if (tree->current->right->color == Red)
                goto meta(context, RotateL);
        
        goto meta(context, FixUp);
    }

    if (tree->current->left != 0)
        if (tree->current->left->left != 0)
            if (tree->current->left->color != Red && tree->current->left->left->color != Red)
                goto meta(context, MoveRedL);

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

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

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