// Paso 2: construir de abajo hacia arriba frente a n inserciones.
// Cuenta comparaciones y mide tiempos, con -O2 y sin sanitizers. Los tiempos dependen de la máquina.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "bench.h"
#include "min_heap.h"

namespace {

struct CountingLess {
    long* count;
    bool operator()(int a, int b) const {
        (*count)++;
        return a < b;
    }
};

std::vector<int> make_input(const std::string& order, int n) {
    std::vector<int> items(n);
    std::iota(items.begin(), items.end(), 0);
    if (order == "desc") {
        std::reverse(items.begin(), items.end());
    } else if (order == "azar") {
        std::mt19937 generator(13);
        std::shuffle(items.begin(), items.end(), generator);
    }
    return items;
}

}  // namespace

int main() {
    std::cout << "       n orden  comp.build  /n  comp.push  /n  t.build  t.push\n";
    for (int n : {1 << 14, 1 << 16, 1 << 18, 1 << 20, 1 << 22}) {
        for (const std::string order : {"azar", "desc"}) {
            std::vector<int> items = make_input(order, n);
            long build_count = 0;
            {
                MinHeap<int, CountingLess> heap(items, CountingLess{&build_count});
                keep(heap.top());
            }
            long push_count = 0;
            {
                MinHeap<int, CountingLess> heap{CountingLess{&push_count}};
                for (int item : items) {
                    heap.push(item);
                }
                keep(heap.top());
            }
            double build_time = median_seconds(3, [&] {
                MinHeap<int> heap(items);
                keep(heap.top());
            });
            double push_time = median_seconds(3, [&] {
                MinHeap<int> heap;
                for (int item : items) {
                    heap.push(item);
                }
                keep(heap.top());
            });
            std::cout << std::setw(8) << n << std::setw(6) << order << std::setw(12) << build_count << std::fixed
                      << std::setprecision(2) << std::setw(5) << double(build_count) / n << std::setw(11)
                      << push_count << std::setw(6) << double(push_count) / n << std::setprecision(4) << std::setw(8)
                      << build_time << std::setw(8) << push_time << "\n";
        }
    }
    return 0;
}