// Compresión de Huffman de un arreglo de bytes. Completen cada función marcada con not_implemented.
// Los tipos y el formato ya están decididos: las pruebas comparan archivos byte por byte.
#ifndef HUFFMAN_H
#define HUFFMAN_H

#include <array>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <string>
#include <vector>

#include "bit_io.h"
#include "min_heap.h"
#include "not_implemented.h"

// El formato del archivo comprimido:
//   bytes 0-3   "HUF1"
//   bytes 4-11  tamaño original en bytes, de 64 bits, primero el byte menos significativo
//   después, solo si el tamaño no es 0, una corriente de bits (ver bit_io.h):
//     el árbol en preorden: un nodo interno es un bit 0 seguido de sus hijos, izquierdo y derecho;
//       una hoja es un bit 1 seguido de los 8 bits de su símbolo
//     los códigos de los bytes del archivo, en orden
//     ceros de relleno hasta completar el último byte
// Un archivo con un solo símbolo tiene un árbol de una hoja, cuyo código tiene 0 bits.
inline constexpr std::size_t header_size = 12;
inline constexpr int max_tree_depth = 255;

using Frequencies = std::array<std::uint64_t, 256>;
using Codes = std::array<std::string, 256>;  // el código de cada byte, con caracteres '0' y '1'

// Los nodos viven en un arreglo y se señalan por índice. Así nadie tiene que hacer new ni delete.
struct HuffmanNode {
    std::uint64_t weight = 0;
    int symbol = -1;  // el byte, en una hoja
    int left = -1;    // hijo izquierdo: el bit 0
    int right = -1;   // hijo derecho: el bit 1
    bool is_leaf() const { return left < 0; }
};

struct HuffmanTree {
    std::vector<HuffmanNode> nodes;
    int root = -1;  // -1 si el árbol está vacío
};

// Lo que guarda el heap: un árbol parcial, con su peso.
struct HeapEntry {
    std::uint64_t weight;
    int node;
};

// El desempate es parte del formato: a igual peso, primero el nodo creado antes.
struct LighterEntry {
    bool operator()(const HeapEntry& a, const HeapEntry& b) const {
        if (a.weight != b.weight) {
            return a.weight < b.weight;
        }
        return a.node < b.node;
    }
};

// Viene hecho: cuántas veces aparece cada byte.
inline Frequencies count_frequencies(const Bytes& data) {
    Frequencies frequencies{};
    for (std::uint8_t byte : data) {
        frequencies[byte]++;
    }
    return frequencies;
}

// Paso 4: una hoja por cada byte con frecuencia mayor que 0, de menor a mayor símbolo. Luego, con
// MinHeap<HeapEntry, LighterEntry>, unan los dos más livianos hasta que quede uno: el primero que
// sale es el hijo izquierdo, y el nodo nuevo va al final de nodes. Sin símbolos, root queda en -1.
inline HuffmanTree build_tree(const Frequencies& frequencies) {
    (void)frequencies;
    not_implemented("build_tree");
}

// Viene hecho: el camino desde la raíz hasta cada hoja, 0 a la izquierda y 1 a la derecha. La recursión
// llega a 255 niveles como máximo. Una sola hoja tiene un código vacío. write_tree se escribe parecido.
inline void collect_codes(const HuffmanTree& tree, int node, std::string& path, Codes& codes) {
    const HuffmanNode& current = tree.nodes[node];
    if (current.is_leaf()) {
        codes[current.symbol] = path;
        return;
    }
    path.push_back('0');
    collect_codes(tree, current.left, path, codes);
    path.back() = '1';
    collect_codes(tree, current.right, path, codes);
    path.pop_back();
}

inline Codes make_codes(const HuffmanTree& tree) {
    Codes codes;
    if (tree.root >= 0) {
        std::string path;
        collect_codes(tree, tree.root, path, codes);
    }
    return codes;
}

// Paso 5: el árbol en preorden, como dice el formato. Requiere un árbol no vacío.
inline void write_tree(const HuffmanTree& tree, BitWriter& writer) {
    (void)tree;
    (void)writer;
    not_implemented("write_tree");
}

// Paso 5: lo contrario de write_tree. Los pesos quedan en 0. Un archivo dañado no debe agotar la
// pila ni colgar el programa: lancen std::runtime_error si la profundidad pasa de max_tree_depth
// o si hay más de 256 hojas. Si se acaban los bits, BitReader ya lanza su error.
// Cuidado: un push_back en nodes puede invalidar las referencias a sus elementos.
inline HuffmanTree read_tree(BitReader& reader) {
    (void)reader;
    not_implemented("read_tree");
}

// Paso 5: la cabecera, y si hay datos, el árbol y los códigos, con un BitWriter sobre el mismo
// arreglo. No olviden finish().
inline Bytes compress_bytes(const Bytes& data) {
    (void)data;
    not_implemented("compress_bytes");
}

// Paso 5: lanza std::runtime_error si no empieza con la cabecera correcta. Se detiene por el tamaño de
// la cabecera, y no porque se acaben los bits: el relleno no son símbolos. Antes de leer un bit,
// miren si ya están en una hoja.
inline Bytes decompress_bytes(const Bytes& compressed) {
    (void)compressed;
    not_implemented("decompress_bytes");
}

#endif