#include<iostream>
#include<fstream>
#include<string>
using namespace std;

typedef struct{
	char         ch;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void Select(HuffmanTree,int,int&,int&);

void InitHuffman(HuffmanTree &HT,HuffmanCode &HC,int n){
	int m,i,s1,s2,start;
	unsigned c,f;
	char *cd;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
	HuffmanTree p;
	cout<<"請依次字符和權(quán)值的順序各個輸入！"<<endl;
	cout<<"字符如果是空格，請用#代替！"<<endl;
	for(p=HT+1,i=1;i<=n;i++,p++){
		cin>>p->ch;
		cin>>p->weight;
		p->parent=0; p->lchild=0; p->rchild=0;
	}
	
	for(;i<=m;++i,p++){
		p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; 
	}
	for(i=n+1;i<=m;++i){
		Select(HT,i-1,s1,s2);
		HT[s1].parent=i;  HT[s2].parent=i;
		HT[i].lchild=s1;  HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight + HT[s2].weight;
	}
    
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    // 分配n個字符編碼的頭指針向量([0]不用)
    cd=(char*)malloc(n*sizeof(char)); // 分配求編碼的工作空間
    cd[n-1]='\0'; // 編碼結(jié)束符
    for(i=1;i<=n;i++)
    { // 逐個字符求赫夫曼編碼
        start=n-1; // 編碼結(jié)束符位置
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
      // 從葉子到根逆向求編碼
            if(HT[f].lchild==c)
	            cd[--start]='0';
            else
			    cd[--start]='1';
		}
        HC[i]=(char*)malloc((n-start)*sizeof(char));
     // 為第i個字符編碼分配空間	
        strcpy(HC[i],&cd[start]); // 從cd復(fù)制編碼(串)到HC
    }
	//
	free(cd);
	ofstream fout("hfmTree.txt");
	fout<<n<<endl;
	i=1;
	while(i<=n){
	   fout<<HT[i].ch<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<" ";
	   fout<<HC[i]<<endl;
	   i++;
	}
	while(i<=m){
		fout<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
		i++;
	}
	fout.close();
	cout<<"初始化成功！哈弗曼樹已存入“hfmTree.txt”文件中！"<<endl;
}//end of InitHuffMan

void Select(HuffmanTree HT,int i,int &s1,int &s2){
	
	unsigned w=10000;
	for(int j=1;j<=i;j++){
		if(HT[j].weight<w&&HT[j].parent==0) {
           w=HT[j].weight; s1=j;
		}
	}
	HT[s1].parent=1;
	w=10000;
    for(j=1;j<=i;j++){
		if(HT[j].weight<w&&HT[j].parent==0){
           w=HT[j].weight; s2=j;
		}
	}
}//end of Select

void ReadHuffman(HuffmanTree &HT,HuffmanCode &HC,int &n){
	string code;
	int i=1;
	ifstream fin("hfmTree.txt");
	fin>>n;
	HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	while(i<=n){
		fin>>HT[i].ch>>HT[i].parent>>HT[i].lchild>>HT[i].rchild;
		fin>>code;
		//HT[i].ch=c;
		//.str()將字符串轉(zhuǎn)化成const char*類型，為將const性質(zhì)強制去掉
		HC[i]=(char*)malloc(30*sizeof(char));
		strcpy(HC[i],code.c_str());
		i++;
	}
	while(!fin.eof()){
		fin>>HT[i].parent>>HT[i].lchild>>HT[i].rchild;
		i++;
	}
	cout<<"已從文件獲取哈弗曼樹！"<<endl;
	fin.close();
}

void Encoding(HuffmanTree HT,HuffmanCode HC,int n){
	cout<<"正在從文件ToBeTran.txt讀取要編碼的數(shù)據(jù)..."<<endl;
	ifstream fin("ToBeTran.txt");
	ofstream fout("CodeFile.txt");
	if(!fin) {cout<<"文件讀取失敗！"<<endl; return; }
	char c;  int i=0;
	while(!fin.eof()){
		c=fin.get();
		for(int i=1;i<=n;++i){
			if(c==HT[i].ch) {fout<<HC[i]; cout<<HC[i]<<endl; break;}
		}//for
		if(i==n+2){
			cout<<"字符編碼失敗，編碼表中不存在此字符，程序結(jié)束！"<<endl;
			return;
		}//if
	}//while
	cout<<"編碼成功！結(jié)果已經(jīng)存入CodeFile.txt文件中！"<<endl;
	fin.close();
	fout.close();
}//end of Encoding

