#include <stdio.h>

#include "../context.h"
#interface "FTree.h"
#interface "Stack.h"

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

FTree* createFileSystemTree(struct Context* context, struct FTree* cDirectory) {
    struct FTree* fTree = new FTree();
    struct FileSystemTree* fileSystemTree = new FileSystemTree();
    fTree->fTree = (union Data*)fileSystemTree;
    fileSystemTree->root = NULL;
    fileSystemTree->nodeStack = createSingleLinkedStack(context);
    fTree->treeParent = cDirectory;
    fTree->put = C_putFileSystemTree;
    fTree->get = C_getFileSystemTree;
    fTree->remove = C_removeFileSystemTree;
    // fTree->clear = C_clearFileSystemTree;
    return fTree;
}

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 putFileSystemTree(struct FileSystemTree* fTree, struct Node* node) {
    struct Node* newNode = &ALLOCATE(context, Node)->Node;
    struct Node* root = fTree->root;
    //printTree((union Data*)(fTree->root));
    fTree->newNode = newNode;
    fTree->root = newNode; // this should done at stackClear
    fTree->parent = NULL;
    if (root) {
        fTree->current = root;
        fTree->result = compare(fTree->current, node);
        fTree->findNodeNext = C_insertNode;
        goto findNode(fTree);
    }
    goto insertNode(fTree, node);
}

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

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

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

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

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

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

__code insertCase3(struct FileSystemTree* fTree) {
    struct Stack* nodeStack = fTree->nodeStack;
    struct Node* uncle;

    if (fTree->grandparent->left == fTree->parent) {
        uncle = fTree->grandparent->right;
    } else {
        uncle = fTree->grandparent->left;
    }

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

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

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

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

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

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

        goto nodeStack->pop(rotateRight);
    }

    goto insertCase5();
}

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

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

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

    fTree->current = grandparent;

    rotateTree->traverse = fTree;
    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, FTree)->fTree->FTree.fTree->FileSystemTree,
                      Gearef(context, RotateTree),
                      parent,
                      grandparent);
}

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

__code rotateLeft_stub(struct Context* context) {
    struct FileSystemTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
    goto rotateLeft(context, traverse);
}
    
__code rotateLeft1(struct Node* node, struct FileSystemTree* fTree, 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 {
        fTree->root = tmp;
    }

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

__code rotateLeft1_stub(struct Context* context) {
    struct FileSystemTree* 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 FileSystemTree* fTree) {
    struct Stack* nodeStack = fTree->nodeStack;
    goto nodeStack->get(rotateRight1);
}

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

__code rotateRight1(struct Node* node, struct FileSystemTree* 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 FileSystemTree* 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 FileSystemTree* fTree, struct Stack* nodeStack, __code next(...)) {
    fTree->current = 0;
    nodeStack->stack = (union Data*)fTree->nodeStack;
    nodeStack->next = next;
    goto meta(context, fTree->nodeStack->clear);
}

__code getFileSystemTree(struct FileSystemTree* fTree, struct Node* node, __code next(...)) {
    if (fTree->root) {
        fTree->current = fTree->root;

        goto search(node);
    }

    goto next(...);
}

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

    goto next(...);
}


__code removeFileSystemTree(struct FileSystemTree* fTree, struct Node* node, __code next(...)) {
    struct Node* newNode = &ALLOCATE(context, Node)->Node;
    struct Node* root = fTree->root;
    printTree((union Data*)(fTree->root));
    fTree->newNode = newNode;
    fTree->root = newNode; // this should done at stackClear
    fTree->parent = NULL;
    if (root) {
        fTree->current = root;
        fTree->result = compare(fTree->current, node);
        fTree->findNodeNext = C_replaceNodeForDelete2;
        goto findNode(fTree);
    }
    goto next(...);
}



__code delete2(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 deleteCase1(current);
    }

    goto delete3(fTree, current);
}



__code delete3(struct FileSystemTree* fTree, struct Node* current, __code next(...)) {
    struct Node* tmp = current->right == NULL ? current->left : current->right;
    struct Stack* nodeStack = fTree->nodeStack;

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


    if (fTree->parent == NULL && tmp) {
        tmp->color = Black;
    }

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

    Gearef(context, Stack)->stack = (union Data*) nodeStack;
    Gearef(context, Stack)->next = next;
    goto meta(context, nodeStack->pop);

//    gato nodeStack->pop(next);
}



__code replaceNodeForDelete2(struct FileSystemTree* fTree, struct Node* newNode) {
    if (fTree->current->left && fTree->current->right) {
        fTree->parent = newNode;
        fTree->current = newNode->left;
        newNode->left = context->heap;


        fTree->parent = newNode;
        
        goto findMax1(fTree,oldNode, newNode);
    }

    goto delete2(current);
}


__code findMax1(struct FileSystemTree* fTree, struct Node* oldNode, struct Node* newNode) {
    *newNode = *oldNode;

    if (newNode->right) {
        goto findMax2(fTree, oldNode, newNode);
    }
    
    fTree->current = newNode;

    goto delete2(current);
}


    

