/* plot_sort.c:
   C program to  generate visual plots from the timing  data obtained by
   running various sorting algorithms on  a variety of inputs having (a)
   different sizes  from 'start' to  'stop' in increments of  'step' (b)
   different extents of  sortedness: best, worst and  average cases. The
   plotting application used is GNUPLOT.
   
   For every algorithm:
   (1) Inputs for cases (a) and (b) are generated and stored in memory
   (2) Inputs are sorted and the running time is measured
   (3) Time data is written to a file
   (2) Gnuplot script to plot the data for that file.
*/

#define _GNU_SOURCE
#include <stdio.h>  /* snprintf */
#include <stdlib.h> /* rand, srand and system */
#include <time.h>   /* clock_gettime */

#include "sorting_functions.c" 

typedef struct array {
    int count;
    int *ptr;
} array_t ;

int randint (int lower, int upper)
{
    static int called_before = 0;
    int n;
    if (!called_before) { 
        called_before = 1;
        srand (time (NULL));
    }
    n = rand (); 
    return lower + n % (upper - lower + 1);
}

void arr_restore (int *arr, int len)
{
    for (int i = 0; i < len; i++) 
        arr[i] = arr[i + len];
}

#define NANOSECONDS_PER_SECOND 1e9
long time_sort (int (*sort)(int *, int, int), int *arr, int len)
{
    long elapsed;
    struct timespec temp, start, end;
    clock_gettime (CLOCK_MONOTONIC, &start);
    sort (arr, 0, len - 1);
    clock_gettime (CLOCK_MONOTONIC, &end);
    if ((end.tv_nsec - start.tv_nsec) < 0) {
        temp.tv_sec = end.tv_sec - start.tv_sec - 1;
        temp.tv_nsec = NANOSECONDS_PER_SECOND + end.tv_nsec - start.tv_nsec;
    } 
    else {
        temp.tv_sec = end.tv_sec - start.tv_sec;
        temp.tv_nsec = end.tv_nsec - start.tv_nsec;
    }
    elapsed = (temp.tv_sec * NANOSECONDS_PER_SECOND) + temp.tv_nsec;
    return elapsed;
}

void *xmalloc (size_t siz)
{
    void *mem = malloc (siz);
    if (mem == NULL) 
        exit (2);
    return mem;
}

int genscript
(char *algorithm, char *datafile, char *scriptfile, char *output, size_t siz)
{
    int success;
    /* generate name of plotting script and pdf output from algo name */
    snprintf (scriptfile, siz, "plot%c.plt", algorithm[0]);
    snprintf (output, siz, "plot%c.pdf", algorithm[0]);

    FILE *stream = fopen (scriptfile, "w");
    if (stream == NULL) {
        perror ("fopen");
        return 0;
    }
    success = fprintf (stream, 
            "# autogenerated plotting script\n\n"
            "set terminal pdfcairo enhanced color notransparent "
            "font \"Latin Modern Math\"\n"
            "set output \"%s\"\n\n" 

            /* linestyles */
            "set style line 1 lc rgb \"#008b8b\" lw 1.5\n"
            "set style line 2 lc rgb \"#8b0000\" lw 1.5\n"
            "set style line 3 lc rgb \"#8b8b00\" dashtype 2 lw 1.5\n"
            "set style line 4 lc rgb \"#e6e6e6\"\n\n"

            /* setup */
            "set title \"Analysis of %s\"\n"
            "set xlabel \"Input Size\"\n"
            "set ylabel \"Running time (ns)\" offset -0.5\n"
            "set grid xtics ytics back ls 4\n\n"

            /* legend */
            "set key box top left spacing 1.5\n\n"

            /* plot the data separtely */
            "plot \"%s\" using 1:2 with lines ls 1 title \"Best case\"\n"
            "plot \"%s\" using 1:3 with lines ls 2 title \"Worst case\"\n"
            "plot \"%s\" using 1:4 with lines ls 3 title \"Avg case\"\n\n"

            /* plot the data on same graph */
            "plot \"%s\" using 1:2 with lines ls 1 title \"Best case\",\\\n"
            "\"%s\" using 1:3 with lines ls 2 title \"Worst case\",\\\n"
            "\"%s\" using 1:4 with lines ls 3 title \"Avg case\"\n\n"

            "set output", output, algorithm, datafile, datafile, datafile, 
                          datafile, datafile, datafile);
    fclose (stream);
    if (success) 
        return 1;
    return 0;
}

#ifndef BUFFER_SIZES
#define BUFF 1024
#define LARGE_BUFF (4 * BUFF)
#endif

/* define a reasonably large size for comparision */
#define DEF_START_SIZE 10 
#define DEF_STOP_SIZE 30000
#define DEF_STEP_SIZE 1000

