// Comparaciones de heapsort según la entrada. Los conteos no dependen de la máquina.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "heapsort.h"

namespace {

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

}  // namespace

int main() {
    std::cout << "        n  entrada  comparaciones   /n  /(n log2 n)\n";
    for (int n : {1000, 10000, 100000, 1000000}) {
        for (const std::string kind : {"azar", "asc", "desc", "iguales"}) {
            std::vector<int> items = make_input(kind, n);
            long comparisons = 0;
            heapsort(items, [&](int a, int b) {
                comparisons++;
                return a < b;
            });
            if (!std::is_sorted(items.begin(), items.end())) {
                std::cout << "no quedo ordenado\n";
                return 1;
            }
            std::cout << std::setw(9) << n << std::setw(9) << kind << std::setw(15) << comparisons
                      << std::fixed << std::setprecision(2) << std::setw(7) << double(comparisons) / n
                      << std::setw(13) << double(comparisons) / (n * std::log2(n)) << "\n";
        }
    }
    return 0;
}