#include "mpi.h"
#include <stdio.h>
#include <math.h>

#define YES 1
#define NO 0
#define MILLION 100000000
#define ONEITEM 1
#define MPIHEAD 0
#define NULLTOKEN '*'
#define LONG long

/******************************************************************/
/* a useful struct so I can return both "from" and "to" links     */
/* from the functions that compute them                           */
/******************************************************************/
typedef struct
{
  int sendto;
  int recvfrom;
} links;

/******************************************************************/
/* notwithstanding conventions about minimizing the use of global */
/* variables, these two seem reasonable in this program.  in the  */
/* second assignment, in which changing communicators is useful   */
/* to handle matrix multiplication, these should probably become  */
/* local variables.                                               */
/******************************************************************/
int commsize,myrank;

#include "INC.MPI.tdecl.c"

void butterfly(LONG size);

void grid(LONG size);
links gridlinksright(MPI_Comm gridcomm,LONG size,int myrank);
links gridlinksdown(MPI_Comm gridcomm,LONG size,int myrank);

void threed(LONG x,LONG y,LONG z);
links threedlinks(MPI_Comm gridcomm,LONG x,LONG y,LONG z,int myrank);

void wavefront(LONG size);

int main(int argc,char *argv[])
{
    int  namelen;
    char processor_name[MPI_MAX_PROCESSOR_NAME];

    MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&commsize);
    MPI_Comm_rank(MPI_COMM_WORLD,&myrank);
    MPI_Get_processor_name(processor_name,&namelen);

    timecall("beginning",stdout,myrank);

/******************************************************************/
/* using ifdefs is a simple hack to allow the use of one program  */
/* for all four assignments.                                      */
/******************************************************************/
#ifdef GRID
    grid(4);
#endif
#ifdef THREED
    threed(2,2,3);
#endif
#ifdef BUTTERFLY
    butterfly(16);
#endif
#ifdef WAVEFRONT
    wavefront(4);
#endif

    timecall("ending",stdout,myrank);
    MPI_Finalize();
    return 0;
}

void butterfly(LONG size)
{
  LONG i,mytoken = 0,recvtoken = 0,stride,timestep;

  MPI_Status status;

  links fromto;

  mytoken = (1 << myrank);

  timestep = 0;
  stride = 1;
  while(stride < size)
  {
    MPI_Barrier(MPI_COMM_WORLD);
    if((myrank % (2*stride)) < stride)
      fromto.sendto = myrank + stride;
    else
      fromto.sendto = (commsize + myrank - stride) % commsize;
    fromto.recvfrom = fromto.sendto;

    fprintf(stdout,"(time,proc,mytoken) (from,to) (%2ld,%2d,",
            timestep,myrank);
    for(i = 0; i < commsize; i++) fprintf(stdout,"%1lx",((mytoken>>i)&1));
    fprintf(stdout,") (%2d,%2d)\n",fromto.sendto,fromto.recvfrom);
    fflush(stdout);

    MPI_Sendrecv(&mytoken,ONEITEM,MPI_LONG,fromto.sendto,timestep,
                 &recvtoken,ONEITEM,MPI_LONG,fromto.recvfrom,timestep,
                 MPI_COMM_WORLD,&status);

    mytoken = mytoken | recvtoken;

    timestep++;
    stride = (stride << 1);
  } /* end while(stride < size) */

  MPI_Barrier(MPI_COMM_WORLD);
  fprintf(stdout,"(time,proc,mytoken) (from,to) (%2ld,%2d,",
          timestep,myrank);
  for(i = 0; i < commsize; i++) fprintf(stdout,"%1lx",((mytoken>>i)&1));
  fprintf(stdout,") (%2d,%2d)\n",fromto.sendto,fromto.recvfrom);
}

