/**
 * Copyright (c) 2021 Corona.
 * cBST is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2. 
 * You may obtain a copy of Mulan PSL v2 at:
 *          http://license.coscl.org.cn/MulanPSL2 
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.  
 * See the Mulan PSL v2 for more details.  
 */

#ifndef __CBST_C
#define __CBST_C

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


/********************************* 
 * Tool Functions
 *********************************/
/**
 * 判断一个cBST是否为空
 * 是空返回cBST_TRUE
 * 否则返回cBST_FALSE
 */
cBST_BOOL isNULL(cBST* node) {
    if (node == NULL || node->isEmpty == cBST_TRUE) {
        return cBST_TRUE;
    } else {
        return cBST_FALSE;
    }
}

/**
 * 比较两个整数
 */
int cmpInt(const int a, const int b) {
    if (a < b) {
        return -1;
    } else if (a == b) {
        return 0;
    } else {
        return 1;
    }
}

int cmpDouble(const double a, const double b) {
    if (a < b) {
        return -1;
    } else if (a == b) {
        return 0;
    } else {
        return 1;
    }
}

int cmpString(const char* str1, const char* str2) {
    return strcmp(str1, str2);
}

/**
 * 检查是否有左子结点
 */
cBST_BOOL cBST_HasLeftChild(cBST* root) {
    return isNULL(root->leftChild) == cBST_TRUE ? cBST_FALSE : cBST_TRUE;
}

/**
 * 检查是否有右子结点
 */
cBST_BOOL cBST_HasRightChild(cBST* root) {
    return isNULL(root->rightChild) == cBST_TRUE ? cBST_FALSE : cBST_TRUE;
}

/**
 * 获取一颗cBST中的结点数
 */
cBST_INTEGER cBST_Size(cBST* root) {
    if (isNULL(root) == cBST_TRUE) {
        return 0;
    }
    return cBST_Size(root->leftChild) + cBST_Size(root->rightChild) + 1;
}

/**
 * 获取一颗cBST的高度
 */
cBST_INTEGER cBST_Height(cBST* root) {
    if ( isNULL(root) == cBST_TRUE ) {
        return 0;
    } else {
        cBST_INTEGER leftHeight = cBST_Height(root->leftChild);
        cBST_INTEGER rightHeight = cBST_Height(root->rightChild);
        cBST_INTEGER height = ( leftHeight > rightHeight ? leftHeight : rightHeight ) + 1;
        return height;
    }
}
/********************************
 * Print Functions
 *******************************/

/**
 * 输出缩进
 */
static void printIndent(FILE* fout, const unsigned int n) {
    const int indentWidth = 4;
    for (unsigned int i = 0; i < n; i++) {
        for (int j = 0; j < indentWidth; j++) {
            fprintf(fout, " ");
        }
    }
}

/**
 * 打印cBST
 */

void cBST_Print(FILE* fout, const unsigned int generation, cBST* root) {

    if (isNULL(root) == cBST_FALSE) {
        fprintf(fout, "[");
        fprintf(fout, "\n");
        printIndent(fout, generation + 1);
        
        // 输出该结点的值
        if (root->type == cBST_TYPE_INTEGER) {
            fprintf(fout, "valueInt = %d,\n", root->valueInt);
        } else if ( root->type == cBST_TYPE_DOUBLE ) {
            fprintf(fout, "valueDouble = %f,\n", root->valueDouble);
        } else if ( root->type == cBST_TYPE_STRING ) {
            fprintf(fout, "valueString = \"%s\",\n", root->valueString);
        } else {
            fprintf(fout, "SOMETHING WRONG:");
            fprintf(fout, "type = %d, valueInt = %d, valueDouble = %.2f, valueString = %s\n", 
                    root->type, root->valueInt, root->valueDouble, root->valueString
                    );
        }
        printIndent(fout, generation + 1); fprintf(fout, "address = %p,\n", root);
        printIndent(fout, generation + 1); fprintf(fout, "father  = %p,\n", root->father);
        printIndent(fout, generation + 1); fprintf(fout, "left = ");
        cBST_Print(fout, generation + 1, root->leftChild);

        printIndent(fout, generation + 1); fprintf(fout, "right = ");
        cBST_Print(fout, generation + 1, root->rightChild);

        printIndent(fout, generation); fprintf(fout, "]\n");
    } else {
        fprintf(fout, "[ NULL ]\n");
    }
}

