// Huffman sobre una tabla pequeña. Cada árbol se guarda como su lista de códigos: al unir dos árboles,
// los códigos del primero ganan un 0 adelante y los del segundo un 1.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

namespace {

struct Symbol {
    char letter;
    long frequency;
};

struct Partial {
    long weight;
    int order;  // desempata: primero el creado antes
    std::vector<std::pair<char, std::string>> codes;
    std::string name;
};

struct Heavier {
    bool operator()(const Partial& a, const Partial& b) const {
        if (a.weight != b.weight) {
            return a.weight > b.weight;
        }
        return a.order > b.order;
    }
};

void run(const std::vector<Symbol>& symbols) {
    std::priority_queue<Partial, std::vector<Partial>, Heavier> heap;
    int order = 0;
    long total_symbols = 0;
    for (const Symbol& symbol : symbols) {
        heap.push({symbol.frequency, order++, {{symbol.letter, ""}}, std::string(1, symbol.letter)});
        total_symbols += symbol.frequency;
    }
    long merged_total = 0;
    while (heap.size() > 1) {
        Partial first = heap.top();
        heap.pop();
        Partial second = heap.top();
        heap.pop();
        std::cout << "une " << first.name << ":" << first.weight << " con " << second.name << ":" << second.weight
                  << " -> " << first.weight + second.weight << "\n";
        Partial joined{first.weight + second.weight, order++, {}, "(" + first.name + second.name + ")"};
        for (auto& [letter, code] : first.codes) {
            joined.codes.push_back({letter, "0" + code});
        }
        for (auto& [letter, code] : second.codes) {
            joined.codes.push_back({letter, "1" + code});
        }
        merged_total += joined.weight;
        heap.push(joined);
    }
    long bits = 0;
    const Partial& root = heap.top();
    for (const Symbol& symbol : symbols) {
        for (const auto& [letter, code] : root.codes) {
            if (letter == symbol.letter) {
                std::cout << symbol.letter << " (" << symbol.frequency << "): " << code << "\n";
                bits += symbol.frequency * static_cast<long>(code.size());
            }
        }
    }
    std::size_t fixed_width = 0;
    while ((std::size_t{1} << fixed_width) < symbols.size()) {
        fixed_width++;
    }
    std::cout << "bits: " << bits << ", suma de los pesos unidos: " << merged_total
              << ", con codigo fijo de " << fixed_width << " bits: " << total_symbols * static_cast<long>(fixed_width)
              << "\n";
}

}  // namespace

int main() {
    run({{'a', 5}, {'b', 2}, {'c', 1}, {'d', 1}});
    std::cout << "\n";
    run({{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}});
    std::cout << "\n";
    run({{'a', 1}, {'b', 1}, {'c', 1}, {'d', 1}});
    return 0;
}