/******************************************************************************/
/**
@dir "MPI/C/Primer 6 - heat"
@brief Paralelno resenje Heat Equation.
*/
/******************************************************************************/
/**
@file "MPI/C/Primer 6 - heat/heat_mpi.c"
@brief Paralelno resenje Heat Equation

@author Milos Gligoric
@author Andrija Bosnjakovic
*/
/******************************************************************************/

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

/******************************************************************************/

/**
@def MASTER
@brief Rang mastera.
*/
#define MASTER 0

/**
@def TAG
@brief Tag koji ce biti koriscen u komunikaciji.
*/
#define TAG 123

/**
@def NON_NEIGHBOUR
@brief Znak da sused ne postoji.
*/
#define NON_NEIGHBOUR -1

/**
@def MIN_MATRIX_DIM
@brief Miminalna dimenzija matrice.
*/
#define MIN_MATRIX_DIM 5

/**
@def MAX_MATRIX_DIM
@brief Maksimalna dimenzija matrice.
*/
#define MAX_MATRIX_DIM 99

/**
@def MIN_NUM_OF_PROCS
@brief Minimalni broj procesa.
*/
#define MIN_NUM_OF_PROCS 3

/**
@def MAX_NUM_OF_PROCS
@brief Maksimalni broj procesa
*/
#define MAX_NUM_OF_PROCS 5

/**
@def MIN_NUM_OF_STEPS
@brief Minimalni broj koraka za izracunavanje konacne toplote
*/
#define MIN_NUM_OF_STEPS 1

/**
@def MAX_NUM_OF_STEPS
@brief Maksimalni broj koraka za izracunavanje konacne toplote
*/
#define MAX_NUM_OF_STEPS 100

/**
@def ErrorDimension
@brief Greska dimenzije matrice
*/
#define ErrorDimension 1

/**
@def ErrorNumOfSteps
@brief Greska u zadatom broju koraka
*/
#define ErrorNumOfSteps 2

/**
@def ErrorNumOfProcs
@brief Greska ukoliko je zadat nekorektan broj procesa
*/
#define ErrorNumOfProcs 3

/**
@def Cx
@brief Konstanta koja se koristi pri izracunavanju narednost stanja
Pogledati formulu za izracunavanje narednog stanja
*/
#define Cx 0.1

/**
@def Cy
@brief Konstanta koja se koristi pri izracunavanju narednog stanja
Pogledati formulu za izracunavanje narednog stanja
*/
#define Cy 0.1

/*
double test[5][5] = {0, 0, 0, 0, 0,
                    0, 0, 2, 0, 0,
                    0, 2, 3, 2, 0,
                    0, 0, 2, 0, 0};
*/

/******************************************************************************/

/**
@brief Informacije o okruzenju procesa
*/
typedef struct {
    /**
    @property size
    @brief Velicina MPI sveta.
    */
    int size;

    /**
    @property tag
    @brief Tag preko koga ide komunikacija.
    */
    int tag;

    /**
    @property rank
    @brief Rang procesa
    */
    int rank;

    /**
    @property rightRank
    @brief Rang levog suseda
    */
    int rightRank;

    /**
    @property leftRank
    @brief Rang desnog suseda
    */
    int leftRank;
} EnvironmentStruct;

/**
@brief Podaci procesa.
*/
typedef struct {
    /**
    @property heatMatrix
    @brief Matrica toplote
    */
    double heatMatrix[MAX_MATRIX_DIM][MAX_MATRIX_DIM];

    /**
    @property matrixDimension;
    @brief Dimenzija matrice (validno samo u Master procesu)
    */
    int matrixDimension;

    /**
    @property numOfRows
    @brief Broj kolona koje proces uzima u obzir pri racunu narednog stanja
    */
    int numOfRows;

    /**
    @property initNumOfRows
    @brief Broj kolona za koje je proces odgovoran
    @details Vrednost koja se dobija pri inicijalizaciji i koja zaista predstavlja
    broj kolona koje su pod kontrolom ovog procesa.
    */
    int initNumOfRows;

    /**
    @property numOfCols
    @brief Broj vrsta koje proces uzima u obzir pri racunanju narednog stanja
    */
    int numOfCols;

    /**
    @property initNumOfCols
    @brief Broj vrsta za koje je proces odgovran pri azuriranju
    */
    int initNumOfCols;

    /**
    @property numOfSteps
    @brief Broj koraka koje proces treba da sprovede do konacnog stanja.
    */
    int numOfSteps;

    /**
    @property columnType
    @brief Tip kolone uveden radi jednostavnije komunikacije.
    */
    MPI_Datatype columnType;
} DataStruct;

