//
// Created by dongl on 22-11-11.
//

#ifndef CPP_DATA_STRUCT_HUFFMAN_TREE_H
#define CPP_DATA_STRUCT_HUFFMAN_TREE_H
#include <fstream>
#include <iostream>

/// 可变长度的字符串 树组
typedef char** huffman_code;

/// 哈夫曼节点结构 一棵树的节点结构
struct HTNodeBase {
    struct HTNodeBase* parent; // 父节点
    struct HTNodeBase* left;   // 左子节点
    struct HTNodeBase* right;  // 右子节点
};

/// 哈夫曼节点结构 一棵树的节点信息
typedef struct HTNode : public HTNodeBase{
    int weight; // 节点权重
    int index;  // 下标
    char info;  // 节点信息
} *HuffmanTree;


/// 字母信息 与 出现的次数
struct Alphabet {
    char data;  // 字符
    int count;  // 字母出现次数
};

/// 哈夫曼树  一棵树的结构
/// 构建树 操作树 的类
class Huffman{
private:
    HuffmanTree ht;   // 树根
    int tree_node_sum{};  // 树的叶子数
public:
    // 构建哈夫曼树
    Huffman(int n, Alphabet* alphabet) {
        // 如果节点小于1 没有必要构建 直接return
        if (n <= 1)
            return;

        // 树的空间
        // 0号单元未用  ht[2 * n - 1]表示根节点
        int m = 2 * n - 1;
        ht = new HTNode[m + 1];
        // 构建树的全部节点
        for (int i = 1; i <= m; ++i) {
            ht[i].left = nullptr;
            ht[i].right = nullptr;
            ht[i].parent = nullptr;
        }
        // 构建存在个数节点的 字符与权重
        for (int i = 1; i <= n; ++i) {
            ht[i].weight = alphabet[i].count;
            ht[i].info = alphabet[i].data;
        }

        // 正式 构建 构造 huffman 的节点关系 点与点之间的关系
        for (int i = n+1; i < m; ++i) {
            // 左右节点
            int s1,s2;
            SelectHuffmanTree(i, s1, s2);
            // 表示从F中删除s1 ,s2
            ht[i].left = &ht[s1];
            ht[i].right = &ht[s2];
            // s1 和 s2 分为为 i 的 左右叶子  权值为他俩的和
            ht[i].weight = ht[s1].weight + ht[s2].weight;
        }
    }

    HuffmanTree getHuffmanTree() {
        return ht;
    }

private:
    /// 建立哈夫曼树 根据统计结果
    /// @param ht
    /// @param n
    /// @param s1
    /// @param s2
    void SelectHuffmanTree(int n, int& s1, int& s2){
        s1 = min_index(n - 1);
        s2 = min_index(n - 1);
    }

    inline int min_index(int n){
        int min;
        int min_weight;

        for (int i = 1; i <= n; ++i) {
            // 没有父节点 未分配过的
            if(ht[i].parent == nullptr){
                min = i;
                min_weight = ht[i].weight;
            }
        }
        ht[min].parent = &ht[n + 1];
        std::cout << "min=" << min << ", n=" << n << ", parent="
        << ht[min].parent << ", weight=" << ht[min].weight
        << ", info=" << ht[min].info << std::endl;
        return min;
    }
};
#endif //CPP_DATA_STRUCT_HUFFMAN_TREE_H