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

#define MXLEN 71
#define NMAX 1000
#define DEBUG 0


void get_data(char s[][MXLEN], int *n) {
  int i;
  char *nl;
  fgets( s[0], MXLEN, stdin );
  *n = atoi(s[0]);
  for ( i=0; i<*n; i++ ) {
    fgets(s[i],MXLEN,stdin);
    if (( nl=strchr(s[i],'\n'))) *nl='\0';   // remove newline character
  }
}

int ordered( char s[][MXLEN], int n ) {
  int i;
  for ( i=0; i<n-1; i++ ) {
    if ( strcmp( s[i], s[i+1] ) > 0 )
      return 0;
  }
  return 1;
}

//******************************************************************
// 
//  Array of strings is divided into blocks. One process checks if
//  the block assigned to it is in alphabetical order.
//  Master process checks first the block junctions. 
// 
//******************************************************************


char s[NMAX][MXLEN];

int main( int argc, char *argv[] ) {
  int n, np, me, i, nn, ok, pos, nloc;
  MPI_Status stat;

  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD,&np);
  if ( np < 2 ) {
    MPI_Finalize();
    printf("np should be at least 2\n");
    return -1;
  }
  MPI_Comm_rank(MPI_COMM_WORLD,&me);
  //
  int ok2[np], is[np], ie[np];
  MPI_Request req[np];
  //
  if ( me==0 ) {
    // ********************
    // *** Master task ****
    // ********************
    
    // Get strings
    //
    get_data(s,&n);
    if ( DEBUG > 1 ) {
      printf("Strings:\n");
      for ( i=0; i<n; i++)
	printf("*** %s\n",s[i]);
    }
    //
    // Calculate block start/end indices to be assigned to workers
    //
    pos = 0;
    nloc = n/np;
    for ( i=0; i<np; i++ ) {
      is[i] = pos;
      if ( i < n%np ) 
	pos += nloc+1;
      else
	pos += nloc;
      ie[i] = pos-1;
      if ( DEBUG )
	printf("P%d takes care of strings s[%d]...s[%d]\n",i,is[i],ie[i]);
    }
    //
    // Check if block boundaries in order or not:
    //
    ok = 1;
    for ( i=0; i<np-1; i++ ) {
      if ( strcmp(s[ie[i]],s[is[i+1]]) > 0 ) {
	ok=0;
	printf("\n ***Strings s[%d] and s[%d] not in order\n\n",
	       ie[i],is[i+1]);
      }
    }
    //
    // Send result of the previous check to workers
    //
    for ( i=1; i<np; i++ )
      MPI_Send(&ok,1,MPI_INT,i,555,MPI_COMM_WORLD);
    if (!ok) {
      MPI_Finalize();
      return 0;
    }
    //
    // Send blocks to be checked to workers
    //
    for ( i=1; i<np; i++ ) {
      nn = ie[i]-is[i]+1;
      MPI_Send(&nn,1,MPI_INTEGER,i,558,MPI_COMM_WORLD);
      MPI_Isend(&s[is[i]][0],MXLEN*nn,MPI_CHAR,i,556,MPI_COMM_WORLD,&req[i]);
    }
    //
    // Master checks one block, too
    //
    ok2[0]=ordered(s,ie[0]+1);
    //
    // Receive results from workers
    //
    for ( i=1; i<np; i++ ) 
      MPI_Recv(&ok2[i],1,MPI_INT,i,557,MPI_COMM_WORLD,&stat);
    //
    // Report result:
    //
    ok = 1;
    for ( i=0; i<np; i++ ) {
      if ( ! ok2[i] ) {
	printf("\n*** Block s[%d]...s[%d] not in order\n\n",is[i],ie[i]);
	ok=0;
      }
    }
    if ( ok ) printf("\nAll strings in alphabetical order\n\n");
  }
  else {
    // *******************
    // *** Worker task ***
    // *******************

    MPI_Recv(&ok,1,MPI_INT,0,555,MPI_COMM_WORLD,&stat);
    if ( DEBUG ) 
      printf("me=%d received ok=%d from master\n",me,ok);
    if ( ok ) {
      //
      // Receive number of strings assigned to me
      //
      MPI_Recv(&nn,1,MPI_INT,0,558,MPI_COMM_WORLD,&stat);
      if ( DEBUG ) 
	printf("me=%d received nn=%d\n",me,nn);
      char sbuf[nn][MXLEN];
      //
      // Receive strings
      //
      MPI_Recv(&sbuf[0][0],MXLEN*nn,MPI_CHAR,0,556,MPI_COMM_WORLD,&stat);
      if ( DEBUG > 1 ) {
	printf("me=%d received strings\n",me);
	for ( i=0; i<nn; i++ )
	  printf("%d: %s\n",me,sbuf[i]);
      }
      //
      // Check if received strings are in order
      //
      ok = ordered(sbuf,nn);
      if ( DEBUG ) 
	printf("me=%d ordered=%d\n",me,ok);
      //
      // Send result of checking to master
      //
      MPI_Send(&ok,1,MPI_INT,0,557,MPI_COMM_WORLD);
    }
    else {
      //
      // Master detected that the strings are not in order 
      // => No work assigned to me.
      //
      if ( DEBUG ) 
	printf("Task %d needs to do nothing\n",me);
    }
  }
  MPI_Finalize();
}