/**
 * @brief Helper func: rotate left (Black-Red tree rotation)
 * @param node a node
 * @param tree a tree
 */
void rotateLeft(Node *node, RBTree *tree)
{
    Node *new_node = node->right;
    Node *par = node->parent;
    int rootValidator = 0;
    if (node->parent == NULL)
    {
        rootValidator = 1;
    }
    if (new_node == NULL)
    {
        return;
    }
    node->right = new_node->left;
    new_node->left = node;
    node->parent = new_node;
    if (node->right != NULL)
    {
        node->right->parent = node;
    }
    if (par != NULL)
    {
        if (node == par->left)
        {
            par->left = new_node;
        }
        else if (node == par->right)
        {
            par->right = new_node;
        }
    }
    new_node->parent = par;
    if ((node->parent != NULL) && (rootValidator == 1))
    {
        tree->root = node->parent;
    }

}

/**
 * @brief Helper func: rotate right (Black-Red tree rotation)
 * @param node a node
 * @param tree a tree
 */
void rotateRight(Node *nodePtr, RBTree *tree)
{
    Node *new_node = nodePtr->left;
    Node *par = nodePtr->parent;
    int rootValidator = 0;

    if (nodePtr->parent == NULL)
    {
        rootValidator = 1;
    }
    if (new_node == NULL)
    {
        return;
    }
    nodePtr->left = new_node->right;
    new_node->right = nodePtr;
    nodePtr->parent = new_node;

    if (nodePtr->left != NULL)
    {
        nodePtr->left->parent = nodePtr;
    }

    if (par != NULL)
    {
        if (nodePtr == par->left)
        {
            par->left = new_node;
        }
        else if (nodePtr == par->right)
        {
            par->right = new_node;
        }
    }
    new_node->parent = par;
    if ((nodePtr->parent != NULL) && (rootValidator == 1))
    {
        tree->root = nodePtr->parent;
    }
}


/**
* Scenario 4 from the specifications
* @param node a node
* @param tree a tree
*/
void scenario4Insertion(Node *nodePtr, RBTree *tree)
{
    Node *par = nodePtr->parent;
    Node *grand = nodePtr->parent->parent;

    if (grand->left == par)
    {
        if (par->right == nodePtr)
        {
            rotateLeft(par, tree);
            rotateRight(grand, tree);
            nodePtr->color = BLACK;
            grand->color = RED;

        }
        else
        {

            rotateRight(grand, tree);
            par->color = BLACK;
            grand->color = RED;

        }

    }

    else if (grand->right == par)
    {
        if (par->left == nodePtr)
        {
            rotateRight(par, tree);
            rotateLeft(grand, tree);
            nodePtr->color = BLACK;
            grand->color = RED;
        }
        else
        {
            rotateLeft(grand, tree);
            par->color = BLACK;
            grand->color = RED;
        }

    }

}


/**
 * @brief Fix tree function. this function is called in order to fix the tree structure aftetr
 * insert
 * @param node a node that was inserted
 * @param tree a tree to fix
 */
void rotate(Node *node, RBTree *tree)
{
    if (node->parent == NULL)
    {   //INSERT - CASE 1
        if (node->parent == NULL)
        {
            node->color = BLACK;
        }
    }
    else if (node->parent->color == BLACK)
    {
        return;
    }
    else if (getUncle(tree, node) != NULL && getUncle(tree, node)->color == RED
             && node->color == RED)
    {
        node->parent->color = BLACK;
        getUncle(tree, node)->color = BLACK;
        node->parent->parent->color = RED;
        rotate(node->parent->parent, tree);
    }
    else if ((getUncle(tree, node) != NULL && getUncle(tree, node)->color == BLACK
             && node->parent->color == RED) ||
             (getUncle(tree, node) == NULL
             && node->parent->color == RED))
    {
        scenario4Insertion(node, tree);
    }
}


/**
 * add an item to the tree
 * @param tree: the tree to add an item to.
 * @param data: item to add to the tree.
 * @return: 0 on failure, other on success. (if the item is already in the tree - failure).
 */
int addToRBTree(RBTree *tree, void *data)
{
    // Check If Contains
    if (containsRBTree(tree, data) != 0)        // data is already in the tree
    {
        return 0;
    }

    // Create Node
    Node *nodePtr = (Node *) malloc(sizeof(Node));

    Node createdNode = {NULL, NULL, NULL, RED, data};
    *nodePtr = createdNode;

    // Case 1
    if (tree->size == 0)
    {
        addCaseOne(tree, nodePtr);    // size++ inside
        return 1;
    }


    // aggressive - insert node
    insertAggressive(tree, nodePtr);


    // rotate (Cases 2,3,4)
    rotate(nodePtr, tree);

    // update Tree Root (tree field)
    if (tree->root->parent != NULL)
    {
        tree->root = tree->root->parent;
    }

    tree->size++;
    return 1;


}