// La demostración de Huffman, con números: el intercambio y la inducción.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "huffman.h"

namespace {

void print_depths(const std::vector<long long>& freq, const std::vector<int>& depth, const std::string& label) {
    std::cout << label << " profundidades";
    for (int value : depth) std::cout << ' ' << value;
    std::cout << "  costo " << code_cost(freq, depth) << '\n';
}

void exchange() {
    std::vector<long long> freq = {1, 2, 3, 4};
    std::vector<int> depth = {1, 2, 3, 3};
    std::cout << "Intercambio, con frecuencias 1 2 3 4:\n";
    print_depths(freq, depth, "  árbol inicial:   ");
    std::swap(depth[0], depth[2]);
    print_depths(freq, depth, "  cambia 1 con 3:  ");
    std::swap(depth[1], depth[3]);
    print_depths(freq, depth, "  cambia 2 con 4:  ");
    print_depths(freq, huffman(freq).depth, "  Huffman:         ");
}

void induction(std::vector<long long> freq) {
    std::cout << "\nInducción, reemplazando los dos menores por su suma:\n";
    std::cout << "alfabeto                 x   y   costo = costo del siguiente + x + y\n";
    std::vector<std::vector<long long>> alphabets;
    std::vector<long long> costs;
    std::vector<long long> current = freq;
    while (current.size() >= 2) {
        alphabets.push_back(current);
        costs.push_back(code_cost(current, huffman(current).depth));
        std::sort(current.begin(), current.end());
        long long joined = current[0] + current[1];
        current.erase(current.begin(), current.begin() + 2);
        current.push_back(joined);
    }
    for (std::size_t i = 0; i < alphabets.size(); i++) {
        std::vector<long long> sorted = alphabets[i];
        std::sort(sorted.begin(), sorted.end());
        std::string text;
        for (long long value : sorted) text += std::to_string(value) + " ";
        std::cout << std::left << std::setw(22) << text << std::right << std::setw(4) << sorted[0] << std::setw(4)
                  << sorted[1] << std::setw(7) << costs[i] << " = ";
        long long next = i + 1 < alphabets.size() ? costs[i + 1] : 0;
        std::cout << next << " + " << sorted[0] << " + " << sorted[1] << '\n';
    }
}

}  // namespace

int main() {
    exchange();
    induction({1, 1, 2, 3, 5, 8});
}