//#include <hwloc/helper.h>
#define Change(x,y) (x)^=(y)^=(x)^=(y);
struct HNode{
    int weight;
    int parent;
    int LChild;
    int RChild;
    char data;
    bool operator<(HNode & r){
        if(this->parent != -1) return false;
        if(r.parent != -1) return true;
        return (this->weight < r.weight);
    }
};
struct HCode{
    char data;
    char code[100];
    bool operator==(char &_in){ return this->data == _in;}
};
class Huffman{
private:
    HNode *HTree; // 哈弗曼树
    HCode *HCodeTable; // 哈弗曼编码表
    void SelectMin(int &x,int &y,int begin,int end); // 找两个最小值
    void Reveres(char a[]); // 字符串倒置
public:
    void CreateHTree(const int a[],const char *b,int n);
    void CreateCodeTable(int n);
    void Encode(char *s,char *b);
    void Decode(char *s,char *b);
    explicit Huffman(const char *a);
    HCode *GetHCodeTable(){return HCodeTable;}
    HNode *GetHTree(){return HTree;}
    ~Huffman();
};
void Huffman::SelectMin(int &x, int &y, int begin, int end){
    x = begin-1;while (HTree[++x].parent !=-1);
    y = x;while (HTree[++y].parent !=-1);
    if(HTree[y] < HTree[x]) Change(x,y);
    for(int i = x;i < end;i++) if(HTree[i] < HTree[x]) x = i;
    for(int i = y;i < end;i++) if(HTree[i] < HTree[y] && i != x) y = i;
}
void Huffman::Reveres(char *a) {
    int l = 0;
    while (a[++l] != '\0');
    for(int i = 0;i<l/2;i++) Change(a[i],a[l-1-i]);
}
void Huffman::CreateHTree(const int *a,const char *b, int n) {
    HTree = new HNode[2*n-1];
    for(int i = 0;i<n;i++){
        HTree[i].weight = a[i];
        HTree[i].LChild = HTree[i].RChild = HTree[i].parent = -1;
        HTree[i].data = b[i];
    }
    int x,y;
    for(int i = n;i <2*n-1;i++){
        SelectMin(x,y,0,i);
        HTree[x].parent = HTree[y].parent = i;
        HTree[i].weight = HTree[x].weight + HTree[y].weight;
        HTree[i].LChild = x;
        HTree[i].RChild = y;
        HTree[i].parent = -1;
    }
}
void Huffman::CreateCodeTable(int n){
    HCodeTable = new HCode[n];
    for(int i = 0;i < n;i++){
        HCodeTable[i].data = HTree[i].data;
        int child = i;
        int parent = HTree[i].parent;
        int k = 0;
        while (parent != -1){
            if(child == HTree[parent].LChild)
                HCodeTable[i].code[k] = '0';
            else
                HCodeTable[i].code[k] = '1';
            k++;
            child = parent;
            parent = HTree[child].parent;
        }
        HCodeTable[i].code[k] = '\0';
        Reveres(HCodeTable[i].code);
    }
}
void Huffman::Decode(char *s, char *b) {
    while (*s!='\0'){
        int parent = -1;
        while (HTree[++parent].parent != -1);
        while (HTree[parent].LChild != -1){
            if(*s == '0')
                parent = HTree[parent].LChild;
            if(*s == '1')
                parent = HTree[parent].RChild;
            s++;
        }
        *b = HCodeTable[parent].data;
        b++;
    }
}
void Huffman::Encode(char *s, char *b) {
    int h=0;
    int n = -1;
    while (s[++n] != '\0');
    for(int i = 0;i<n;i++){
        int j = -1;
        while (HCodeTable+(++j)){
            if(HCodeTable[j] == s[i])break;
        }
        int hc = 0;
        while (HCodeTable[j].code[hc] != '\0')
            b[h++] = HCodeTable[j].code[hc++];
    }
}
Huffman::~Huffman() {
    delete[](HCodeTable);
    delete[](HTree);
}
Huffman::Huffman(const char *a){
    int cont = 0;
    HTree = nullptr;
    HCodeTable = nullptr;
    while (a[++cont] != '\0');
    auto *A = new char[cont]{'\0'};
    auto *B = new int[cont]{0};
    for(int i = 0; i<cont;i++){
        int head = 0;
        for(;head <= cont;head++){
            if(head == cont){
                head = -1;
                while (B[++head] != 0);
                A[head] = a[i];
                break;
            }
            if(A[head] == a[i]) break;
        }
        B[head]++;
    }
    cont = -1;
    while (B[++cont] != 0);
    CreateHTree(B,A,cont);
    CreateCodeTable(cont);
    delete[] A;
    delete[] B;
}
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>

