//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

// UNSUPPORTED: c++03, c++11, c++14

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <tuple>
#include <vector>

#include "benchmark/benchmark.h"

#include "../CartesianBenchmarks.h"
#include "../GenerateInput.h"

namespace {

template <typename I, typename N>
std::array<I, 10> every_10th_percentile_N(I first, N n) {
  N step = n / 10;
  std::array<I, 10> res;

  for (size_t i = 0; i < 10; ++i) {
    res[i] = first;
    std::advance(first, step);
  }

  return res;
}

template <class IntT>
struct TestIntBase {
  static std::vector<IntT> generateInput(size_t size) {
    std::vector<IntT> Res(size);
    std::generate(Res.begin(), Res.end(), [] { return getRandomInteger<IntT>(0, std::numeric_limits<IntT>::max()); });
    return Res;
  }
};

struct TestInt32 : TestIntBase<std::int32_t> {
  static constexpr const char* Name = "TestInt32";
};

struct TestInt64 : TestIntBase<std::int64_t> {
  static constexpr const char* Name = "TestInt64";
};

struct TestUint32 : TestIntBase<std::uint32_t> {
  static constexpr const char* Name = "TestUint32";
};

struct TestMediumString {
  static constexpr const char* Name  = "TestMediumString";
  static constexpr size_t StringSize = 32;

  static std::vector<std::string> generateInput(size_t size) {
    std::vector<std::string> Res(size);
    std::generate(Res.begin(), Res.end(), [] { return getRandomString(StringSize); });
    return Res;
  }
};

using AllTestTypes = std::tuple<TestInt32, TestInt64, TestUint32, TestMediumString>;

struct LowerBoundAlg {
  template <class I, class V>
  I operator()(I first, I last, const V& value) const {
    return std::lower_bound(first, last, value);
  }

  static constexpr const char* Name = "LowerBoundAlg";
};

struct UpperBoundAlg {
  template <class I, class V>
  I operator()(I first, I last, const V& value) const {
    return std::upper_bound(first, last, value);
  }

  static constexpr const char* Name = "UpperBoundAlg";
};

struct EqualRangeAlg {
  template <class I, class V>
  std::pair<I, I> operator()(I first, I last, const V& value) const {
    return std::equal_range(first, last, value);
  }

  static constexpr const char* Name = "EqualRangeAlg";
};

using AllAlgs = std::tuple<LowerBoundAlg, UpperBoundAlg, EqualRangeAlg>;

template <class Alg, class TestType>
struct PartitionPointBench {
  size_t Quantity;

  std::string name() const {
    return std::string("PartitionPointBench_") + Alg::Name + "_" + TestType::Name + '/' + std::to_string(Quantity);
  }

  void run(benchmark::State& state) const {
    auto Data = TestType::generateInput(Quantity);
    std::sort(Data.begin(), Data.end());
    auto Every10Percentile = every_10th_percentile_N(Data.begin(), Data.size());

    for (auto _ : state) {
      for (auto Test : Every10Percentile)
        benchmark::DoNotOptimize(Alg{}(Data.begin(), Data.end(), *Test));
    }
  }
};

} // namespace

int main(int argc, char** argv) {
  benchmark::Initialize(&argc, argv);
  if (benchmark::ReportUnrecognizedArguments(argc, argv))
    return 1;

  const std::vector<size_t> Quantities = {1 << 8, 1 << 10, 1 << 20};
  makeCartesianProductBenchmark<PartitionPointBench, AllAlgs, AllTestTypes>(Quantities);
  benchmark::RunSpecifiedBenchmarks();
}