/*******************************************************************
* Problema de decodificación de señal discreta,
solución con ascensión de colinas
*********************************************************************/

#include <string.h>  // Funcion memset
#include <stdlib.h>
#include <iostream>
#include <omp.h>
#include <time.h>
using namespace std;

//#define NUMGENALE 10000000
#define NUMGENALE 150000
//#define NUMGENALE 20




long unsigned int generar_siguiente_vecino(int nt, int nr, int*x, int *tA, int **A, int *SOA, int VOA, int *H) {
    int **hijos = (int**) malloc(sizeof(int)*nt);

    long unsigned int mejorValor = -1;
    /* Para generar los vecinos iteramos sobre el vector solución actual cambiando cada
    una de las componentes, así tendremos tantos vecinos como número de componentes tiene
    el vector de envío. Almacenaremos en la variable hijos */
    for(int i = 0; i < nt;i++) {
        hijos[i] = (int*) malloc(sizeof(int)*nt);
        // Copio la solución actual en cada uno de los vecinos,
        // ya que solo va a cambiar un valor.
        copiar(hijos[i], SOA, nt);
        // Relacion de vecindad, cambio un valor de cada vector de forma aleatoria.
        // Cojo un número aleatorio entre 0 y el tamaño del alfabeto de la componente actual.
        int valorCambiado = rand() % tA[i];

        // Si da la casualidad de que el valor cambiado es el mismo que ya tengo, cojo el
        // siguiente
        if (A[i][valorCambiado] == hijos[i][i]) {
            valorCambiado = (valorCambiado + 1) % tA[i];
        }

        // Cambio el valor por el nuevo.
        hijos[i][i] = A[i][valorCambiado];

        // Calculo su fitness.
        long unsigned int valor = calcularvalor(hijos[i], x, A, H, nt, nr);

        // Si es mejor que el valor óptimo actual lo cambio y me quedo con esta solución,
        if (valor < VOA) {
            VOA = valor;
            mejorValor = VOA;
            copiar(SOA, hijos[i], nt);
        }
        free(hijos[i]);
    }
    free(hijos);
    // Devuelvo el mejor valor fitness y en SOA tendremos el mejor vecino al pasarlo por referencia.
    // En caso de que no hayamos encontrado una mejor solución devolveremos -1.
    // -1 será nuestra señal de que la ascensión se ha estancado.
    return mejorValor;

}

long unsigned int ascensionColinas(int nt,int nr,int *x,int **A,int *tA,int *H,int *SOA, int np)
{
    long int VOA;

    // Genero un aleatorio inicial.
    generaraleatorio(SOA,nt,A,tA);
    // Calculo su fitness.
    VOA=calcularvalor(SOA,x,A,H,nt,nr);
    bool fin = false;
    while (!fin) {
        /* Con este método genero, de todos los vecinos el mejor o si la función
        devuelve -1 es simbolo de estancamiento. */
        long unsigned int nextVOA = generar_siguiente_vecino(nt, nr, x, tA, A, SOA, VOA, H);
        // Si nos devuelven -1 terminamos el procedimiento
        // Si no, nos quedamos con el valor devuelto por la función anterior y seguimos.
        if (nextVOA != -1) VOA = nextVOA;
        else fin = true;
    }
    return VOA;
}


