// Mide Gale-Shapley con tabla de rangos y recorriendo la lista. Compilar con -O2 y sin sanitizers.
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <vector>

#include "instances.h"

namespace {

// Corre fn `reps` veces y devuelve la mediana en segundos.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
    std::vector<double> times;
    for (int i = 0; i < reps; i++) {
        auto start = std::chrono::steady_clock::now();
        fn();
        auto stop = std::chrono::steady_clock::now();
        times.push_back(std::chrono::duration<double>(stop - start).count());
    }
    std::sort(times.begin(), times.end());
    return times[times.size() / 2];
}

void print_ratio(double now, double before) {
    if (before > 0) {
        std::cout << std::setprecision(1) << std::setw(7) << now / before;
    } else {
        std::cout << std::setw(7) << "-";
    }
}

}  // namespace

int main() {
    std::cout << "    n   tabla (s)  razón  ns/propuesta   lista (s)  razón  ns/casilla  lista/tabla\n";
    double previous_table = 0;
    double previous_scan = 0;
    int total = 0;
    for (int n : {500, 1000, 2000, 4000}) {
        Preferences proposers = same_list_proposers(n);
        Preferences receivers = latest_wins_receivers(n);
        long long proposals = 0;
        double table = median_seconds(5, [&] {
            Matching result = gale_shapley(proposers, receivers);
            proposals = result.proposals;
            total += result.partner[0];
        });
        long long steps = 0;
        double scan = median_seconds(3, [&] {
            steps = 0;
            total += gale_shapley_scan(proposers, receivers, steps).partner[0];
        });
        std::cout << std::fixed << std::setw(5) << n << std::setprecision(4) << std::setw(12) << table;
        print_ratio(table, previous_table);
        std::cout << std::setprecision(1) << std::setw(14) << table * 1e9 / static_cast<double>(proposals)
                  << std::setprecision(4) << std::setw(12) << scan;
        print_ratio(scan, previous_scan);
        std::cout << std::setprecision(2) << std::setw(12) << scan * 1e9 / static_cast<double>(steps)
                  << std::setprecision(0) << std::setw(13) << scan / table << '\n';
        previous_table = table;
        previous_scan = scan;
    }
    // Se imprime para que el compilador no pueda borrar los cálculos.
    std::cerr << "control: " << total << '\n';
}