void grid(LONG size)
{
  char mytoken,recvtoken;
  char *tokenlist = "ABCDEFGHIJKLMNOP";
  int mygridrank,reorder = 1,tag = 0;
  int coords[2],dimsizes[2],wraparound[2];
  LONG timestep;
  MPI_Status status;
  MPI_Comm gridcomm;
  links fromto;

  if(0 == (myrank % size))
    mytoken = tokenlist[myrank/size];
  else
    mytoken = NULLTOKEN;

  dimsizes[0] = size;
  dimsizes[1] = size;
  wraparound[0] = 1;
  wraparound[1] = 1;

  MPI_Cart_create(MPI_COMM_WORLD,2,dimsizes,wraparound,reorder,&gridcomm);
  MPI_Comm_rank(gridcomm,&mygridrank);
  MPI_Cart_coords(gridcomm,mygridrank,2,coords);

#ifdef EBUG
  fprintf(stdout,"myrank,mygridrank,coords %2d %2d (%2d,%2d)\n",
          myrank,mygridrank,coords[0],coords[1]);
#endif

  fromto = gridlinksright(gridcomm,size,myrank);
#ifdef EBUG
  fprintf(stdout,"(from,myself,to) (%2d,%2d,%2d)\n",
          fromto.recvfrom,myrank,fromto.sendto);
#endif

  for(timestep = 0; timestep <= size; timestep++)
  {
    if(NULLTOKEN != mytoken)
    {
      fprintf(stdout,"(time,proc,token) (%2ld,%2d,%c)\n",
              timestep,myrank,mytoken);
    }

    MPI_Send(&mytoken,ONEITEM,MPI_CHAR,fromto.sendto,tag,MPI_COMM_WORLD);

    MPI_Recv(&recvtoken,ONEITEM,MPI_CHAR,fromto.recvfrom,
             tag,MPI_COMM_WORLD,&status);
    mytoken = recvtoken;
  }
}

links gridlinksdown(MPI_Comm gridcomm,LONG size,int myrank)
{
  int coords[2];
  int mygridrank;
  links thelink;

  MPI_Comm_rank(gridcomm,&mygridrank);
  MPI_Cart_coords(gridcomm,mygridrank,2,coords);

  coords[0] = (coords[0] + 1) % size;
  MPI_Cart_rank(gridcomm,coords,&mygridrank);
  thelink.sendto = mygridrank;
  
  coords[0] = (size + coords[0] - 2) % size;
  MPI_Cart_rank(gridcomm,coords,&mygridrank);
  thelink.recvfrom = mygridrank;

  return(thelink);
}

links gridlinksright(MPI_Comm gridcomm,LONG size,int myrank)
{
  int coords[2];
  int mygridrank;
  links thelink;

  MPI_Comm_rank(gridcomm,&mygridrank);
  MPI_Cart_coords(gridcomm,mygridrank,2,coords);

  coords[1] = (coords[1] + 1) % size;
  MPI_Cart_rank(gridcomm,coords,&mygridrank);
  thelink.sendto = mygridrank;
  
  coords[1] = (size + coords[1] - 2) % size;
  MPI_Cart_rank(gridcomm,coords,&mygridrank);
  thelink.recvfrom = mygridrank;

  return(thelink);
}

void threed(LONG xsize,LONG ysize,LONG zsize)
{
  char mytoken;
  char *tokenlist = "AGJDEKHBCILF";
  int mygridrank,reorder = 1,tag = 0;
  int coords[3],dimsizes[3],wraparound[3];
  LONG timestep;
  MPI_Comm gridcomm;
  MPI_Status status;
  links fromto;

  mytoken = tokenlist[myrank];

  dimsizes[0] = 2;
  dimsizes[1] = 2;
  dimsizes[2] = 3;

  wraparound[0] = 1;
  wraparound[1] = 1;
  wraparound[2] = 1;

  MPI_Cart_create(MPI_COMM_WORLD,3,dimsizes,wraparound,reorder,&gridcomm);
  MPI_Comm_rank(gridcomm,&mygridrank);
  MPI_Cart_coords(gridcomm,mygridrank,3,coords);

#ifdef EBUG
  fprintf(stdout,"myrank,mygridrank,coords %2d %2d (%2d,%2d,%2d)\n",
          myrank,mygridrank,coords[0],coords[1],coords[2]);
#endif

  fromto = threedlinks(gridcomm,xsize,ysize,zsize,myrank);
#ifdef EBUG
  fprintf(stdout,"(from,myself,to) ");
  MPI_Cart_coords(gridcomm,fromto.recvfrom,3,coords);
  fprintf(stdout,"(%2d,%2d,%2d)",coords[0],coords[1],coords[2]);
  MPI_Cart_coords(gridcomm,mygridrank,3,coords);
  fprintf(stdout,"(%2d,%2d,%2d)",coords[0],coords[1],coords[2]);
  MPI_Cart_coords(gridcomm,fromto.sendto,3,coords);
  fprintf(stdout,"(%2d,%2d,%2d)\n",coords[0],coords[1],coords[2]);
#endif

  for(timestep = 0; timestep <= 6; timestep++)
  {
    if(NULLTOKEN != mytoken)
    {
      fprintf(stdout,"(time,proc,token) (%2ld,%2d:(%d,%d,%d),%c)\n",
              timestep,myrank,coords[0],coords[1],coords[2],mytoken);
    }

    MPI_Send(&mytoken,commsize,MPI_CHAR,fromto.sendto,tag,MPI_COMM_WORLD);
    MPI_Barrier(MPI_COMM_WORLD);
    MPI_Recv(&mytoken,commsize,MPI_CHAR,fromto.recvfrom,
             tag,MPI_COMM_WORLD,&status);
    MPI_Barrier(MPI_COMM_WORLD);
  }
}