__code findMax2(struct FileSystemTree* fTree, struct Node* oldNode, struct Node* newNode) {
    *newNode = *oldNode;

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

        fTree->parent = newNode;
        
        goto findMax2(fTree, oldNode, newNode);
    }

    fTree->current = newNode;
    
    goto delete2(fTree,current);
}
    

__code deleteCase1(struct FileSystemTree* fTree, struct Node* current) {
    if (fTree->parent) {
        goto deleteCase2(fTree,current);
    }

    goto delete3(fTree, current);
}



__code deleteCase2(struct FileSystemTree* fTree, struct Node* current, struct RotateTree* rotateTree) {
    struct Node* sibling = current == fTree->parent->left ? fTree->parent->right : fTree->parent->left;
    struct Stack* nodeStack = fTree->nodeStack;
    
    if ((sibling == NULL ? Black : sibling->color) == Red) {
        fTree->parent->color = Red;
        sibling->color = Black;

        current == fTree->parent->left ? (fTree->parent->left = context->heap) : (fTree->parent->right = context->heap);

        struct Node* node = sibling;
        
        fTree->current = fTree->parent;

        rotateTree->traverse = fTree;
        rotateTree->next = C_deleteCase3;

        if (current == fTree->parent->left) {
            goto nodeStack->push((union Data*)node,rotateLeft);
        } else {
            goto nodeStack->push((union Data*)node,rotateRight);
        }

        goto deleteCase3(fTree,current);
    }
}



__code deleteCase3(struct FileSystemTree* fTree, struct Node* current) {
    struct Node* sibling = current == fTree->parent->left ? fTree->parent->right : fTree->parent->left;
    
    if (fTree->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;

        fTree->current = fTree->parent;
        goto deleteCase1(current);
    }

    goto deleteCase4(current);
}



__code deleteCase4(struct FileSystemTree* fTree,struct Node* current) {
    struct Node* sibling = current == fTree->parent->left ? fTree->parent->right : fTree->parent->left;
    
    if (fTree->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;
        fTree->parent->color = Black;

        goto delete3(fTree,current);
    }

    goto deleteCase5(fTree,current);
}



__code deleteCase5(struct FileSystemTree* fTree, struct Node* current, struct RotateTree* rotateTree) {
    struct Node* sibling = current == fTree->parent->left ? fTree->parent->right : fTree->parent->left;
    struct Stack* nodeStack = fTree->nodeStack;
    // sibling->parent = fTree->parent;
    
    if (current == fTree->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);
        sibling == fTree->parent->left ? (fTree->parent->left = context->heap) : (fTree->parent->right = context->heap);

        struct Node* node = new Node();
        node = sibling->left;

        struct Node* tmp = node;
        *tmp = *sibling;
        fTree->parent = current;
        
        tmp->left = context->heap;
/*         struct Node* node = new Node(); */
/*         node = *sibling->left; */
        fTree->parent = tmp;

        fTree->current = tmp;
        

        rotateTree->traverse = fTree;
        rotateTree->next = C_deleteCase6;

        goto nodeStack->push((union Data*)node,rotateRight);
    } else if (current == fTree->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 == fTree->parent->left ? (fTree->parent->left = context->heap) : (fTree->parent->right = context->heap);

        struct Node* node = new Node();
        node = sibling->right;

        struct Node* tmp = node;
        *tmp = *sibling;
        // tmp->parent = current;

        tmp->right = context->heap;
/*         struct Node* node = new Node(); */
/*         node = *sibling->right; */
        //node->parent = tmp;

        fTree->current = tmp;
        

        rotateTree->traverse = fTree;
        rotateTree->next = C_deleteCase6;

        goto nodeStack->push((union Data*)node,rotateLeft);
    }

    goto deleteCase6(fTree,current);
}


__code deleteCase6(struct FileSystemTree* fTree, struct Node* current, struct RotateTree* rotateTree) {
    struct Node* sibling = current == fTree->parent->left ? fTree->parent->right : fTree->parent->left;
    struct Stack* nodeStack = fTree->nodeStack;
    sibling == fTree->parent->left ? (fTree->parent->left = context->heap) : (fTree->parent->right = context->heap);

    struct Node* tmp = sibling;
    // *tmp = *sibling;
    fTree->parent = current;

    tmp->color = fTree->parent->color;
    fTree->parent->color = Black;
    
    
    if (current == fTree->parent->left) {
        tmp->right->color = Black;
        fTree->current = fTree->parent;

        rotateTree->traverse = fTree;
        rotateTree->next = C_delete3;

        goto nodeStack->push((union Data*)tmp,rotateLeft);
    } else {
        tmp->left->color = Black;
        fTree->current = fTree->parent;

        rotateTree->traverse = fTree;
        rotateTree->next = C_delete3;

        goto nodeStack->push((union Data*)tmp,rotateLeft);
    }
}