#include <stdio.h>

#include "context.h"
#include "origin_cs.h"

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

typedef struct Tree {
    union Data* tree;
    struct Node* node;
    enum Code put;
    enum Code get;
    enum Code remove;
    enum Code clear;
    enum Code next;
} Tree;

typedef struct RedBlackTree {
    struct Node* root;
    struct Node* current; // reading node of original tree
    struct Node* previous; // parent of reading node of original tree
    struct Node* newNode; // writing node of new tree
    struct Node* parent;
    struct Node* grandparent;
    struct Stack* nodeStack;
    int result;
} RedBlackTree;

typedef struct RotateTree {
    enum Code next;
    struct RedBlackTree* traverse;
    struct Tree* tree;
} rotateTree;

typedef struct Node {
    int key; // comparable data segment
    union Data* value;
    struct Node* left;
    struct Node* right;
    // need to balancing
    enum Color { Red, Black, } color;
} node;

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 put(struct Stack* nodeStack,  struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, __code next(...)) {
    printTree((union Data*)(tree->root));
    Node* newNode = new Node();
    traverse->newNode = newNode;
    tree->root = newNode; // this should done at stackClear
    traverse->parent = NULL;
    if (root) {
        traverse->current = root;
        traverse->result = compare(traverse->current, node);
        goto replaceNode(traverse, traverse->current, newNode);
    }

    goto insertNode(traverse, traverse->node, newNode);
}

__code replaceNode(struct Traverse* traverse, struct Node* oldNode, struct Node* newNode) {
    Stack* nodeStack = new Stack();
    traverse->previous = newNode;
    *newNode = *oldNode;
    nodeStack->stack = traverse->nodeStack;
    nodeStack->data = newNode;
    nodeStack->next = replaceNode1;
    goto traverse->nodeStack->push(nodeStack);
    // goto traverse->nodeStack->push(newNode, replaceNode1);
}

__code replaceNode1(struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, int result, __code next(...)) {
    Node* newnewNode = new Node();
    if (result == EQ) {
        newNode->value = node->value;
        // go to stack clear
        goto next(...);
    } else if (result == GT) {
        traverse->current = oldNode->right;
        newNode->right = newnewNode;
    } else {
        traverse->current = oldNode->left;
        newNode->left = newnewNode;
    }
    traverse->newNode = newnewNode;
    if (traverse->current) {
        traverse->result = compare(traverse->current, node);
        goto replaceNode(traverse, traverse->current, newNode);
    }
    goto insertNode(traverse, traverse->node, newNode);
}

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

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

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

__code insertCase3(struct Traverse* traverse) {
    Stack* nodeStack = new Stack(); 
    struct Node* uncle;

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

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

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

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

        rotateTree->traverse = traverse;
        rotateTree->next = insertCase5;

        nodeStack->stack = (union Data*)traverse->nodeStack;
        nodeStack->next = rotateLeft;
        goto nodeStack->pop(nodeStack);
    } else if ((traverse->current == traverse->parent->left) && (traverse->parent == traverse->grandparent->right)) {
        traverse->parent = traverse->grandparent;
        traverse->current = traverse->current->right;

        rotateTree->traverse = traverse;
        rotateTree->next = insertCase5;

        nodeStack->stack = (union Data*)traverse->nodeStack;
        nodeStack->next = rotateRight;
        goto nodeStack->pop(nodeStack);
    }

    goto insertCase5(traverse);
}

__code insertCase5(struct Traverse* traverse) {
    Stack* stack = new Stack;
    nodeStack->stack = (union Data*)traverse->nodeStack;
    nodeStack->next = insertCase51;
    goto traverse->nodeStack->pop2(nodeStack);
}

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

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

    traverse->current = grandparent;

    rotateTree->traverse = traverse;
    rotateTree->next = stackClear;

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

__code rotateLeft(struct Traverse* traverse) {
    Stack* nodeStack = new Stack();
    nodeStack->stack = (union Data*)traverse->nodeStack;
    nodeStack->next = rotateLeft1;
    goto traverse->nodeStack->get(nodeStack);
}

__code rotateLeft1(struct Node* node, struct Tree* tree, struct Traverse* traverse, 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;
    traverse->current = tmp;
    
    goto rotateTree->next(...);
}
    
__code rotateRight(struct Traverse* traverse) {
    Stack* nodeStack = new Stack();
    nodeStack->stack = (union Data*)traverse->nodeStack;
    nodeStack->next = rotateRight1;
    goto traverse->nodeStack->get(nodeStack);
}

__code rotateRight1(struct Node* node, struct Tree* tree, struct Traverse* 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 {
        tree->root = tmp;
    }

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

__code stackClear(struct Traverse* traverse) {
    Stack* nodeStack = new Stack();
    traverse->current = 0;
    nodeStack->stack = (union Data*)traverse->nodeStack;
    nodeStack->next = context->next;
    goto traverse->nodeStack->clear(nodeStack);
}

__code get(struct Tree* tree, struct Traverse* traverse) {
    if (tree->root) {
        traverse->current = tree->root;

        goto search(traverse, traverse->node);
    }

    goto traverse->next(...);
}

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

    goto traverse->next(...);
}