#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rbtree.h"

struct RB_Node *root = NULL;


struct RB_Node *rb_left_rotate(struct RB_Node *pN)
{
    struct RB_Node *pY = pN->right;
    pY->parent = pN->parent;
    if (pN->parent)
    {
        if (pN->parent->left == pN)
        {
            pN->parent->left = pY;
        }
        else
        {
            pN->parent->right = pY;
        }
    }
    else
    {
        root = pY;
    }
    
    pN->right = pY->left;
    if (pN->right)
    {
        pN->right->parent = pN;
    }
    pN->parent = pY;
    pY->left = pN;
    return pY;
}

struct RB_Node *rb_right_rotate(struct RB_Node *pN)
{
    struct RB_Node *pY = pN->left;
    pY->parent = pN->parent;
    if (pN->parent)
    {
        if (pN->parent->left == pN)
        {
            pN->parent->left = pY;
        }
        else
        {
            pN->parent->right = pY;
        }
    }
    else
    {
        root = pY;
    }
    
    pN->left = pY->right;
    if (pN->left)
    {
        pN->left->parent = pN;
    }
    pN->parent = pY;
    pY->right = pN;
    return pY;
}
void rb_insert_fixup(struct RB_Node *pN)
{
    struct RB_Node *pP;
    struct RB_Node *pGP;
    struct RB_Node *pU;
    struct RB_Node *pGPP;
    
    while (1)
    {
        pP = pN->parent;
        
        if (NULL == pP)
        {
            pN->color = COLOR_BLACK;
            root = pP;
            return;
        }
        
        if (COLOR_BLACK == pP->color)
        {
            return;
        }
        
        
        // 父节点为红色
        pGP = pP->parent;

        if (pP == pGP->left)
        {
            printf("%s : %d, val = %d\n", __FILE__, __LINE__, pN->val);
            pU = pGP->right;
            if (pU && COLOR_RED == pU->color)
            {
                pP->color = COLOR_BLACK;
                pU->color = COLOR_BLACK;
                pGP->color = COLOR_RED;
                pN = pGP;
                continue;
            }
            

            if (pN == pP->right)
            {
                pP = rb_left_rotate(pP);
                pN = pP->left;
                pGP = pP->parent;
            }
            

            pP->color = COLOR_BLACK;
            pGP->color = COLOR_RED;
            rb_right_rotate(pGP);
            return;
        }
        else
        {
            
            pU = pGP->left;
            if (pU && COLOR_RED == pU->color)
            {
                pP->color = COLOR_BLACK;
                pU->color = COLOR_BLACK;
                pGP->color = COLOR_RED;
                pN = pGP;
                continue;
            }
            

            if (pN == pP->left)
            {
                pP = rb_right_rotate(pP);
                pN = pP->right;
                pGP = pP->parent;
            }
            

            pP->color = COLOR_BLACK;
            pGP->color = COLOR_RED;
            rb_left_rotate(pGP);
            return;
        }
    }
}

struct RB_Node *insert(struct RB_Node *pN)
{
    pN->color = COLOR_RED;
    pN->parent = NULL;
    pN->left = NULL;
    pN->right = NULL;
        
    if (NULL == root)
    {
        root = pN;
        pN->color = COLOR_BLACK;
        return pN;
    }
    
    struct RB_Node *pCurrent = root;
    
    
    while (1)
    {
        if (pN->val < pCurrent->val)
        {
            if (NULL == pCurrent->left)
            {
                pCurrent->left = pN;
                pN->parent = pCurrent;
                rb_insert_fixup(pN);
                return pN;
            }
            else
            {
                pCurrent = pCurrent->left;
                continue;
            }
        }
        else if (pN->val > pCurrent->val)
        {
            if (NULL == pCurrent->right)
            {
                pCurrent->right = pN;
                pN->parent = pCurrent;
                rb_insert_fixup(pN);
                return pN;
            }
            else
            {
                pCurrent = pCurrent->right;
                continue;
            }
        }
        else
        {
            return NULL;
        }
    }
    
}

void insertVal(int val)
{
    struct RB_Node *pN = malloc(sizeof(struct RB_Node));
    pN->val = val;
    if (insert(pN))
    {
        printf("插入 %d 成功\n", val);
    }
    else
    {
        printf("插入 %d 冲突\n", val);
        free(pN);
    }
}


char buffer[20][126];

struct RB_Node nodeArr[10];



void init()
{
    memset(buffer, ' ', sizeof(buffer));
    for (int i=0; i < 19; i++)
    {
        buffer[i][125] = '\n';
    }
    buffer[19][125] = '\0';
}

void show(struct RB_Node *root, int start, int width, int depth)
{
    // printf("%s : %d\n", __FILE__, __LINE__);
    if (NULL == root)
    {
        return;
    }
    // if (root)
    //  printf("%d\n", root->val);
    char buf[32];
    int mid = start + width / 2;
    if (root->color == COLOR_RED)
    {
        snprintf(buf, sizeof(buf), "R(%d)", root->val);
        printf("R(%d)\n", root->val);
    }
    else
    {
        snprintf(buf, sizeof(buf), "B(%d)", root->val);
        printf("B(%d)\n", root->val);
    }
    
    // memcpy(&buffer[depth][mid - 2], buf, strlen(buf));
    
    show(root->left, start, width / 2, depth + 1);
    show(root->right, mid, width / 2, depth + 1);
}

void showNode(struct RB_Node *root)
{
    // init();
    show(root, 0, 120, 0);
    // printf("%s\n", buffer[0]);
}




int main(int argc, char *argv[])
{
    // root = &nodeArr[0];
    
    // nodeArr[0].parent = NULL;
    
    char buffer[1024];
    
    while (NULL != fgets(buffer, sizeof(buffer), stdin))
    {
        int val = atoi(buffer);
        insertVal(val);
    }
    
    
    showNode(root);
    return 0;
}