//任意給定一個信源模型，編程實現其二進制Shannon編碼，輸出編碼結果并給出譯碼過程。

#include <iostream.h>
#include <stdlib.h>
#include <math.h>

//實現信源概率的輸入,如果輸入概率歸一則返回1，否則返回0
 int Input(char X[],float P[],int num){
	int i=0;
	float Pa=0;       //累加概率以記錄信源是否滿足概率歸一性
	cout<<"輸入信源及對應概率:";	
	while(i<num){ 
		cin>>X[i];
		cin>>P[i];
		Pa=Pa+P[i];
		i++;
	}	
	if(Pa!=1)
	{	cout<<"     概率不歸一，請確認后重新輸入!!!"<<endl;
	    cout<<endl<<endl;
	    Input(X,P,num);
	    //exit(0);
	}
	 
	  return 1;
}

//對信源符號按概率按從大到小順序排列
void Sort_P(char X[],float P[],float num)  
{  float temp,char Xtemp;
	for(int i=0;i<num;i++)
		for(int j=i+1;j<num+1;j++)       
				if(P[i]<P[j])
				{   
					temp=P[i];
					Xtemp=X[i];
					P[i]=P[j];
					X[i]=X[j];
					P[j]=temp;
			        X[j]=Xtemp;}
}

//實現第j個碼字的累加概率
float Pacum(float P[],int j){   
	if(j==0)
		return 0;
	else 
		return (Pacum(P,j-1)+P[j-1]);
}

//計算每個信源的碼長
int CodeLength(float P){
	return int(3.32*log10f(1/P)+1);
}

void Shannon(char X[],float P[],int num){  
	//CODER[10][20]用來存放香農碼，p_dec為累加概率的小數部分  
	int k,CODER[10][20],j=0;   
	float p_dec;
	while(j<num){
		cout<<X[j]<<"  的編碼是:";
		p_dec=Pacum(P,j)-int(Pacum(P,j));
		k=CodeLength(P[j]);
		for(int i=0;i<k;i++){
			CODER[j][i]=int(p_dec*2);
			cout<<CODER[j][i];
			p_dec=p_dec*2-int(p_dec*2);
		}
		j++;
		cout<<endl;
	}
}

//輸入一個香農編碼，實現譯碼功能
void Coding(char X[],float P[],int num){
	int i,k,m,CODER[10][20],j=0,n=-1;
	int code[10];  
	bool flag=false;    //flag用來標志譯碼是否成功
	cout<<"輸入要譯的編碼：";
  while(code[n]!=2){   
		n++;
		cin>>code[n];
  }
  
	float p_dec;                  //將信源的編碼存入一個二維數組中
	while(P[j]){
		p_dec=Pacum(P,j)-int(Pacum(P,j));
		k=CodeLength(P[j]);
		for(i=0;i<k;i++){
			CODER[j][i]=int(p_dec*2);
			p_dec=p_dec*2-int(p_dec*2);
		} 
		j++;
	}
 //此時的j是信源的個數
	i=0;	
	while(i<j&&!flag){
		m=0;
		flag=true;
		k=CodeLength(P[i]);
		if((n)==k)
		{   
			while(flag&&(m<k))
			{ 
				if(code[m]==CODER[i][m])
				{
					m++;
					flag=true;
				}
				else
					flag=false;
			}
		}
		else
			flag=false;
		i++;
	}
	if(flag)
		cout<<"對應的信源為:   "<<X[i-1]<<endl;
	else
		cout<<"沒有信源與之對應"<<endl;
}


int main(){	
	int num,flag; //num是信源的個數，flag用來返回輸入函數的值
	char X[20]={NULL};
    float P[10]={NULL};
	char ch,c,N,M;
	cout<<"                    WELCOME　　           "<<endl;
	cout<<"輸入信源的個數：";
	cin>>num;	
	Input(X,P,num); 
	Sort_P(X,P,num);
	Shannon(X,P,num);
    cout<<"請根據需要選擇!"<<endl;
	    cout<<"  ﹡﹡﹡﹡﹡﹡﹡ 1.編碼請輸入 S ﹡﹡﹡﹡﹡﹡﹡"<<endl;
		cout<<"  ﹡﹡﹡﹡﹡﹡﹡ 2.譯碼請輸入 C﹡﹡﹡﹡﹡﹡﹡"<<endl;
		cout<<"  ﹡﹡﹡﹡﹡﹡﹡ 3.退出請輸入 Q ﹡﹡﹡﹡﹡﹡﹡"<<endl;
		cout<<"請輸入:";
		cin>>ch;
	switch(ch)
	{ case 'S':	 Shannon(X,P,num);break;
	  case 'C': do
				{Coding(X,P,num); 
				cout<<"是否還要譯碼?(Y/N)"<<endl;
				cin>>c;
				}
				while(c!='N');
				break;
	  case 'Q':  cout<<"成功退出!!"<<endl; break;
	  default:   cout<<"error"<<endl;
	}
    return 0;
}