// g++ -O3  -march=native -std=c++11 -o pointersort pointersort.cpp -I .
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <string.h>
#include <numeric>
#include <vector>
#include <algorithm>
#include <string>
#include <timsort.hpp>

#define RDTSC_START(cycles)                                                    \
  do {                                                                         \
    unsigned cyc_high, cyc_low;                                                \
    __asm volatile("cpuid\n\t"                                                 \
                   "rdtsc\n\t"                                                 \
                   "mov %%edx, %0\n\t"                                         \
                   "mov %%eax, %1\n\t"                                         \
                   : "=r"(cyc_high), "=r"(cyc_low)::"%rax", "%rbx", "%rcx",    \
                     "%rdx");                                                  \
    (cycles) = ((uint64_t)cyc_high << 32) | cyc_low;                           \
  } while (0)

#define RDTSC_FINAL(cycles)                                                    \
  do {                                                                         \
    unsigned cyc_high, cyc_low;                                                \
    __asm volatile("rdtscp\n\t"                                                \
                   "mov %%edx, %0\n\t"                                         \
                   "mov %%eax, %1\n\t"                                         \
                   "cpuid\n\t"                                                 \
                   : "=r"(cyc_high), "=r"(cyc_low)::"%rax", "%rbx", "%rcx",    \
                     "%rdx");                                                  \
    (cycles) = ((uint64_t)cyc_high << 32) | cyc_low;                           \
  } while (0)

/*
 * Prints the best number of operations per cycle where
 * test is the function call, answer is the expected answer generated by
 * test, repeat is the number of times we should repeat and size is the
 * number of operations represented by test.
 */
