//a 0.25  e 0.0625 f 0.0625 g 0.0625 h 0.0625 b 0.25 c 0.125 d 0.125
//a 0.32 b 0.22 c 0.18 d 0.16 e 0.08 f 0.04
//a 0.2 b 0.15 c 0.15 d 0.15 e 0.1 f 0.1 g 0.1 h 0.05
#include"iostream.h"
#include<iomanip.h>
#include"vector"
#include"algorithm"
#include"math.h"
using namespace std;
struct bitree
{//定義結(jié)構(gòu)用于存儲編碼結(jié)果的二叉樹結(jié)構(gòu),在譯碼時用到
	char ch;	//用于存儲碼符號
	char mz;	//用于存儲碼字
	bitree * lchild;
	bitree * rchild;

};
struct data
{//用于存儲相關的信源符號以及其概率
	double p;
	char ch;
	vector<char> code;
	int ml;
};
bool sortspecial(data dt1,data dt2)
{//用于排序時用
	return dt1.p>dt2.p;
}
void print2(vector<char>vd)
{//用于打印譯碼結(jié)果
	for(int i=0;i<vd.size();i++)
		cout<<vd[i]<<" ";
	cout<<endl;
}
void read(vector <data> &vd)
{//用于讀入相關的信源符號以及概率
	int n;
	while(true)
	{
		cout<<"請輸入信源符號數(shù):"<<endl;
		cin>>n;
		cout<<"請輸入相應的信源符號及其概率:"<<endl;
		data dt;
		int	i=0;		
		while(i<n)
		{	
			cin>>dt.ch;
			cin>>dt.p;
			dt.ml=0;
			vd.push_back(dt);
			i++;
			
		}
		double sum=0;
		vector<data>::iterator pit;
		for(pit=vd.begin();pit!=vd.end();pit++)
		{
			sum+=pit->p;
		}
		if(sum!=1)
		{
			cout<<"你輸入的概率不符合要求,請重新輸入."<<endl;
			sum=0;
			continue;
		}
		sort(vd.begin(),vd.end(),sortspecial);
		break;
	}
}

void append(char ch1,char ch2,bitree *&bt)
{//用于再構(gòu)造碼字二叉樹時向其中添加結(jié)點
	bitree * bit=new bitree;
	bit->ch=ch1;
	bit->mz=ch2;
	bit->lchild=NULL;
	bit->rchild=NULL;
	if(ch1=='0')
		bt->rchild=bit;
	else bt->lchild=bit;
}
void Creatmz1(vector<data>& vd,int begin1,int end1  ,double pn ,bitree *&bt)
{//進行編碼,用遞歸的方法進行編碼
	int begin=begin1,end=end1;
	if(begin==end) return;
	else if(begin+1==end)
	{
		return;
	}
	else if(begin+2==end){
		vd[begin].code.push_back('0');
		vd[begin].ml++;
		append('0',vd[begin].ch,bt);
		vd[end-1].code.push_back('1');
		vd[end-1].ml++;
		append('1',vd[end-1].ch,bt);
		return;
	}
	else{
			double sum0=0,sum1=0,sum2=0;
			do{
				 sum1+=vd[begin].p;
				 sum2=sum1+vd[begin+1].p;
				 begin++;
			 }while(fabs(sum1/pn-0.5)>fabs(sum2/pn-0.5));//用于找到上下兩組碼的分點使得其概率和近于相同
			for(int i=begin1;i<begin;i++){
				vd[i].code.push_back('0');
				vd[i].ml++;
			}
			if(begin1+1 == begin){
				append('0',vd[begin1].ch,bt);
			}
			else append('0','0',bt);
			for(int j=begin;j<=end1-1;j++){
				vd[j].code.push_back('1');
				vd[j].ml++;
			}
			if(begin+1 == end1){
				append('1',vd[begin].ch,bt);
			}
			else append('1','0',bt);
			Creatmz1(vd,begin1 ,begin,sum1,bt->rchild );//對分點前的進行編碼
			Creatmz1(vd,begin ,end1,pn-sum1,bt->lchild);//對分點后的進行編碼
	}
}
void print1(vector<data> vd)
{//用于打印編碼結(jié)果
	cout<<"xi"<<setw(8)<<"P(xi)"<<setw(8)<<"碼長"
        <<setw(8)<<"碼字"<<setw(8)<<endl;
	for(int i=0;i<vd.size();i++){
		cout<<vd[i].ch<<setw(8)<<vd[i].p<<setw(8)<<vd[i].ml<<setw(8);
		for(int j=0;j<vd[i].code.size();j++)
			cout<<vd[i].code[j];
			cout<<setw(8)<<endl;
	}
}

