#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) {
        tree->current = tree->root;
        tree->root = &context->data[context->dataNum]->node;
        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[Allocate]->allocate);
}

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

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

        stack_pop(context->code_stack, &context->next);
        goto meta(context, context->next);
    } 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) {
        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, Balance1);
}

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

__code balance1(struct Context* context, struct Node* current) {
    if (current->parent == 0) {
        current->color = Black;
        
        stack_pop(context->code_stack, &context->next);
        goto meta(context, context->next);
    } else {
        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->parent->color == Black)
        goto meta(context, SetRoot);
    else
        goto meta(context, Balance3);
}

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

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

    if (grandparent == 0)
        uncle = 0;
    
    if (grandparent->left == current->parent)
        uncle = grandparent->right;
    else
        uncle = grandparent->left;
    
    if ((uncle != 0) && (uncle->color == Red)) {
        current->parent->color = Black;
        uncle->color = Black;
        grandparent->color = Red;
        tree->current = grandparent;
        goto meta(context, Balance1);
    } else {
        goto meta(context, Balance4);
    }
}

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

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

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

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

    goto meta(context, Balance5);
}

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

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

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

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

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

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

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

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

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

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

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

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

    if (tmp->left != 0)
        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 == 0) {
        tree->root = tmp;
    } else {
        if (node == node->parent->left)
            node->parent->left = tmp;
        else
            node->parent->right = tmp;
    }

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

    node->left = tmp->right;

    if (tmp->right != 0)
        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 colorFlip(struct Context* context, struct Node* node) {
    node->color ^= 1;

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

    if (node->right)
        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) {
    if(node->parent) {
        tree->current = tree->current->parent;
        goto meta(context, SetRoot);
    }

    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)
        goto meta(context, Get);

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

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

        goto meta(context, FindMin);
    }
    
    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);
}

__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)
        if (tree->current->left->left)
            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);
}