/*
---------------------------------------------------------------------------------------
Benchmark                                                Time           CPU Iterations
---------------------------------------------------------------------------------------
BM_UniqueSort/10000                                 427641 ns     427878 ns       1623   22.2884M items/s
BM_UniqueSort/32768                                1574255 ns    1575103 ns        440     19.84M items/s
BM_UniqueSort/262144                              14759406 ns   14767144 ns         47   16.9295M items/s
BM_UniqueSort/2097152                            139690581 ns  139767236 ns          5   14.3095M items/s
BM_UniqueSort/16777216                          1281876575 ns 1282551187 ns          1   12.4751M items/s
BM_UniqueSort/100000000                         8465389316 ns 8469560234 ns          1     11.26M items/s
BM_UniqueSet<std::set<int>>/10000                   920241 ns     920688 ns        767   10.3583M items/s
BM_UniqueSet<std::set<int>>/32768                  4468282 ns    4470346 ns        157   6.99051M items/s
BM_UniqueSet<std::set<int>>/262144                59091943 ns   59118904 ns         13   4.22877M items/s
BM_UniqueSet<std::set<int>>/2097152              916682350 ns  917108834 ns          1   2.18077M items/s
BM_UniqueSet<std::set<int>>/16777216            12306704851 ns 12311840027 ns          1   1.29956M items/s
BM_UniqueSet<std::set<int>>/100000000           105985874336 ns 106006139165 ns          1   921.232k items/s
BM_UniqueSet<std::unordered_set<int>>/10000         385781 ns     385818 ns       1835   24.7182M items/s
BM_UniqueSet<std::unordered_set<int>>/32768        1359416 ns    1359437 ns        520   22.9875M items/s
BM_UniqueSet<std::unordered_set<int>>/262144      11666135 ns   11667829 ns         58   21.4264M items/s
BM_UniqueSet<std::unordered_set<int>>/2097152    179158325 ns  179174401 ns          4   11.1623M items/s
BM_UniqueSet<std::unordered_set<int>>/16777216  1753106587 ns 1753300050 ns          1   9.12565M items/s
BM_UniqueSet<std::unordered_set<int>>/100000000 10425629809 ns 10426576113 ns          1   9.14657M items/s
BM_UniqueSet<ska::flat_hash_set<int>>/10000         150666 ns     150677 ns       4707   63.2925M items/s
BM_UniqueSet<ska::flat_hash_set<int>>/32768         551839 ns     551921 ns       1251   56.6204M items/s
BM_UniqueSet<ska::flat_hash_set<int>>/262144       4581551 ns    4582179 ns        152   54.5592M items/s
BM_UniqueSet<ska::flat_hash_set<int>>/2097152     55052293 ns   55061662 ns         12   36.3229M items/s
BM_UniqueSet<ska::flat_hash_set<int>>/16777216   494396740 ns  494457701 ns          2   32.3587M items/s
BM_UniqueSet<ska::flat_hash_set<int>>/100000000 3777955780 ns 3777951981 ns          1   25.2432M items/s
*/
// Benchmark file contents, depends on google-benchmark and flat_hash_map (from abseil or Chrome/ska).
#include <benchmark/benchmark.h>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

#include "flat_hash_map/flat_hash_map.hpp"

namespace {

#define TEST_RANGE ->Range(10000, 100000000);

// Generate an array of int32s where 50% of the values are unique.
std::vector<int> MakeVector(std::size_t n) {
  std::vector<int> result(n);
  for (int i = 1; i < n; ++i) {
    int val = rand();
    result[i] = val & 0x1 ? val >> 1 : result[val % i];
  }
  return result;
}


static void BM_UniqueSort(benchmark::State &state) {
  const int size = state.range(0);
  const auto input_data = MakeVector(size);
  std::vector<int> output_data;
  output_data.reserve(size);
  for (auto _ : state) {
     output_data = input_data;
     std::sort(output_data.begin(), output_data.end());
     output_data.erase(std::unique(output_data.begin(), output_data.end()),
                       output_data.end());
  }
  state.SetItemsProcessed(state.iterations() * size);
}
BENCHMARK(BM_UniqueSort) TEST_RANGE;


template <typename T> void reserve(T* set, int n) {}
template <typename T> void reserve(std::unordered_set<T>* set, int n) {  set->reserve(n); }
template <typename T> void reserve(ska::flat_hash_set<T>* set, int n) {  set->reserve(n); }

template <typename Set> static void BM_UniqueSet(benchmark::State &state) {
  const int size = state.range(0);
  const auto input_data = MakeVector(size);
  std::vector<int> output_data;
  output_data.reserve(size);

  for (auto _ : state) {
    Set set;
    reserve(&set, size);  // Specialized to allow usage with std::set.
    output_data.resize(size);
    auto output_iter = output_data.begin();
    for (const int value : input_data) {
      if (set.insert(value).second) {
        *output_iter++ = value;
      }
    }
    output_data.erase(output_iter, output_data.end());
  }
  state.SetItemsProcessed(state.iterations() * size);
}
BENCHMARK_TEMPLATE(BM_UniqueSet, std::set<int>) TEST_RANGE;
BENCHMARK_TEMPLATE(BM_UniqueSet, std::unordered_set<int>) TEST_RANGE;
BENCHMARK_TEMPLATE(BM_UniqueSet, ska::flat_hash_set<int>) TEST_RANGE;

}  // namespace

BENCHMARK_MAIN();