// Construir un min-heap de dos formas, contando comparaciones. Los conteos no dependen de la máquina.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "heapsort.h"
#include "int_heap.h"

namespace {

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;
}

long count_pushes(const std::vector<int>& items) {
    IntHeap heap;
    for (int item : items) {
        heap.push(item);
    }
    heap.check_invariants();
    return heap.comparisons();
}

// build_max_heap con el orden al revés da un min-heap: la raíz es la menor.
long count_bottom_up(std::vector<int> items, std::size_t* levels = nullptr) {
    long comparisons = 0;
    std::size_t total = build_max_heap(items, [&](int a, int b) {
        comparisons++;
        return a > b;
    });
    if (levels != nullptr) {
        *levels = total;
    }
    return comparisons;
}

// Cuántos nodos de un árbol perfecto tienen altura h, y cuánto pueden bajar en total.
void print_levels(int k) {
    int n = (1 << (k + 1)) - 1;
    std::cout << "\nArbol perfecto con n = " << n << ", entrada descendente\n";
    std::cout << " altura  nodos  bajan como maximo\n";
    long total = 0;
    for (int h = 0; h <= k; h++) {
        long nodes = 1L << (k - h);
        total += nodes * h;
        std::cout << std::setw(7) << h << std::setw(7) << nodes << std::setw(19) << nodes * h << "\n";
    }
    std::size_t real = 0;
    count_bottom_up(make_input("desc", n), &real);
    std::cout << "suma: " << total << ", niveles que bajaron de verdad: " << real << "\n";
}

}  // namespace

int main() {
    std::cout << "        n  orden  abajo-arriba  /n    n pushes  /n  log2n\n";
    for (int n : {1023, 16383, 262143, 1048575}) {
        for (const std::string order : {"asc", "azar", "desc"}) {
            std::vector<int> items = make_input(order, n);
            long bottom_up = count_bottom_up(items);
            long pushes = count_pushes(items);
            std::cout << std::setw(9) << n << std::setw(7) << order << std::setw(14) << bottom_up
                      << std::fixed << std::setprecision(2) << std::setw(6) << double(bottom_up) / n
                      << std::setw(10) << pushes << std::setw(6) << double(pushes) / n
                      << std::setprecision(1) << std::setw(5) << std::log2(n) << "\n";
        }
    }
    print_levels(9);
    return 0;
}