void Decoding(HuffmanTree HT,int n){
	ifstream fin("CodeFile.txt");
	ofstream fout("TextFile.txt");
    if(!fin) {cout<<"文件讀取失敗！"<<endl; return; }
	char c;
	int fen=2*n-1;   //flag始終跟在fen變量的后邊第一個，用于輸出
	while(!fin.eof()){
		c=fin.get();	
	    if(c=='0')
			fen=HT[fen].lchild;
	    else
			fen=HT[fen].rchild;
		if(!HT[fen].lchild){    //判斷是否已經(jīng)到葉子結(jié)點，是的話輸出此葉子結(jié)點的字符
		    cout<<HT[fen].ch;
			fout<<HT[fen].ch;
			fen=2*n-1; //當譯出一個字符時，fen回到樹根，準備下一個譯碼
		}      
	}//while
	cout<<"\n譯碼成功！結(jié)果已經(jīng)存入TextFile.txt文件中！"<<endl;
	fin.close();
	fout.close();
}//end of Decoding 

void Print(){
	char c;
	int counter=1;
	ifstream fin("CodeFile.txt");
	ofstream fout("CodePrin.txt");
	while(!fin.eof()){
		c=fin.get();
		if(counter%50==1){ cout<<"\n";  fout<<"\n";}
        cout<<c;   fout<<c;
		counter++;
	}
	cout<<"\n編碼成功保存在“CodePrin.txt”文件中！"<<endl;
	fin.close();
	fout.close();
}//end of Print

//按樹狀打印輸出二叉樹的元素,i表示結(jié)點所在層次,初次調(diào)用時i=0
void Print_BiTree(HuffmanTree T,int m,int i)
{
	
    if(T[m].rchild){
        //m=T[m].rchild;
		Print_BiTree(T,T[m].rchild,i+1);
	}
    for(int j=1;j<=i;j++) cout<<" ";    //打印i個空格以表示出層次
    cout<<T[m].weight<<" "<<endl;  //打印T元素,換行
    if(T[m].lchild) {
		//m=T[m].lchild;
		Print_BiTree(T,T[m].lchild,i+1);}
}//Print_BiTree

void main(){
	HuffmanTree HT;
	HuffmanCode HC;
	int n,i=0;
	char choice;
	while(1){
	    cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl
            <<"☆     歡迎使用哈弗曼編/譯器,請選擇（I,E,D,P,T,Q ）:      ☆"<<endl
	        <<"☆           I.初始化                                     ☆"<<endl
		    <<"☆           E.編碼                                       ☆"<<endl
		    <<"☆           D.譯碼                                       ☆"<<endl
		    <<"☆           P.印代碼文件                                 ☆"<<endl
		    <<"☆           T.印哈弗曼樹                                 ☆"<<endl
	        <<"☆           Q.退出系統(tǒng)                                   ☆"<<endl
		    <<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl;
	    cin>>choice;
		switch(choice){
		case 'i':
		case 'I':{
            cout<<"請輸入您要建立的曼哈頓樹的葉子個數(shù)n："<<endl;
			cin>>n;
			InitHuffman(HT,HC,n); 
			}break;
		case 'e':
		case 'E':{
			cout<<"哈弗曼樹是否已在內(nèi)存中?(y/n)"<<endl;
			char ans;
			cin>>ans;
			if(ans=='y'||ans=='Y')
                Encoding(HT,HC,n);
			else{
				cout<<"正在從文件讀取哈弗曼樹..."<<endl;
				ReadHuffman(HT,HC,n);
				Encoding(HT,HC,n);
				 }
				 }
			break;
		case 'd':
		case 'D':
			Decoding(HT,n);
			break;
		case 'p':
		case 'P':
			Print();
			break;
		case 't':
		case 'T':
			Print_BiTree(HT,2*n-1,i);
			break;
		case 'q':
		case 'Q':
			return;
			break;
		default: cout<<"選擇錯誤！"<<endl;
		}
	}	
}