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

int comp(const int32_t *i, const int32_t *j) {
    return *i - *j;
}

struct TreeNode {
    void *val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode *Insert(struct TreeNode *root, void *val,
                        int (*compare)(const void *, const void *)) {
    if (root == 0) {
        root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
        root->val = val;
        root->left = 0;
        root->right = 0;
        return root;
    }

    if ((*compare)((void *) val, (void *) root->val) <= 0) {
        root->left = Insert(root->left, val, compare);
    } else if ((*compare)((void *) val, (void *) root->val) > 0) {
        root->right = Insert(root->right, val, compare);
    }

    return root;
}

void Write_Inorder(struct TreeNode *root,
                   void *target,
                   size_t num,
                   size_t size,
                   int *ptr) {
    if (root != 0) {
        Write_Inorder(root->left, target, num, size, ptr);

        memcpy((char *) target + (size * (*ptr)++), root->val, size);

        Write_Inorder(root->right, target, num, size, ptr);
    }
}

void Destroy(struct TreeNode *root) {
    if (root != 0) {
        Destroy(root->left);
        Destroy(root->right);
        free(root);
    }
}

int32_t Get_Random_In_Range(/* in */ int32_t lower, /* in */ int32_t upper) {
    return lower + rand() % (upper - lower + 1);;
}

int16_t TreeSort( /* in */ void *base,
        /* in */ size_t num,
        /* in */ size_t size,
        /* in */ int (*compare)(const void *, const void *)) {
    struct TreeNode *bst = 0;
    int ptr = 0;
    int i = 0;

    if (base == 0 || compare == 0) {
        return -1;
    }

    for (i = 0; i < num; ++i) {
        bst = Insert(bst, (char *) base + (size * i), compare);
    }

    Write_Inorder(bst, base, num, size, &ptr);

    Destroy(bst);

    return 0;
}

int main(void) {
    int32_t *arr = 0;
    uint32_t i = 0;

    srand(time(NULL));

    arr = (int32_t *) malloc(sizeof(int32_t) * 12);

    for (i = 0; i < 12; ++i) {
        ((int32_t *) arr)[i] = Get_Random_In_Range(-300, 300);
    }

    for (i = 0; i < 12; ++i) {
        printf("%5i ", ((int32_t *) arr)[i]);
    }
    printf("\n");

    TreeSort(arr, 12, sizeof(int32_t), (int (*)(const void *, const void *)) (comp));

    for (i = 0; i < 12; ++i) {
        printf("%5i ", ((int32_t *) arr)[i]);
    }

    return 0;
}