struct hash{
    size_t largo;
    size_t cantidad;
    hash_destruir_dato_t destruir_dato;
    lista_t** tabla;
};

typedef struct datos{
    char* clave;
    void* valor;
}datos_t;

void borrar_tabla(hash_t* hash, size_t cantidad, bool es_redimensionar, lista_t** tabla_nueva);

bool redimensionar_hash(hash_t* hash, size_t redimension);

size_t hashing(const char* clave, size_t tam);

void destruir_datos(hash_t* hash, datos_t* dato);

lista_t** crear_tabla(size_t capacidad);

datos_t* crear_dato(char* clave, void* valor){
    datos_t* dato = malloc(sizeof(datos_t));
    if(!dato) return NULL;
    dato->clave = strdup(clave);
    dato->valor = valor;
    return dato;
}

lista_t** crear_tabla(size_t capacidad){
    lista_t** tabla = malloc(sizeof(hash_t)*capacidad);
    if (!tabla) return NULL;
    size_t i  = 0;
    while( i < capacidad){
        tabla[i] = lista_crear();
        i++;
    }
    return tabla;
}

hash_t *hash_crear(hash_destruir_dato_t destruir_dato){
    hash_t* hash = malloc(sizeof(hash_t));
    if(!hash) return NULL;
    hash->largo = TAM;
    hash->cantidad = 0;
    if(destruir_dato != NULL) hash->destruir_dato = destruir_dato;
    else hash->destruir_dato = NULL;
    lista_t** tabla = crear_tabla(hash->largo);
    if (!tabla) return NULL;
    hash->tabla = tabla;
    return hash;
}

size_t hashing(const char* clave, size_t tam){
    size_t hash = 5381;
    int c;
    while((c = *clave++) != 0){
        hash = ((hash << 5) + hash) + c;
    }
    return hash % tam;
}

bool hash_pertenece(const hash_t *hash, const char *clave){
    size_t index = hashing(clave, hash->largo-1);
    lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
    while(!lista_iter_al_final(iter_lista)){
        if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
            lista_iter_destruir(iter_lista);
            return true;
        }
        lista_iter_avanzar(iter_lista);
    }
    lista_iter_destruir(iter_lista);
    return false;
}

size_t hash_cantidad(const hash_t *hash){
    return hash->cantidad;
}

bool hash_guardar(hash_t *hash, const char *clave, void *dato){
    if(((float)hash->cantidad/(float)hash->largo) > FACTOR_AUMENTO){
        size_t redimension = hash->largo * 2;
        if(!redimensionar_hash(hash,redimension)) return false;
    }
    datos_t* datos = crear_dato((char*)clave, dato);
    size_t index = hashing(datos->clave,hash->largo-1);
    lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
    bool pertenece = hash_pertenece(hash, datos->clave);
    if (pertenece){
        while(!lista_iter_al_final(iter_lista)){
            if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
                datos_t* aux = (datos_t*)lista_iter_borrar(iter_lista);
                destruir_datos(hash, aux);
            }
        }
    }
    lista_iter_insertar(iter_lista,datos);
    if (!pertenece) hash->cantidad++;
    lista_iter_destruir(iter_lista);
    return true;
}

void *hash_obtener(const hash_t *hash, const char *clave){
    if (!hash_pertenece(hash,clave)) return NULL;
    size_t index = hashing(clave, hash->largo-1);
    lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
    while(!lista_iter_al_final(iter_lista)){
        if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
            void* dato = ((datos_t*)lista_iter_ver_actual(iter_lista))->valor;
            lista_iter_destruir(iter_lista);
            return dato;
        }
        lista_iter_avanzar(iter_lista);
    }
    lista_iter_destruir(iter_lista);
    return NULL;
}

void *hash_borrar(hash_t *hash, const char *clave){
    if (!hash_pertenece(hash,clave)) return NULL;
    size_t index = hashing(clave, hash->largo-1);
    lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
    while(!lista_iter_al_final(iter_lista)){
        if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
            datos_t* dato_aux = (datos_t*)lista_iter_borrar(iter_lista);
            void* aux = dato_aux->valor;
            free(dato_aux->clave);
            free(dato_aux);
            hash->cantidad--;
            lista_iter_destruir(iter_lista);
            return aux;
        }
        lista_iter_avanzar(iter_lista);
    }
    lista_iter_destruir(iter_lista);
    if(((float)hash->cantidad/(float)hash->largo) > FACTOR_REDUCCION){
        size_t redimension = hash->largo / 2;
        if(redimension > TAM) redimensionar_hash(hash,redimension);
    }
    return NULL;
}

