#include <benchmark/benchmark.h>
#include <deque>
#include <forward_list>

using namespace std;

static void sequentialArray (benchmark::State &state) {
    int n = state.range(0);
    int *arr = new int[n];

    for (auto _ : state) {
        int i = 0;
        for (int j = 0; j < 1'000'000'000; j++) {
            arr[i] = i;
            i = (i + 1 < n ? i + 1 : 0);
        }
        benchmark::DoNotOptimize(arr);
        benchmark::ClobberMemory();
    }
}
BENCHMARK(sequentialArray)->RangeMultiplier(16)->Range(1 << 4, 1 << 24)->Iterations(10);

static void sequentialDeque (benchmark::State &state) {
    int n = state.range(0);
    deque<int> dq(n);

    for (auto _ : state) {
        int i = 0;
        for (int j = 0; j < 1'000'000'000; j++) {
            dq[i] = i;
            i = (i + 1 < n ? i + 1 : 0);
        }
        benchmark::DoNotOptimize(dq);
        benchmark::ClobberMemory();
    }
}
BENCHMARK(sequentialDeque)->RangeMultiplier(16)->Range(1 << 4, 1 << 24)->Iterations(10);

static void sequentialList (benchmark::State &state) {
    int n = state.range(0);
    forward_list<int> fwl(n);

    for (auto _ : state) {
        forward_list<int>::iterator it = fwl.begin();
        int i = 0;
        for (int j = 0; j < 1'000'000'000; j++) {
            *it = i;
            i = (i + 1 < n ? i + 1 : 0);
            it++;
            if (it == fwl.end()) it = fwl.begin();
        }
        benchmark::DoNotOptimize(fwl);
        benchmark::ClobberMemory();
    }
}
BENCHMARK(sequentialList)->RangeMultiplier(16)->Range(1 << 4, 1 << 24)->Iterations(10);

BENCHMARK_MAIN();