/******************************************************************************/

/**
@brief Ucitava elemente u zadatu matricu vrstu po vrstu
@param pHeatMatrix Matrica u koju je potrebno ucitati elemente.
@param pRows Broj vrsta koje treba ucitati
@param pCols Broj kolona koje treba ucitati
*/
void scanfMatrix(double pHeatMatrix[][MAX_MATRIX_DIM], int pRows, int pCols) {
    int i, j;

    for (i = 0; i < pRows; i++) {
        printf("vrsta %d: ", i+1);
        for (j = 0; j < pCols; j++) {
            scanf("%lf", &pHeatMatrix[i][j]);
            //pHeatMatrix[i][j] = test[i][j];
        }
    }
}

/**
@brief Ispis navedene matrice.
@param pHeatMatrix Matrica koja se ispisuje.
@param pRows Broj vrsta matrice
@param pCols Broj kolona matrice
@param pFormat Format koji ce biti koriscen za ispis svakog elementa matrice
*/
void printfMatrix(double pHeatMatrix[][MAX_MATRIX_DIM], int pRows, int pCols, const char *pFormat) {
    int i, j;
    
    for (i = 0; i < pRows; i++) {
        for (j = 0; j < pCols; j++) {
            printf(pFormat, pHeatMatrix[i][j]);
        }
        printf("\n");
    }
}

/******************************************************************************/

/**
@brief "Konstruktor" tipa kolone matrice
@param pCount Broj elemenata u jednom boloku
@param pBlockLength Duzina bloka
@param pStride Razmak medju grupama
@param pType Tip koji se konstruise (izlazni parametar);
*/
void ColumnType(int pCount, int pBlockLength, int pStride, MPI_Datatype *pType) {
    MPI_Type_vector(pCount, pBlockLength, pStride, MPI_DOUBLE, pType);
    MPI_Type_commit(pType);
}

/**
@brief "Destruktor" tipa kolone matrice.
*/
void _ColumnType(MPI_Datatype *pType) {
    MPI_Type_free(pType);
}

/******************************************************************************/

/**
@brief Provera korektnosti broja procesa.
@param pNumOfProcs Broj procesa.
@param pMatrixDimension Dimenzija matrice.
@return != 0 ukoliko je zadat nekorektan broj procesa.
*/
int isWrongNumOfProcs(int pNumOfProcs, int pMatrixDimension) {
    return (pNumOfProcs < MIN_NUM_OF_PROCS || pNumOfProcs > MAX_NUM_OF_PROCS ||
        pNumOfProcs > pMatrixDimension);
}

/**
@brief Prekida izvrsavanja programa u slucaju nekorektnog broja procesa.
@param pNumOfProcs Broj procesa.
@param pMatrixDimension Dimenzija matrice.
*/
void ifWrongNumOfProcsAbort(int pNumOfProcs, int pMatrixDimension) {
    if (isWrongNumOfProcs(pNumOfProcs, pMatrixDimension)) {
        MPI_Abort(MPI_COMM_WORLD, ErrorNumOfProcs);
    }
}

/**
@brief Provera korektnosti dimenzije matrice toplote.
@param pMatrixDimension Dimenzija matrice
@return Vraca vrednost != 0 ukoliko je zadata dimenzija nekorektna
*/
int isWrongDimension(int pMatrixDimension) {
    return (pMatrixDimension < MIN_MATRIX_DIM || pMatrixDimension > MAX_MATRIX_DIM ||
        pMatrixDimension%2 != 1);
}

/**
@brief Prekida izvrsavanje programa u slucaju nekorektne dimenzije matrice.
@param pMatrixDimension Dimenzija matrice.
*/
void ifWrongDimensionAbort(int pMatrixDimension) {
    if (isWrongDimension(pMatrixDimension)) {
        MPI_Abort(MPI_COMM_WORLD, ErrorDimension);
    }
}

/**
@brief Provera korektnosti broja koraka za izracunavanje konacnog stanja.
@param pNumOfSteps Broj koraka koje treba sprovesti.
@return Vraca vrednost != 0 ukoliko je zadati broj koraka nekorektan.
*/
int isWrongNumOfSteps(int pNumOfSteps) {
    return (pNumOfSteps < MIN_NUM_OF_STEPS || pNumOfSteps > MAX_NUM_OF_STEPS);
}

