#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <time.h>
#include "mpi.h"

using namespace std;

#define NI 1000
#define NJ 1000
#define NSTEPS 5000

double dt = 0.005;

struct Cell
{
	int ziva;
	double duzinaZivota;
};

double* allocate_1D(int n)
{
	double *a;
	a = (double *) malloc((unsigned)n*sizeof(double));
	return a;
}

struct Cell* allocate_Cells_1D(int n)
{
	struct Cell *cells = (struct Cell*)malloc(n*sizeof(struct Cell));

	return cells;
}

void printMat(int *a, int n, int m)
{
	int i,j;

	for(i = 0; i < n; i++)
	{
		for(j = 0; j < m; j++) printf("%3d", a[i*m+j]);
		printf("\n");
	}  
}


int main(int argc, char *argv[])
{
	int np, id;
	int poproc, step;
	int i,j, ii, ni, nj, nn, nni, nnj, nnp;
	struct Cell *oldCells, *myOldCells, *myNewCells, *helpCells;
	double max, *globalmax;
	int imax, jmax;
	double elapsed_time;

	MPI_Status status;

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &id);
	MPI_Comm_size(MPI_COMM_WORLD, &np);

	int blocklengths[2] = {1,1};
	MPI_Datatype datatypes[2] = {MPI_INT, MPI_DOUBLE};
	MPI_Aint intex;
	MPI_Type_extent(MPI_INT, &intex);
	MPI_Aint displacements[2] = {0, intex};
	MPI_Datatype cellType, arrayCellType;

	MPI_Type_struct(2, blocklengths, displacements, datatypes, &cellType);
	MPI_Type_commit(&cellType);

	MPI_Type_contiguous(NJ+2, cellType, &arrayCellType);
	MPI_Type_commit(&arrayCellType);

	poproc = NI/np;

	if(id == 0)
	{
		double r;
		int n = NI*NJ;
		helpCells = allocate_Cells_1D(n);
		globalmax = allocate_1D(np);
		
		srand(time(NULL));

		for (i = 0; i < n; i++)
		{
			helpCells[i].duzinaZivota = 0;
			r = (double)rand()/(RAND_MAX);
			if(r < 0.5) helpCells[i].ziva = 1;
			else helpCells[i].ziva = 0;
		}
	}

	/* dimenzije nove matrice sa ghost prvom i poslednjom kolonom */
	ni = NI + 2;
	nj = NJ + 2;
	nn = ni*nj;

	/* dimenzije matrice na svakom procesu */
	nni = poproc + 2;
	nnj = nj;
	nnp = nni * nnj;

	myOldCells = allocate_Cells_1D(nnp);
	myNewCells = allocate_Cells_1D(nnp);

	if(id == 0)
	{
		oldCells = allocate_Cells_1D(nn);
		for(i = 0; i < nn; i++) 
		{
			oldCells[i].ziva = 0;
			oldCells[i].duzinaZivota = 0.0;
		}
		ii = 0;
		for(i = 1; i < ni-1; i++)
			for(j = 1; j < nj-1; j++)
				oldCells[i*nj + j] = helpCells[ii++];

		oldCells[0]    = oldCells[(ni-1)*nj-1]; oldCells[ni*nj-1]   = oldCells[nj+1]; // coskovi
		oldCells[nj-1] = oldCells[(ni-2)*nj+1]; oldCells[(ni-1)*nj] = oldCells[2*nj-2]; // coskovi

		for(j = 1; j < nj-1; j++) oldCells[j] = oldCells[(ni-2)*nj + j]; /* posledjnu ne ghost vrstu kopiramo u nultu (ghost) vrstu */
		for(j = 1; j < nj-1; j++) oldCells[(ni-1)*nj + j] = oldCells[nj + j]; /* prvu ne ghost vrstu kopiramo u poslednju(ghost) vrstu */

		for(i = 1; i < ni-1; i++) oldCells[i*nj] = oldCells[(i+1)*nj -2]; /* posledjnu ne ghost kolonu kopiramo u nultu (ghost) kolonu */
		for(i = 1; i < ni-1; i++) oldCells[(i+1)*nj-1] = oldCells[i*nj+1]; /* prvu ne ghost kolonu kopiramo u poslednju(ghost) kolonu */

		//spremanje kolona za sebe
		for(i = 0; i < nnp; i++) myOldCells[i] = oldCells[i];

		/*poslati svakom procesu deo niza sa kojim ce oni rukovati*/  
		for(i = 1; i < np; i++)
			MPI_Send(&oldCells[i*poproc*nnj], nnp, cellType, i, 30, MPI_COMM_WORLD);
	}
	else 
	{
		MPI_Recv(myOldCells, nnp, cellType, 0, 30, MPI_COMM_WORLD, &status);
	}

	max = 0.0;
	
	MPI_Barrier(MPI_COMM_WORLD);
	elapsed_time = -MPI_Wtime();

	for(step = 0; step < NSTEPS; step++)
	{
		/* u svakom koraku provera zivota za svaku celiju */
		for(i = nnj+1; i < (nnp-nnj-2); i++)
			if(!((i%nnj == 0)||(i%(nnj) == nnj-1))) // da ne pitamo za GHOST celije
			{
				int alive = 0;
				alive = myOldCells[i-nnj+1].ziva + myOldCells[i+1].ziva + myOldCells[i+nnj+1].ziva + 
					    myOldCells[i-nnj].ziva   +						  myOldCells[i+nnj].ziva   +
					    myOldCells[i-nnj-1].ziva + myOldCells[i-1].ziva + myOldCells[i+nnj-1].ziva ;
				switch(alive)
				{
				case 3: /* ako ima zive tri celije u okolini ostaje ziva ili se radja*/
					if (myOldCells[i].ziva) 
					{
						myNewCells[i].duzinaZivota = myOldCells[i].duzinaZivota + dt;
						myNewCells[i].ziva = 1;
					}
					else
					{
						myNewCells[i].duzinaZivota = 0.0;
						myNewCells[i].ziva = 1;
					}
						 
					break;

				case 2: /* ako ima dve zive celije u okolini, ostaje kao i u prethodnom koraku */
					if (myOldCells[i].ziva) 
					{
						myNewCells[i].duzinaZivota = myOldCells[i].duzinaZivota + dt;
						myNewCells[i].ziva = 1;
					}
					else
					{
						myNewCells[i].duzinaZivota = 0.0;
						myNewCells[i].ziva = 0;
					}
					break;

				default: /* u suprotnom umire */
					{
						myNewCells[i].duzinaZivota = 0.0;
						myNewCells[i].ziva = 0;
					}
				}        

			}

			for(i = nnj; i < (nnp-1); i++) myOldCells[i] = myNewCells[i]; //prepisivanje u staru matricu

			for(i = 1; i < nni-1; i++)
			{
				myOldCells[i*nnj]       = myOldCells[(i+1)*nnj-2]; //     granicni
				myOldCells[(i+1)*nnj-1] = myOldCells[i*nnj+1]; //          uslovi 
			}

			if(id == 0)
			{
				if(np !=1 )
				{
					MPI_Send(&myOldCells[nnj], 1, arrayCellType, np-1, 50, MPI_COMM_WORLD);
					MPI_Recv(&myOldCells[0],   1, arrayCellType, np-1, 50, MPI_COMM_WORLD, &status);

					MPI_Send(&myOldCells[(nni-2)*nnj], 1, arrayCellType, id+1, 50, MPI_COMM_WORLD);
					MPI_Recv(&myOldCells[(nni-1)*nnj], 1, arrayCellType, id+1, 50, MPI_COMM_WORLD, &status);
				}
			}

			else if(id == np-1)
			{
				MPI_Recv(&myOldCells[(nni-1)*nnj], 1, arrayCellType, 0, 50, MPI_COMM_WORLD, &status);
				MPI_Send(&myOldCells[(nni-2)*nnj], 1, arrayCellType, 0, 50, MPI_COMM_WORLD);

				MPI_Recv(&myOldCells[0],   1, arrayCellType, id-1, 50, MPI_COMM_WORLD, &status);
				MPI_Send(&myOldCells[nnj], 1, arrayCellType, id-1, 50, MPI_COMM_WORLD);
			}

			else
			{
				MPI_Recv(&myOldCells[0],   1, arrayCellType, id-1, 50, MPI_COMM_WORLD, &status);
				MPI_Send(&myOldCells[nnj], 1, arrayCellType, id-1, 50, MPI_COMM_WORLD);

				MPI_Send(&myOldCells[(nni-2)*nnj], 1, arrayCellType, id+1, 50, MPI_COMM_WORLD);
				MPI_Recv(&myOldCells[(nni-1)*nnj], 1, arrayCellType, id+1, 50, MPI_COMM_WORLD, &status);
			}

		for(i = 1; i < nni-1; i++)
			for (j = 1; j < nnj; j++)
				if (myOldCells[i * nnj + j].duzinaZivota > max) 
				{
					max = myOldCells[i * nnj + j].duzinaZivota;
					imax = i;
					jmax = j;
				}
	}  
	
	MPI_Gather(&max, 1, MPI_DOUBLE, globalmax, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);

	elapsed_time += MPI_Wtime();

	int npmax;
	if(id == 0)
	{
		npmax = 0;
		max = globalmax[0];
		for (i = 1; i < np; i++)
			if(globalmax[i] > max) 
			{
				max = globalmax[i];
				npmax = i;
			}

		printf("Najduzi zivot je trajao %lf!\n ", max);
		printf("npmax = %d\n", npmax);
	}
	
	MPI_Bcast(&npmax, 1, MPI_INT, 0, MPI_COMM_WORLD);

	if(id == npmax)
	{
		printf("A najduzi zivot se razvijao na poziciji [%d][%d]!\n", id*poproc + imax, jmax);
		printf("ElapsedTime = %lf\n", elapsed_time);
	}


	MPI_Finalize();

	return 1;
}