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

/* structure from which binary search tree consists of */

/* Initializes binary search tree.
 * Parameter root is pointer to pointer which points to the tree's root.
 */
void bst_init(bst_node_t **root){
    bst_node_t *newNode = malloc(sizeof(bst_node_t));
    newNode->value = NULL;
    newNode->parent = NULL;
    newNode->left = NULL;
    newNode->right = NULL;
    *root = newNode;
}

/* Insert key to binary search tree.
 * Parameter root is pointer to pointer which points to the tree's root.
 * value is the string which is put to the tree (key), you're not supposed to
 * make copy of the string.
 * Returns 0 if succesful, -1 otherwise
 */
int bst_insert(bst_node_t **root, char *value){
    bst_node_t *newNode = malloc(sizeof(bst_node_t));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->value = value;
    if((*root)->value == NULL){
     //   printf("Empty tree, making new root\n");
        newNode->parent = NULL;
        *root = newNode;
        return 0;
    }

    bst_node_t *current = *root;

    while(1){
        int comparison = strcmp((current->value),value);
      //  printf("Comparing %s and %s\n", current->value, value);
        if(comparison < 0){ //Current->value < value, mennaan oikealle
            if(current->right == NULL){
              //  printf("Inserted right\n");
                current->right = newNode;
                newNode->parent = current;
                return 0;
            }
            else {
                current = current->right;
                continue;
            }
        }
        else if(comparison > 0){ //Current->value > value, mennaan vasemmalle
            if(current->left == NULL){
                current->left = newNode;
                newNode->parent = current;
             //   printf("Inserted left\n");
                return 0;
            }
            else {
                current = current->left;
                continue;
            }
        }
        else{ // current->data == value, virhe
          //  printf("Error\n");
            return -1;
        }
    }
}

void replaceNode(bst_node_t* node1, bst_node_t* node2){
    if(node1->parent != NULL){
        if(node1->parent->left == node1){
            node1->parent->left = node2;
        }
        else{
            node1->parent->right = node2;
        }
    }
    else{
        if(node2 != NULL) node2->parent = NULL;
    }
    if(node1->left != node2 && node2 != NULL){
        node2->left = node1->left;
        if(node1->left != NULL){
            node1->left->parent = node2;
        }
    }
    if(node1->right != node2 && node2 != NULL){
        node2->right = node1->right;
        if(node1->right != NULL){
            node1->right->parent = node2;
        }
    }
}

/* Delete key from binary search tree.
 * Parameter root is pointer to pointer which points to the tree's root.
 * Node is pointer to node which needs to be removed.
 * Returns pointer to value of the removed node if succesful, null otherwise.
 */
char *bst_delete(bst_node_t **root, bst_node_t *node){

    char* value = node->value;
    bst_node_t* newRoot = NULL;
    int changingRoot = 0;
    if(node == *root) changingRoot = 1;

    if(node->left == NULL && node->right == NULL){ //No children

        replaceNode(node,NULL);
        if(changingRoot == 1){
            (*root)->value = NULL;
            return value;
        }
        free(node);
    }
    else if(!(node->left != NULL && node->right != NULL)){ // One child
        if(node->left != NULL){
            newRoot = node->left;
            replaceNode(node,node->left);
            free(node);
        }
        else{
            newRoot = node->right;
            replaceNode(node,node->right);
            free(node);
        }
    }
    else { //Two children
        bst_node_t* successor = bst_next(node);
        replaceNode(node,successor);
        if(node->left != NULL){
            newRoot = node->left;
            replaceNode(node,node->left);
            free(node);
        }
        else{
            newRoot = node->right;
            replaceNode(node,node->right);
            free(node);
        }
    }

    if(changingRoot == 1){
        *root = newRoot;
    }

    return value;
}

/* Find key from bst (binary search tree).
 * Parameter root is pointer to the trees root.
 * value is the key which we are searching
 * Returns pointer to the node which has the same value when compared using
 * strcmp.
 */
bst_node_t *bst_find(bst_node_t *root, char *value){
    bst_node_t* current = root;
    while(1){
     //   printf("Comparing %s and %s\n", current->value, value);
        int comparison = strcmp((current->value),value);
        if(comparison < 0){ //Current->data < value, mennaan oikealle
            if(current->right == NULL){ //Not found
                return NULL;
            }
            else {
                current = current->right;
                continue;
            }
        }
        else if(comparison > 0){ //Current->data > value, mennaan vasemmalle
            if(current->left == NULL){ //Not found
                return NULL;
            }
            else {
                current = current->left;
                continue;
            }
        }
        else{ // current->data == value, loytyi
            return current;
        }
    }
}

/* Find next node from the node passed in parameter (meaning that the value
 * of the node pointed by parameter node is smaller than the value of the
 * successor but there are no nodes in bst that have value smaller than
 * successor and greater than node pointed by parameter node)
 * Parameter node gives pointer to node which successor we are finding of.
 * Returns pointer to successor node.
 */
bst_node_t *bst_next(bst_node_t *node){
    if(node->right == NULL){ //Mennaan ylos, kunnes siirrytaan oikealle
        bst_node_t* current = node;
        while(1){
            bst_node_t* parentNode = current->parent;
            if(parentNode == NULL){
                return NULL;
            }
            if(parentNode->left == current){
                return parentNode;
            }
            else{
                current = parentNode;
            }
        }
    }

    else{ //Yksi oikealle, ja sitten vasemmalle niin pitkalle, kuin paasee
        bst_node_t* current = node->right;
        while(current->left != NULL){
            current = current->left;
        }
        return current;
    }
}

/* Find node that has minimal value in bst.
 * Parameter root gives pointer to the root of the tree.
 * Returns pointer to node that has minimal value in bst.
 */
bst_node_t *bst_find_min(bst_node_t *root){
    //Mennaan vasemmalle niin pitkalle kuin paasee
    bst_node_t* current = root;
    while(current->left != NULL){
        current = current->left;
    }
    return current;

}

/* Find node that has maximal value in bst.
 * Parameter root gives pointer to the root of the tree.
 * Returns pointer to node that has maximal value in bst.
 */
bst_node_t *bst_find_max(bst_node_t *root){
    //Mennaan oikealle niin pitkalle kuin paasee
    bst_node_t* current = root;
    while(current->right != NULL){
        current = current->right;
    }
    return current;
}