#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* TODO: split into files
    RedBlackTree.c & .h
    RedBlackTree Node.c & .h
    main.c
*/

#ifndef NULL
#define NULL 0
#endif

typedef enum COLOR_ {BLACK, RED} COLOR;

typedef struct RedBlackTreeNode {
    COLOR color;
    int value;
    struct RedBlackTreeNode *parent, *left, *right;

} RBTNode;

typedef struct RedBlackTree {
    RBTNode *root;
    RBTNode *median1, *median2;
    bool parity;

    // functions pointers
    void (*insert)(struct RedBlackTree *self, RBTNode *node);
    void (*print_median)(struct RedBlackTree *self);
    RBTNode* (*get_successor)(struct RedBlackTree *self, RBTNode *node);
    RBTNode* (*get_predecessor)(struct RedBlackTree *self, RBTNode *node);
} RBT;

RBTNode* new_node(int value) {
    // should be freed after usage

    RBTNode* node = (RBTNode *)malloc(sizeof(RBTNode));
    node->value = value;
    node->color = BLACK;
    node->parent = node->left = node->right = NULL;
    return node;
}

void free_node(RBTNode *node) {
    free(node);
    node = NULL;
}

void in_order_traversal(RBTNode *node, void (*callback_function)(RBTNode *node)) {
    // scans the tree in O(n)
    // execute callback function on each node
    if (node == NULL)
        return;
    in_order_traversal(node->left, callback_function);
    callback_function(node);
    in_order_traversal(node->right, callback_function);
}

void RBT_print_median(RBT* self) {
    RBTNode* median;
    if (self->parity == 0)
        median = self->median1;
    else
        median = self->median1 < self->median2 ? self->median1 : self->median2;

    printf("The median is: %d\n", median->value);
}

RBT* RedBlackTreeConstruct() {
    // creates a tree and initiallize the struct's function
    // should be freed after_usage

    RBT *rbt = (RBT *)malloc(sizeof(RBT));
    rbt->root = NULL;
    rbt->parity = 0;

    // TODO: change to actual function
    rbt->insert = NULL;
    rbt->print_median = RBT_print_median;
    rbt->get_successor = NULL;
    rbt->get_predecessor = NULL;
    return rbt;
}

void RedBlackTreeDestruct(RBT* tree) {
    // frees all elements
    in_order_traversal(tree->root, free_node);
    free(tree);
    tree = NULL;
}

void fill_array_with_random(int *arr, int length) {
    for (int i = 0; i < length; i++)
        arr[i] = rand() % 1024;
}

void the_algorithm(int *arr, int n1, int n2, int n3) {

    RBT *tree = RedBlackTreeConstruct();
    for (int i = 0; i < n1; i++)
        tree->insert(tree, new_node(arr[i]));
    tree->print_median(tree);
    for (int i = n1; i < n2; i++)
        tree->insert(tree, new_node(arr[i]));
    tree->print_median(tree);
    for (int i = n2; i < n3; i++)
        tree->insert(tree, new_node(arr[i]));
    tree->print_median(tree);

    RedBlackTreeDestruct(tree);
}

int main(int argc, char *argv[]) {
    srand(time(NULL));

    RBTNode *node = new_node(1);
    int A[200], B[400], C[800];
    int a_n1, a_n2, a_n3;
    int b_n1, b_n2, b_n3;
    int c_n1, c_n2, c_n3;

    a_n1 = (sizeof(A) / sizeof(*A)) / 4;
    a_n2 = a_n1 * 2;
    a_n3 = a_n1 * 3;

    b_n1 = (sizeof(A) / sizeof(*A)) / 4;
    b_n2 = b_n1 * 2;
    b_n3 = b_n1 * 3;

    c_n1 = (sizeof(A) / sizeof(*A)) / 4;
    c_n2 = c_n1 * 2;
    c_n3 = c_n2 * 3;

    fill_array_with_random(A, sizeof(A) / sizeof(*A));
    fill_array_with_random(B, sizeof(B) / sizeof(*B));
    fill_array_with_random(C, sizeof(C) / sizeof(*C));


    the_algorithm(A, a_n1, a_n2, a_n3);
    the_algorithm(B, b_n1, b_n2, b_n3);
    the_algorithm(B, c_n1, c_n2, c_n3);

    free_node(node);
}