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

#define true 1
#define false 0

// Struct of a tree
typedef struct Leaf {
    struct Leaf *left;
    struct Leaf *right;
    int value;
    int pos;
} Leaf;

// Find a value in a vector
int find(int *vector, int size, int match) {
    int counter = 0;
    while (counter < size) {
        if (vector[counter] == match) {
            return(counter);
        }
        counter++;
    }
    return(-1);
}

// Variables to create a tree/vector
int maxrand = 10;
int counter = 0;

// Create a tree/vector
Leaf *makeTree(int *vector,int size) {
    if (size != 0) {
        Leaf *aux = (Leaf *)malloc(sizeof(Leaf));
        int rs = -1;
        int value = 0;
        do {
            value = rand()%(maxrand+1);
            rs = find(vector,counter,value);
        } while (rs != -1);
        vector[counter] = value;
        aux->value = value;
        aux->pos = counter;
        counter++;
        aux->left = makeTree(vector,size/2);
        aux->right = makeTree(vector,size - (size/2) - 1);
        return(aux);
    } else {
        return(NULL);
    }
}

// Print a vector
void print(int *vector,int size) {
    int counter = 0;
    while (counter < size) {
        printf("[%d] => %d\n", counter,vector[counter]);
        counter++;
    }
}

// Print a tree
void printt(Leaf *tree) {
    if (tree != NULL) {
        printf("[%d] => %d\n",tree->pos,tree->value);
        printt(tree->left);
        printt(tree->right);
    }
}

int iterator = 0;
// Find in a tree
int findt(Leaf *tree,int value) {
    iterator++;
    if (tree == NULL) {
        return(-1);
    } else {
        if (tree->value == value) {
            return(tree->pos);
        } else {
            int rs = findt(tree->left,value);
            if (rs == -1) {
                return(findt(tree->right,value));
            } else {
                return(rs);
            }
        }
    }
    return(-1);
}

// Main Loop
int main(int argc, char *argv[]) {
    if (argc != 4) {
        printf("You need to use %s [size] [random max number] [search].\nEx: %s 30 100 8.\n",argv[0],argv[0]);
    } else {
        srand(time(NULL));
        int size = atoi(argv[1]);
        maxrand = atoi(argv[2]);
        int search = atoi(argv[3]);

        int vector[size];
        Leaf *tree = makeTree(vector,size);
        //printf("Original Vector:\n");
        //print(vector,size);
        printf("\nTree:\n");
        printt(tree);
        int res = find(vector,size,search);
        if (res == -1) {
            printf("\nNot found using While,%d iteractions.\n", size);
        } else {
            printf("\nFound using While (pos = %d),%d iteractions.\n",res,res+1);
        }
        res = findt(tree,search);
        if (res == -1) {
            printf("\nNot found using Tree, %d iteraction.\n", iterator);
        } else {
            printf("\nFound using Tree (pos = %d), %d iteractions.\n",res,iterator);
        }
    }
    return(false);
}