/**
 * 打印cBST
 */
void cBST_PrintPretty(FILE* fout, cBST* root) {
    cBST_Print(fout, 0, root);
}


/**********************************
 * Create Functions
 *********************************/

/**
 * 创建一个新结点
 */
static cBST* cBST_NewNode() {
    cBST* node = (cBST*)malloc(sizeof(cBST));
    memset(node, 0, sizeof(cBST));
    return node;
}

/**
 * 创建一个空的cBST
 */
cBST* cBST_NewEmptyBST( void ) {
    cBST * root = NULL;
    return root;
}

/**
 * 创建一个int类型的BST
 */
cBST* cBST_NewIntBST( const int valueInt ) {
    cBST* root = cBST_NewNode();
    root->father = NULL;
    root->leftChild = NULL;
    root->rightChild = NULL;
    root->valueString = NULL;
    root->valueDouble = 0;
    root->valueInt = valueInt;
    root->type = cBST_TYPE_INTEGER;
    return root;
}

/**
 * 创建一个double类型的cBST
 */
cBST* cBST_NewDoubleBST( const double valueDouble ) {
    cBST* root = cBST_NewNode();
    root->father = NULL;
    root->leftChild = NULL;
    root->rightChild = NULL;
    root->valueString = NULL;
    root->valueInt = 0;
    root->valueDouble = valueDouble;
    root->type = cBST_TYPE_DOUBLE;
    return root;
}

/**
 * 创建一个String类型的cBST
 */
cBST* cBST_NewStringBST( const char* str ) {
    cBST* root = cBST_NewNode();
    root->father = NULL;
    root->leftChild = NULL;
    root->rightChild = NULL;
    root->valueInt = 0;
    root->valueDouble = 0;
    root->type = cBST_TYPE_STRING;

    unsigned int len = strlen(str);
    root->valueString = malloc(len+1);
    strcpy(root->valueString, str);
    return root;
}

/*********************************
 * Add Functions
 ********************************/
/**
 * 向BST中添加一个整数
 */
cBST_BOOL cBST_AddInt(cBST** root, const int valueInt) {
    if (isNULL(*root) == cBST_TRUE) {
        // 向一颗空树中添加该值
        *root = cBST_NewIntBST(valueInt);
        return cBST_TRUE;
    }

    if ((*root)->type != cBST_TYPE_INTEGER) {
        return cBST_FALSE;
    }

    if ( cmpInt( (*root)->valueInt, valueInt ) == 0 ) {
        return cBST_TRUE;
    } else if ( cmpInt( (*root)->valueInt, valueInt ) < 0 ) {
        if (isNULL((*root)->rightChild) == cBST_TRUE) {
            (*root)->rightChild = cBST_NewIntBST(valueInt);
            (*root)->rightChild->father = *root;
        } else {
            cBST_AddInt(&((*root)->rightChild), valueInt);
        }
    } else {
        if (isNULL((*root)->leftChild) == cBST_TRUE) {
            (*root)->leftChild = cBST_NewIntBST(valueInt);
            (*root)->leftChild->father = *root;
        } else {
            cBST_AddInt(&((*root)->leftChild), valueInt);
        }
    }
}

/**
 * 向cBST中添加一个double
 */
