// Compile: cc measure-order.c
// Execute: ./a.out < datafile.dat
//
// given listing of packet orders per node, generate measures
// and histogram; the idea here is to separate statistics and
// measuring from actual packet order generations (and simulation)

// Measures implemented:
// * M2
//
// Input format:
//
// numNodes(or hops) numPackets numSuccessfulRuns(or data sets) 
// foreach S numSuccessfulRuns
//   foreach N numHodes
//     nodeNumber: orderPacketsReceived
//

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

int numNodes=-1,numPackets=-1,numSuccessfulRuns=-1,*packets,**m2_histogram,M2_MAX,
      meth2,*totalM2Score,*meth2_max,*meth2_min,nodeCount;
double *meth2_avg;


// dumps array to stdout
void print_array( int* array, int size )
{ int i;
 for (i = 0; i < size; i++)
     printf("%d ", array[i]);
 printf("\n");
}

// sum of 'larger' packets arriving before i
int calc_disorder_2 ( int* permutation )
{ int i, j, disorder = 0;
 for (i = 0; i < numPackets; i++)
 { for (j = i - 1; j >= 0; j--)
   { if ( permutation[j] > permutation[i] )
          disorder++;
   }
 }
 return disorder;
}

// tracks number of the same measures for histogram of results
void makeMeasurements (int *permutation) 
{  meth2 = calc_disorder_2 ( permutation );
   totalM2Score[nodeCount] += meth2;
   if (meth2 > meth2_max[nodeCount])
     meth2_max[nodeCount] = meth2;
   if (meth2 < meth2_min[nodeCount])
     meth2_min[nodeCount] = meth2;
   // store meth2 results in m2_histogram
   m2_histogram[nodeCount][meth2]++;
   //printf("count:%d, score:%d\n",m2_histogram[nodeCount][meth2],meth2);
}

void SkipToEndofLine(FILE *fpInp)
{ while (getc(fpInp) != '\n');}

void ProcessInput()
{ int i,j,currentNode;
  FILE *fp;
  fp = stdin;
  fscanf(fp, "%d %d %d",&numNodes,&numPackets,&numSuccessfulRuns); 
  SkipToEndofLine(fp);
  M2_MAX=numPackets*(numPackets-1)/2;
  // allocate memory for tracking stats
  packets      = (int *)malloc(numPackets*sizeof(int)); 
  meth2_avg    = (double *)malloc(numNodes*sizeof(double));  
  meth2_min    = (int *)malloc(numNodes*sizeof(int));
  meth2_max    = (int *)malloc(numNodes*sizeof(int)); 
  totalM2Score = (int *)malloc(numNodes*sizeof(int));
  m2_histogram = (int**)malloc(sizeof(int*)*numNodes);
  for (i=0;i<numNodes;i++)
  { m2_histogram[i] = (int*)malloc(sizeof(int)*(M2_MAX+1));// init array of ints
    for (j=0;j<M2_MAX;j++)
        m2_histogram[i][j] = 0;                        // init int vals
    meth2_min[i]=INT_MAX;
  }
  //now cycle over each set of lines and packet orderings
  for (j=0;j<numSuccessfulRuns;j++)
  { for (nodeCount=0;nodeCount<numNodes;nodeCount++)
    { fscanf(fp, "%d:",&currentNode);                  // not currently used
      for (i=0;i<numPackets;i++)
          fscanf(fp, "%d", &packets[i]);               //get packets
      SkipToEndofLine(fp);
      //perform measurements on packet
      makeMeasurements(packets);
      //print_array(packets,numPackets);
    }
  }
}

// handles outputting of stats at the end (average, min, max, etc)
void FinalStats ( void )
{  int i,j;
   double normal_val,prob,*std_dev,e_x, e_x2;
   std_dev = (double *)malloc(numNodes*sizeof(double)); 
   for (i=0;i<numNodes;i++)
   { meth2_avg[i] = totalM2Score[i]/numSuccessfulRuns;
     e_x = e_x2 = 0.0; 
     for (j=0;j<=M2_MAX;j++)
     { e_x  += j*m2_histogram[i][j];  
       e_x2 += j*j*m2_histogram[i][j];
     }
     std_dev[i]=sqrt(e_x2/numSuccessfulRuns - pow(e_x/numSuccessfulRuns,2));
   }
   // output m2_histogram and statistical analysis -- handle 0 count values!!
   for (i=0;i<numNodes;i++)
   { if (0 < totalM2Score[i]) { 
       printf("#LABEL:Node %d\n#M2:     Count: (x-a)/stdev:    Prob:\n",i);
       for (j=0;j<=M2_MAX;j++)
           printf("%4d %6d %10.6f %10.6f\n",j,m2_histogram[i][j],(j-meth2_avg[i])/std_dev[i],((double)m2_histogram[i][j]/numSuccessfulRuns)*std_dev[i]);
       printf("#avg: %10.6f; st.dev: %10.6f \n",meth2_avg[i],std_dev[i]);
     }
   }
}

int main(int argc, char** argv)
{ ProcessInput();
  FinalStats();
  return EXIT_SUCCESS;
}