// Experimental content: Print level by cdf

#include "sortlib.cuh"
#define READ_NO_OUTPUT
#include "read_helper_p.h"
#include <random>

long pow_for_sample(long n) {
  auto x = 2;
  for (int i = 1; i < n; i++) {
    x *= 2;
  }
  return x - 1;
}
constexpr size_t MAX_LEVEL = 32;
constexpr auto RESULT_LENGTH = MAX_LEVEL + 3;

static unsigned trailing_zeroes(size_t index) {
  constexpr auto block_size = 2;
  unsigned bits = 0;
  auto x = index / block_size;

  if (x) {
    while (x % block_size == 0) {
      ++bits;
      x /= block_size;
    }
  }
  return bits;
}

inline double calcSliceSize(size_t insertion_size) {
  return 1.0 / (double)insertion_size;
}

void generateRandomLevel(std::vector<unsigned int> &v, long run_times) {
  // auto levels = new int[size];
  std::random_device randomDevice;
  std::mt19937 randomEngine(randomDevice());
  std::geometric_distribution<> distribution(0.5);
  for (int i = 0; i < run_times; i++) {
    v[(int)std::min(MAX_LEVEL, (size_t)distribution(randomEngine))]++;
  }
}

void multiple_generate(std::vector<unsigned int> &v, long run_times,
                       const int outer_times = 10) {
  std::vector<std::vector<unsigned int>> results(outer_times);
  std::random_device randomDevice;
  std::mt19937 randomEngine(randomDevice());
  std::geometric_distribution<> distribution(0.5);
  for (int x = 0; x < outer_times; x++) {
    results[x].resize(RESULT_LENGTH, 0);
    for (int i = 0; i < run_times; i++) {
      results[x]
             [(int)std::min(MAX_LEVEL, (size_t)distribution(randomEngine))]++;
    }
  }
  for (int level = 0; level < MAX_LEVEL; level++) {
    auto sum = 0L;
    for (int i = 0; i < outer_times; i++) {
      sum += results[i][level];
    }
    v[level] = sum / outer_times;
  }
}

int main(int argc, char const *argv[]) {

  auto multiple_times = 0L;
  if (argc < 3) {
    printf("Usage %s [sample(pow)] [population]\n", argv[0]);
    return 1;
  }

  if (argc == 4) {
    multiple_times = strtol(argv[3], nullptr, 10);
    printf("multiple_times defined: %ld\n", multiple_times);
  }

  auto sample_length = pow_for_sample(strtol(argv[1], nullptr, 10));
  auto population_length = strtol(argv[2], nullptr, 10);

  printf("sample length: %ld, population length: %ld\n", sample_length,
         population_length);

  ReadHelper<key_type> readHelper("normal_distribution.txt", sample_length,
                                  population_length);
  readHelper.readFile();

  std::vector<key_type> sample, population;
  std::vector<unsigned int> result(RESULT_LENGTH), result2(RESULT_LENGTH);
  readHelper.split_into(sample, population);
  rebuildSort(sample);

  auto scale_size = calcSliceSize(population_length);

  auto sort = CustomSort(sample_length, sizeof(key_type) * 8);

  for (auto element : population) {
    auto ret = sort.sample_cdf_custom_version(sample.data(), element);
    auto cdf_index = ret / scale_size;
    auto index = trailing_zeroes((size_t)cdf_index);
    result[index]++;
  }

  if (!multiple_times) {
    generateRandomLevel(result2, population_length);
  } else {
    multiple_generate(result2, population_length);
  }

  for (int i = 0; i < 32; i++) {
    if (!result[i] && !result2[i]) {
      continue;
    }
    printf("%d: %d %d\n", i, result[i], result2[i]);
  }
}