#include <mpi.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/**
 * @author cristian.chilipirea
 * Run: mpirun -np 12 ./a.out
 */

int graph[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 11}, {11, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10}, {10, 9}, {9, 8}, {8, 7}, {7, 6}, {6, 5}, {5, 11}, {11, 4}, {4, 3}, {3, 2}, {2, 1}, {1, 0}, {9, 5}, {5, 9}, {5, 3}, {3, 5}, {0, 2}, {2, 0}, {9, 7}, {7, 9}};

int *getNeighbors(int myRank)
{
	int *neigh = malloc(sizeof(int) * 100);
	int i;
	int j = 1;
	for (i = 0; i < 30; i++)
	{
		if (graph[i][0] == myRank)
		{
			neigh[j] = graph[i][1];
			j++;
		}
	}
	neigh[0] = j;
	return neigh;
}

int *getLocalTopology(int myRank, int *neigh)
{
	int *topology = malloc(sizeof(int) * 100);
	int i;
	int j = 1;
	for (i = 1; i < neigh[0]; i++)
	{
		topology[2 * j] = myRank;
		topology[2 * j + 1] = neigh[i];
		j++;
	}
	topology[0] = j;
	return topology;
}

int IsSame(int *vec1, int *vec2)
{

	if (vec1[0] == vec2[0] && vec1[1] == vec2[1])
	{
		return 1;
	}
	else if (vec1[1] == vec2[0] && vec1[0] == vec2[1])
	{
		return 1;
	}
	return 0;
}

void Concat(int *Top1, int *Top2)
{
	int count = Top1[0];
	int bool;

	for (int i = 1; i < Top2[0]; i++)
	{
		bool = 0;

		for (int j = 1; j < Top1[0]; j++)
		{
			if (IsSame(Top2 + (2 * i), Top1 + (2 * j)))
			{
				bool = 1;
			}
		}
		if (bool == 0)
		{
			Top1[2 * count] = Top2[2 * i];
			Top1[2 * count + 1] = Top2[2 * i + 1];
			count++;
		}
	}

	Top1[0] = count;
}

int main(int argc, char *argv[])
{
	int rank;
	int nProcesses;

	MPI_Init(&argc, &argv);
	MPI_Status status;
	MPI_Request request;

	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &nProcesses);
	printf("Hello from %i/%i\n", rank, nProcesses);

	int *neigh = getNeighbors(rank);
	int i;
	char aux[1000];
	aux[0] = 0;
	sprintf(aux + strlen(aux), "Rank %i neighbors: ", rank);
	for (i = 1; i < neigh[0]; i++)
	{
		sprintf(aux + strlen(aux), " %i,", neigh[i]);
	}
	sprintf(aux + strlen(aux) - 1, "\n");
	printf("%s", aux);

	// YOU ARE ONLY ALLOWED TO COMMUNICATE WITH NEIGHBOR PROCESSES
	// The goal of the first exercise is to pretend you don't have graph and rebuild it in a distributed manner
	// The goal of the second exercise is to build routing tables. Routing tables are a list of destination + next hope.
	// Routing table for 5 is:
	// 0 -> 3 ; 1 -> 3 ; 2 -> 3 ; 3 -> 3 ; 4 -> 3 ; 5 -> 5 ; 6 -> 6 ; 7 -> 6 ; 8 -> 9 ; 9 -> 9 ; 10 -> 9 ; 11 -> 11

	int *LocTop = getLocalTopology(rank, neigh);

	for (int i = 0; i < 100; i++)
	{
		for (int j = 1; j < neigh[0]; j++)
		{
			MPI_Send(LocTop, 100, MPI_INT, neigh[j], 0, MPI_COMM_WORLD);
		}
		for (int j = 1; j < neigh[0]; j++)
		{
			int *NewTop = (int *)malloc(100 * sizeof(int));
			MPI_Recv(NewTop, 100, MPI_INT, neigh[j], 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
			Concat(LocTop, NewTop);
		}
	}

	printf("Bye from %i/%i\n", rank, nProcesses);

		if (rank == 0)
	{
		for (i = 1; i < LocTop[0]; i++)
		{
			printf("%d -> %d\n", LocTop[2 * i], LocTop[2 * i + 1]);
		}
	}

	int Parent[12] = {-3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

	int *Q = malloc(12 * sizeof(int));
	Q[0] = 0;
	int T = 1;
	int H = 0;

	while (H < T)
	{
		int *neigh = getNeighbors(Q[H]);

		for (int i = 1; i < neigh[0]; i++)
		{
			if (Parent[neigh[i]] == -1)
			{
				Parent[neigh[i]] = Q[H];
				Q[T] = neigh[i];
				T++;
			}
		}
		H++;
	}

	int *Parent2 = malloc(12 * sizeof(int));
	for (int i = 0; i < 12; i++)
	{
		Parent2[i] = -1;
	}

	int num;
	if (rank == 0)
	{
		for (int i = 0; i < 12; i++)
		{
			printf("%d ", Parent[i]);
		}
		printf("\n");
		num = 22;

		int find = 10;

		while (find != 0)
		{
			Parent2[find] = Parent[find];
			find = Parent[find];
		}
		for (int i = 0; i < 12; i++)
		{
			printf("%d ", Parent2[i]);
		}
		printf("\n");
	}

	MPI_Bcast(Parent2, 12, MPI_INT, 0, MPI_COMM_WORLD);

	if (rank == 0)
	{
		int index;
		for (int i = 0; i < 12; i++)
		{
			if (Parent2[i] == 0)
			{
				index = i;
			}
		}

		printf("Eu sunt %d si ii trimit lui %d\n", rank, index);
		MPI_Send(&num, 1, MPI_INT, index, 0, MPI_COMM_WORLD);
	}

	if (Parent2[rank] != -1)
	{
		int index;
		for (int i = 0; i < 12; i++)
		{
			if (Parent2[i] == rank)
			{
				index = i;
			}
		}

		printf("Eu sunt %d si am primit de la %d\n", rank, Parent2[rank]);

		MPI_Recv(&num, 1, MPI_INT, Parent2[rank], 0, MPI_COMM_WORLD, NULL);
		if (rank != 10)
		{
			printf("Eu sunt %d si ii trimit lui %d\n", rank, index);
			MPI_Send(&num, 1, MPI_INT, index, 0, MPI_COMM_WORLD);
		}
	}

	if (rank == 10)
	{
		printf("%d: %d\n", rank, num);
	}

	MPI_Finalize();
	return 0;
}