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

/**
 * @author cristian.chilipirea
 * Run: mpirun -np 4 ./a.out
 */

int graph[][2] = { { 0, 1 },
                  { 1, 0 }, { 1, 2 }, { 1, 3 },
                  { 2, 1 }, { 2, 3 },
                  { 3, 1 }, { 3, 2 } };

void set(int *a, int c, int sz)
{
  for (int i = 0; i < sz; ++ i) a[i] = c;
}

int main(int argc, char * argv[]) {
	int rank;
	int nProcesses;
  int parent = -1;
  int i, j;

  int topology[4];
  int null[4];
  int recv[4];
  set(recv, 0, 4);
  set(null, -1, 4);
  set(topology, -1, 4);



	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);

  if (rank == 0)
  {
    for (i = 0; i < 8; ++ i)
    {
      if (graph[i][0] == rank)
      {
        MPI_Send(null, 4, MPI_INT, graph[i][1], 0, MPI_COMM_WORLD);
      }
    }

    int temp_topo[4];
    for (i = 0; i < 8; ++ i)
    {
      set(temp_topo, -1, 4);
      if (graph[i][0] == rank)
      {
        MPI_Recv(temp_topo, 4, MPI_INT, graph[i][1], 0, MPI_COMM_WORLD, &status);
      }
      for (j = 0; j < 4; ++ j)
      {
        if (topology[j] == -1 && temp_topo[j] != -1) topology[j] = temp_topo[j];
      }
    }

    for (j = 0; j < 4; ++ j)
    {
      printf("Found parent: %d for rank: %d\n", topology[j], j);
    }
  }
  else
  {
    int temp_topo[4];
    MPI_Recv(temp_topo, 4, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
    parent = status.MPI_SOURCE;

    for (i = 0; i < 8; ++ i)
    {
      if (graph[i][0] == rank && graph[i][1] != parent)
      {
        MPI_Send(null, 4, MPI_INT, graph[i][1], 0, MPI_COMM_WORLD);
      }
    }

    for (i = 0; i < 8; ++ i)
    {
      set(temp_topo, -1, 4);
      if (graph[i][0] == rank && graph[i][1] != parent)
      {
        MPI_Recv(temp_topo, 4, MPI_INT, graph[i][1], 0, MPI_COMM_WORLD, &status);
      }
      for (j = 0; j < 4; ++ j)
      {
        if (topology[j] == -1 && temp_topo[j] != -1) topology[j] = temp_topo[j];
      }
    }
    topology[rank] = parent;

    MPI_Send(topology, 4, MPI_INT, parent, 0, MPI_COMM_WORLD);
  }

  if (rank == 0)
  {
    int next = topology[3];
    while (topology[next] != rank) next = topology[next];

    int vect[5];
    vect[0] = topology[0];
    vect[1] = topology[1];
    vect[2] = topology[2];
    vect[3] = topology[3];
    vect[4] = 123;
    MPI_Send(vect, 5, MPI_INT, next, 0, MPI_COMM_WORLD);
  }
  else if (rank != 3)
  {
    int vect[5];
    MPI_Recv(vect, 5, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
    printf("Rank %d received: %d\n", rank, vect[4]);

    int next = vect[3];
    while (vect[next] != rank && next != rank && next != -1)
    {
      next = vect[next];
    }
    if (next == -1) next = parent;

    if (next == rank)
    {
      MPI_Send(vect, 5, MPI_INT, 3, 0, MPI_COMM_WORLD);
    }
    else
    {
      MPI_Send(vect, 5, MPI_INT, next, 0, MPI_COMM_WORLD);
    }
    printf("Rank %d sent to: %d\n", rank, next);
  }
  else
  {
    int vect[5];
    MPI_Recv(vect, 5, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &status);
    printf("Rank: %d received: %d\n", rank, vect[4]);
  }


	printf("Bye from %i/%i\n", rank, nProcesses);
	MPI_Finalize();
	return 0;
}