#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <math.h>

//Samuel Varela, Javier Rapela, Javier Loureiro

double microsegundos() {
    struct timeval t;
    if (gettimeofday(&t, NULL) < 0 )
        return 0.0;
    return (t.tv_usec + t.tv_sec * 1000000.0);
}

void inicializar_semilla() {
    srand(time(NULL));
}

struct nodo {
    int elem;
    int num_repeticiones;
    struct nodo *izq, *der;
};

typedef struct nodo *posicion;
typedef struct nodo *arbol;


static struct nodo *crearnodo(int e) {
    struct nodo *p = malloc(sizeof(struct nodo));
    if (p == NULL) {
        printf("memoria agotada\n"); exit(EXIT_FAILURE);
    }
    p->elem = e;
    p->num_repeticiones = 1;
    p->izq = NULL;
    p->der = NULL;
    return p;
}

arbol insertar(int e, arbol a){
    if (a == NULL)
        return crearnodo(e);
    else if (e < a->elem)
        a->izq = insertar(e, a->izq);
    else if (e > a->elem)
        a->der = insertar(e, a->der);
    else
        a->num_repeticiones++;
    return a;
}

arbol creararbol() { /* devuelve un arbol vacio */
    arbol e =NULL;
    return e;
}

int esarbolvacio(arbol e){
    return (e==NULL);
}

posicion buscar(int key, arbol root){

    if (root == NULL || root->elem == key)
        return root;

    if (root->elem < key)
        return buscar(key, root->der);

    return buscar(key,root->izq);
}



void liberarMemoria(arbol nodo){
    if (nodo != NULL) {

        liberarMemoria(nodo->izq);
        liberarMemoria(nodo->der);
        free(nodo);
    }
}

arbol eliminararbol(arbol nodo){
    liberarMemoria(nodo);
    nodo=NULL;
    return nodo;
}

posicion hijoizquierdo(arbol nodo){
    return nodo->izq;
}

posicion hijoderecho(arbol nodo){
    return nodo->der;
}

int elemento(posicion nodo){
    return nodo->elem;
}

int numerorepeticiones(posicion nodo){
    return nodo->num_repeticiones;
}

int altura(arbol node){
    if (node == NULL) {
        return -1;
    }else {

        int altizq = altura(node->izq);
        int altder = altura(node->der);

        if (altizq > altder)
            return (altizq + 1);
        else
            return (altder + 1);
    }
}

void visualizar2(arbol e){
    if(esarbolvacio(e)){
        return;
    }
    if(e->izq != NULL) {
        printf("(");
    }
    visualizar2(e->izq);
    if(e->izq != NULL) {
        printf(")");
    }
    printf(" %d ",e->elem);
    if(e->der != NULL) {
        printf("(");
    }
    visualizar2(e->der);
    if(e->der != NULL) {
        printf(")");
    }

}

void visualizar(arbol e){
    if(esarbolvacio(e)){
        printf("().");
    }else {
        visualizar2(e);printf(".");
    }
}


void test(){
    int i;
    arbol e = creararbol();
    printf("arbol vacio: ");
    visualizar(e);
    printf("\naltura del arbol: ");
    printf("%d",altura(e));
    e=insertar(3,e);
    printf("\nInserto un 3\n");
    e=insertar(1,e);
    printf("Inserto un 1\n");
    e=insertar(2,e);
    printf("Inserto un 2\n");
    e=insertar(5,e);
    printf("Inserto un 5\n");
    e=insertar(4,e);
    printf("Inserto un 4\n");
    e=insertar(5,e);
    printf("Inserto un 5\n");
    printf("arbol: ");
    visualizar(e);
    printf("\n");
    printf("altura del arbol: ");
    printf("%d",altura(e));
    printf("\n");
    for(i=1;i<=6;i++){
        if(buscar(i,e)!=NULL) {
            printf("Busco %d y encuentro %d repetido: %d veces\n",i,i ,buscar(i, e)->num_repeticiones);
        }else{
            printf("Busco %d y no encuentro nada\n",i);
        }
    }
    printf("Borro todos los nodos liberando la memoria:\n");
    e=eliminararbol(e);
    printf("arbol vacio: ");
    visualizar(e);
    printf("\naltura del arbol: ");
    printf("%d",altura(e));
}

void printINS(double tiemposIns[6]){
    int cont=0;
    int n;
    printf("\nInsercion de n elementos\n");
    printf("n        t(n)        t(n)/0.9       t(n)/1.2        t(n)/1.5\n");
    for(n=8000;n<=256000;n=n*2){
        printf("%d    %f     %f     %f     %f\n", n, tiemposIns[cont], tiemposIns[cont]/pow(n,0.9), tiemposIns[cont]/pow(n,1.2), tiemposIns[cont]/pow(n,1.5));
        cont++;
    }
}

void printBUS(double tiemposBus[6]){
    int cont=0;
    int n;
    printf("\nBusqueda de n elementos\n");
    printf("n        t(n)        t(n)/0.9       t(n)/1.2        t(n)/1.5\n");
    for(n=8000;n<=256000;n=n*2){
        printf("%d    %f     %f     %f     %f\n", n, tiemposBus[cont], tiemposBus[cont]/pow(n,0.9), tiemposBus[cont]/pow(n,1.2), tiemposBus[cont]/pow(n,1.5));
        cont++;
    }

}


int main() {
    int n, cont, random;
    int listaIns=0;
    int listaBus=0;
    arbol a;
    double t1, t2, t_ins, t_bus;
    double tiemposIns[6];
    double tiemposBus[6];
    test();
    printf("\n\nn        t_ins(n)        t_bus(n)\n");
    for(n=8000;n<=256000;n=n*2){
        inicializar_semilla();
        a = creararbol();
        t1=microsegundos();
        for(cont=0;cont<n;cont++){
            random=(rand() % n);
            a = insertar(random,a);
        }
        t2=microsegundos();
        t_ins=t2-t1;
        tiemposIns[listaIns]=t_ins;
        listaIns++;
        t1=microsegundos();
        for(cont=0;cont<n;cont++){
            random=(rand() % n);
            buscar(random,a);
        }
        t2=microsegundos();
        t_bus=t2-t1;

        tiemposBus[listaBus]=t_bus;
        listaBus++;

        printf("%d    %f    %f\n", n, t_ins, t_bus);
    }
    printINS(tiemposIns);
    printBUS(tiemposBus);
    return 0;
}