#include<string.h>
#include<string>
#include<queue>

#include<fstream>
#include<vector>
#include<iostream>
#include<iomanip>
using namespace std;
using std::string;
static const int MAX_SIZE=256;
struct huffman_node;
typedef huffman_node* node_ptr;//huffman結(jié)點指針
struct huffman_node{
	char id;
	int freq;
	string code;
	node_ptr left,right,parent;
};
//類huffman
class compare;
class huffman{
      private:
		  class compare{
		  public:
			  bool operator ()(const node_ptr&c1,const node_ptr&c2){
				  return (*c1).freq>(*c2).freq;
			  }//重載運算符（）
		  };//類compare
          node_ptr node_array[MAX_SIZE];//指針型結(jié)點的數(shù)組
	      priority_queue<node_ptr,vector<node_ptr>,compare> pq;
		  fstream in_file,out_file;
	      string in_file_name;
		  string out_file_name;
	  public:
		  huffman(string in_file_name,string out_file_name);
		  void create_pq();
		  void create_node_array();
		  void create_huffman_tree();
		  void calculate_huffman_codes();
		  void save_to_file();
		 
			  
			 
};
 
huffman::huffman(string in_file_name,string out_file_name){
	(*this).in_file_name=in_file_name;
	(*this).out_file_name=out_file_name;
	in_file.open(in_file_name.c_str (),ios::in);

    out_file.open(out_file_name.c_str(),ios::out);
	
}//構(gòu)造器
//創(chuàng)建huffman結(jié)點數(shù)組,根據(jù)讀入的每一行的字符，存入下標(biāo)是自身Asc碼數(shù)字的指針數(shù)組
void huffman::create_node_array(){
	node_ptr entry;
	string line;
	while(getline(in_file,line)){
		for(unsigned j=0;j<line.length();j++){
			entry=node_array[(int)(line[j])];
			(*entry).freq++;
			if((*entry).freq==1){
				(*entry).left=NULL;
				(*entry).right=NULL;
				(*entry).parent=NULL;
			}//if
		}//for
		entry=node_array[(int)'\n'];
		(*entry).freq++;
		(*entry).left=NULL;
		(*entry).right=NULL;
		(*entry).parent=NULL;
	}//while
	
}//create_node_array
//將所有huffman結(jié)點插入優(yōu)先隊列
void huffman::create_pq(){
     node_ptr entry;
	 int sum=0,n_chars=0;
	 for(int i=0;i<MAX_SIZE;i++){  //定義單個結(jié)點
		 node_array[i]=new huffman_node;
         (*node_array[i]).freq=0;
	 }//初始化數(shù)組
	 create_node_array();
	 for(int j=0;j<MAX_SIZE;j++){
		 entry=node_array[j];
		 if((*entry).freq>0){
			 pq.push(entry);
			 sum+=(*entry).freq;
			 n_chars++;

		 }
	 }
}
void huffman::create_huffman_tree(){
	node_ptr left;
	node_ptr right;
	node_ptr sum;
	while(pq.size()>1){
		left=pq.top();
		pq.pop();
		(*left).code=string ("0");

		right=pq.top();
		pq.pop();
		(*right).code=string ("1");

		sum=new huffman_node;
		(*sum).parent=NULL;
		(*sum).freq=(*left).freq+(*right).freq;
		(*sum).left=left;
		(*sum).right=right;
		(*left).parent=sum;
		(*right).parent=sum;

		pq.push(sum);
	}
}
//對各個字符進(jìn)行編碼
void huffman::calculate_huffman_codes(){
	const string HUFFMAN_CODES="Here are the huffman codes: ";
	const string ENCODED_SIZE_MESSAGE="\n\nThe size of the encoded message, in bits,is ";
	int total=0;//記錄編碼后的總位數(shù)
	string code;
	node_ptr entry;
	cout<<endl<<HUFFMAN_CODES<<endl;
	for(int i=0;i<MAX_SIZE;i++){
		code=" ";    
		entry=node_array[i];
		if((*entry).freq>0){
			cout<<char(i)<<" "; //注意，空格和回車非打印字符，所以是空格，但有編碼
			do{
				code=(*entry).code+code;//將葉子代碼和上層的父節(jié)點連接，迭代到根結(jié)點
				entry=(*entry).parent;
			}while((*entry).parent!=NULL);
			
				cout<<code<<endl;
			(*node_array[i]).code=code;
			total+=code.length()*(*node_array[i]).freq;//每個字符編碼*每個字符頻率
		}//if
	}//for
	cout<<ENCODED_SIZE_MESSAGE<<total<<endl;
}//
//輸出每個字符和其huffman編碼和編碼后的文件
void huffman::save_to_file(){
	node_ptr entry;
	string line;
	(*this).in_file.close();
	(*this).in_file.open(in_file_name.c_str(),ios::in);
	for(int i=0;i<MAX_SIZE;i++){
		entry=node_array[i];//指針數(shù)組中如果頻率大于0表示存在編碼信息
		if((*entry).freq>0)
			out_file<<(char)i<<" "<<(*entry).code<<endl;
	}//for
	out_file<<"----"<<endl;
	while(getline(in_file,line)){//這里問題出現(xiàn)，調(diào)試時根本進(jìn)入不了，所以文件編碼不能寫進(jìn)h2.txt
	
		for(unsigned j=0;j<line.length();j++){
			entry=node_array[(int)(line[j])];//給定字符，尋找指針數(shù)組中下標(biāo)對應(yīng)的編碼信息
			out_file<<(*entry).code;//寫出編碼
		}//for
		entry=node_array[(int)'\n'];
		out_file<<(*entry).code;//寫出換行符編碼
	}//while
	out_file.close();
	in_file.close();
}//save_to_file
void main(){

        
		huffman h("h1.txt","h2.txt");
		h.create_pq();
		h.create_huffman_tree();
		h.calculate_huffman_codes();
		h.save_to_file();
}