#define BEST_TIME(test, pre, repeat, size)                                     \
  do {                                                                         \
    printf("%40s [%40s]: ", #test, #pre);                                      \
    fflush(NULL);                                                              \
    uint64_t cycles_start, cycles_final, cycles_diff;                          \
    uint64_t min_diff = (uint64_t)-1;                                          \
    for (int i = 0; i < repeat; i++) {                                         \
      pre;                                                                     \
      __asm volatile("" ::: /* pretend to clobber */ "memory");                \
      RDTSC_START(cycles_start);                                               \
      test;                                                                    \
      RDTSC_FINAL(cycles_final);                                               \
      cycles_diff = (cycles_final - cycles_start);                             \
      if (cycles_diff < min_diff)                                              \
        min_diff = cycles_diff;                                                \
    }                                                                          \
    uint64_t S = size;                                                         \
    float cycle_per_op = (min_diff) / (double)S;                               \
    printf(" %.2f cycles per element", cycle_per_op);                          \
    printf("\n");                                                              \
    fflush(NULL);                                                              \
  } while (0)

#define BEST_TIME_COND(test, expected, pre, repeat, size)                      \
  do {                                                                         \
    printf("%40s [%40s]: ", #test, #pre);                                      \
    fflush(NULL);                                                              \
    uint64_t cycles_start, cycles_final, cycles_diff;                          \
    uint64_t min_diff = (uint64_t)-1;                                          \
    for (int i = 0; i < repeat; i++) {                                         \
      pre;                                                                     \
      __asm volatile("" ::: /* pretend to clobber */ "memory");                \
      RDTSC_START(cycles_start);                                               \
      if (test != expected)                                                    \
        printf("bug");                                                         \
      RDTSC_FINAL(cycles_final);                                               \
      cycles_diff = (cycles_final - cycles_start);                             \
      if (cycles_diff < min_diff)                                              \
        min_diff = cycles_diff;                                                \
    }                                                                          \
    uint64_t S = size;                                                         \
    float cycle_per_op = (min_diff) / (double)S;                               \
    printf(" %.2f cycles per element", cycle_per_op);                          \
    printf("\n");                                                              \
    fflush(NULL);                                                              \
  } while (0)

template <class T> struct pointer_cmp {
  bool operator()(T *a, T *b) { return *a < *b; }
};

struct vstr_cmp {
  bool operator()(const char *a, const char *b) {
     return strcmp(a,b) < 0;
  }
 };

template <int length> struct cstr_cmp {
  bool operator()(const char *a, const char *b) {
    if (length == 8) {
      uint64_t fa, fb;
      memcpy(&fa, a, 8);
      memcpy(&fb, b, 8);
      fa = __builtin_bswap64(fa);
      fb = __builtin_bswap64(fb);
      return fa < fb;
    } else {
      for (int k = 0; k < length; ++k) {
        if (a[k] < b[k]) {
          return true;
        }
        if (a[k] > b[k]) {
          return false;
        }
      }
      return false;
    }
  }
};

void demo(int size) {
  printf("size = %d values \n", size);
  int repeat = 500;
  const int N = 8;
  std::vector<uint32_t> v(size);
  for (uint32_t i = 0; i < size; ++i)
    v[i] = i;
  std::vector<uint32_t> t(size);
  for (uint32_t i = 0; i < size; ++i)
    t[i] = i;
  std::vector<std::string> s(size);
  for (uint32_t i = 0; i < size; ++i) {
    s[i] = std::to_string(i);
  }
  std::vector<const char *> vs(size);
  for (uint32_t i = 0; i < size; ++i) {
    vs[i] = s[i].c_str();
  }
  std::vector<const char *> cs(size);
  for (uint32_t i = 0; i < size; ++i) {
    cs[i] = strncpy(new char[N], s[i].c_str(), N);
    assert(strcmp(s[i].c_str(), cs[i]) == 0);
  }

  pointer_cmp<uint32_t> cmp;
  cstr_cmp<N> ccmp;
  vstr_cmp vcmp;

  BEST_TIME_COND(std::is_sorted(v.begin(), v.end()),true, std::sort(v.begin(), v.end()),
            repeat, size);
  BEST_TIME_COND(std::is_sorted(s.begin(), s.end()),true, std::sort(s.begin(), s.end()),
            repeat, size);
  BEST_TIME_COND(std::is_sorted(cs.begin(), cs.end(), ccmp),true,
            std::sort(cs.begin(), cs.end(), ccmp), repeat, size);
  BEST_TIME_COND(std::is_sorted(vs.begin(), vs.end(), vcmp),true,
            std::sort(vs.begin(), vs.end(), vcmp), repeat, size);
   for (uint32_t i = 0; i < size; ++i) {
    assert(strcmp(s[i].c_str(), cs[i]) == 0);
  }


  printf("\n");
  BEST_TIME(std::sort(v.begin(), v.end()), std::sort(v.begin(), v.end()),
            repeat, size);
  BEST_TIME(std::sort(s.begin(), s.end()), std::sort(s.begin(), s.end()),
            repeat, size);
  BEST_TIME(std::sort(cs.begin(), cs.end(), ccmp),
            std::sort(cs.begin(), cs.end(), ccmp), repeat, size);
  BEST_TIME(std::sort(vs.begin(), vs.end(), ccmp),
            std::sort(vs.begin(), vs.end(), vcmp), repeat, size);


  printf("\n");

  BEST_TIME(gfx::timsort(v.begin(), v.end()), std::sort(v.begin(), v.end()),
            repeat, size);
  BEST_TIME(gfx::timsort(s.begin(), s.end()), std::sort(s.begin(), s.end()),
            repeat, size);
  BEST_TIME(gfx::timsort(cs.begin(), cs.end(), ccmp),
            std::sort(cs.begin(), cs.end(), ccmp), repeat, size);

  printf("\n");

  BEST_TIME(std::sort(v.begin(), v.end()),
            std::random_shuffle(v.begin(), v.end()), repeat, size);
  BEST_TIME(std::sort(s.begin(), s.end()),
            std::random_shuffle(s.begin(), s.end()), repeat, size);
  BEST_TIME(std::sort(cs.begin(), cs.end(), ccmp),
            std::random_shuffle(cs.begin(), cs.end()), repeat, size);
  BEST_TIME(std::sort(vs.begin(), vs.end(), vcmp),
            std::random_shuffle(vs.begin(), vs.end()), repeat, size);


  printf("\n");

  BEST_TIME(gfx::timsort(v.begin(), v.end()),
            std::random_shuffle(v.begin(), v.end()), repeat, size);
  BEST_TIME(gfx::timsort(s.begin(), s.end()),
            std::random_shuffle(s.begin(), s.end()), repeat, size);
  BEST_TIME(gfx::timsort(cs.begin(), cs.end(), ccmp),
            std::random_shuffle(cs.begin(), cs.end()), repeat, size);

  for (uint32_t i = 0; i < size; ++i) {
    delete[] cs[i];
  }

  printf("\n");
}

int main() {
  demo(1024);
  demo(1 << 16);
  demo(1000000);
  return 0;
}