#ifdef WIN32
#define CLEAR "cls"
#elif defined(linux)
#define CLEAR "clear"
#endif
using namespace std;
void printTheHuffmanTree(Huffman &_in);
void printTheHuffmanCodeTable(Huffman &_in);
void DEplay(Huffman &_in);
int main(){
    system(CLEAR);
    cout <<"+----------------------------+"<<endl;
    cout <<"|          哈弗曼树实现        |"<<endl;
    cout <<"|                            |"<<endl;
    cout <<"|          请先输入字符        |"<<endl;
    cout <<"+----------------------------+"<<endl;
    cout <<"输入字符：";
    char a[100]={'\0'};
    //cin >> a;
    cin.get(a,100);
    Huffman Huffman1(a);
    char b[800]={'\0'};
    char c[100]={'\0'};
    int nb = -1,nc = -1;
    Huffman1.Encode(a,b);
    Huffman1.Decode(b,c);
    while(b[++nb] != '\0');
    while(c[++nc] != '\0');
    system(CLEAR);
    cout <<"+----------------------------+"<<endl;
    cout <<"|          哈弗曼树实现        |"<<endl;
    cout <<"|                            |"<<endl;
    cout <<"|        哈弗曼树初始完毕       |"<<endl;
    cout <<"|      初始化使用的字符串为：    |"<<endl;
    cout <<"|"<<setw(28)<<setiosflags(ios::left)<<a<<"|"<<endl;
    cout <<"|        该字符串编码为：       |"<<endl;
    cout <<"|"<<setw(28)<<setiosflags(ios::left)<<b<<"|"<<endl;
    cout <<"|        编码重新解码为：       |"<<endl;
    cout <<"|"<<setw(28)<<setiosflags(ios::left)<<c<<"|"<<endl;
    cout <<"|        按Enter进入菜单       |"<<endl;
    cout <<"+----------------------------+"<<endl;
    cout <<"编码前长度"<<endl;
    cout << nc*8 << endl;
    cout << "编码后长度" <<endl;
    cout << nb << endl;
    cout << "压缩率" << endl;
    cout << (double)nb/(nc*8) << endl;
    cin.get();cin.get();
    int chouse;
    goback:;
    system(CLEAR);
    cout <<"+----------------------------+"<<endl;
    cout <<"|          哈弗曼树实现        |"<<endl;
    cout <<"|                            |"<<endl;
    cout <<"|    输入下面数字完成对应的操作  |"<<endl;
    cout <<"|   0  打印哈弗曼树的结构       |"<<endl;
    cout <<"|   1  打印哈弗曼编码表         |"<<endl;
    cout <<"|   2  进行其他编码/解码操作    |"<<endl;
    cout <<"|   3  退出                   |"<<endl;
    cout <<"+----------------------------+"<<endl;
    cout <<"请输入：";
    cin >> chouse;
    switch(chouse){
        case 0:
            printTheHuffmanTree(Huffman1);
            break;
        case 1:
            printTheHuffmanCodeTable(Huffman1);
            break;
        case 2:
            DEplay(Huffman1);
            break;
        case 3:
            return 0;
        default:
            goto goback;
    }
    goto goback;
}
void printTheHuffmanTree(Huffman & _in){
    HNode * root = _in.GetHTree();
    int a = -1;
    HNode * Hlist = root;
    while (Hlist[++a].parent != -1);
    root = &Hlist[a];
    HNode * list[100][100];
    list[0][0] = root;
    int deep = 0;
    bool end;
    do{
        deep++;
        for(int bh = 0;bh<pow(2,deep-1);bh++){
            if(list[deep-1][bh]){
                if(list[deep-1][bh]->LChild != -1)
                    list[deep][bh*2] = &Hlist[list[deep-1][bh]->LChild];
                if(list[deep-1][bh]->RChild != -1)
                    list[deep][bh*2+1] = &Hlist[list[deep-1][bh]->RChild];
            }
        }
        end = true;
        for(int bh = 0;bh<pow(2,deep);bh++)if(list[deep][bh]) end = false;
    }while (!end);
    system(CLEAR);
    auto *soot = new int[deep];
    soot[0]=2;
    for(int n=1;n<deep;n++)soot[n]=2*soot[n-1]+1;
    for(int n=0;n<deep;n++){
        for(int bh = 0;bh < pow(2,n);bh++) {
            if(!list[n][bh])
                cout <<setw(soot[deep - n] + 1) << ' ';
            else{
                if (n != 0)
                    cout << setw(soot[deep - n] + 1)
                         << setfill(' ')
                         << setiosflags(ios::left);
                if(list[n][bh]->data == '\0')
                    cout << list[n][bh]->weight ;
                else
                    cout << list[n][bh]->data;
            }
        }
        cout << endl;
        for(int bh = 0;bh < pow(2,n);bh++) {
            if(list[n][bh] && list[n][bh]->data == '\0')
                cout << setw(soot[deep-n-1]+1)
                     << setfill('-')
                     << setiosflags(ios::left)
                     << '|'
                     << setw(soot[deep-n-1]+1)
                     << setfill(' ')
                     << setiosflags(ios::left)
                     << '+';
            else cout << setw(2*(soot[deep-n-1]+1))
                      << setfill(' ') << ' ';
        }
        cout << endl;
        for(int bh = 0;bh < pow(2,n);bh++) {
            if(list[n][bh] && list[n][bh]->data == '\0')
                cout << setw(soot[deep-n-1]+1)
                     << setfill(' ')
                     << setiosflags(ios::left)
                     << '|'
                     << setw(soot[deep-n-1]+1)
                     << setfill(' ')
                     << setiosflags(ios::left)
                     << '|';
            else cout << setw(2*(soot[deep-n-1]+1))
                      << setfill(' ') << ' ';
        }
        cout << endl;
    }
    delete[] soot;
    cout<< "按回车回到主菜单";
    cin.get();cin.get();
}
/*
 * 0           0
 * |-----+     |-----+
 * |     |     |     |
 * 1     1     1     1
 * |--+  |--+  |--+  |--+
 * |  |  |  |  |  |  |  |
 * 2  2  2  2  2  2  2  2
 */
