Untitled

/*
分兩部分

1.每一個符號frequency (確認用)
2.huffman code (複製用)

*/
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include<fstream>
using namespace std;

struct ch_n{
    char chh;
    int ff=0;
    string code="";

};
typedef struct ch_n chn;

struct Tree
{
    int freq;  // 出現頻率，即權重
    char ch;
    struct Tree *left=nullptr;
    struct Tree *right=nullptr;

};
typedef struct Tree tree;
typedef struct Tree* ptree;

vector<chn>  storelist(128);
vector<ptree>  prior;
int prior_n=0;


void printin(ptree pt, string st)
{
    if (pt==nullptr)  return; //空節點


    if (pt->left)  st+='0'; // 訪問left，添加 "0"

    printin(pt->left, st);

    // last 節點
    if (!(pt->left && pt->right)){
        storelist[static_cast<int>(pt->ch)].code=st;
    }
    st.pop_back();  // 退一個字元

    if (pt->right) st+='1'; // 訪問rifht，添加 "1"

    printin(pt->right, st);
}


void input(){
    char ch;

    ifstream infile("HUFFMANtree.txt",ios::in);

    while(infile.get(ch)){

        storelist[static_cast<int>(ch)].chh=ch;
        storelist[static_cast<int>(ch)].ff++;
    }

    //確認frequency
    cout<<endl<<"-----確認每一個char都有對應frequency-----"<<endl;
    for(int i=0;i<128;i++){
        cout<<i<<"\t";
        if(storelist[i].chh==' ') cout<<"space";
        else if(storelist[i].chh=='\n') cout<<"line";
        else cout<<storelist[i].chh;
        cout<<"\t"<<storelist[i].ff<<endl;
    }
    //

    for(int i=0;i<127;i++){
        if(storelist[i].ff!=0){
            ptree pt = new tree;
            pt->ch = storelist[i].chh;
            pt->freq = storelist[i].ff;
            prior.push_back(pt);
            prior_n++;

        }

    }

}

void output(){
    chn cc;
    cout<<endl<<"-----HUFFMAN CODE-----"<<endl<<endl;
    for(int next=0;next<128;next++){
        cc=storelist[next];
        if(cc.ff!=0){
            cout<<"code["<<next<<"]= 12'b ";
            if(cc.code.length()!=12) cout<<"x";
            cout<<cc.code<<";"<<endl;
        }

    }


}

void lookmin(){

    for(int i=0;i<prior_n-1;i++){
        for(int j=0;j<prior_n-i-1;j++){
            if(prior[j]->freq > prior[j+1]->freq){
                ptree st;
                st=prior[j];
                prior[j]=prior[j+1];
                prior[j+1]=st;
            }

        }
    }

}


void examine2(){
    char ch;
    string s="";

    ifstream infile("HUFFMANtree.txt",ios::in);

    while(infile.get(ch)){

        s+=storelist[static_cast<int>(ch)].code;

    }
    cout<<s.length();
}

void struct_huffmantree(){

     while (prior_n > 1){

        lookmin();
        ptree pt = new tree;
        ptree pleft, pright;
        pleft = prior[0];
        prior.erase(prior.begin());
        pright = prior[0];
        prior.erase(prior.begin());

        pt->left = pleft;
        pt->right = pright;
        pt->freq = pleft->freq + pright->freq;
        prior_n--;
        prior.push_back(pt);
    }

}


// 霍夫曼編碼
void huffman(){
    string initial("");//initialize
    input();
    struct_huffmantree();
    printin(prior[0], initial);
    output();
    examine2();
}

int main(){
    huffman();
    return 0;
}