int main (int argc, char **argv)
{
    int start, stop, step;
    int i, j, k, N, code = 0;
    long ns_elapsed_b, ns_elapsed_w, ns_elapsed_a;

    char cmd[LARGE_BUFF];
    char datafile[5][BUFF];
    char plot[5][BUFF];
    char script[5][BUFF];
    FILE *datafile_stream = NULL;
    extern struct algorithm algo[];
 
    if (argc == 1) {
        start = DEF_START_SIZE;
        stop = DEF_STOP_SIZE;
        step = DEF_STEP_SIZE;
    } 
    else if (argc == 4) {
        start = atoi (argv[1]);
        stop = atoi (argv[2]);
        step = atoi (argv[3]);
    }
    else {
        fprintf (stderr, "Usage: %s [START STOP STEP]\n", argv[0]);
        exit (1);
    }
    N = (stop - start) / step + 1;

    array_t *best = (array_t *) xmalloc (sizeof (array_t) * N);
    array_t *worst = (array_t *) xmalloc (sizeof (array_t) * N);
    array_t *average = (array_t *) xmalloc (sizeof (array_t) * N);

    /* 1. generate inputs */
    for (i = 0, j = start; i < N; i++, j += step) {
        best[i].count = j;
        worst[i].count = j;
        average[i].count = j;

        best[i].ptr = (int *) xmalloc (sizeof (int) * j);
        worst[i].ptr = (int *) xmalloc (2 * sizeof (int) * j);
        average[i].ptr = (int *) xmalloc (2 * sizeof (int) * j);

        for (k = 0; k < j; k++) {
            best[i].ptr[k] = k + 1;
            worst[i].ptr[k] 
                = worst[i].ptr[k + worst[i].count] = j - k;
            average[i].ptr[k] 
                = average[i].ptr[k + average[i].count] = randint (1, j);
        }
    }

    /* generate date and script to plot that data */
    for (i = 0; i < 5; i++) { /* for every algorithm */

        /* create datafile with unique name for that sort type */
        snprintf (datafile[i], BUFF, "data%c.txt", algo[i].name[0]);
        datafile_stream = fopen (datafile[i], "w"); 
        if (datafile_stream == NULL) {
            perror ("fopen");
            code = 2;
            goto free_and_exit;
        }

        printf ("%s: analysing %s...\n", argv[0], algo[i].name);

        /* 2. time and write timing data to file */
        fprintf (datafile_stream, "# Analysis of %s\n", algo[i].name);
        fprintf (datafile_stream, "# %11s %11s %11s %11s\n",
                 "Inputs-size", "Best-case", "Worst-case", "Average-case");
        for (j = 0; j < N; j++) { /* for every case */
            ns_elapsed_b 
                = time_sort (algo[i].sort, best[j].ptr, best[j].count);

            ns_elapsed_w 
                = time_sort (algo[i].sort, worst[j].ptr, worst[j].count);
            arr_restore (worst[j].ptr, worst[j].count);

            ns_elapsed_a 
                = time_sort (algo[i].sort, average[j].ptr, average[j].count);
            arr_restore (average[j].ptr, average[j].count);

            fprintf (datafile_stream, "%11d %11ld %11ld %11ld\n",
                    best[j].count, ns_elapsed_b, ns_elapsed_w, ns_elapsed_a);
        }
        fclose (datafile_stream);

        printf ("%s: data has been written to %s\n", argv[0], datafile[i]);

        /* 3. generate gnuplot script for that datafile */
        if (genscript (algo[i].name, datafile[i], script[i], plot[i],
                   BUFF)) {
            printf ("%s: gnuplot script has been written to %s\n\n",
                    argv[0], script[i]);
        }
        else {
            fprintf (stderr, "%s: could not create script.\n", argv[0]);
        }
    }

    printf ("Executing scripts...\n");

    /* 4. run the generated scripts */
    for (i = 0; i < 5; i++) {
        snprintf (cmd, LARGE_BUFF, "gnuplot ./%s", script[i]);
        switch (system (cmd)) {
            case 0: /* success */
                printf ("%s: plot for %s has been generated as: %s\n",
                        argv[0], algo[i].name, plot[i]);
                break;

            case -1: /* child process could not be created */
                perror (argv[0]);
                break;

            default: 
                fprintf (stderr, "%s: %s failed to execute\n", argv[0], 
                        script[0]);
                break;
        }
    }

free_and_exit:
    /* free the memory associated with the arrays */
    for (i = 0; i < N; i++) {
        free (best[i].ptr);
        free (worst[i].ptr);
        free (average[i].ptr);
    }
    free (best);
    free (worst);
    free (average);
    printf ("Memory successfully deallocated. Exiting process.\n");
    exit (code);
}