cBST_BOOL cBST_AddDouble(cBST** root, const double valueDouble) {
    if (isNULL(*root) == cBST_TRUE) {
        *root = cBST_NewDoubleBST(valueDouble);
        return cBST_TRUE;
    }

    if ((*root)->type != cBST_TYPE_DOUBLE) {
        return cBST_FALSE;
    }
    if ( cmpDouble( (*root)->valueDouble, valueDouble) == 0 ) {
        return cBST_TRUE;
    } else if ( cmpDouble( (*root)->valueDouble, valueDouble) < 0 ) {
        if (isNULL((*root)->rightChild) == cBST_TRUE) {
            (*root)->rightChild = cBST_NewDoubleBST(valueDouble);
            (*root)->rightChild->father = *root;
        } else {
            return cBST_AddDouble(&((*root)->rightChild), valueDouble);
        }
    } else {
        if (isNULL((*root)->leftChild) == cBST_TRUE) {
            (*root)->leftChild = cBST_NewDoubleBST(valueDouble);
            (*root)->leftChild->father = *root;
        } else {
            return cBST_AddDouble(&((*root)->leftChild), valueDouble);
        }
    }
}

/**
 * 向cBST中添加一个String
 */
cBST_BOOL cBST_AddString(cBST** root, const char* valueString) {
    if (isNULL(*root) == cBST_TRUE) {
        *root = cBST_NewStringBST(valueString);
        return cBST_TRUE;
    }

    // 向一个非STRING类型BST中插入String会返回失败
    if ((*root)->type != cBST_TYPE_STRING) {
        return cBST_FALSE;
    }

    if ( cmpString((*root)->valueString, valueString) == 0 ) {
        return cBST_TRUE;
    } else if ( cmpString((*root)->valueString, valueString) < 0 ) {
        if (isNULL((*root)->rightChild) == cBST_TRUE) {
            (*root)->rightChild = cBST_NewStringBST(valueString);
            (*root)->rightChild->father = *root;
        } else {
            return cBST_AddString(&((*root)->rightChild), valueString);
        }
    } else {
        if (isNULL((*root)->leftChild) == cBST_TRUE) {
            (*root)->leftChild = cBST_NewStringBST(valueString);
            (*root)->leftChild->father = *root;
        } else {
            return cBST_AddString(&((*root)->leftChild), valueString);
        }
    }
}

/********************************
 * Search Functions
 *******************************/
/**
 * 搜索Int
 */
cBST_BOOL cBST_SearchInt(cBST* root, const int valueInt) {
    if (isNULL(root) == cBST_TRUE) {
        return cBST_FALSE;
    }

    if ( cmpInt(root->valueInt, valueInt) == 0 ) {
        return cBST_TRUE;
    } else if ( cmpInt( root->valueInt, valueInt) < 0 ) {
        return cBST_SearchInt(root->rightChild, valueInt);
    } else {
        return cBST_SearchInt(root->leftChild, valueInt);
    }
}

/**
 * 搜索double
 */

cBST_BOOL cBST_SearchDouble(cBST* root, const double valueDouble) {
    if (isNULL(root) == cBST_TRUE) {
        return cBST_FALSE;
    }

    if ( cmpDouble( root->valueDouble, valueDouble) == 0 ) {
        return cBST_TRUE;
    } else if ( cmpDouble( root->valueDouble, valueDouble) < 0 ) {
        return cBST_SearchDouble(root->rightChild, valueDouble);
    } else {
        return cBST_SearchDouble(root->leftChild, valueDouble);
    }
}

cBST_BOOL cBST_SearchString(cBST* root, const char* str) {
    if (isNULL(root) == cBST_TRUE) {
        return cBST_FALSE;
    }

    if (cmpString(root->valueString, str) == 0) {
        return cBST_TRUE;
    } else if (cmpString(root->valueString, str) < 0) {
        return cBST_SearchString(root->rightChild, str);
    } else {
        return cBST_SearchString(root->leftChild, str);
    }
}

/********************************
 * Delete Functions
 *******************************/

void cBST_Free(cBST* root) {
    free( root->valueString ); // 释放该结点下的字符串
    free( root );
}

