#include <stdlib.h>
#include <time.h>       // time for srand(time(NULL)) and perhaps clock()
#include <stdio.h>

#include "List.h"
#include "MergeSort.h"  // prototype for void mergeSort (int*,int);
#define TRUE  1
#define FALSE 0

//#define DEBUG

#define UNIX

#ifdef UNIX
#include <sys/times.h>  // Defines the struct tms
#include <unistd.h>     // Pulls in _SC_CLK_TCK
#include <time.h>

// Replacement for clock() --- and its precision problem
// return as floating point seconds both the CPU time
// and the wall-clock time.

void getTimes( double *wallClock, double *cpuClock )
{
   static double cvt = 0.0;
   struct tms cpu;
   double wall = times( &cpu );

   if ( cvt == 0.0 )
      cvt = 1.0 / sysconf(_SC_CLK_TCK);
   *wallClock = cvt * wall;
   *cpuClock  = cvt * cpu.tms_utime;
}

double cpuTime()
{
   double cpu, wall;

   getTimes (&wall, &cpu);
   return cpu;
}
#else   // Probably Microsoft Visual C/C++
double cpuTime()
{  return (double) clock() / CLOCKS_PER_SEC;  }
#endif

/**
 * Fill the array with increasing sequence starting at 1
 */
void fillArray ( int *x, int n )
{  int k;
   for ( k = 0; k < n; k++ )
      x[k] = (k+1);
} // end fillArray()

/**
* Fill the list from x[]
*/
NodePtr fillList ( int *x, int n )
{
   NodePtr head = newNode (x[0], NULL),
           tail = head;
   int   k;

   for (k = 1; k < n; k++ )
   {
      tail = insertAfter( tail, newNode (x[k], NULL) );
      tail = tail->next;
   }
   return head;
}

void copyArray ( int *out, int *x, int size )
{  int k;
   for ( k = 0; k < size; k++ )
      out[k] = x[k];
} // end fillArray()

int nextInt(int lim)
{  return (int) ( (double)rand() * lim / (RAND_MAX + 1.0) );  }

/**
 * Shuffle the entire array, using the class scope generator
 */
void shuffleArray ( int *x, int lim )
{  while ( lim > 1 )
   {  int item;
      int save = x[lim-1];

      item = nextInt(lim);
      x[--lim] = x[item];                // Note predecrement on lim
      x[item] = save;
   } // end while
} // end shuffleArray()

int validateList ( NodePtr entry )
{
   NodePtr last = entry;

   if (entry == NULL) return TRUE;

   entry = entry->next;
   while ( entry != NULL )
   {
      if ( last->data > entry->data )
         return FALSE;
      last  = entry;
      entry = entry->next;
   }
   return TRUE;
}

int validateArray ( int *x, int size )
{
   int k;

   for ( k = 1; k < size; k++ )
      if ( x[k-1] > x[k] )
         return FALSE;
   return TRUE;
}

// Function that can be passed to qsort
int compareInt ( const void *x, const void *y )
{
   const int *lt = (const int*) x,
             *rt = (const int*) y;

   return *lt - *rt;
}

#define nElapsed 5

