/**
 * benchmark.c
 *
 * Creation Date: 13/04/2019
 *
 * Authors:
 * Leonardo Vencovsky (https://github.com/LeoVen)
 *
 * Benchmarks:
 * - Input
 * - Search
 * - Iteration
 * - Output
 */
#include <assert.h>
#include <inttypes.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>

#include "util/twister.c"

#include "cmc/cor/hashtable.h"
#include "cmc/cor/heap.h"
#include "cmc/utl/foreach.h"
#include "cmc/utl/futils.h"
#include "cmc/utl/timer.h"

#define NTOTAL UINT64_C(10000000)
#define NMIN UINT64_C(100)

// Percentage % macro
#define PC(x) x * 100.0

size_t randsize(size_t min, size_t max, mt_state_ptr st)
{
    return (size_t)floor(twist_real(st) * ((double)max - (double)min + 1.0) + (double)min);
}

void shuffle(int *array, mt_state_ptr st)
{
    for (size_t i = 0; i < NTOTAL; i++)
    {
        size_t j = randsize(0, NTOTAL - 1, st);
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }
}

struct
{
    CMC_DEF_FTAB_CMP(size_t);
    CMC_DEF_FTAB_CPY(size_t);
    CMC_DEF_FTAB_STR(size_t);
    CMC_DEF_FTAB_FREE(size_t);
    CMC_DEF_FTAB_HASH(size_t);
    CMC_DEF_FTAB_PRI(size_t);
} int_ftab = { cmc_size_cmp, NULL, cmc_size_str, NULL, cmc_size_hash, cmc_size_cmp };

#define CMC_ARGS_FALLTHROUGH
#define V int
#define K int
#define CMC_EXT_ITER

#define SNAME bitset
#define PFX bs
#include "cmc/bitset.h"
#define SNAME deque
#define PFX d
#include "cmc/deque.h"
#define SNAME hashbidimap
#define PFX hbm
#include "cmc/hashbidimap.h"
#define SNAME hashmap
#define PFX hm
#include "cmc/hashmap.h"
#define SNAME hashmultimap
#define PFX hmm
#include "cmc/hashmultimap.h"
#define SNAME hashmultiset
#define PFX hms
#include "cmc/hashmultiset.h"
#define SNAME hashset
#define PFX hs
#include "cmc/hashset.h"
#define SNAME heap
#define PFX h
#include "cmc/heap.h"
#define SNAME intervalheap
#define PFX ih
#include "cmc/intervalheap.h"
#define SNAME linkedlist
#define PFX ll
#include "cmc/linkedlist.h"
#define SNAME list
#define PFX l
#include "cmc/list.h"
#define SNAME queue
#define PFX q
#include "cmc/queue.h"
#define SNAME sortedlist
#define PFX sl
#include "cmc/sortedlist.h"
#define SNAME stack
#define PFX s
#include "cmc/stack.h"
#define SNAME treemap
#define PFX tm
#include "cmc/treemap.h"
#define SNAME treeset
#define PFX ts
#include "cmc/treeset.h"

#undef CMC_ARGS_FALLTHROUGH
#include "cmc/cor/undef.h"