/**
@brief Prekida izvrsavanje programa u slucaju nekorektnog broja koraka.
@param pNumOfSteps Broj koraka koje treba sprovesti.
*/
void ifWrongNumOfStepsAbort(int pNumOfSteps) {
    if (isWrongNumOfSteps(pNumOfSteps)) {
        MPI_Abort(MPI_COMM_WORLD, ErrorNumOfSteps);
    }
}

/******************************************************************************/

/**
@brief Odredjivanje levog i desnog suseda
@param env Informacije o okruzenju procesa (in/out parametar)
*/
void determineLeftAndRightNeighbour(EnvironmentStruct *env) {
    if (env->rank == 1) 
        env->leftRank = NON_NEIGHBOUR;
    else 
        env->leftRank = env->rank - 1;

    if (env->rank == env->size-1)
        env->rightRank = NON_NEIGHBOUR;
    else 
        env->rightRank = env->rank + 1;

    printf("%d %d\n", env->leftRank, env->rightRank);
}

/**
@brief Ispituje postojanje levog suseda.
@param env Informacije o okruzenju procesa.
@return Vraca vrednost != 0 ukoliko proces poseduje levog suseda.
*/
int hasLeftNeighbour(EnvironmentStruct *env) {
    return (env->leftRank != NON_NEIGHBOUR);
}

/**
@brief Ispituje postojanje desnog suseda.
@param env Informacije o okruzenju procesa.
@return Vraca vrednost != 0 ukoliko proces poseduje desnog suseda.
*/
int hasRightNeighbour(EnvironmentStruct *env) {
    return (env->rightRank != NON_NEIGHBOUR);
}

/**
@brief Ispituje da li je proces krajnji levi (nema levog suseda).
@param env Informacije o okruzenju procesa.
@return Vraca vrednost != 0 ukoliko je proces krajnji levi.
*/
int isLeftMost(EnvironmentStruct *env) {
    return (env->rank == 1);
}

/**
@brief Ispituje da li je proces krajnji desni (nema desnog suseda).
@param env Informacije o okruzenju procesa.
@return Vraca vrednost != 0 ukoliko je proces krajnji desni.
*/
int isRightMost(EnvironmentStruct *env) {
    return (env->rank == env->size-1);
}

/**
@brief Ispituje da li zadati rang pripada Master procesu
@param pRank Rang procesa
@return Vraca vrednost != 0 ukoliko zadati rang pripada Master procesu
*/
int isProcessMaster(int pRank) {
    return (pRank == MASTER);
}

/**
@brief Inicijalizuje Master proces.
@param pEnv Informacije o okruzenju procesa (in/out parametar).
@param pData Podaci procesa (out parametar).
*/
void initMaster(EnvironmentStruct *pEnv, DataStruct *pData) {
    int i, j;
    int numOfSlaves = pEnv->size - 1;
    int nextColumn;

    printf("Unesite dimenziju matrice: ");
    scanf("%d", &pData->matrixDimension);
    ifWrongDimensionAbort(pData->matrixDimension);
    ifWrongNumOfProcsAbort(numOfSlaves, pData->matrixDimension);
    MPI_Bcast(&pData->matrixDimension, 1, MPI_INT, MASTER, MPI_COMM_WORLD);

    printf("Unesite toplotu za svaku celiju: \n");
    scanfMatrix(pData->heatMatrix, pData->matrixDimension, pData->matrixDimension);

    printf("Unesite broj koraka za izracunavanje krajnje toplote: ");
    scanf("%d", &pData->numOfSteps);
    ifWrongNumOfStepsAbort(pData->numOfSteps);
    MPI_Bcast(&pData->numOfSteps, 1, MPI_INT, MASTER, MPI_COMM_WORLD);

    ColumnType(pData->matrixDimension, 1, MAX_MATRIX_DIM, &pData->columnType);

    nextColumn = 0;
    for (i = 0; i < numOfSlaves; i++) {
        int numOfColumns = pData->matrixDimension / numOfSlaves;
        numOfColumns += i < pData->matrixDimension % numOfSlaves ? 1 : 0;
        MPI_Send(&numOfColumns, 1, MPI_INT, i+1, pEnv->tag, MPI_COMM_WORLD);
        for (j = 0; j < numOfColumns; j++) {
            MPI_Send(&pData->heatMatrix[0][nextColumn++], 1, pData->columnType, i+1, pEnv->tag, MPI_COMM_WORLD);
        }
    }
}

