#include <stdio.h>

#include "../context.h"
#interface "Tree.h"
#interface "Stack.h"
#include "compare.c"

extern enum Relational compare(struct Node* node1, struct Node* node2);

Tree* createRedBlackTree(struct Context* context) {
    struct Tree* tree = new Tree();
    struct RedBlackTree* redBlackTree = new RedBlackTree();
    tree->tree = (union Data*)redBlackTree;
    redBlackTree->root = NULL;
    redBlackTree->nodeStack = createSingleLinkedStack(context);
    tree->put = C_putRedBlackTree;
    tree->get = C_getRedBlackTree;
    // tree->remove = C_removeRedBlackTree;
    // tree->clear = C_clearRedBlackTree;
    return tree;
}

void printTree1(union Data* data) {
    struct Node* node = &data->Node;
    if (node == NULL) {
        printf("NULL");
    } else {
        printf("key = %d (", node->key);
        printTree1((union Data*)(node->right));
        printf("), (");
        printTree1((union Data*)(node->left));
        printf(")");
    }
}

void printTree(union Data* data) {
    printTree1(data);
    printf("\n");
}

__code putRedBlackTree(struct RedBlackTree* tree, struct Node* node) {
    struct Node* newNode = &ALLOCATE(context, Node)->Node;
    struct Node* root = tree->root;
    printTree((union Data*)(tree->root));
    tree->newNode = newNode;
    tree->root = newNode; // this should done at stackClear
    tree->parent = NULL;
    if (root) {
        tree->current = root;
        tree->result = compare(tree->current, node);
        goto findNode(tree);
    }
    goto insertNode(tree, node);
}

__code findNode(struct RedBlackTree* tree) {
    struct Stack* nodeStack = tree->nodeStack;
    struct Node* oldNode = tree->current;
    struct Node* newNode = tree->newNode;
    tree->previous = newNode;
    *newNode = *oldNode;
    goto nodeStack->push((union Data*)newNode, findNode1);
}

__code findNode1(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
    struct Node* oldNode = tree->current;
    struct Node* newNode = tree->previous;
    struct Node* newnewNode = &ALLOCATE(context, Node)->Node;
    int result = tree->result;
    if (result == EQ) {
        newNode->value = node->value;
        // go to stack clear
        goto next(...);
    } else if (result == GT) {
        tree->current = oldNode->right;
        newNode->right = newnewNode;
    } else {
        tree->current = oldNode->left;
        newNode->left = newnewNode;
    }
    tree->newNode = newnewNode;
    if (tree->current) {
        tree->result = compare(tree->current, node);
        goto findNode(tree);
    }
    goto insertNode(tree, node);

}

__code insertNode(struct RedBlackTree* tree, struct Node* node) {
    struct Stack* nodeStack = tree->nodeStack;
    struct Node* newNode = tree->newNode;
    *newNode = *node;
    newNode->color = Red;
    tree->current = newNode;
    goto nodeStack->get2(insertCase1);
}

__code insertCase1(struct RedBlackTree* tree, struct Node *parent, struct Node *grandparent) {
    if (parent != NULL) {
        tree->parent = parent;
        tree->grandparent = grandparent;
        goto insertCase2(tree);
    }
    tree->root->color = Black;
    goto stackClear();
}

__code insertCase1_stub(struct Context* context) {
    goto insertCase1(context, 
        &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
        &context->data[D_Stack]->Stack.data->Node,
        &context->data[D_Stack]->Stack.data1->Node);
}

__code insertCase2(struct RedBlackTree* tree) {
    if (tree->parent->color == Black) {
        goto stackClear();
    }
    goto insertCase3(tree);
}

__code insertCase3(struct RedBlackTree* tree) {
    struct Stack* nodeStack = tree->nodeStack;
    struct Node* uncle;

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

    if (uncle && (uncle->color == Red)) {
        // do insertcase1 on grandparent, stack must be pop by two
        tree->parent->color = Black;
        uncle->color = Black;
        tree->grandparent->color = Red;
        tree->current = tree->grandparent;
        goto nodeStack->pop2(insertCase1);
    }
    goto insertCase4();
}

