#include <stdio.h>

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

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


Tree* createRedBlackTree(struct Context* context) {
    struct Tree* tree = new Tree();
    struct RedBlackTree* rbtree = new RedBlackTree();

    tree->tree = (union Data*)rbtree;
     rbtree->root = NULL;
     rbtree->nodeStack = (union Data*)createSingleLinkedStack(context);
     tree->put = C_putRedBlackTree;
    // tree->get = C_getRedBlackTree;
    // tree->remove = C_removeRedBlackTree;
    // tree->clear = C_clearRedBlackTree;
     return tree;
}

void printNode(struct Node* node) {
  if (node == NULL) {
    printf("leaf");
  } else {
    printf("((%d,%d (",node->color, node->key);
    printNode(node->right);
    printf(") (");
    printNode(node->left);
    printf(")");
  }
}

void printTree(struct RedBlackTree* tree) {
  printf("\n");
  tree->current = tree->root;
  printNode(tree->current);
  printf(")\n");
}

__code putRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
    printf("C_putRedBlackTree\n");
    printf("value->%d,key->%d \n",node->value,node->key);
    tree->previous = tree->newNode;
    tree->newNode = node;
    tree->newNode->color = Red;
    tree->current = tree->root;
    goto insertRBTree(node, tree);
}

__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
   tree->current = 0;
   nodeStack->stack = 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 insertRBTree();
        // goto deleteRBTree();
      }
    goto next(...);
}

__code insertRBTree(struct Node* node, struct RedBlackTree* tree, struct Stack* stack, __code next(...)) {
  // first case tree->current = root;
  printf("C_insertRBTree\n");
  printf("value->%d,key->%d\n",node->value,node->key);
  printf("newNode value->%d,newNode key->%d\n",tree->newNode->value,tree->newNode->key);

  if (tree->root == NULL) {
    printf("insertRBTree_root eq NULL\n");
    tree->root = tree->newNode;
    tree->root->color = Black;
    printf("tree->root->key = %d, tree->root->color = %d \n",tree->root->key,tree->root->color);
    printTree(tree);
    goto next(tree,...);
  } else {
    goto searchInsertLocation(node, tree, stack);
  }
}

__code insertRBTree_stub(struct Context* context) {
	Node* node = Gearef(context, Tree)->node;
	RedBlackTree* tree = (RedBlackTree*)GearImpl(context, Tree, tree);
	Stack* stack = createSingleLinkedStack(context);
	enum Code next = Gearef(context, Tree)->next;
	goto insertRBTree(context, node, tree, stack, next);
} 

__code searchInsertLocation(struct Node* node, struct RedBlackTree* tree) {
  // first case tree->current = root; PreCase remove root=NULL case.don't exist firstCase tree->current=NULL
  printf("C_searchInsertLocation\n");
  printf("nownode->key %d , previous->key %d \n",tree->newNode->key,tree->previous->key);

  tree->result = compare(tree->current, node);
  printf("tree->current->key = %d, node->key %d\n",tree->current->key,node->key);
  printf("compare (%d,%d)\n",tree->current,node);

  Stack* stack = tree->nodeStack;

  if (tree->current == NULL) {
    printf("goto insertLocationBackInsert stack->pop\n");
    goto stack->pop(insertLocationBackInsert);
  }
  if (tree->result == GT) {
    printf("GT searchInsertLocation\n");
    tree->current = tree->current->right;
    goto stack->push(tree->newNode,insertLocationBackInsert);
  } else if (tree->result == LT) {
    printf("LT searchInsertLocation\n");
    tree->current = tree->current->left;
    goto stack->push(tree->newNode, searchInsertLocation);
  } else if (tree->result == EQ) {
    printf("already member this node : __code searchInsertLocation()\n");
    goto meta(context, C_exit_code);
  } else {
    printf("$insert value tree : __code searchInsertLocation() \n");
    goto meta(context, C_exit_code);
  }
}

__code searchInsertLocation_stub(struct Context* context) {
	Node* node = Gearef(context, Tree)->node;
	RedBlackTree* tree = (RedBlackTree*)GearImpl(context, Tree, tree);
  Stack* stack = (struct Stack*)Gearef(context, Stack)->stack;
	goto searchInsertLocation(context, node, tree);
}