/**
@brief Inicijalizacija Slave procesa.
@param pEnv Informacije o okruzenju procesa (in/out parametar).
@param pData Podaci procesa (out parametar).
*/
void initSlave(EnvironmentStruct *pEnv, DataStruct *pData) {
    MPI_Status status;
    int i, index;

    MPI_Bcast(&pData->numOfRows, 1, MPI_INT, MASTER, MPI_COMM_WORLD);
    MPI_Bcast(&pData->numOfSteps, 1, MPI_INT, MASTER, MPI_COMM_WORLD);

    ColumnType(pData->numOfRows, 1, MAX_MATRIX_DIM, &pData->columnType);

    MPI_Recv(&pData->numOfCols, 1, MPI_INT, MASTER, pEnv->tag, MPI_COMM_WORLD, &status);

    index = isLeftMost(pEnv) ? 0 : 1;
    for (i = 0; i < pData->numOfCols; i++, index++) {
        MPI_Recv(&pData->heatMatrix[0][index], 1, pData->columnType, MASTER, pEnv->tag, MPI_COMM_WORLD, &status);
    }

    pData->initNumOfCols = pData->numOfCols;
    pData->initNumOfRows = pData->numOfRows;
    if (!isLeftMost(pEnv)) pData->numOfCols++;
    if (!isRightMost(pEnv)) pData->numOfCols++;
}

/**
@brief Zavrsne radnje Master procesa.
@param pEnv Informacije o okruzenju procesa.
@param pData Podaci procesa.
*/
void finishMaster(EnvironmentStruct *pEnv, DataStruct *pData) {
    int i, j;
    int numOfSlaves = pEnv->size-1;
    int nextColumn = 0;
    MPI_Status status;

    for (i = 0; i < numOfSlaves; i++) {
        int numOfColumns = pData->matrixDimension / numOfSlaves;
        numOfColumns += i < pData->matrixDimension % numOfSlaves ? 1 : 0;
        for (j = 0; j < numOfColumns; j++) {
            MPI_Recv(&pData->heatMatrix[0][nextColumn++], 1, pData->columnType, i+1, pEnv->tag, MPI_COMM_WORLD, &status);
        }
    }
    _ColumnType(&pData->columnType);

    printfMatrix(pData->heatMatrix, pData->matrixDimension, pData->matrixDimension, "%#6.3g     ");
}

/**
@brief Zavrsne radnje Slave procesa.
@param pEnv Informacije o okruzenju procesa.
@param pData Podaci procesa.
*/
void finishSlave(EnvironmentStruct *pEnv, DataStruct *pData) {
    int i;
    int index = isLeftMost(pEnv) ? 0 : 1;
    

    for (i = 0; i < pData->initNumOfCols; i++, index++) {
        MPI_Send(&pData->heatMatrix[0][index], 1, pData->columnType, MASTER, pEnv->tag, MPI_COMM_WORLD);
    }
    _ColumnType(&pData->columnType);
}

/**
@brief Ispis zaglavlja
@param pEnv Informacije o okruzenju procesa
@param pData Podaci procesa
Ispis informacija o procesu na pocetku izvrsavanja
*/
void printHeader(EnvironmentStruct *pEnv, DataStruct *pData) {
    printf("\n///////////////////////////////////////////////////////\n");
    printf("// proces: #%d\n", pEnv->rank);
    printf("// levi sused: #%d\n", pEnv->leftRank);
    printf("// desni sused: #%d\n", pEnv->rightRank);
    printf("///////////////////////////////////////////////////////\n");
    printf("\n_ _ _ _ _ _ _ pocetne vrednosti _ _ _ _ _ \n");

    printfMatrix(pData->heatMatrix, pData->numOfRows, pData->numOfCols, "%#6.3g     ");
}

/**
@brief Ispis nakon zavrsetka obrade
@param pEnv Informacije o okruzenju procesa
@param pData Podaci procesa
*/
void printFooter(EnvironmentStruct *pEnv, DataStruct *pData) {
    printf("\n//////////////////  END EXECUTION  ///////////////////////\n");
}

/**
@brief Ispis informacija tokom jedne iteracije
@param pIteration Broj iteracije
*/
void printIteration(int pIteration) {
    printf("\n_ _ _ _ _ _ _ #%d iteracija _ _ _ _ _ _ _ _\n", pIteration); 
}

