// Heapsort paso a paso, y un caso que muestra que no es estable.
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "heapsort.h"

namespace {

using Item = std::pair<int, char>;

void print_range(const std::vector<int>& items, std::size_t end) {
    std::cout << "[";
    for (std::size_t i = 0; i < items.size(); i++) {
        if (i == end) {
            std::cout << " | ";
        } else if (i > 0) {
            std::cout << " ";
        }
        std::cout << items[i];
    }
    if (end == items.size()) {
        std::cout << " |";
    }
    std::cout << "]\n";
}

std::string text(const std::vector<Item>& items) {
    std::string out;
    for (const Item& item : items) {
        out += std::to_string(item.first) + std::string(1, item.second) + " ";
    }
    return out;
}

}  // namespace

int main() {
    auto ascending = [](int a, int b) { return a < b; };
    std::vector<int> items = {4, 1, 7, 3, 9, 2};
    std::cout << "entrada:   ";
    print_range(items, items.size());
    build_max_heap(items, ascending);
    std::cout << "heap:      ";
    print_range(items, items.size());
    for (std::size_t end = items.size(); end > 1; end--) {
        std::swap(items[0], items[end - 1]);
        sift_down_max(items, 0, end - 1, ascending);
        std::cout << "saca " << items[end - 1] << ":    ";
        print_range(items, end - 1);
    }

    // Tres claves: los dos 2 salen en el orden contrario al de entrada.
    std::vector<Item> pairs = {{2, 'a'}, {2, 'b'}, {1, 'c'}};
    std::cout << "\nentrada: " << text(pairs) << "\n";
    heapsort(pairs, [](const Item& a, const Item& b) { return a.first < b.first; });
    std::cout << "salida:  " << text(pairs) << "\n";
    return 0;
}