/*----------------------------------------------------------------------------*/
/* Main Program to Test and Time Sequential and Multithreaded Quicksort       */
/*                                                                            */
/* Written by: John Thornley, Computer Science Dept., Caltech.                */
/* Date: October, 1997.                                                       */
/*                                                                            */
/* Usage: COMMAND -test -seq                                                  */
/*        COMMAND -test -multi                                                */
/*        COMMAND -time -seq n seed trials                                    */
/*        COMMAND -time -breaks -seq n seed trials                            */
/*        COMMAND -time -multi n t p seed trials                              */
/*        COMMAND -time -breaks -multi n t p seed trials                      */
/* where: n       = number of data items (>= 0)                               */
/*        t       = number of threads (>= 1)                      */
/*        p       = number of processors (>= 1)                               */
/*        seed    = seed for random generation of data items                  */
/*        trials  = number of timing trials (>= 1)                            */
/*                                                                            */
/* Copyright (c) 1997 by John Thornley.                                       */
/*----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <bool.h>
#include <timing.h>
#include <multiprocessing.h>
#include "quicksort.h"

/*----------------------------------------------------------------------------*/
/* Constants                                                                  */
/*----------------------------------------------------------------------------*/

static const item *no_items;
static const item one_item[] = {1};
static const item two_equal[] = {1, 1};
static const item two_ascending[] = {0, 1};
static const item two_descending[] = {1, 0};
static const item nine_equal[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
static const item nine_ascending[] = {0, 0, 1, 1, 2, 3, 3, 4, 4};
static const item nine_descending[] = {4, 4, 3, 3, 2, 1, 1, 0, 0};
static const item nine_random[] = {3, 2, 4, 0, 3, 1, 4, 0, 1};
static const item twenty_equal[] = 
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
static const item twenty_ascending[] =
    {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4};
static const item twenty_descending[] =
    {4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0};
static const item twenty_random[] =
    {1, 3, 4, 4, 1, 1, 0, 3, 0, 4, 2, 2, 0, 3, 2, 0, 2, 1, 4, 3};
static const item one_hundred_equal[] =
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
static const item one_hundred_ascending[] =
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9};
static const item one_hundred_descending[] =
    {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
static const item one_hundred_random[] =
    {3, 5, 1, 4, 9, 4, 3, 2, 4, 1, 0, 1, 7, 0, 9, 6, 3, 8, 0, 2,
     0, 6, 9, 2, 6, 7, 8, 5, 6, 5, 3, 5, 4, 9, 4, 5, 2, 7, 6, 9,
     2, 9, 5, 8, 1, 5, 6, 5, 9, 6, 7, 2, 8, 6, 7, 7, 9, 6, 3, 8,
     1, 0, 6, 7, 3, 2, 9, 4, 3, 4, 9, 0, 3, 5, 8, 2, 4, 8, 7, 0,
     8, 1, 3, 0, 1, 1, 7, 8, 2, 0, 4, 8, 1, 2, 7, 3, 0, 1, 5, 4};

/*----------------------------------------------------------------------------*/
/* Miscelleanous array functions                                              */
/*----------------------------------------------------------------------------*/

static void print_items(int n, const item items[])
{
    int i;

    assert(n >= 0);

    printf("{");
    if (n > 0) printf("%i", items[0]);
    for (i = 1; i < n; i++) printf(", %i", items[i]);
    printf("}");
}

/*----------------------------------------------------------------------------*/

static bool equal_items(int n, const item left[], const item right[])
{
    bool equal;
    int i;

    assert(n >= 0);

    equal = true;
    for (i = 0; equal && i < n; i++)
        equal = (left[i] == right[i]);
    return equal;
}

/*----------------------------------------------------------------------------*/
/* Test sequential quicksort                                                  */
/*----------------------------------------------------------------------------*/

static void test_seq(
        const char message[], int n,
        const item unsorted[], const item expected[],
        bool *passed)
{
    item *data;
    int i;

    assert(n >= 0);

    data = (item *) malloc(n*sizeof(item));
    for (i = 0; i < n; i++) data[i] = unsorted[i];
    printf("Sorting %s:\n", message);
    printf("Unsorted items = "); 
    print_items(n, data); printf("\n");
    seq_quicksort(n, data);
    printf("Sorted items   = ");
    print_items(n, data); printf("\n");
    if (equal_items(n, data, expected)) {
        *passed = true;
        printf("Passed test\n");
    } else {
        *passed = false;
        printf("Expected       = ");
        print_items(n, expected); printf("\n");
        printf(">>>>> FAILED TEST <<<<<\n");
    }
    printf("\n");
    free(data);
}

/*----------------------------------------------------------------------------*/

static void test_seq_quicksort(void)
{
    bool passed, passed_all;

    printf("TESTING SEQUENTIAL QUICKSORT\n");
    printf("\n");

    passed_all = true;

    test_seq("no items", 0, 
        no_items, no_items, &passed);
    passed_all = passed_all && passed;

    test_seq("one item", 1, 
        one_item, one_item, &passed);
    passed_all = passed_all && passed;

    test_seq("two equal items", 2, 
        two_equal, two_equal, &passed);
    passed_all = passed_all && passed;

    test_seq("two ascending items", 2,
        two_ascending, two_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("two descending items", 2, 
        two_descending, two_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("nine equal items", 9, 
        nine_equal, nine_equal, &passed);
    passed_all = passed_all && passed;

    test_seq("nine ascending items", 9, 
        nine_ascending, nine_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("nine descending items", 9, 
        nine_descending, nine_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("nine random items", 9, 
        nine_random, nine_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("twenty equal items", 20, 
        twenty_equal, twenty_equal, &passed);
    passed_all = passed_all && passed;

    test_seq("twenty ascending items", 20, 
        twenty_ascending, twenty_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("twenty descending items", 20, 
        twenty_descending, twenty_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("twenty random items", 20,
        twenty_random, twenty_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("one hundred equal items", 100, 
        one_hundred_equal, one_hundred_equal, &passed);
    passed_all = passed_all && passed;

    test_seq("one hundred ascending items", 100, 
        one_hundred_ascending, one_hundred_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("one hundred descending items", 100, 
        one_hundred_descending, one_hundred_ascending, &passed);
    passed_all = passed_all && passed;

    test_seq("one hundred random items", 100,
        one_hundred_random, one_hundred_ascending, &passed);
    passed_all = passed_all && passed;

    if (passed_all)
        printf("PASSED ALL TESTS.\n");
    else
        printf("FAILED SOME TESTS.\n");
}

/*----------------------------------------------------------------------------*/
/* Test multithreaded quicksort                                               */
/*----------------------------------------------------------------------------*/

static void test_multi(
        const char message[], int n,
        const item unsorted[], const item expected[],
        bool *passed)
{
    item *data;
    int i, t;

    assert(n >= 0);

    data = (item *) malloc(n*sizeof(item));
    *passed = true;
    for (t = 1; t <= n + 1; t = (t < 4 ? t + 1 : 2*t)) {
        for (i = 0; i < n; i++) data[i] = unsorted[i];
        printf("Sorting %s (t = %i):\n", message, t);
        printf("Unsorted items = "); 
        print_items(n, data); printf("\n");
        multi_quicksort(n, data, t);
        printf("Sorted items   = ");
        print_items(n, data); printf("\n");
        if (equal_items(n, data, expected))
            printf("Passed test\n");
        else {
            *passed = false;
            printf("Expected       = ");
            print_items(n, expected); printf("\n");
            printf(">>>>> FAILED TEST <<<<<\n");
        }
        printf("\n");
    }
    free(data);
}

/*----------------------------------------------------------------------------*/

static void test_multi_quicksort(void)
{
    bool passed, passed_all;

    printf("TESTING MULTITHREADED QUICKSORT\n");
    printf("\n");

    passed_all = true;

    test_multi("no items", 0,
        no_items, no_items, &passed);
    passed_all = passed_all && passed;

    test_multi("one item", 1,
        one_item, one_item, &passed);
    passed_all = passed_all && passed;

    test_multi("two equal items", 2, 
        two_equal, two_equal, &passed);
    passed_all = passed_all && passed;

    test_multi("two ascending items", 2,
        two_ascending, two_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("two descending items", 2, 
        two_descending, two_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("nine equal items", 9, 
        nine_equal, nine_equal, &passed);
    passed_all = passed_all && passed;

    test_multi("nine ascending items", 9, 
        nine_ascending, nine_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("nine descending items", 9, 
        nine_descending, nine_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("nine random items", 9, 
        nine_random, nine_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("twenty equal items", 20, 
        twenty_equal, twenty_equal, &passed);
    passed_all = passed_all && passed;

    test_multi("twenty ascending items", 20, 
        twenty_ascending, twenty_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("twenty descending items", 20, 
        twenty_descending, twenty_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("twenty random items", 20,
        twenty_random, twenty_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("one hundred equal items", 100, 
        one_hundred_equal, one_hundred_equal, &passed);
    passed_all = passed_all && passed;

    test_multi("one hundred ascending items", 100, 
        one_hundred_ascending, one_hundred_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("one hundred descending items", 100, 
        one_hundred_descending, one_hundred_ascending, &passed);
    passed_all = passed_all && passed;

    test_multi("one hundred random items", 100,
        one_hundred_random, one_hundred_ascending, &passed);
    passed_all = passed_all && passed;

    if (passed_all)
        printf("PASSED ALL TESTS.\n");
    else
        printf("FAILED SOME TESTS.\n");
}

/*----------------------------------------------------------------------------*/
/* Miscellaneous functions used in timing                                     */
/*----------------------------------------------------------------------------*/

static void print_current_time(void)
{
    time_t calendar_time;

    calendar_time = time(NULL);
    printf("%s", asctime(localtime(&calendar_time)));
}

/*----------------------------------------------------------------------------*/

static void sort(int n, double data[])
{
    int i, j, k;
    double temp;

    assert(n >= 0);

    for (i = 1; i < n; i++) {
        temp = data[i];
        k = 0;
        for (j = i - 1; j >= 0; j--)
            if (temp < data[j])
                data[j + 1] = data[j];
            else {
                k = j + 1;
                break;
            }
        data[k] = temp;
    }
}

/*----------------------------------------------------------------------------*/
/* Time sequential quicksort                                                  */
/*----------------------------------------------------------------------------*/

static void time_seq_quicksort(
        bool breaks, int n, int seed, int trials)
{
    item *data;
    int trial;
    int i;
    double *elapsed;
    int quarter;
    double total;

    assert(n >= 0);
    assert(trials >= 1);

    data = (item *) malloc(n*sizeof(item));
    elapsed = (double *) malloc(trials*sizeof(double));
    printf("TIMING SEQUENTIAL QUICKSORT ");
    printf("(N = %i, SEED = %i)\n", n, seed);
    print_current_time();
    for (trial = 0; trial < trials; trial++) {
        srand(seed);
        for (i = 0; i < n; i++) data[i] = rand();
        clear_processor_caches();
        if (breaks) {
            printf("Starting trial %i (press Enter to continue) ...", trial);
            getchar();
        }
        start_timing();
        seq_quicksort(n, data);
        finish_timing(&elapsed[trial]);
        if (breaks) {
            printf("Finished trial %i (press Enter to continue) ...", trial);
            getchar();
        }
       printf("Trial %i took %.2f seconds\n", trial, elapsed[trial]);
    }
    print_current_time();
    sort(trials, elapsed);
    quarter = trials/4;
    total = 0.0;
    for (trial = quarter; trial < trials - quarter; trial++) 
        total = total + elapsed[trial];
    printf("STATISTICS FOR MEDIAN %i TRIALS:\n", trials - 2*quarter);
    printf("LOWEST = %.2f seconds, ", elapsed[quarter]);
    printf("HIGHEST = %.2f seconds, ", elapsed[trials - quarter - 1]);
    printf("AVERAGE = %.2f seconds.\n", total/(trials - 2*quarter));
    free(data);
    free(elapsed);
}

/*----------------------------------------------------------------------------*/
/* Time multithreaded quicksort                                               */
/*----------------------------------------------------------------------------*/

static void time_multi_quicksort(
        bool breaks, int n, int t, int p, int seed, int trials)
{
    item *data, *expected;
    int trial;
    int i;
    double *elapsed;
    int quarter;
    double total;

    assert(n >= 0);
    assert(t >= 1);
    assert(p >= 1);
    assert(trials >= 1);

    data = (item *) malloc(n*sizeof(item));
    elapsed = (double *) malloc(trials*sizeof(double));
    printf("TIMING MULTITHREADED QUICKSORT ");
    printf("(N = %i, T = %i, P = %i, SEED = %i)\n", n, t, p, seed);
    set_processor_usage(p);
    print_current_time();
    for (trial = 0; trial < trials; trial++) {
        srand(seed);
        for (i = 0; i < n; i++) data[i] = rand();
        clear_processor_caches();
        if (breaks) {
            printf("Starting trial %i (press Enter to continue) ...", trial);
            getchar();
        }
        start_timing();
        multi_quicksort(n, data, t);
        finish_timing(&elapsed[trial]);
        if (breaks) {
            printf("Finished trial %i (press Enter to continue) ...", trial);
            getchar();
        }
        printf("Trial %i took %.2f seconds\n", trial, elapsed[trial]);
    }
    print_current_time();
    {
        expected = (item *) malloc(n*sizeof(item));
        srand(seed);
        for (i = 0; i < n; i++) expected[i] = rand();
        seq_quicksort(n, expected);
        if (!equal_items(n, data, expected)) 
            printf(">>>>> MULTITHREADED DIFFERENT FROM SEQUENTIAL <<<<<\n");
        free(expected);
    }
    sort(trials, elapsed);
    quarter = trials/4;
    total = 0.0;
    for (trial = quarter; trial < trials - quarter; trial++) 
        total = total + elapsed[trial];
    printf("STATISTICS FOR MEDIAN %i TRIALS:\n", trials - 2*quarter);
    printf("LOWEST = %.2f seconds, ", elapsed[quarter]);
    printf("HIGHEST = %.2f seconds, ", elapsed[trials - quarter - 1]);
    printf("AVERAGE = %.2f seconds.\n", total/(trials - 2*quarter));
    free(data);
    free(elapsed);
}

/*----------------------------------------------------------------------------*/
/* Print program usage                                                        */
/*----------------------------------------------------------------------------*/

static void print_program_usage(const char command[])
{
    fprintf(stderr, "Usage: %s -test -seq\n", command);
    fprintf(stderr, "       %s -test -multi\n", command);
    fprintf(stderr, "       %s -time -seq n seed trials\n", command);
    fprintf(stderr, "       %s -time -breaks -seq n seed trials\n", command);
    fprintf(stderr, "       %s -time -multi n t p seed trials\n", command); 
    fprintf(stderr, "       %s -time -breaks -multi n t p seed trials\n", 
            command); 
    fprintf(stderr, "where: n       = number of items (>= 0)\n");
    fprintf(stderr, "       t       = number of threads (>= 1)\n");
    fprintf(stderr, "       p       = number of processors (>= 1)\n");
    fprintf(stderr, "       seed    = seed for random generation of items\n");
    fprintf(stderr, "       trials  = number of timing trials (>= 1)\n");
}

/*----------------------------------------------------------------------------*/
/* Main program                                                               */
/*----------------------------------------------------------------------------*/

void main(int argc, char *argv[])
{
    int n, t, p, seed, trials;
    bool args_ok;
    int result;

    switch (argc) {
    case 3:
        if (strcmp(argv[1], "-test") == 0 && 
            strcmp(argv[2], "-seq") == 0)
            test_seq_quicksort();
        else if (strcmp(argv[1], "-test") == 0 && 
            strcmp(argv[2], "-multi") == 0)
            test_multi_quicksort();
        else
            print_program_usage(argv[0]);
        break;
    case 6:
        if (strcmp(argv[1], "-time") == 0 && 
            strcmp(argv[2], "-seq") == 0) {
            args_ok = true;
            result = sscanf(argv[3], "%i", &n);
            args_ok = args_ok && result == 1 && n >= 0;
            result = sscanf(argv[4], "%i", &seed);
            args_ok = args_ok && result == 1;
            result = sscanf(argv[5], "%i", &trials);
            args_ok = args_ok && result == 1 && trials >= 1;
            if (args_ok)
                time_seq_quicksort(false, n, seed, trials);
            else
                print_program_usage(argv[0]);
        } else 
            print_program_usage(argv[0]);
        break;
    case 7:
        if (strcmp(argv[1], "-time") == 0 && 
            strcmp(argv[2], "-breaks") == 0 &&
            strcmp(argv[3], "-seq") == 0) {
            args_ok = true;
            result = sscanf(argv[4], "%i", &n);
            args_ok = args_ok && result == 1 && n >= 0;
            result = sscanf(argv[5], "%i", &seed);
            args_ok = args_ok && result == 1;
            result = sscanf(argv[6], "%i", &trials);
            args_ok = args_ok && result == 1 && trials >= 1;
            if (args_ok)
                time_seq_quicksort(true, n, seed, trials);
            else
                print_program_usage(argv[0]);
        } else 
            print_program_usage(argv[0]);
        break;
    case 8:
        if (strcmp(argv[1], "-time") == 0 && 
            strcmp(argv[2], "-multi") == 0) {
            args_ok = true;
            result = sscanf(argv[3], "%i", &n);
            args_ok = args_ok && result == 1 && n >= 0;
            result = sscanf(argv[4], "%i", &t);
            args_ok = args_ok && result == 1 && t >= 1;
            result = sscanf(argv[5], "%i", &p);
            args_ok = args_ok && result == 1 && p >= 1;
            result = sscanf(argv[6], "%i", &seed);
            args_ok = args_ok && result == 1;
            result = sscanf(argv[7], "%i", &trials);
            args_ok = args_ok && result == 1 && trials >= 1;
            if (args_ok)
                time_multi_quicksort(false, n, t, p, seed, trials);
            else
                print_program_usage(argv[0]);
        
        } else
            print_program_usage(argv[0]);
        break;
    case 9:
        if (strcmp(argv[1], "-time") == 0 && 
            strcmp(argv[2], "-breaks") == 0 &&
            strcmp(argv[3], "-multi") == 0) {
            args_ok = true;
            result = sscanf(argv[4], "%i", &n);
            args_ok = args_ok && result == 1 && n >= 0;
            result = sscanf(argv[5], "%i", &t);
            args_ok = args_ok && result == 1 && t >= 1;
            result = sscanf(argv[6], "%i", &p);
            args_ok = args_ok && result == 1 && p >= 1;
            result = sscanf(argv[7], "%i", &seed);
            args_ok = args_ok && result == 1;
            result = sscanf(argv[8], "%i", &trials);
            args_ok = args_ok && result == 1 && trials >= 1;
            if (args_ok)
                time_multi_quicksort(true, n, t, p, seed, trials);
            else
                print_program_usage(argv[0]);
        
        } else
            print_program_usage(argv[0]);
        break;
    default:
        print_program_usage(argv[0]);
        break;
    }

}

/*----------------------------------------------------------------------------*/