#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <math.h>
#define LONGITUD_CLAVE 30
#define LONGITUD_SINONIMOS 300
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    typedef struct {
        char clave [LONGITUD_CLAVE];
        char sinonimos [LONGITUD_SINONIMOS];
    } item;

    typedef struct entrada_ {
        int ocupada;
        char clave [LONGITUD_CLAVE];
        char sinonimos [LONGITUD_SINONIMOS];
    } entrada;

    typedef int colisiones;

    typedef int pos;

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    typedef entrada *tabla_cerrada;
        tabla_cerrada d;

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    double microsegundos() {
        /* obtiene la hora del sistema en microsegundos */
        struct timeval t;

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


// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    void mostrarTiemposCotas(double time, int n, int flag) {
        double cotasub, cotaaxus, cotasobre;

        cotasub= time / pow(n, 0.8);
        cotaaxus= time / n;
        cotasobre= time / pow(n, 1.2);
        if (flag==0) {
            printf("%13d%17f%13f%13f%13f\n", n, time, cotasub, cotaaxus,
               cotasobre);
        } else {
            printf("%3s%10d%17f%13f%13f%13f\n","(*)", n, time, cotasub, cotaaxus,
               cotasobre);
        }
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    int dispersionA(char *clave, int tamTabla) {
        int i, valor = clave[0], n = strlen(clave);


        for (i = 1; i < n; i++)
            valor += clave[i];
        return valor % tamTabla;
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    int dispersionB(char *clave, int tamTabla) {
        int i, n = MIN(8, strlen(clave));
        unsigned int valor = clave[0];


        for (i = 1; i < n; i++)
            valor = (valor<<5) + clave[i]; /* el desplazamiento de 5 bits equivale a */
        return valor % tamTabla;        /* multipicar por 32 */
    }


// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    void inicializar_cerrada(tabla_cerrada *diccionario, int TAM){


        for(int i = 0; i<TAM; i++){
            (*diccionario)[i].ocupada=0;
        }
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    int resolucionLineal(int pos_inicial, int num_intento){
        return num_intento;
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    int resolucionCuadratica(int pos_inicial, int num_intento){
        return (num_intento )*(num_intento );
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    pos buscar_cerrada(char *clave, tabla_cerrada diccionario, int TAM,
        int (*dispersion)(char *, int),
        int (*resolucion_colisiones)(int pos_inicial,
        int num_intento)){
        int i=0;
        int x = (*dispersion)(clave, TAM);


        pos PosActual = x;
        while ( (diccionario[PosActual].ocupada != 0) &&
                (strcmp(diccionario[PosActual].clave,clave) != 0) ){
            i++;
            PosActual = (x + (*resolucion_colisiones) (x,i))%TAM;
        }
        return PosActual;
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    colisiones insertar_cerrada(char *clave, char *sinonimos,
                             tabla_cerrada *diccionario, int TAM,
                             int (*dispersion)(char *, int),
                             int (*resolucion_colisiones)(int pos_inicial,
                             int num_intento)) {

        int i = 0;
        pos Posicion = buscar_cerrada(clave, *diccionario, TAM,
                              dispersion, resolucion_colisiones);


        if ((*diccionario)[Posicion].ocupada    != 1){
            strcpy((*diccionario)[Posicion].clave, clave);
            strcpy((*diccionario)[Posicion].sinonimos, sinonimos);
                    (*diccionario)[Posicion].ocupada = 1;
        }
        return i;
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    int ndispersion(char *clave, int tamTabla) {


        if (strcmp(clave, "ANA")==0) return 7;
        if (strcmp(clave, "JOSE")==0) return 7;
        if (strcmp(clave, "OLGA")==0) return 7;
        return 6;
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    void mostrar_cerrada(tabla_cerrada diccionario, int TAM) {
        for (int i = 0; i < TAM; i++) {
            printf(" %d%s%s%s\n",i,"- (",(diccionario[i].clave),")\n");
        }
        printf(")\n");
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

     void resultadoBusqueda(tabla_cerrada diccionario, char* nombre, int TAM,
                            int (*dispersion)(char *, int),
                            int (*resolucion_colisiones)(int pos_inicial,
                            int num_intento)) {
        pos p;
        p = buscar_cerrada(nombre, diccionario, TAM, dispersion, resolucion_colisiones);
        if (strcmp(diccionario[p].clave, nombre)==0) {
            printf("%s%s%s%s\n", "Al buscar: ", nombre, ", encuentro: ",nombre);
        } else {
            printf("%s%s\n", "No encuentro: ",nombre);
        }
    }


// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    void test(int (*resolucion_colisiones)(int pos_inicial,
                            int num_intento)) {
        tabla_cerrada d = malloc(11 * sizeof(entrada));
        int TAM = 11;


        inicializar_cerrada(&d, 11);
        insertar_cerrada("ANA", "Vacio", &d, TAM, ndispersion, resolucion_colisiones );
        insertar_cerrada("LUIS", "Vacio", &d, TAM, ndispersion, resolucion_colisiones);
        insertar_cerrada("JOSE", "Vacio", &d, TAM, ndispersion,  resolucion_colisiones);
        insertar_cerrada("OLGA", "Vacio", &d, TAM, ndispersion,  resolucion_colisiones);
        insertar_cerrada("ROSA", "Vacio", &d, TAM, ndispersion,  resolucion_colisiones);
        insertar_cerrada("IVAN", "Vacio", &d, TAM, ndispersion,  resolucion_colisiones);
        mostrar_cerrada(d,TAM);
        resultadoBusqueda(d, "ANA", 11, ndispersion, resolucion_colisiones);
        resultadoBusqueda(d, "LUIS", 11, ndispersion, resolucion_colisiones);
        resultadoBusqueda(d, "JOSE", 11, ndispersion, resolucion_colisiones);
        resultadoBusqueda(d, "OLGA", 11, ndispersion, resolucion_colisiones);
        resultadoBusqueda(d, "ROSA", 11, ndispersion, resolucion_colisiones);
        resultadoBusqueda(d, "IVAN", 11, ndispersion, resolucion_colisiones);
        resultadoBusqueda(d, "CARLOS", 11, ndispersion, resolucion_colisiones);
        printf("\n");
        free(d);

    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    colisiones insertarDatos(item datos[], tabla_cerrada *d, int TamTabla, int TamDatos,
                            int (*dispersion)(char *, int),
                            int (*resolucion_colisiones)(int pos_inicial,
                            int num_intento)){
        int i = 0;
        colisiones cont = 0;


        for(i=0; i<TamDatos; i++){
            cont += insertar_cerrada(datos[i].clave,datos[i].sinonimos, d, TamTabla,
                                     dispersion, resolucion_colisiones);

        }
        return cont;
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    int leer_sinonimos(item datos[]) {
        char c;
        int i, j;
        FILE *archivo;


        if ((archivo = fopen("sinonimos.txt", "r")) == NULL) {
            printf("Error al abrir ’sinonimos.txt’\n");
            return(EXIT_FAILURE);
        }
        for (i = 0; fscanf(archivo, "%s", datos[i].clave) != EOF; i++) {
            if ((c = fgetc(archivo)) != '\t') {
                printf("Error al leer el tabulador\n");
                return(EXIT_FAILURE);
            }
            for (j = 0; (c = fgetc(archivo)) != '\n'; j++) {
                if (j < LONGITUD_SINONIMOS - 1)
                    datos[i].sinonimos[j] = c;
            }
            datos[i].sinonimos[MIN(j, LONGITUD_SINONIMOS -1)] = '\0';
        }
        if (fclose(archivo) != 0) {
            printf("Error al cerrar el fichero\n");
        return(EXIT_FAILURE);
        }
        return(i);
    }


// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------


    double comprobacionTiempoAnomalo (int n, char * orden, int (*resolucion_colisiones)
                                      (int pos_inicial,
                                      int num_intento),
                                      int (*dispersion)(char *, int)) {
        int cont = 0;
        double atime, btime;
        double time;
        int TamTabla = 38197;
        tabla_cerrada d;
        int TamDatos = 19062;
        item datos[TamDatos];


        d = malloc (TamTabla * sizeof(entrada));
        atime = microsegundos();
        while (cont <= 10000) {
            leer_sinonimos(datos);
            insertarDatos(datos, &d, TamTabla, TamDatos, dispersion, resolucion_colisiones);
            for (int i = 0; i < n; i++)
                resultadoBusqueda(d, d[i].clave, TamTabla,dispersion, resolucion_colisiones);
            cont++;
        }
        btime = microsegundos();
        time = btime - atime;

        cont = 0;
        atime = microsegundos();
        while (cont <= 10000) {
            leer_sinonimos(datos);
            insertarDatos(datos, &d, TamTabla, TamDatos, dispersion, resolucion_colisiones);
            cont++;
        }
        btime = microsegundos();
        time = time - (btime - atime);
        time = time / cont;

        return time;
    }

// ---------------------------------------------------------------------
// *********************************************************************
// ---------------------------------------------------------------------

    int main(){
        int TamTabla = 38197;
        tabla_cerrada d= malloc (TamTabla * sizeof(entrada));
        int TamDatos = 19062;
        item datos[TamDatos];


        printf("Leidos correctamente %i sinonimos\n",leer_sinonimos(datos));
        insertarDatos(datos, &d, TamTabla, TamDatos, dispersionA, resolucionLineal);
        mostrar_cerrada(d, 1000);
        resultadoBusqueda(d, "zuzo", TamTabla,dispersionA, resolucionLineal);

        /*
        printf("***TABLA CERRADA LINEAL\n");
        test(resolucionLineal);
        printf("***TABLA CERRADA CUADRATICA\n");
        test(resolucionCuadratica);
        */
        return 0;
    }