#include <iostream>
#include <random>
#include <cstring>
#include <ctime>
#include <algorithm>
#include "mqsort.h"

template<typename T>
int compr(const void *a, const void *b) {
  T aa = *(T *) a;
  T bb = *(T *) b;
  if (aa > bb)
    return 1;
  if (aa < bb)
    return -1;
  return 0;
}

template<typename T>
void genInt(void *base, size_t num) {
  std::random_device r;
  std::mt19937_64 e(r());
  std::uniform_int_distribution<T> unifrom_dist(0, (T) 1 << (sizeof(T) * 8 - 2));
  T *res = (T *) base;
  for (size_t i = 0; i < num; ++i)
    res[i] = unifrom_dist(e);
}

template<typename T>
void genFloat(void *base, size_t num) {
  std::random_device r;
  std::mt19937_64 e(r());
  std::uniform_real_distribution<T> unifrom_dist(0, 1);
  T *res = (T *) base;
  for (size_t i = 0; i < num; ++i)
    res[i] = unifrom_dist(e);
}

template<typename T>
void gen(void *base, size_t num) {
  genInt<T>(base, num);
}

template<>
void gen<float>(void *base, size_t num) {
  genFloat<float>(base, num);
}

template<>
void gen<double>(void *base, size_t num) {
  genFloat<double>(base, num);
}

int compeq(uint32_t *a, uint32_t *b, size_t size) {
  for (size_t i = 0; i < size; ++i)
    if (a[i] != b[i])
      return 1;
  return 0;
}

template<typename T>
void runAndTest(size_t num, size_t it) {
  clock_t tst;
  clock_t tmd;
  clock_t ted;
  std::vector<clock_t> mine, stnd;
  size_t size = sizeof(T);
  void *base = malloc(num * size);
  void *base2 = malloc(num * size);
  for (size_t t = 0; t < it; ++t) {
    gen<T>(base, num);
    memcpy(base2, base, num * size);
    tst = clock();
    mqsort(base, num, size, compr<T>);
    tmd = clock();
    qsort(base2, num, size, compr<T>);
    ted = clock();
    if (compeq((uint32_t *) base, (uint32_t *) base2, num * size / 4)) {
      std::cout << "Not equal" << std::endl;
      return;
    }
    mine.push_back(tmd - tst);
    stnd.push_back(ted - tmd);
  }
  free(base);
  free(base2);
  std::sort(mine.begin(), mine.end());
  std::sort(stnd.begin(), stnd.end());
  double m = 0, s = 0;
  for (auto itt = mine.begin(); itt < mine.end(); ++itt)
    m += *itt;
  for (auto itt = stnd.begin(); itt < stnd.end(); ++itt)
    s += *itt;
  std::cout << "Average time taken for me  (s): " << m / CLOCKS_PER_SEC / it << std::endl;
  std::cout << "Average time taken for std (s): " << s / CLOCKS_PER_SEC / it << std::endl;
  std::cout << "Speedup over std : " << s / m << std::endl;
  if (it & 1) {
    m = mine[it >> 1];
    s = stnd[it >> 1];
  } else {
    m = mine[it >> 1];
    m += mine[(it >> 1) - 1];
    m /= 2;
    s = stnd[it >> 1];
    s += stnd[(it >> 1) - 1];
    s /= 2;
  }
  std::cout << "Median time taken for me  (s): " << m / CLOCKS_PER_SEC << std::endl;
  std::cout << "Median time taken for std (s): " << s / CLOCKS_PER_SEC << std::endl;
  std::cout << "Speedup over std : " << s / m << std::endl;
}

void usage() {
  std::cout << "Usage: <this> [TYPE] [LENGTH]" << std::endl;
  std::cout << "    [TYPE]" << std::endl;
  std::cout << "          c : char(int8)" << std::endl;
  std::cout << "          s : short(int16)" << std::endl;
  std::cout << "          i : int" << std::endl;
  std::cout << "          l : long" << std::endl;
  std::cout << "          f : float" << std::endl;
  std::cout << "          d : double" << std::endl;
  std::cout << "    [LENGTH]" << std::endl;
  std::cout << "          An int specify the number of elements in the list to be sorted" << std::endl;
  std::cout << "    [ITERATIONS]" << std::endl;
  std::cout << "          An int specify the number of iterations of test" << std::endl;
}

int main(int argc, char **argv) {
  if (argc < 4) {
    usage();
    return -1;
  }
  size_t num;
  size_t it;
  try {
    num = (size_t) std::stoi(argv[2]);
    if (num > 10000000)
      std::cout << "The [LENGTH] seems to be too large" << std::endl;
    it = (size_t) std::stoi(argv[3]);
    if (it > 10000000)
      std::cout << "The [ITERATIONS] seems to be too large" << std::endl;
  } catch (std::exception &e) {
    std::cout << e.what() << std::endl;
    usage();
    return -1;
  }
  switch (argv[1][0]) {
    case 'c':
      std::cout<<num<<" Char for "<<it<<" Iterations"<<std::endl;
      runAndTest<int8_t>(num, it);
      break;
    case 's':
      std::cout<<num<<" Short for "<<it<<" Iterations"<<std::endl;
      runAndTest<int16_t>(num, it);
      break;
    case 'i':
      std::cout<<num<<" Int for "<<it<<" Iterations"<<std::endl;
      runAndTest<int>(num, it);
      break;
    case 'l':
      std::cout<<num<<" Long for "<<it<<" Iterations"<<std::endl;
      runAndTest<long>(num, it);
      break;
    case 'f':
      std::cout<<num<<" Float for "<<it<<" Iterations"<<std::endl;
      runAndTest<float>(num, it);
      break;
    case 'd':
      std::cout<<num<<" Double for "<<it<<" Iterations"<<std::endl;
      runAndTest<double>(num, it);
      break;
    default:
      usage();
      return -1;
  }
  return 0;
}