void clear(bitree * & bt)
{//對二叉樹的動態(tài)存儲空間進行釋放
	if(bt!=NULL&&bt->lchild!=NULL)
		clear(bt->lchild);
	if(bt!=NULL&&bt->rchild!=NULL)
		clear(bt->rchild);
	delete bt;
}

bool des_code(vector <char> & vr,vector <char> vt,bitree *bt)
{//用二叉編碼樹進行解碼
	if(bt==NULL)
	{
		cout<<"碼樹不存在!!!"<<endl;
		return false;
	}
	int pit=0;
	bitree * mbt=bt;
	while ((mbt->lchild!=NULL||mbt->rchild!=NULL)||pit<vt.size())
	{
		if(mbt->lchild==NULL&&mbt->rchild==NULL&&mbt->mz!='0')
		{
			vr.push_back(mbt->mz);
			mbt=bt;
		}
		if(mbt->lchild!=NULL&& vt[pit]=='1')
		{
			mbt=mbt->lchild;
			pit++;
		}
		else if(mbt->rchild!=NULL&& vt[pit]=='0')
		{
			mbt=mbt->rchild;
			pit++;
		}	
		else if(mbt->lchild!=NULL&&mbt->rchild!=NULL) break;
	}
	if(mbt->lchild!=NULL&&mbt->rchild!=NULL)
	{
		cout<<"你輸入的是一個錯誤的碼序列,請較正后再輸入."<<endl;
		return false;
	}
	else {
		vr.push_back(mbt->mz);
		return true;
	}
}
void read1(vector<char>& vd)
{//用于讀入要解碼的序列
	cout<<"請輸要譯碼的序列(以'#'結(jié)束):"<<endl;
	char dt;
	int	i=0;
	cin>>dt;		
	while(dt!='#')
	{	
		vd.push_back(dt);
		cin>>dt;
	}
}	

void print_H_L_R(vector<data>vd)
{//用于計算并打印信息熵,平均碼長,效率
	double H=0,L=0,R=0;
	for(int i=0;i<vd.size();i++)
	{	
		H+=vd[i].p*(log10(1/vd[i].p)/log10(2));
		L+=vd[i].p*(double)vd[i].ml;
	}
	R=H/L;
	cout<<"此碼的信息熵(H)是:"<<H<<endl;
	cout<<"此碼的平均碼長(L)為:"<<L<<endl;
	cout<<"此碼的效率(U)為:"<<R<<endl;
}
int main()
{
	bitree * bt=new bitree;
	bt->ch = '#';
	bt->mz = '*';
	bt->lchild=NULL;
	bt->rchild=NULL;
	vector <data> vd;
	vector <char> vr;
	vector <char> vt;
	cout<<"************下面將對Fano編,譯碼的過程進行演示*************"<<endl;
	cout<<"__________________________________________________________"<<endl;
	cout<<endl;
	cout<<"************下面顯示編碼的過程及相關參數(shù)和結(jié)果************"<<endl;
	read(vd);
	if(vd.size()==1)
	{
		vd[0].code.push_back('0');
		vd[0].ml++;
		append('0',vd[0].ch,bt);
	}
	cout<<endl;
	Creatmz1(vd,0,vd.size(),1,bt);
	cout<<"**************    編碼結(jié)果    **************"<<endl;
	print1(vd);
	print_H_L_R(vd);
	cout<<endl;
	cout<<"************   下面將進行譯碼過程操作的演示   ************"<<endl;
	cout<<endl;
	read1(vt);
	if(des_code(vr,vt,bt))
		print2(vr);
	clear(bt);
	return 1;
}