void printTheHuffmanCodeTable(Huffman &_in){
    HCode * table = _in.GetHCodeTable();
    system(CLEAR);
    cout << "+------+----------+"<<endl;
    cout << "| code |  coding  |"<<endl;
    cout << "+------+----------+"<<endl;
    int i = -1;
    while (table[++i].code[0] != '\0'){
        cout <<"|   "<<table[i].data<<"  |"<<setw(10)<<setfill(' ')<<table[i].code<<"|"<<endl;
    }
    cout << "+------+----------+"<<endl;
    cout << "按回车返回菜单"<<endl;
    cin.get();cin.get();
}
void DEplay(Huffman &_in){
    cout << "请选择："<<endl;
    cout << "1. 编码"<<endl;
    cout << "2. 解码"<<endl;
    cout << "当前可以编码的字符：";
    HCode * table = _in.GetHCodeTable();
    int i = -1;
    while (table[++i].code[0] != '\0'){
        cout <<table[i].data<<" ";
    }
    cout <<endl;
    cout << "当前可以解码的字符：";
    i = -1;
    while (table[++i].code[0] != '\0'){
        cout <<table[i].code<<" ";
    }
    cout <<endl;
    cout << "请输入：";
    cin >> i;
    char a[800];
    char b[100];
    if(i == 2){
        cout << "请输入需要解码的字符：";
        cin >> a;
        _in.Decode(a,b);
        cout << "解码完毕 结果是："<<endl;
        cout << b <<endl;
    } else{
        cout << "请输入需要编码的字符：";
        cin >> b;
        _in.Encode(b,a);
        cout << "编码完毕 结果为："<< endl;
        cout << a<<endl;
        cout << "顺便帮你解一下"<<endl;
        _in.Decode(a,b);
        cout << b << endl;
    }
    cout << "按回车返回"<<endl;
    cin.get();cin.get();
}