int main (void)
{
    int  nt,nr; //número de componentes de la señal transmitida y recibida
    int *x; //vector recibido
    int **A; //Alfabetos para los datos a transferir
    int *tA; //tamaños de los alfabetos
    int *H; //matriz de transferencia
    long unsigned int valsol = -1; //valor de la solución
    int numReinicios; // Numero de reinicios de la ascension de colinas.
    int *sol;
    int *solpart;
    leer(&nt,&nr,&x,&A,&tA,&H);
    // El numero de reinicios es la variable que venía con el modelo NUMGENALE
    numReinicios = NUMGENALE;

    // Cojo el número de threads que se van a generar.
    int numThreads = omp_get_max_threads();
    // Si tengo mas procesadores que reinicios pongo un hilo por reinicio.
    if (numThreads > numReinicios) {
        numThreads = numReinicios;
        omp_set_num_threads(numThreads);
    }

    /* Inicializo el espacio de memoria compartida, en estos
    vectores los threads colocarán la mejor solución que se va
    encontrando. Tanto el valor fitness como la solucion en si. */
    int *VOAS = (int*) malloc(sizeof(int)*numThreads);
    int **SOAS = (int**)malloc(sizeof(int)*numThreads);
    for(int i = 0; i < numThreads; i++) SOAS[i] =(int*) malloc(sizeof(int)*nt);

    // A partir de aquí se hace en paralelo.
    #pragma omp parallel private(valsol, sol, solpart)
    {

    // En este vector irá la mejor solución encontrada por cada hilo.
    sol = (int*) malloc(sizeof(int)*nt);
    // En este vector guardaremos la mejor solución encontrada por cada hilo en cada reinicio.
    solpart = (int *) malloc(sizeof(int)*nt);
    int np = omp_get_thread_num();
    /* Cambio la semilla de generación aleatoria utilizando el tiempo
    actual y para que cada hilo explore una zona distinta utilizo el identificador de proceso */
    srand(time(NULL)  + np);

    // Inicializo SOA.
    for(int j=0;j<nt;j++)
    {
         sol[j]=-1;
    }

    // Calculo para cada hilo, los reinicios que le tocan
    /* Ejemplo: son 15 reinicios y tenemos 4 hilos.
    Hilo 1: Iteraciones 0-3
    Hilo 2: Iteraciones 4-8
    Hilo 3: Iteraciones 9-11
    Hilo 4: Iteraciones 12-14
    */
    int range = numReinicios / numThreads;
    int rest = numReinicios % numThreads;
    int myStart = np*range;
    int myEnd = (np+1)*range;

    if (np < rest) {
        myStart += (np);
        myEnd += (np+1);
    } else {
        myStart += rest;
        myEnd += rest;
    }

    // Inicializo VOA a un valor muy alto.
    valsol = -1;

    // Cada hilo hace su rango de reinicios.
    for (int i = myStart; i < myEnd ;i++) {
        // Método principal de la ascensión de colinas.
        long unsigned int valsolreinicio = ascensionColinas(nt,nr,x,A,tA,H,solpart, np);
        // Tras terminar el procedimiento tendremos en solpart el máximo local.
        // En valsolreinicio tendremos el valor fitness de solpart.
        // Si valsolreinicio (maximo local) es menor que valsol (maximo global)
        // cambio valsolreinicio por valsol ya que es mejor solución global.
        // y además copio en sol (la mejor solución global) solpart (mejor solución local).
        if (valsolreinicio < valsol || valsol == -1) {
            valsol = valsolreinicio;
            copiar(sol, solpart, nt);
        }
    }
    // Al terminar las iteraciones que le toca a cada hilo guardamos en el vector
    // que inicializamos antes de entrar a iterar tanto la mejor solución como el valor de la misma.
    VOAS[np] = valsol;
    SOAS[np] = sol;
    }

    // Al final tenemos dos vectores, uno con los valores de las mejores soluciones encontradas.
    // y otro con las soluciones en sí.
    // El hilo maestro de las soluciones de cada proceso busca la mejor.
    valsol = VOAS[0];
    sol = (int*) malloc(sizeof(int)*nt);

    copiar(sol, SOAS[0], nt);
    escribirVector(sol, nt);
    // en este bucle simplemente buscamos la mejor solución
    for(int i = 1; i < numThreads; i++) {
        if (VOAS[i] < valsol) {
            valsol = VOAS[i];
            copiar(sol, SOAS[i], nt);
        }
        free(SOAS[i]);
    }
    free(SOAS[0]);
    free(SOAS);
    free(VOAS);
    // Imprimimos el resultado.
    cout << valsol << endl;
    for(int j=0;j<nt-1;j++)
    {
         cout << sol[j] << " ";
    }
    cout <<sol[nt-1]<<endl;
    free(sol);
    liberar(nt,nr,&x,&A,&tA,&H);
}