__code insertCase4(struct RedBlackTree* tree, struct RotateTree* rotateTree) {
    struct Stack* nodeStack = tree->nodeStack;

    if ((tree->current == tree->parent->right) && (tree->parent == tree->grandparent->left)) {
        tree->current = tree->current->left;
        tree->parent = tree->grandparent;

        rotateTree->traverse = tree;
        rotateTree->next = C_insertCase5;

        goto nodeStack->pop(rotateLeft);
    } else if ((tree->current == tree->parent->left) && (tree->parent == tree->grandparent->right)) {
        tree->parent = tree->grandparent;
        tree->current = tree->current->right;

        rotateTree->traverse = tree;
        rotateTree->next = C_insertCase5;

        goto nodeStack->pop(rotateRight);
    }

    goto insertCase5();
}

__code insertCase5(struct RedBlackTree* tree) {
    struct Stack* nodeStack = tree->nodeStack;
    goto nodeStack->pop2(insertCase51);
}

__code insertCase51(struct RedBlackTree* tree, struct RotateTree* rotateTree, struct Node* parent, struct Node* grandparent) {
    struct Node* current = tree->current;
    tree->parent = parent;
    tree->grandparent = grandparent;

    parent->color = Black;
    grandparent->color = Red;

    tree->current = grandparent;

    rotateTree->traverse = tree;
    rotateTree->next = C_stackClear;

    if ((current == parent->left) && (parent == grandparent->left))
        goto rotateRight();
    else
        goto rotateLeft();
}

__code insertCase51_stub(struct Context* context) {
    struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
    struct Node* grandparent = &context->data[D_Stack]->Stack.data1->Node;
    goto insertCase51(context,
                      &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
                      Gearef(context, RotateTree),
                      parent,
                      grandparent);
}

__code rotateLeft(struct RedBlackTree* tree) {
    struct Stack* nodeStack = tree->nodeStack;
    goto nodeStack->get(rotateLeft1);
}

__code rotateLeft_stub(struct Context* context) {
    struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
    goto rotateLeft(context, traverse);
}
    
__code rotateLeft1(struct Node* node, struct RedBlackTree* tree, struct Node* parent, struct RotateTree* rotateTree) {
    struct Node* tmp = node->right;

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

    node->right = tmp->left;
    tmp->left = node;
    tree->current = tmp;
    
    goto meta(context, rotateTree->next);
}

__code rotateLeft1_stub(struct Context* context) {
    struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
    struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
    goto rotateLeft1(context,
                    traverse->current,
                    traverse,
                    parent,
                    Gearef(context, RotateTree));
}

__code rotateRight(struct RedBlackTree* tree) {
    struct Stack* nodeStack = tree->nodeStack;
    goto nodeStack->get(rotateRight1);
}

__code rotateRight_stub(struct Context* context) {
    struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
    goto rotateLeft(context, traverse);
}

__code rotateRight1(struct Node* node, struct RedBlackTree* traverse,struct Node *parent,struct RotateTree *rotateTree) {
    struct Node* tmp = node->left;
    
    if (parent) {
        if (node == parent->left)
            parent->left = tmp;
        else
            parent->right = tmp;
    } else {
        traverse->root = tmp;
    }

    node->left = tmp->right;
    tmp->right = node;
    traverse->current = tmp;
    
    goto meta(context, rotateTree->next);
}

__code rotateRight1_stub(struct Context* context) {
    struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
    struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
    goto rotateRight1(context,
                     traverse->current,
                     traverse,
                     parent,
                     Gearef(context, RotateTree));
}

__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
    tree->current = 0;
    nodeStack->stack = (union Data*)tree->nodeStack;
    nodeStack->next = next;
    goto meta(context, tree->nodeStack->clear);
}

__code getRedBlackTree(struct RedBlackTree* tree, __code next(...)) {
    if (tree->root) {
        tree->current = tree->root;

        goto search();
    }

    goto next(...);
}

__code search(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
    // compare(context, traverse, traverse->current->key, node->key);
    tree->result = compare(tree->current, node);
    if (tree->result == EQ) {
        *node = *tree->current;
        
        goto meta(context, next);
    } else if (tree->result == GT) {
        tree->current = tree->current->right;
    } else {
        tree->current = tree->current->left;
    }
        
    if (tree->current)
        goto meta(context, C_search);

    goto next(...);
}

// __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);
// }