links threedlinks(MPI_Comm gridcomm,LONG xsize,LONG ysize,LONG zsize,int myrank)
{
  int coords[3];
  int mygridrank;
  links thelink;

  MPI_Comm_rank(gridcomm,&mygridrank);
  MPI_Cart_coords(gridcomm,mygridrank,3,coords);

  coords[0] = (coords[0] + 1) % xsize;
  coords[1] = (coords[1] + 1) % ysize;
  coords[2] = (coords[2] + 1) % zsize;
  MPI_Cart_rank(gridcomm,coords,&mygridrank);
  thelink.sendto = mygridrank;
  
  coords[2] = (zsize + coords[2] - 2) % zsize;
  MPI_Cart_rank(gridcomm,coords,&mygridrank);
  thelink.recvfrom = mygridrank;

  return(thelink);
}

void wavefront(LONG size)
{
  char mytoken,prevtoken;
  int mygridrank,reorder = 1,tag = 0;
  int coords[2],dimsizes[2],wraparound[2];
  LONG timestep;
  MPI_Status status;
  MPI_Comm gridcomm;
  links fromto[2];

  prevtoken = '*';
  mytoken = '*';
  if(   ( 3 == myrank) || ( 6 == myrank)
     || ( 9 == myrank) || (12 == myrank))
  {
    mytoken = 'A';
  }

  dimsizes[0] = size;
  dimsizes[1] = size;
  wraparound[0] = 1;
  wraparound[1] = 1;

  MPI_Cart_create(MPI_COMM_WORLD,2,dimsizes,wraparound,reorder,&gridcomm);
  MPI_Comm_rank(gridcomm,&mygridrank);
  MPI_Cart_coords(gridcomm,mygridrank,2,coords);

#ifdef EBUG
  fprintf(stdout,"myrank,mygridrank,coords %2d %2d (%2d,%2d)\n",
          myrank,mygridrank,coords[0],coords[1]);
#endif

  fromto[0] = gridlinksright(gridcomm,size,myrank);
#ifdef EBUG
  fprintf(stdout,"right (from,myself,to) (%2d,%2d,%2d)\n",
          fromto[0].recvfrom,myrank,fromto[0].sendto);
#endif

  fromto[1] = gridlinksdown(gridcomm,size,myrank);
#ifdef EBUG
  fprintf(stdout,"down (from,myself,to) (%2d,%2d,%2d)\n",
          fromto[1].recvfrom,myrank,fromto[1].sendto);
#endif

  for(timestep = 0; timestep < size+1; timestep++)
  {
    if(('A' == mytoken) && ('*' == prevtoken))
    {
      MPI_Cart_coords(gridcomm,mygridrank,2,coords);
      fprintf(stdout,"(time,proc,token) %2ld %2d:(%2d,%2d) %c\n",
              timestep,myrank,coords[0],coords[1],mytoken);
    }

#ifdef EBUG
    fprintf(stdout,"(timestep,from,myself,to) (%2ld,%2d,%2d,%2d)\n",
            timestep,fromto[timestep%2].recvfrom,
            myrank,fromto[timestep%2].sendto);
#endif
    MPI_Barrier(MPI_COMM_WORLD);
    MPI_Send(&mytoken,ONEITEM,MPI_CHAR,fromto[timestep%2].sendto,
             tag,MPI_COMM_WORLD);
    MPI_Barrier(MPI_COMM_WORLD);
    MPI_Recv(&mytoken,ONEITEM,MPI_CHAR,fromto[timestep%2].recvfrom,
             tag,MPI_COMM_WORLD,&status);
    MPI_Barrier(MPI_COMM_WORLD);
  }
}