#include "sortlib.h"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>

typedef unsigned long long key_type;
std::vector<key_type> population_vector, sample_vector;
constexpr size_t SAMPLE_LENGTH = 1023, TEST_LENGTH = 1024;
constexpr int MOVE_OFFSET = sizeof(key_type) * 8 - 1;

auto custom_sort = CustomSort<key_type>(SAMPLE_LENGTH, MOVE_OFFSET);

unsigned long long max_value = 0, min_value = 0xfffffffff;
inline void store_into_vector(unsigned long long value) {
  if (max_value < value) {
    max_value = value;
  }
  if (min_value > value) {
    min_value = value;
  }
  population_vector.push_back(value);
}

void valid_sort(std::vector<key_type> &tmp) {
  auto iter_end = population_vector.begin() + SAMPLE_LENGTH + 5;
  for (auto it = population_vector.begin() + SAMPLE_LENGTH; it != iter_end;
       it++) {
    // long std_search =
    //     std::lower_bound(tmp.begin(), tmp.end(), *it) - tmp.begin();
    long std_search = custom_sort.original_binary_search(
                          tmp.data(), tmp.data() + tmp.size(), *it) -
                      tmp.data();

    auto cuda_binary_search =
        custom_sort.binary_search(sample_vector.data(), *it) -
        sample_vector.data();
    cuda_binary_search = custom_sort.calculate_location(cuda_binary_search) - 1;
    /*printf("%ld:%ld %llu:%llu\n", std_search, cuda_binary_search,
     *(tmp.begin() + std_search),
     *(cuda_binary_search + sample_vector.begin()));*/
    printf("%ld:%ld \n", std_search, cuda_binary_search);
    // assert(std_search == cuda_binary_search);
  }
}

int main() {
  FILE *file = fopen("normal_distribution.txt", "r");
  assert(file);
  for (long long i; fscanf(file, "%lld ", &i) != EOF; store_into_vector(i))
    ;
  fclose(file);

  std::vector<key_type> tmp(population_vector.begin(),
                            population_vector.begin() + SAMPLE_LENGTH - 2);
  tmp.push_back(max_value);
  tmp.push_back(min_value);

  std::sort(tmp.begin(), tmp.end());

  sample_vector.resize(SAMPLE_LENGTH);
  for (size_t i = 0; i < SAMPLE_LENGTH; i++) {
    sample_vector[custom_sort.calculate_location_inverse(i) - 1] = tmp[i];
    auto location = custom_sort.calculate_location(i);
    auto location2 = custom_sort.calculate_location_inverse(location - 1);
    // printf("%zu %zu\n", location, location2);
    assert(location2 - 1 == i);
  }
  // valid_sort(tmp);
  /*for (auto element : sample_vector) {
    printf("%d ", element);
  }*/
  valid_sort(tmp);
  puts("");
}