text: #include <array.hxx>
  #include <algorithm.hxx>
  #include <cassert.hxx>
  #include <cstdint.hxx>
  #include <tuple.hxx>
  #include <vector.hxx>
  
  #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>(); });
      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();
  }
  