__code insertLocationBackInsert(struct RedBlackTree* tree, struct Node* node, struct Stack* stack) {
  printf("C_insertLocationBackInsert\n");
  struct Node* hoge = stack->data;
  printf("stackpopdata%d\n",stack->data);
  tree->current = tree->previous;
  // tree->current = nodeStack->data;
  // this CS is ones only backTrace, and insert node
  tree->result = compare(tree->previous,tree->newNode);
  printf("back,compare\n");
  if (tree->result == GT) {
    printf("GT\n");
    tree->current->right = tree->newNode;
    printTree(tree);
    goto insertBalance(tree, stack, node, next);
  } else if (tree->result == LT) {
    printf("LT\n");
    tree->current->left = tree->newNode;
    goto insertBalance(tree, stack, node, next);
  } else {
    printf("error : __code insertLocationBackTrace() \n");
    goto meta(context, C_exit_code);
  }
}

__code insertLocationBackInsert_stub(struct Context* context) {
	RedBlackTree* tree = (RedBlackTree*)GearImpl(context, Tree, tree);
  SingleLinkedStack* singleLinkedStack = (SingleLinkedStack*)GearImpl(context, Stack, stack);
	Node* node = Gearef(context, Tree)->node;
  Stack* stack = (struct Stack*)Gearef(context, Stack)->stack;
	goto insertLocationBackInsert(context, tree, node, stack);
}

__code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node, __code next(...)) {
  printf("C_insertBalance\n");
  struct Node* traceNode = tree->nodeStack->data;
  tree->current = traceNode;
  struct Stack* stack = tree->nodeStack;

  // exit insertion code
  if (tree->current == tree->root) {
    tree->current->color = Black;
    printTree(tree);
    //printTree
    goto next(tree,...);
  }


  //current color eq Red
  if (tree->current->color == Red)
    goto stack->pop(insertBalance);

  // current color eq Black
  if (tree->current->left->left || tree->current->left->right) {
    goto insertBalanceLeft(tree,nodeStack);
  } else if (tree->current->right->left || tree->current->right->right) {
    goto insertBalanceRight(tree,nodeStack);
  } else {
    goto stack->pop(insertBalance);
  }
}

__code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) {
  printf("C_insertBalanceLeft\n");
  struct Stack* stack = tree->nodeStack;

  if (tree->current->color == Black && tree->current->left->color == Red && tree->current->left->left->color == Red) {
    struct Node* tmpCurrent  = tree->current;
    struct Node* tmpLeft     = tree->current->left;
    struct Node* tmpLeftLeft = tree->current->left->left;

    tree->current = tmpLeft;
    tree->current->right = tmpCurrent;
    tree->current->left = tmpLeftLeft;
    tree->current->right->left = tmpLeft->right;
    tree->current->color = Red;
    tree->current->left->color = Black;
    tree->current->right->color = Black;
    goto stack->pop(insertBalance);

  } else if (tree->current->color == Black && tree->current->left->color == Red && tree->current->left->right->color == Red) {
    struct Node* tmpCurrent   = tree->current;
    struct Node* tmpLeft      = tree->current->left;
    struct Node* tmpLeftRight = tree->current->left->right;

    tree->current = tmpLeft;
    tree->current->right = tmpCurrent;
    tree->current->left = tmpLeftRight;
    tree->current->right->left = tmpLeft->left;
    tree->current->color = Red;
    tree->current->left->color = Black;
    tree->current->right->color = Black;
    goto stack->pop(insertBalance);

  }
}

__code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) {
  printf("C_insertBalanceLeft\n");
  struct Stack* stack = tree->nodeStack;

  if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->right->color == Red) {
    struct Node* tmpCurrent    = tree->current;
    struct Node* tmpRight      = tree->current->right;
    struct Node* tmpRightRight = tree->current->right->right;

    tree->current = tmpRight;
    tree->current->left = tmpCurrent;
    tree->current->right = tmpRightRight;
    tree->current->left->right = tmpRight->left;
    tree->current->color = Red;
    tree->current->left->color = Black;
    tree->current->right->color = Black;
    goto stack->pop(insertBalance);

  } else if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->left->color == Red) {

    struct Node* tmpCurrent = tree->current;
    struct Node* tmpRight = tree->current->right;
    struct Node* tmpRightLeft = tree->current->right->left;

    tree->current = tmpRight;
    tree->current->right = tmpCurrent;
    tree->current->left = tmpRightLeft;
    tree->current->left->right = tmpRight->right;
    tree->current->color = Red;
    tree->current->left->color = Black;
    tree->current->right->color = Black;
    goto stack->pop(insertBalance);

  } else {
    printf("unkwon error : __code insertBalanceRight() \n");
    goto meta(context, C_exit_code);
  }
}
// insertCode end