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

const int max_references=255; //Max amount of gold standard reference translations
const int max_sentence_length = 255; // Counted in words

int verbose=0; // 0=Verbose Off --- 1=Verbose On
int cs=0; //cs default is not case sensitive

void CalculateRuns(char *ReferenceTokens[max_sentence_length],int rTokenCount,char *CandidateTokens[max_sentence_length],int cTokenCount,int runs[max_sentence_length*max_references],int RefTokenBarrier[max_references])
{
  int runindex=0;
  
// Greedy Algorithm
  
  bool RefTokenUsed[max_sentence_length];
  bool CanTokenUsed[max_sentence_length];
  memset(&RefTokenUsed,0,sizeof(RefTokenUsed));
  memset(&CanTokenUsed,0,sizeof(CanTokenUsed));

  int Can;   // Can en Ref are the indices to run over the
  int Ref;     // Candidate Reference grid, comparing tokens

  int LargestRun; // Size of the Largest Run left;
  int RunLocationCan,RunLocationRef; // Where in the grid have we found the largest run still available
   
  do {
    Can=0;
    while ((Can<cTokenCount) && CanTokenUsed[Can]) Can++;
    LargestRun=0;
    
// Look for the largest run left
    while (Can<cTokenCount) {
      Ref=0;
      while ((Ref<rTokenCount) && RefTokenUsed[Ref]) Ref++;

      while (Ref<rTokenCount) {

        if (((cs==1) && (strcmp(ReferenceTokens[Ref],CandidateTokens[Can])==0)) || ((cs==0) && (strcasecmp(ReferenceTokens[Ref],CandidateTokens[Can])==0))) {
          int RunSize=1;
          int RefBarrier=0;
          for(int i=rTokenCount-1;i>=0;i--) if (Ref <  RefTokenBarrier[i]) RefBarrier=RefTokenBarrier[i];
          while (((Ref+RunSize<RefBarrier) && (Can+RunSize<cTokenCount)) &&
                 ((CanTokenUsed[Can+RunSize]==0) && (RefTokenUsed[Ref+RunSize]==0)) &&
                 (((cs==1) && (strcmp(ReferenceTokens[Ref+RunSize],CandidateTokens[Can+RunSize])==0)) || ((cs==0) && (strcasecmp(ReferenceTokens[Ref+RunSize],CandidateTokens[Can+RunSize])==0)))) RunSize++; 
          if (RunSize>LargestRun) {
            LargestRun=RunSize;
            RunLocationCan=Can;
            RunLocationRef=Ref;

          }
        }

        Ref++;
        while ((Ref<rTokenCount) && RefTokenUsed[Ref]) Ref++;

      }
      Can++;
      while ((Can<cTokenCount) && CanTokenUsed[Can]) Can++;

    }
    if (LargestRun>0) {

      runs[runindex++]=LargestRun;
      for(int i=0;i<LargestRun;i++) {
        CanTokenUsed[RunLocationCan+i]=1;
        RefTokenUsed[RunLocationRef+i]=1;
      }

    }

  } while (LargestRun>0);
  
}