#define BENCHMARK(NAME, PFX, SNAME, initfunc, insertbody, removebody, searchbody) \
    void NAME##_io_benchmark(int *array, int *sarray, size_t s) \
    { \
        printf("+------------------------------------------------------------ %10s\n", #NAME); \
        printf("+------------------------------------------------------------ \n"); \
        struct cmc_timer timer, total; \
        CMC_UNUSED int r; \
\
        struct SNAME *coll = initfunc; \
\
        cmc_timer_start(total); \
        cmc_timer_start(timer); \
\
        for (size_t i = 0; i < NTOTAL; i++) \
        { \
            insertbody; \
        } \
\
        cmc_timer_stop(timer); \
\
        size_t s1 = PFX##_count(coll); \
\
        printf("    INPUT %10s TOOK %8.0lf milliseconds for %8" PRIuMAX " elements\n", #NAME, timer.result, s1); \
\
        double input_time = timer.result; \
\
        cmc_timer_start(timer); \
\
        for (size_t i = 0; i < s; i++) \
        { \
            searchbody; \
        } \
\
        cmc_timer_stop(timer); \
\
        printf("   SEARCH %10s TOOK %8.0lf milliseconds for %8" PRIuMAX " elements\n", #NAME, timer.result, s); \
\
        double search_time = timer.result; \
\
        cmc_timer_start(timer); \
\
        CMC_FOREACH (PFX, SNAME, iter, coll) \
        { \
        } \
\
        cmc_timer_stop(timer); \
\
        printf("ITERATION %10s TOOK %8.0lf milliseconds for %8" PRIuMAX " elements\n", #NAME, timer.result, s1); \
\
        double iter_time = timer.result; \
\
        cmc_timer_start(timer); \
\
        for (size_t i = 0; i < NTOTAL; i++) \
        { \
            removebody; \
        } \
\
        cmc_timer_stop(timer); \
\
        size_t s2 = PFX##_count(coll); \
\
        printf("   OUTPUT %10s TOOK %8.0lf milliseconds for %8" PRIuMAX " elements\n", #NAME, timer.result, s1); \
\
        double output_time = timer.result; \
\
        cmc_timer_stop(total); \
\
        PFX##_free(coll); \
\
        double adj_search_time = (total.result - search_time) + (search_time * (double)NTOTAL) / (double)s; \
        double no_search = input_time + iter_time + output_time; \
\
        printf("+------------------------------------------------------------ \n"); \
        printf("TOTAL TIME    : %.0lf milliseconds\n", total.result); \
        printf("ADJUSTED TIME : %.0lf milliseconds\n", adj_search_time); \
\
        printf("+------------------------------------------------------------ \n"); \
        printf("    INPUT : %5.2lf%% (%5.2f%%)\n", PC(input_time / total.result), PC(input_time / no_search)); \
        printf("   SEARCH : %5.2lf%%\n", PC(search_time / total.result)); \
        printf("ITERATION : %5.2lf%% (%5.2f%%)\n", PC(iter_time / total.result), PC(iter_time / no_search)); \
        printf("   OUTPUT : %5.2lf%% (%5.2f%%)\n", PC(output_time / total.result), PC(output_time / no_search)); \
        printf("+------------------------------------------------------------ \n"); \
\
        assert(s1 == NTOTAL && s2 == 0); \
\
        printf("+------------------------------------------------------------ %10s\n\n", #NAME); \
    }

BENCHMARK(DEQUE, d, deque, d_new(NTOTAL, (struct deque_fval *)&int_ftab), d_push_back(coll, array[i]), d_pop_back(coll),
          d_contains(coll, sarray[i]))
BENCHMARK(HASHMAP, hm, hashmap, hm_new(NTOTAL, 0.6, (struct hashmap_fkey *)&int_ftab, (struct hashmap_fval *)&int_ftab),
          hm_insert(coll, array[i], array[i]), hm_remove(coll, array[i], &r), hm_contains(coll, sarray[i]))
BENCHMARK(HASHSET, hs, hashset, hs_new(NTOTAL, 0.6, (struct hashset_fval *)&int_ftab), hs_insert(coll, array[i]),
          hs_remove(coll, array[i]), hs_contains(coll, sarray[i]))
BENCHMARK(HEAP, h, heap, h_new(NTOTAL, CMC_MIN_HEAP, (struct heap_fval *)&int_ftab), h_insert(coll, array[i]),
          h_remove(coll), h_contains(coll, sarray[i]))
BENCHMARK(LINKEDLIST, ll, linkedlist, ll_new((struct linkedlist_fval *)&int_ftab), ll_push_back(coll, array[i]),
          ll_pop_back(coll), ll_contains(coll, sarray[i]))
BENCHMARK(LIST, l, list, l_new(NTOTAL, (struct list_fval *)&int_ftab), l_push_back(coll, array[i]), l_pop_back(coll),
          l_contains(coll, sarray[i]))
BENCHMARK(QUEUE, q, queue, q_new(NTOTAL, (struct queue_fval *)&int_ftab), q_enqueue(coll, array[i]), q_dequeue(coll),
          q_contains(coll, sarray[i]))
BENCHMARK(STACK, s, stack, s_new(NTOTAL, (struct stack_fval *)&int_ftab), s_push(coll, array[i]), s_pop(coll),
          s_contains(coll, sarray[i]))
BENCHMARK(TREEMAP, tm, treemap, tm_new((struct treemap_fkey *)&int_ftab, (struct treemap_fval *)&int_ftab),
          tm_insert(coll, array[i], array[i]), tm_remove(coll, array[i], &r), tm_contains(coll, sarray[i]))
BENCHMARK(TREESET, ts, treeset, ts_new((struct treeset_fval *)&int_ftab), ts_insert(coll, array[i]),
          ts_remove(coll, array[i]), ts_contains(coll, sarray[i]))

BENCHMARK(INTERVALHEAP, ih, intervalheap, ih_new(NTOTAL, (struct intervalheap_fval *)&int_ftab),
          ih_insert(coll, array[i]), ih_remove_max(coll), ih_contains(coll, sarray[i]))
BENCHMARK(MULTIMAP, hmm, hashmultimap,
          hmm_new(NTOTAL, 0.8, (struct hashmultimap_fkey *)&int_ftab, (struct hashmultimap_fval *)&int_ftab),
          hmm_insert(coll, array[i], array[i]), hmm_remove(coll, array[i], &r), hmm_contains(coll, sarray[i]))
BENCHMARK(MULTISET, hms, hashmultiset, hms_new(NTOTAL, 0.6, (struct hashmultiset_fval *)&int_ftab),
          hms_insert(coll, array[i]), hms_remove(coll, array[i]), hms_contains(coll, sarray[i]))

int main(void)
{
    // Using the Mersenne Twister to generate random numbers. This seed
    // guarantees that everytime this program runs it will generate the same
    // random numbers. The random numbers influence on the shuffling of the
    // array.
    mt_state st;
    twist_init(&st, UINT64_C(12604951237));

    int *array = malloc(NTOTAL * sizeof(int));
    int *sarray = malloc(NTOTAL * sizeof(int));

    if (!array)
    {
        printf("Allocation failed\n");
        return 1;
    }

    for (int i = -5000000; i < 5000000; i++)
        array[i + 5000000] = i;

    shuffle(array, &st);

    memcpy(sarray, array, NTOTAL * sizeof(int));

    shuffle(sarray, &st);

    printf("\nNote: Adjusted Time refers to if the container had done a search over all %" PRIuMAX " elements.\n\n",
           NTOTAL);

    // Linear containers have to search for NMIN elements and non-linear (hash
    // and tree) have to search for all elements.
    struct cmc_timer timer;
    cmc_timer_start(timer);

    DEQUE_io_benchmark(array, sarray, NMIN);
    HASHMAP_io_benchmark(array, sarray, NTOTAL);
    HASHSET_io_benchmark(array, sarray, NTOTAL);
    HEAP_io_benchmark(array, sarray, NMIN);
    LINKEDLIST_io_benchmark(array, sarray, NMIN);
    LIST_io_benchmark(array, sarray, NMIN);
    QUEUE_io_benchmark(array, sarray, NMIN);
    STACK_io_benchmark(array, sarray, NMIN);
    TREEMAP_io_benchmark(array, sarray, NTOTAL);
    TREESET_io_benchmark(array, sarray, NTOTAL);

    //     INTERVALHEAP_io_benchmark(array, array, NMIN);
    //     MULTIMAP_io_benchmark(array, array, NTOTAL);
    //     MULTISET_io_benchmark(array, array, NTOTAL);

    cmc_timer_stop(timer);

    printf("+-----------------------------------------------------------+ \n");
    printf("| Total Benchmark Running Time : %12.0lf seconds       | \n", timer.result / 1000);
    printf("+-----------------------------------------------------------+ \n");

    free(array);
    free(sarray);

    return 0;
}