int main ( int argc, char* argv[] )
{  NodePtr    data = NULL;
   int       *test;
   int       *scratch;
   int        k;
   int        size, maxSize, sizeStep;   // control outer loop
   int        nPasses, pass;             // inner loop
   double     start,                     // initial times in msec.
              elapsed[nElapsed];         // five elapsed times
   FILE      *csvFile;

   csvFile = fopen("MergeSort.csv", "a");

   if ( csvFile == NULL )
   {  printf ("CSV file open failed\n");
      exit(-1);
   }

   fputs ("Initial array length,  ", stdout);
   if ( argc <= 1 )
      scanf ("%d", &size);
   else
   {  size = atoi(argv[1]);
      printf ("%d\n", size);
   } // end if/else regarding argv[1]

   fputs ("Maximum array length,  ", stdout);
   if ( argc <= 2 )
      scanf ("%d", &maxSize);
   else
   {  maxSize = atoi(argv[2]);
      printf ("%d\n", maxSize);
   } // end if/else regarding argv[2]

   fputs ("Increment for length,  ", stdout);
   if ( argc <= 3 )
      scanf ("%d", &sizeStep);
   else
   {  sizeStep = atoi(argv[3]);
      printf ("%d\n", sizeStep);
   } // end if/else regarding argv[3]

   fputs ("Number of passes,  ", stdout);
   if ( argc <= 4 )
   {
      scanf ("%d", &nPasses);
      do
         k = getchar();
      while ( k != '\n' && k != EOF );
   }
   else
   {  nPasses = atoi(argv[4]);
      printf ("%d\n", nPasses);
   } // end if/else regarding argv[4]

   test = (int*) calloc (maxSize, sizeof(*test));
   scratch = (int*) calloc (maxSize, sizeof(*scratch));
   fillArray ( test, maxSize );

   fprintf (csvFile, "n,mergeRecur,mergeIter,mergeNatural,quickSort,iterArray\n");
   printf  ("n,mergeRecur,mergeIter,mergeNatural,quickSort,iterArray\n");
   fflush(csvFile); fflush(stdout);
   srand (time(NULL));

   while ( size <= maxSize )
   {  long seed = (long)rand() * rand(); // Same sequence in all

      printf ("%d", size); fflush(stdout);

      start = cpuTime();
      srand(seed);
      for ( pass = 0; pass < nPasses; pass++ )
      {  shuffleArray ( test, size );
         data = fillList(test, size);
         data = mergeRecurse(data);
#ifdef DEBUG
         if ( !validateList (data) )
         {
            puts ("Error in sorting.  BREAK");
            break;
         }
#endif
         data = empty(data);
      } // end for
      elapsed[0] = cpuTime() - start;
      printf ( ",%3.3f", elapsed[0] );  fflush(stdout);

      start = cpuTime();
      srand(seed);
      for ( pass = 0; pass < nPasses; pass++ )
      {  shuffleArray ( test, size );
         data = fillList(test, size);
         data = mergeIter(data);
#ifdef DEBUG
         if ( !validateList (data) )
         {
            puts ("Error in sorting.  BREAK");
            break;
         }
#endif
         data = empty(data);
      } // end for
      elapsed[1] = cpuTime() - start;
      printf ( ",%3.3f", elapsed[1] );  fflush(stdout);

      start = cpuTime();
      srand(seed);
      for ( pass = 0; pass < nPasses; pass++ )
      {  shuffleArray ( test, size );
         data = fillList(test, size);
         data = mergeNatural(data);
#ifdef DEBUG
         if ( !validateList (data) )
         {
            puts ("Error in sorting.  BREAK");
            break;
         }
#endif
         data = empty(data);
      } // end for
      elapsed[2] = cpuTime() - start;
      printf ( ",%3.3f", elapsed[2] );  fflush(stdout);

      start = cpuTime();
      srand(seed);
      for ( pass = 0; pass < nPasses; pass++ )
      {  shuffleArray ( test, size );
         data = fillList(test, size);
         data = quickSort(data);
#ifdef DEBUG
         if ( !validateList (data) )
         {
            puts ("Error in sorting.  BREAK");
            break;
         }
#endif
         data = empty(data);
      } // end for
      elapsed[3] = cpuTime() - start;
      printf ( ",%3.3f", elapsed[3] );  fflush(stdout);

      start = cpuTime();
      srand(seed);
      for ( pass = 0; pass < nPasses; pass++ )
      {  shuffleArray ( test, size );
         copyArray ( scratch, test, size);
         mergeSort (scratch, size);
#ifdef DEBUG
         if ( !validateArray (scratch, size) )
         {
            puts ("Error in sorting.  BREAK");
            break;
         }
#endif
      } // end for
      elapsed[4] = cpuTime() - start;
      printf ( ",%3.3f", elapsed[4] );  fflush(stdout);

      fprintf(csvFile, "%d", size);
      for ( k = 0; k < nElapsed; k++ )
         fprintf(csvFile, ",%3.3f", elapsed[k] );
      putchar('\n');
      putc ('\n', csvFile);
      fflush(csvFile); fflush(stdout);

      size += sizeStep;             // Next size
   } // end while ( size <= maxSize )
   return 0;
} // end main()