int main(int argc, char *argv[])
{
  int i,j; // loop variables;
  
  int e=2; //exponent used in the sum

  char *cfilename=0; //filename of candidate or to check translations
  int ref=0; // Number of gold standard reference files
  char *rfilename[max_references]; // filenames of gold standard reference files

// Cleaning op argv[0], removing path
  i=0; j=0;
  while (*(argv[0]+i)!=0) {
    i++;
    if (*(argv[0]+i)=='/') j=i+1;
  }
  argv[0]=argv[0]+j;

// Processing commandline arguments
  for (i=1;i<argc;i++) {

// Help?
    if (strcmp(argv[i],"-h")==0) {
      fprintf(stdout,"FMeasure an evaluation tool for Machine Translation\nWritten by S.Zwarts\n");
      fprintf(stdout,"Based on the paper:\n   Evaluation of Machine Translation and its Evaluation\n   by Turian J. P., Shen L., Melamed I. D.\n\n");
      fprintf(stdout,"Usage: %s [-v] [-c] [-e number] candidatefile referencefile1 [referencefile2 ...]\nOr use %s -h for help.\n\n",argv[0],argv[0]);
      fprintf(stdout,"   -h   Print this message and quit\n");
      fprintf(stdout,"   -v   Turn on verbose mode\n");
      fprintf(stdout,"   -e   Must be followed by a positive nonzero integer\n        Sets the argument for the exponent. Default is 2\n");
      fprintf(stdout,"   -c   Turn on Case Sensitivity\n");
      return 0;
    } else

// Non default exponent?
    if (strcmp(argv[i],"-e")==0) {
       if (++i >= argc) {
         fprintf(stderr,"Missing argument for -e\n   Usage -e <integer>\n");
         return -1;
       }
      e=atoi(argv[i]);
      if (e <= 0) {
        fprintf(stderr,"%s is an invalide argument for -e\n  Usage -e <integer>\nArgument must be a nonzero positive integer\n",argv[i]);
        return -1;
      }

    } else

// Turn on Case Sensitivty
    if (strcmp(argv[i],"-c")==0) {
      cs=1;
    } else 

// Turning on verbose mode
    if (strcmp(argv[i],"-v")==0) {
      verbose=1;
    } else {
      if (cfilename==0) {
        cfilename=argv[i];
      } else {
        rfilename[ref++]=argv[i];
      }
    }
  }
  if (cfilename==0) {
    fprintf(stderr,"Missing file with Candidate Translations\n\nUsage: %s [-v] [-c] [-e number] candidatefile referencefile1 [referencefile2 ...]\nOr use %s -h for help.\n",argv[0],argv[0]);
    return -1;
  }
  if (ref==0) {
    fprintf(stderr,"Missing file with Reference Translations\n\nUsage: %s [-v] [-c] [-e number] candidatefile referencefile1 [referencefile2 ...]\nOr use %s -h for help.\n",argv[0],argv[0]);
    return -1;
  }

// Opening files

  FILE *fd=fopen(cfilename,"r");
  FILE *fd_ref[max_references];
  if (fd==NULL) {
    fprintf(stderr,"Error opening file: %s\n",cfilename);
    return -1;
  }
// Open reference files
  for(i=0;i<max_references;i++) {
    if (i>=ref) fd_ref[i]=NULL;
    else {
      fd_ref[i]=fopen(rfilename[i],"r");
      if (fd_ref[i]==NULL)
        fprintf(stderr,"Error opening file: %s\n",rfilename[i]);
    }
  }

// Start information
  if (verbose) {
    fprintf(stdout,"Running %s on %s\n",argv[0],cfilename);
    fprintf(stdout,"  Exponent: %i\n  Algorithm: ",e);
    fprintf(stdout, "\nUsing the following gold standard reference");
    if (ref>1) fprintf(stdout, "s; \n");
    else fprintf(stdout, ": \n");
    for(i=0;i<ref;i++) {
      fprintf(stdout, "   %s\n",rfilename[i]);
    }
    fprintf(stdout,"\n");
  }

// Files are open, parameters are read, we're ready to go
// Start reading the sentence with the gold standard ones

  char *cline=(char *)malloc(4096); // Maximum sentence length 4096 letters
  char *cfline=(char *)malloc(4096); // Candidate Final Line
  char *ctokens=(char *)malloc(4096+max_sentence_length);


  char *rline=(char *)malloc(4096); // Maximum sentence length 4096 letters
  char *rfline=(char *)malloc(4096); // Reference Final Line
  char *rtokens=(char *)malloc((4096+max_sentence_length)*max_references); 
  char *firstrtoken;

  firstrtoken=rtokens;

  *cfline = '\0';
  *rfline = '\0';

  int c; // Store the length of the final string in here
  int cTokenCount, rTokenCount;

  char *CandidateTokens[max_sentence_length];
  char *ReferenceTokens[max_sentence_length*max_references];
  int RefTokenBarrier[max_references]; // Where in the token list does this reference ends? (For when there are more gold standards)

  int runs[max_sentence_length*max_references];

  double TotalC=0;
  double TotalR=0;
  double TotalMMS=0;

  while (!(feof(fd)) ) {

// Read Candidate Sentence
    memset(cfline,0,4096*sizeof(*cfline));
    c=0;

    do { // Sentence can be spread out over more lines. * marks end of sentence
      fgets(cline,4096,fd);
      if (*cline!='*') {
        for (;*(cfline+c)!='\0';c++);
        strncat(cfline,cline,4096-c);
      }
    } while (!(feof(fd)) && (*cline!='*'));
    // cfline now containes the entire sentence


// Tokenise Candidate Sentence
    cTokenCount=0;
    i=0;
    while (*(cfline+i)!='\0') {
      while(((*(cfline+i)<'A' || *(cfline+i)>'Z') && (*(cfline+i)<'a' || *(cfline+i)>'z') &&  (*(cfline+i)<'À' || *(cfline+i)>'ÿ') && (*(cfline+i)<'0' || *(cfline+i)>'9')) && *(cfline+i)!='\0') i++;
      j=i;
      while(((*(cfline+i)>='A' && *(cfline+i)<='Z') || (*(cfline+i)>='a' && *(cfline+i)<='z') ||  (*(cfline+i)>='À' && *(cfline+i)<='ÿ') || (*(cfline+i)>='0' && *(cfline+i)<='9')) && *(cfline+i)!='\0') i++;
      if (i!=j) {
        memcpy(ctokens+j+cTokenCount,cfline+j,i-j);
        CandidateTokens[cTokenCount]=(ctokens+j+cTokenCount);
        *(CandidateTokens[cTokenCount]+(i-j))='\0';
        cTokenCount++;
      }
      i++;

    }

    int r; //which reference

// Read Gold standard Sentences
    memset(&runs,0,sizeof(runs));
    rtokens=firstrtoken;
    rTokenCount=0;
    if (*cfline!=0)
    for (r=0;r<ref;r++) { // For every gold standard file      
      memset(rfline,0,4096*sizeof(*rfline));
      c=0;
      if (feof(fd_ref[r])) { 
        fprintf(stdout,"Warning Reference %i contains not enough references for sentence:\n\"%s\"\n",r,cfline);
        fprintf(stdout,"%i",*cfline);
      }
      else do { // Sentence can be spread out over more lines. * marks end of sentence
        fgets(rline,4096,fd_ref[r]);
        if (*rline!='*') {
          for (;*(rfline+c)!='\0';c++);
          strncat(rfline,rline,4096-c);
        }
      } while (!(feof(fd_ref[r])) && (*rline!='*'));
      // rfline now containes the entire sentence
// Tokenize Reference Sentences
      i=0;
      while (*(rfline+i)!='\0') {
//        while((*(rfline+i)==' ' || *(rfline+i)=='\n') && *(rfline+i)!='\0') i++;
      while(((*(rfline+i)<'A' || *(rfline+i)>'Z') && (*(rfline+i)<'a' || *(rfline+i)>'z') &&  (*(rfline+i)<'À' || *(rfline+i)>'ÿ') && (*(rfline+i)<'0' || *(rfline+i)>'9')) && *(rfline+i)!='\0') i++;

        j=i;
        while(((*(rfline+i)>='A' && *(rfline+i)<='Z') || (*(rfline+i)>='a' && *(rfline+i)<='z') ||  (*(rfline+i)>='À' && *(rfline+i)<='ÿ') || (*(rfline+i)>='0' && *(rfline+i)<='9')) && *(rfline+i)!='\0') i++;
        if (i!=j) {
          memcpy(rtokens,rfline+j,i-j);
          ReferenceTokens[rTokenCount]=rtokens;
          *(rtokens+(i-j))='\0';
          rTokenCount++;
          rtokens+=(i-j)+1;
        }
        i++;
        RefTokenBarrier[r]=rTokenCount;

      }
    } 
    double RefMeanLength=(double)rTokenCount/(double)ref;

    CalculateRuns(ReferenceTokens, rTokenCount,CandidateTokens,cTokenCount,runs,RefTokenBarrier);

    int RunSum=0;
    
    TotalC+=cTokenCount;
    TotalR+=RefMeanLength;
    double MMS=0;

    for(i=0;runs[i]!=0;i++) RunSum+=runs[i];
    if (RunSum<=RefMeanLength) {
      for(i=0;runs[i]!=0;i++) MMS+=pow(runs[i],e);
    } else {
// Totalfound matches exceeds reference length, cut it down starting with the smallest

      double SizeLeft=RefMeanLength;
      i=0;
      while (SizeLeft > 0) {
         if (runs[i]>=SizeLeft) {
           MMS+=pow(SizeLeft,e);
           SizeLeft=0;
         } else {
           MMS+=pow(runs[i],e);
           SizeLeft-=runs[i];
         }
         i++;
      }
    }
    TotalMMS+=pow(MMS,(1.0)/e);
  }

  double precision=(TotalMMS/TotalC);
  double recall=(TotalMMS/TotalR);

  if (verbose) {
    fprintf(stdout,"Tokens in Candidate file: %i\n",int(TotalC));
    if (ref > 1) fprintf(stdout,"Average tokens in Reference files: %f\n",TotalR);
    else fprintf(stdout,"Tokens in Reference file: %i\n",int(TotalR));
    fprintf(stdout,"Total maximum match sizes: %f\n\n",TotalMMS);
  }

  fprintf(stdout,"precision: %f\n",precision);
  fprintf(stdout,"recall   : %f\n",recall);
  fprintf(stdout,"f-measure: %f\n",(2*precision*recall)/(precision+recall));

  return 0;
}