//
// Parallel dictionary search program.
// Says if the word was found in the dictionary.  If the word
// is not found, it prints up to CDIM close words.
//
// The manager distributes chunks of words ("tasks") to worker processes.
// The workers search their chunk for the word and report back to the manager.

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

#define CDIM 10
#define QDIM 31
#define LDIM 81
#define RESDIM QDIM+LDIM
#define MATCH 10
#define CLOSE 12
#define BAD 11
#define YES 1
#define NO 0
#define WORDSSENT 100

#define WORKSTOP -2

/* TAGS */
#define NUMCLOSEWORDSTAG 1
#define CLOSEWORDSTAG 2
#define FOUNDRESULTTAG 3
#define WORKLENGTHTAG 4
#define WORKTAG 5

void sendTask( int recipient, FILE *dictionary, int *outstandingWork, int *endOfFile );
void sendWorkersExit( int exitStatus, int size);
void recvResult(int *outstandingWork);
int copyCloseWords(int closeElement, int closep, char closeWords[CDIM][QDIM], char closew[CDIM][QDIM]);

main(int argc, char **argv) {

  //===========================================\\
  // ----  LOCAL VARIABLE INITIALIZATION  ---- \\
  //===========================================\\


  FILE *dictionary;

  int rank;       // Process Number (for MPI_COMM_RANK)
  int size;       // Number of Processes Running (for MPI_COMM_SIZE)
  int proc = 1;
  int bytes;
  int loopCounter = 0; // used for sending specified amount of words from dictionary to temp array
  int element = 0;     // the specific element that a word is being read into in the temp array
  int answer;
  int i;
  int found = NO;
  int elementExit = WORKSTOP;
  int closep = 0;
  int closeElement = 0;
  int dest = 0;
  int tempSize = 0;
   
  char closew[CDIM][QDIM];
  char mgrClose[CDIM][QDIM];
  char line[LDIM];
  char query[QDIM];
  char temp[WORDSSENT][QDIM];
  char tmp[QDIM];

  int outstandingWork=0;
  int endOfFile = 1;



  double start,finish;

  //======================================\\
  // -------  MPI INITIALIZATION -------- \\
  //======================================\\


  MPI_Init(&argc,&argv);
  MPI_Comm_size(MPI_COMM_WORLD,&size);
  MPI_Comm_rank(MPI_COMM_WORLD,&rank);
  MPI_Status status;


  //===============================\\
  // ------ MANAGER PROCESS ------ \\
  //===============================\\


  /* Ask for word to check */

  if (rank == 0) {

    outstandingWork = 0;

    /* Open dictionary file */
    dictionary = fopen("dictionary","r");

    if (dictionary == NULL) {
      printf("Error opening Dictionary file.\n");
      MPI_Abort(MPI_COMM_WORLD, -5);
      exit(-5);
    }

    printf("Please enter the query word: ");
    fgets(query, QDIM, stdin);
    // remove the last '\n' 
    query[ strlen(query)-1 ] = '\0';

    //timing statement
    start = MPI_Wtime();

    MPI_Bcast(query, QDIM, MPI_CHAR, 0, MPI_COMM_WORLD);

    /*send out initial chunks of data ("tasks") to every proc except
      manager */
    while (proc < size && endOfFile != 0 ) {
      sendTask( proc, dictionary, &outstandingWork, &endOfFile );
      proc++;
    }

    /* start sending out chunks of data based on which processor
       finished checking its data set */
    while (found != YES && endOfFile != 0 ) {

      recvResult(&outstandingWork);
     
      MPI_Recv(&found,1,MPI_INT,MPI_ANY_SOURCE,FOUNDRESULTTAG,MPI_COMM_WORLD,&status);
      proc = status.MPI_SOURCE;

      if (found == NO) {
	sendTask( proc, dictionary, &outstandingWork, &endOfFile );
      }
      else if (found == CLOSE) {
	MPI_Recv(&closep,1,MPI_INT,proc,NUMCLOSEWORDSTAG,MPI_COMM_WORLD,&status);
	MPI_Recv(closew,closep*QDIM,MPI_CHAR,proc,CLOSEWORDSTAG,MPI_COMM_WORLD,&status);

	closeElement = copyCloseWords(closeElement, closep, mgrClose, closew);            
	sendTask(proc, dictionary, &outstandingWork, &endOfFile );
	printf("Outstanding work: %d\n", outstandingWork);
      } 

    } // end while for manager recving results and sending more work
 
      //timing statement
    finish = MPI_Wtime();
 
    /* send out exit symbol to other procs */
    sendWorkersExit(elementExit, size);

    /* Need to hear back from all processes if word has not yet been
       found
    */
    while( found != YES && outstandingWork > 0 ) {
      recvResult(&outstandingWork);
	
      MPI_Recv(&found,1,MPI_INT,MPI_ANY_SOURCE,FOUNDRESULTTAG,MPI_COMM_WORLD,&status);
      proc = status.MPI_SOURCE;

      if (found == CLOSE) {
	MPI_Recv(&closep,1,MPI_INT,proc,NUMCLOSEWORDSTAG,MPI_COMM_WORLD,&status);
	MPI_Recv(closew,closep*QDIM,MPI_CHAR,proc,CLOSEWORDSTAG,MPI_COMM_WORLD,&status);
	closeElement = copyCloseWords(closeElement, closep, mgrClose, closew);
      } 

    }

    if (found == YES)
      printf("%s found in dictionary.\n",query);
    else if (closeElement > 0) {
      printf("The following words were close matches:\n");
      for (i=0;i<closeElement;i++) 
	printf("%s\n",mgrClose[i]);
    }
    else
      printf("%s was not found in the dictionary.\n", query);


    printf("Manager\t\t%1f\n",finish-start);

  } //end manager process (rank 0)

  //===================================\\
  // ----- SUBORDINATE PROCESSES ----- \\
  //===================================\\
   
  else if (rank > 0) {
    
    // Receive the query word
    MPI_Bcast(query, QDIM, MPI_CHAR, 0, MPI_COMM_WORLD);

    /* Receive words from dictionary to check through */
    MPI_Recv(&tempSize,1,MPI_INT,0,WORKLENGTHTAG,MPI_COMM_WORLD,&status);

    //while exit symbol has not been received
    while (tempSize != WORKSTOP) {
      
      MPI_Recv(temp,tempSize*QDIM,MPI_CHAR,0,WORKTAG,MPI_COMM_WORLD,&status);
      closep = 0;
      found = NO;

      while (element < tempSize && found != YES) {

	answer = spell_checker(query,temp[element]);

	if(answer == MATCH) {
	  found = YES;
	  MPI_Send(&found,1,MPI_INT,0,FOUNDRESULTTAG,MPI_COMM_WORLD);
	}
	else if(answer == CLOSE){
	  // keep close words until look through complete chunk
	  found = CLOSE;
	  strcpy(closew[closep],temp[element]);
	  closep++;
	}

	element++;

      } // end inner while
                
      if (found != YES) {
                                      
	MPI_Send(&found,1,MPI_INT,0,FOUNDRESULTTAG,MPI_COMM_WORLD);

	if (closep > 0) {
	  MPI_Send(&closep,1,MPI_INT,0,NUMCLOSEWORDSTAG,MPI_COMM_WORLD);
	  MPI_Send(closew,closep*QDIM,MPI_CHAR,0,CLOSEWORDSTAG,MPI_COMM_WORLD);
	}

      } //end if element == last element of array

      element = 0;
      MPI_Recv(&tempSize,1,MPI_INT,0,WORKLENGTHTAG,MPI_COMM_WORLD,&status);

    } // end Receiving work

      
  } //end worker process (1-?)


  //===================================\\
  // ------- MPI FINALIZATION -------- \\
  //===================================\\


  MPI_Finalize();

  return;

}

