// Primera tabla: recorre todas las permutaciones y cuenta las comparaciones de dos
// ordenamientos reales, frente a la cota ⌈log₂ n!⌉.
// Segunda tabla: compara log₂ n! con las expresiones de la demostración.
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <vector>

#include "comparison_sorts.h"

struct Summary {
    long long best = -1;
    long long worst = 0;
    std::size_t leaves = 0;
};

template <typename Sort>
Summary explore(int n, Sort sort_function) {
    std::vector<int> input(static_cast<std::size_t>(n));
    std::iota(input.begin(), input.end(), 0);
    Summary s;
    std::set<std::string> paths;
    do {
        std::vector<int> a = input;
        CountingLess less;
        sort_function(a, less);
        s.best = s.best < 0 ? less.count() : std::min(s.best, less.count());
        s.worst = std::max(s.worst, less.count());
        paths.insert(less.path());
    } while (std::next_permutation(input.begin(), input.end()));
    s.leaves = paths.size();
    return s;
}

int main() {
    std::cout << " n       n!  cota  inserción       mergesort       hojas distintas\n";
    std::cout << "                   mejor  peor     mejor  peor     ins.     merge\n";
    for (int n = 1; n <= 9; n++) {
        const Summary ins = explore(n, insertion_sort);
        const Summary mer = explore(n, merge_sort);
        unsigned long long factorial = 1;
        for (int i = 2; i <= n; i++) factorial *= static_cast<unsigned long long>(i);
        std::cout << std::setw(2) << n << std::setw(9) << factorial << std::setw(6)
                  << ceil_log2_factorial(n) << std::setw(8) << ins.best << std::setw(6) << ins.worst
                  << std::setw(9) << mer.best << std::setw(6) << mer.worst << std::setw(9)
                  << ins.leaves << std::setw(10) << mer.leaves << '\n';
    }

    std::cout << '\n' << "       n     (n/4) log n   (n/2) log(n/2)        log n!         n log n\n";
    std::cout << std::fixed << std::setprecision(0);
    double log_factorial = 0;
    int n = 1;
    for (int target : {4, 16, 256, 4096, 65536, 1048576}) {
        while (n < target) {
            n++;
            log_factorial += std::log2(n);
        }
        const double m = n;
        std::cout << std::setw(8) << n << std::setw(15) << m / 4 * std::log2(m) << std::setw(17)
                  << m / 2 * std::log2(m / 2) << std::setw(14) << log_factorial << std::setw(16)
                  << m * std::log2(m) << '\n';
    }
}