cBST_BOOL cBST_DeleteInt(cBST** root, const int valueInt) {
    if ( isNULL(*root) == cBST_TRUE ) {
        return cBST_FALSE;
    }
    
    if ( cmpInt( (*root)->valueInt, valueInt) == 0 ) { 
        // 删除当前结点
        if ( cBST_HasLeftChild(*root) == cBST_FALSE && cBST_HasRightChild(*root) == cBST_FALSE ) {
            // 当前结点是叶结点, 直接删除该结点
            if (isNULL((*root)->father) == cBST_FALSE) {
                // 如果该结点的父亲不为空
                if ((*root)->father->leftChild == *root) {
                    // 该结点是其父亲的左子结点
                    (*root)->father->leftChild = NULL;
                } else {
                    // 该结点是其父亲的右子结点
                    (*root)->father->rightChild = NULL;
                }
                cBST_Free(*root);
            } else {
                // 该结点的父亲是NULL，即该结点是根结点，此cBST只有一个结点
                cBST_Free(*root);
                *root = NULL;
            }
            return cBST_TRUE;
            
        } else if ( cBST_HasLeftChild(*root) == cBST_TRUE && cBST_HasRightChild(*root) == cBST_FALSE ) {
            // 只有左子树
            // 用左子树替代此结点
            if ( isNULL((*root)->father) == cBST_FALSE ) {
                cBST* father = (*root)->father;
                int child = 0;
                cBST* left = (*root)->leftChild;
                if ((*root)->father->leftChild == *root) {
                    child = cBST_LEFT;// 该结点是其父亲的左子结点
                } else {
                    child = cBST_RIGHT; // 该结点是其父亲的右子结点
                }
                cBST_Free(*root);

                if (child == cBST_LEFT) {
                    father->leftChild = left;
                    left->father = father;
                } else {
                    father->rightChild = left;
                    left->father = father;
                }
            } else {
                // 该结点已经是根结点
                cBST* left = (*root)->leftChild;
                cBST_Free(*root);
                *root = left;
                (*root)->father = NULL; // 已经是根结点，因此需要将其父亲设为NULL
            }
            return cBST_TRUE;
            
        } else if ( cBST_HasLeftChild(*root) == cBST_FALSE && cBST_HasRightChild(*root) == cBST_TRUE ) {
            // 只有右子树
            if (isNULL((*root)->father) == cBST_FALSE) {
                // 父结点存在
                cBST* father = (*root)->father;
                int child = 0;
                cBST* right = (*root)->rightChild;
                if ((*root)->father->leftChild == *root) {
                    child = cBST_LEFT;// 该结点是其父亲的左子结点
                } else {
                    child = cBST_RIGHT; // 该结点是其父亲的右子结点
                }
                cBST_Free(*root);

                if (child == cBST_LEFT) {
                    father->leftChild = right;
                    right->father = father;
                } else {
                    father->rightChild = right;
                    right->father = father;
                }
            } else {
                // 父结点不存在,该结点是根结点
                cBST* right = (*root)->rightChild;
                cBST_Free(*root);
                *root = right;
                (*root)->father = NULL; // 已经是根结点，因此需要将其父亲设为NULL
            }
            return cBST_TRUE;
            
        } else {
            // 两个子树都存在
            // 寻找右子树中的最小值，替换该结点的值
            cBST** node = &((*root)->rightChild);
            while (cBST_HasLeftChild(*node)) {
                node = &((*node)->leftChild);
            }

            (*root)->valueInt = (*node)->valueInt;
            // 删除node
            return cBST_DeleteInt(node, (*node)->valueInt);
            
        }
        
    } else if ( cmpInt( (*root)->valueInt, valueInt) < 0 ) { 
        // 目标结点可能存在于右子树中
        return cBST_DeleteInt(&( (*root)->rightChild ), valueInt);
        
    } else { 
        // 目标结点可能存在于左子树中
        return cBST_DeleteInt(&( (*root)->leftChild ), valueInt);
    } 
}


/**
 * 删除valueDouble
 */

/**
 * 删除valueString
 */


#endif