//
// Created by grtsinry43 on 5/8/25.
//

#include "problem5.h"

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

// 定义哈夫曼树节点
struct HuffmanNode {
    char character;
    int frequency;
    HuffmanNode *left;
    HuffmanNode *right;

    HuffmanNode(char ch, int freq) : character(ch), frequency(freq), left(nullptr), right(nullptr) {}
};

// 比较器，用于优先队列
struct Compare {
    bool operator()(HuffmanNode *a, HuffmanNode *b) {
        return a->frequency > b->frequency;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const std::unordered_map<char, int> &frequencyTable) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;

    // 将每个字符和频率插入优先队列
    for (const auto &entry : frequencyTable) {
        pq.push(new HuffmanNode(entry.first, entry.second));
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        HuffmanNode *left = pq.top(); pq.pop();
        HuffmanNode *right = pq.top(); pq.pop();

        HuffmanNode *merged = new HuffmanNode('\0', left->frequency + right->frequency);
        merged->left = left;
        merged->right = right;

        pq.push(merged);
    }

    return pq.top();
}

// 生成哈夫曼编码
void generateHuffmanCodes(HuffmanNode *root, const std::string &code, std::unordered_map<char, std::string> &huffmanCodes) {
    if (!root) return;

    if (!root->left && !root->right) {
        huffmanCodes[root->character] = code;
    }

    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}

// 主函数
int problem_5() {
    // 示例字符频率表
    std::unordered_map<char, int> frequencyTable = {
        {'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}
    };

    // 构建哈夫曼树
    HuffmanNode *root = buildHuffmanTree(frequencyTable);

    // 生成哈夫曼编码
    std::unordered_map<char, std::string> huffmanCodes;
    generateHuffmanCodes(root, "", huffmanCodes);

    // 输出每个字符的哈夫曼编码
    std::cout << "Huffman Codes:\n";
    for (const auto &entry : huffmanCodes) {
        std::cout << entry.first << ": " << entry.second << "\n";
    }

    return 0;
}