/**
@brief Izracunava naredno stanje celija matrice toplote.
@param pEnv Informacije o okruzenju procesa.
@param pData Podaci procesa.
*/
void calculateNextState(EnvironmentStruct *pEnv, DataStruct *pData) {
    int x, y;
    static double newMatrix[MAX_MATRIX_DIM][MAX_MATRIX_DIM];

    for (x = 1; x < pData->numOfRows-1; x++) {
        for (y = 1; y < pData->numOfCols-1; y++) {
            newMatrix[x][y] = pData->heatMatrix[x][y] + Cx * (pData->heatMatrix[x+1][y] + pData->heatMatrix[x-1][y] - 2 * pData->heatMatrix[x][y]) +
                Cy * (pData->heatMatrix[x][y+1] + pData->heatMatrix[x][y-1] - 2 * pData->heatMatrix[x][y]);
        }
    }

    for (x = 1; x < pData->numOfRows-1; x++) {
        for (y = 1; y < pData->numOfCols-1; y++) {
            pData->heatMatrix[x][y] = newMatrix[x][y];
        }
    }
}

/**
@brief Izracuanvanje krajnjeg stanja sistema.
@param pEnv Informacije o okruzenju procesa.
@param pData Podaci procesa.
*/
void run(EnvironmentStruct *pEnv, DataStruct *pData) {
    MPI_Request request;
    MPI_Status status;
    int i;

    determineLeftAndRightNeighbour(pEnv);

    printHeader(pEnv, pData);
    for (i = 0; i < pData->numOfSteps; i++) {
        printIteration(i+1);

        if (hasLeftNeighbour(pEnv)) {
            printf("P%d -> P%d\n", pEnv->rank, pEnv->leftRank);
            MPI_Isend(&pData->heatMatrix[0][1], 1, pData->columnType, pEnv->leftRank, pEnv->tag, MPI_COMM_WORLD, &request);
        }
        if (hasRightNeighbour(pEnv)) {
            printf("P%d -> P%d\n", pEnv->rank, pEnv->rightRank);
            MPI_Isend(&pData->heatMatrix[0][pData->numOfCols-2], 1, pData->columnType, pEnv->rightRank, pEnv->tag, MPI_COMM_WORLD, &request);
        }
        
        if (hasLeftNeighbour(pEnv)) {
            printf("P%d <- P%d\n", pEnv->rank, pEnv->leftRank);
            MPI_Recv(&pData->heatMatrix[0][0], 1, pData->columnType, pEnv->leftRank, pEnv->tag, MPI_COMM_WORLD, &status);
        }
        if (hasRightNeighbour(pEnv)) {
            printf("P%d <- P%d\n", pEnv->rank, pEnv->rightRank);
            MPI_Recv(&pData->heatMatrix[0][pData->numOfCols-1], 1, pData->columnType, pEnv->rightRank, pEnv->tag, MPI_COMM_WORLD, &status);
        }

        calculateNextState(pEnv, pData);

        printfMatrix(pData->heatMatrix, pData->numOfRows, pData->numOfCols, "%#6.3g     ");
    }
    printFooter(pEnv, pData);
}

/******************************************************************************/

/**
@brief Glavni program
@param argc Broj argumenata komandne linije
@param argv Argumenti komandne linije
@return Vraca @b 0 ako je sve uspesno izvrseno

Glavni program vrsi inicijalizaciju podataka okruzenja i podataka procesa.
Zatim svaki proces zavisno od njegove uloge izvrsava pozive odgovarajucih
funkcija. Moze se zapaziti da je main funkcija kao i mnoge ranije navedene
opste napisana tj nezavisna od problema koji se resava.
*/
int main(int argc, char *argv[]) {
    EnvironmentStruct *env;
    DataStruct *data;

    env = calloc(1, sizeof(EnvironmentStruct));
	data = calloc(1, sizeof(DataStruct));

	/* Inicijalizujemo MPI */
	MPI_Init(&argc, &argv);
	
	/* Trazimo svoj rang unutar MPI sveta (prvi je 0) */
	MPI_Comm_rank(MPI_COMM_WORLD, &env->rank);
	
	/* Trazimo velicinu MPI sveta */
	MPI_Comm_size(MPI_COMM_WORLD, &env->size);

    env->tag = TAG;

    if (isProcessMaster(env->rank)) {
        initMaster(env, data);
    } else {
        initSlave(env, data);
        run(env, data);
    }

    if (isProcessMaster(env->rank)) {
        finishMaster(env, data);
    } else {
        finishSlave(env, data);
    }
	
    free(env);
    free(data);

	/* Zavrsavamo MPI */
	MPI_Finalize();
	
	return 0;
}

/******************************************************************************/