///////////////////////////// REDIMENSIONAR /////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////

bool redimensionar_hash(hash_t* hash, size_t redimension){
    lista_t** tabla_nueva = crear_tabla(redimension);
    size_t tam_viejo = hash->largo;
    hash->largo = redimension;
    borrar_tabla(hash, tam_viejo, true, tabla_nueva);
    hash->tabla = tabla_nueva;
    return true;
}

void borrar_tabla(hash_t* hash, size_t cantidad, bool es_redimensionar, lista_t** tabla_nueva){
    size_t i = 0;
    while(i != cantidad){
        if (lista_esta_vacia(hash->tabla[i])) lista_destruir(hash->tabla[i],NULL);
        else{
            while(!lista_esta_vacia(hash->tabla[i])){
                datos_t* aux = (datos_t*)lista_borrar_primero(hash->tabla[i]);
                if (es_redimensionar){
                    size_t index = hashing(aux->clave,hash->largo-1);
                    lista_insertar_ultimo(tabla_nueva[index], aux);
                }else destruir_datos(hash,  aux);
            }
            lista_destruir(hash->tabla[i], NULL);
        }
        i++;
    }
    free(hash->tabla);
}

void destruir_datos(hash_t* hash, datos_t* dato){
    free(dato->clave);
    if (hash->destruir_dato != NULL) hash->destruir_dato(dato->valor);
    free(dato);
}

void hash_destruir(hash_t *hash){
    borrar_tabla(hash, hash->largo, false, NULL);
    free(hash);
}
//////////////////////////////////////////////////////////////////
///////////////////  ITERADOR DEL HASH  /////////////////////////
////////////////////////////////////////////////////////////////

struct hash_iter{
    const hash_t* hash;
    size_t pos;
    size_t index;
    lista_iter_t* iter_lista;
};

size_t buscar_indice_valido(size_t indice, hash_iter_t* iter){
    while(indice < iter->hash->largo){
        if(!lista_esta_vacia(iter->hash->tabla[indice])){
            iter->index =  indice;
            return indice;
        }
        indice++;
    }
    return iter->hash->largo-1;
}

hash_iter_t *hash_iter_crear(const hash_t *hash){
    hash_iter_t* iter = malloc(sizeof(hash_iter_t));
    if(!iter) return NULL;
    iter->hash = hash;
    iter->pos = 0;
    iter->index = 0;
    iter->iter_lista = lista_iter_crear(iter->hash->tabla[buscar_indice_valido(iter->index, iter)]);
    return iter;
}

bool hash_iter_al_final(const hash_iter_t *iter){
    if (iter->pos == iter->hash->cantidad || (iter->index == iter->hash->largo-1 && lista_iter_al_final(iter->iter_lista))) return true;
    return false;
}

void comprobar_lugar_valido(hash_iter_t* iter){
    lista_iter_destruir(iter->iter_lista);
    iter->index++;
    iter->iter_lista = lista_iter_crear(iter->hash->tabla[buscar_indice_valido(iter->index, iter)]);
}

bool hash_iter_avanzar(hash_iter_t *iter){
    if(hash_iter_al_final(iter)) return false;
    if (!lista_iter_al_final(iter->iter_lista)){
        lista_iter_avanzar(iter->iter_lista);
        if (lista_iter_al_final(iter->iter_lista) && (!hash_iter_al_final(iter))) comprobar_lugar_valido(iter);
        iter->pos++;
    }
    return true;
}

const char *hash_iter_ver_actual(const hash_iter_t *iter){
    if(hash_iter_al_final(iter)) return NULL;
    datos_t* aux = (datos_t*)lista_iter_ver_actual(iter->iter_lista);
    const char* clave = (const char*)aux->clave;
    return clave;
}

void hash_iter_destruir(hash_iter_t* iter){
    free(iter->iter_lista);
    free(iter);
}