/**
 * for manager to send chunk of words to worker process
 */
void sendTask( int recipient, FILE *dictionary, int *outstandingWork, int *endOfFile ) {

  int element = 0;
  int bytes = 0;
  char temp[WORDSSENT][QDIM];
  char line[QDIM];
  
  bytes = fscanf(dictionary, "%s", line);

  while (element < WORDSSENT && bytes != EOF) {
    strncpy(temp[element],line,QDIM-1);
    element++;
    bytes = fscanf(dictionary, "%s", line);
  }

  if( bytes == EOF )
    *endOfFile = 0;
  
  MPI_Send(&element,1,MPI_INT, recipient,WORKLENGTHTAG,MPI_COMM_WORLD);
  MPI_Send(temp,element*QDIM,MPI_CHAR, recipient,WORKTAG,MPI_COMM_WORLD);

  *outstandingWork= *outstandingWork + 1;
}

/**
 * Send message to workers to exit
 */
void sendWorkersExit( int elementExit, int size) {
  int i;

  for (i=1;i<size;i++) {
    MPI_Send(&elementExit,1,MPI_INT,i,WORKLENGTHTAG,MPI_COMM_WORLD);
  }

}


/**
 * for manager to receive result
 */
void recvResult(int *outstandingWork) {

  *outstandingWork=*outstandingWork-1;

}

/**
 * copy close words from input buffer to master list
 */
int copyCloseWords(int closeElement, int closep, char mgrClose[CDIM][QDIM], char closew[CDIM][QDIM]) {
  int i;
  for (i=0;i<closep && closeElement < CDIM;i++) {
    strcpy(mgrClose[closeElement],closew[i]);
    closeElement++;
  }
  return closeElement;
}


//==============================\\
// ------ SPELL CHECKER ------- \\
//==============================\\


int spell_checker(char query[], char dict[]) {
  int result[RESDIM];
  int i,j,maxans,goal,answer;

  for (i = 0; i < RESDIM; i++)
    result[i] = 0;

  for (i = 0; i <= strlen(query) - 1; i++) {
    for (j = RESDIM - 1; j >= 1; j--)
      result[j] = result[j-1];
    result[0] = 0;
    
    for (j = 0; j <= strlen(dict) - 1; j++) {
      if (query[i] == dict[j])
	result[j] = result[j] + 1;
    }
  }
   
  maxans = 0;

  for (i = 0; i < RESDIM; i++) {
    if (maxans < result[i])
      maxans = result[i];
  }
  if (strlen(query) < strlen(dict))
    goal = strlen(dict);
  else
    goal = strlen(query);
  if (maxans == goal)
    answer = MATCH;
  else if (maxans == goal - 1)
    answer = CLOSE;
  else
    answer = BAD;
  return(answer);
} // end spell_checker