//Author Antonio-Gabriel Sturzu


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<mpi.h>
#define inf 1001

int main(int argc,char *argv[])
{
	int rc,numtasks,rank,**m,n,*line,dim,next=0,strip,*key,*viz,*prev,minl=0,iminl,ming,iming,costl=0,prod,costg,sup;
	int i,j,temp;
	double time1,time2;
	FILE *f;
	MPI_Status status;

	//MPI Initialization
	rc = MPI_Init(&argc,&argv);
	if (rc != MPI_SUCCESS) 
	{
		printf ("Error starting MPI program. Terminating.\n");
		MPI_Abort(MPI_COMM_WORLD, rc);
	}
	MPI_Comm_size(MPI_COMM_WORLD,&numtasks);
	MPI_Comm_rank(MPI_COMM_WORLD,&rank);

	//Reading from file is done by process 0
	if(rank==0)
	{	
		f=fopen("apm2.in","r");
		fscanf(f,"%i",&n);
	}
	//Broadcast n's value to all processes
	MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
	dim=n/numtasks;
	strip=dim;
	if(rank==numtasks-1 && n%numtasks!=0)
		dim=n-dim*(numtasks-1);
	
	m=(int **) calloc(n*dim,sizeof(int *));
	for(i=0;i<n;i++)
			m[i]=(int *) calloc(dim,sizeof(int));
	if(rank==0)
	{
		line=(int *) calloc(n,sizeof(int));
		for(i=0;i<n;i++)
		{
			next=dim;
			for(j=0;j<n;j++)
				fscanf(f,"%i",line+j);
			memmove(m[i],line,dim*sizeof(int));
			for(j=1;j<numtasks-1;j++)
			{
				MPI_Send(&line[next],dim,MPI_INT,j,1,MPI_COMM_WORLD);
				next+=dim;
			}
			if(numtasks>1)
				MPI_Send(&line[next],n-next,MPI_INT,numtasks-1,1,MPI_COMM_WORLD);
		}
	}		
	else
		for(i=0;i<n;i++)
			MPI_Recv(m[i],dim,MPI_INT,0,1,MPI_COMM_WORLD,&status);

	key=(int *) calloc(dim,sizeof(int));
	viz=(int *) calloc(dim,sizeof(int));
	prev=(int *) calloc(dim,sizeof(int));

	MPI_Barrier(MPI_COMM_WORLD);
	time1=MPI_Wtime();
	//Initialize the keys
	if(rank!=0)
	{
		for(i=0;i<dim;i++)
			key[i]=inf;
	}
	else
	{
		for(i=1;i<dim;i++)
			key[i]=inf;
		key[0]=0;
	}

	if(rank!=numtasks-1)
	{
		prod=rank*dim;
		sup=prod+dim;
	}
	else
	{
		prod=rank*strip;
		sup=n;
	}
	MPI_Barrier(MPI_COMM_WORLD);

	//Distributed Prim's algorithm
	for(;;)
	{
		minl=inf;
		for(i=0;i<dim;i++)
		{
			if(viz[i]==0 && key[i]<minl)
			{
				minl=key[i];
				iminl=i;
			}
		}
		//Determine the global minimum value of a key
		MPI_Allreduce(&minl,&ming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
		if(ming==inf)
			break;
	
		if(minl==ming)
		{
			temp=iminl+prod;
			MPI_Allreduce(&temp,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
		}
		else
			MPI_Allreduce(&n,&iming,1,MPI_INT,MPI_MIN,MPI_COMM_WORLD);
	
		//If the newest node that will be added to the tree is owned by this process
		//then marke it as out of the local queue
		
		if(iming>=prod && iming<sup)
		{
			viz[iming-prod]=1;
			costl+=minl;
		}
		for(i=0;i<dim;i++)
		{
			if(m[iming][i]<key[i] && viz[i]==0)
			{
				key[i]=m[iming][i];
				prev[i]=iming;
			}
		}
		MPI_Barrier(MPI_COMM_WORLD);
	}

	MPI_Reduce(&costl,&costg,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
	MPI_Barrier(MPI_COMM_WORLD);
	time2=MPI_Wtime();
	if(rank==0)
		printf("Au trecut %f secunde \n",time2-time1);

	if(rank==0)
	{
		printf("Costul minim este %i\n",costg);
		printf("Muchiile arborelui sunt: \n");
	}
	MPI_Barrier(MPI_COMM_WORLD);

	for(i=0;i<dim;i++)
			if(i+prod!=0)
				printf("%i %i\n",prev[i]+1,i+prod+1);
	for(i=0;i<n;i++)
		free(m[i]);
	free(m);
	free(key);
	free(prev);
	free(viz);
	if(rank==0)
		free(line);
	MPI_Finalize();	
	return 0;
}