/* plot_search.c: 
   Generate plots for the searching algorithms for best, worst and avergae 
   cases */

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

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);
}

int linsearch (int *A, int begin_idx, int end_idx, int key)
{
    int i, len = end_idx - begin_idx + 1;
    for (i = 0; i < len; i++) {
        if (A[i] == key) {
            return i;
        }
    }
    return -1;
}

int binsearch (int *A, int p, int r, int key) 
{
    int q;
    if (p <= r) {
        q = p + (r - p)/2;
        if (A[q] > key) {
            return binsearch (A, p, q - 1, key);
        }
        if (A[q] < key) {
            return binsearch (A, q + 1, r, key);
        }
        if (A[q] == key) { 
            return q;
        }
    }
    return -1;
}

/* for searching algorithms, the best, average and worst case running 
   times are determined by the value of the key */
typedef struct array {
    int count;
    int *ptr;
    int best_case_key;
    int worst_case_key;
    int avg_case_key;
} input_t;

/* structure to encapsulate name, pointer and input to an algorithm */
struct algorithm {
    char name[BUFF];
    int (*search) (int *, int, int, int);
    input_t *dataset;
};

#define NANOSECONDS_PER_SECOND 1e9
long int time_search
(int (*search)(int *, int, int, int), int *arr, int len, int key, int *retval)
{
    long elapsed;
    struct timespec diff, before, after;

    clock_gettime (CLOCK_MONOTONIC, &before);
    *retval = search (arr, 0, len - 1, key);
    clock_gettime (CLOCK_MONOTONIC, &after);

    if ((after.tv_nsec - before.tv_nsec) < 0) {
        diff.tv_sec = after.tv_sec - before.tv_sec - 1;
        diff.tv_nsec = NANOSECONDS_PER_SECOND + after.tv_nsec - before.tv_nsec;
    } 
    else {
        diff.tv_sec = after.tv_sec - before.tv_sec;
        diff.tv_nsec = after.tv_nsec - before.tv_nsec;
    }
    elapsed = (diff.tv_sec * NANOSECONDS_PER_SECOND) + diff.tv_nsec;
    return elapsed;
}

/* generate the script needed to plot the file */
void genscript
(char *algorithm, char *datafile, char *scriptfile, char *output, size_t siz)
{
    snprintf (scriptfile, siz, "plot%cSearch.plt", algorithm[0]);
    snprintf (output, siz, "plot%cSearch.pdf", algorithm[0]);

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

            "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"

            "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"

            "set key box top left spacing 1.5\n\n"

            "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 \"%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);
}

/* try to alllocate, exit with error code on failure */
void *xmalloc (size_t siz, int code)
{
    void *mem = malloc (siz);
    if (mem == NULL) 
        exit (code);
    return mem;
}

#define DEF_START_SIZE 10
#define DEF_STOP_SIZE 30000
#define DEF_STEP_SIZE 1000

int main (int argc, char **argv)
{
    char cmd[LARGE_BUFF];
    char datafile[2][BUFF];
    char script[2][BUFF];
    char plot[2][BUFF];
    FILE *datafile_stream = NULL;

    struct algorithm algo[2] = {
        {"Linear Search", linsearch, NULL},
        {"Binary Search", binsearch, NULL}
    };

    int start = 10, stop = 15, step = 1;
    long ns_elapsed_b, ns_elapsed_w, ns_elapsed_a;
    int i, j, k, *tmp_arr, mid, tmp_val, N, code = 0;

    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;
    algo[0].dataset = (input_t *) xmalloc (sizeof (input_t) * N, 2);
    algo[1].dataset = (input_t *) xmalloc (sizeof (input_t) * N, 2);

    /* 1. generate the inputs (dataset) */
    for (i = 0, j = start; i < N; i++, j += step) {

        /* both algorithms use the same dataset to search for key */
        algo[0].dataset[i].count = j;
        algo[1].dataset[i].count = j;

        tmp_arr = (int *) xmalloc (sizeof (int) * j, 2); 
        for (k = 0; k < j; k++) {
            tmp_arr[k] = k + 1;
        }

        algo[0].dataset[i].ptr = tmp_arr;
        algo[1].dataset[i].ptr = tmp_arr;

        /* generate appropriate keys to search for in the above datasets */
        mid = 1 + (j - 1)/2;
        algo[0].dataset[i].best_case_key = 1;    /* best case */
        algo[1].dataset[i].best_case_key = mid;

        algo[0].dataset[i].worst_case_key = j;   /* worst case */
        algo[1].dataset[i].worst_case_key = j;
        
        algo[0].dataset[i].avg_case_key = mid;   /* average case */
        if (randint (0,1)) {                     
            /* if 1 get random number in lower half */
            algo[1].dataset[i].avg_case_key = randint (2, mid - 1); 
        }
        else { /* get random int from upper half */
            algo[1].dataset[i].avg_case_key = randint (mid + 1, j-1); 
        }
    }

    for (i = 0; i < 2; i++) {
        snprintf (datafile[i], BUFF, "data%csearch.txt", algo[i].name[0]);
        datafile_stream = fopen (datafile[i], "w");
        if (datafile_stream == NULL) {
            perror ("fopen");
            code = 2;
            goto free_and_exit;
        }

        /* 2. feed theis data to the searching functions and time */
        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_search (algo[i].search, algo[i].dataset[j].ptr,
                               algo[i].dataset[j].count,
                               algo[i].dataset[j].best_case_key, &tmp_val);
            ns_elapsed_w
                = time_search (algo[i].search, algo[i].dataset[j].ptr,
                               algo[i].dataset[j].count,
                               algo[i].dataset[j].worst_case_key, &tmp_val);
            ns_elapsed_a
                = time_search (algo[i].search, algo[i].dataset[j].ptr,
                               algo[i].dataset[j].count,
                               algo[i].dataset[j].avg_case_key, &tmp_val);
            fprintf (datafile_stream, "%11d %11ld %11ld %11ld\n",
                     algo[i].dataset[j].count, ns_elapsed_b, ns_elapsed_w,
                     ns_elapsed_a);
        }
        fclose (datafile_stream);

        /* 3. generate the plotting script */
        genscript (algo[i].name, datafile[i], script[i], plot[i], BUFF);
        printf ("%s: script has been writtent to %s.\n", argv[0], script[i]);
        putchar ('\n');
    }

    /* 4. run the script to create the plots */
    printf ("Executing scripts...\n");
    for (i = 0; i < 2; 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]);
                code = 3;
                break;

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

free_and_exit:
    for (i = 0; i < N; i++) {
        free (algo[0].dataset[i].ptr);
    }
    free (algo[0].dataset);
    free (algo[1].dataset);
    exit (code);
}