#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

class H_coding{
public:
	double probablity;
	string code;
	bool connect;
    H_coding();
	H_coding(double pro,string cod,bool con);
	H_coding operator &= (const H_coding cod);
};
H_coding::H_coding(){
		probablity=0;
		code="";
		connect=false;
}
H_coding::H_coding(double pro,string cod,bool con){
	probablity=pro;
	code=cod;
	connect=con;
}

H_coding H_coding::operator &= (const H_coding cod){
	H_coding cod1;
	cod1.probablity=cod.probablity;
	cod1.code=cod.code;
	cod1.connect=cod.connect;
	return cod1;
}

typedef vector<H_coding> Arrary1;


void adding(int m,Arrary1 &a1){
	H_coding coding1(0,"",false);
	int append=0;
	a1.size();
	while((((a1.size()+append)-m)%(m-1))!=0)
		append++;
	for(int i=0;i<append;i++)
		a1.push_back(coding1);
}

int locate_a(double x,Arrary1 a1){
	int locate=0;
	for(;locate<a1.size()&&x<a1[locate].probablity;locate++);
	return locate;
}

int locate_b(double x,Arrary1 a1){
	int locate=0;
	for(;locate<a1.size()&&x<=a1[locate].probablity;locate++);
	return locate;
}

void move(Arrary1 &a1,int i){
	H_coding cod;
	Arrary1::iterator pit;
	pit=a1.begin();
	for(int j=0;j<i;j++)pit++;
	do{
		cod=a1[a1.size()-1];
		a1.insert(pit,cod);
		a1.pop_back();
	}while(a1[a1.size()-1].connect==true);
}

void coding_a(Arrary1 &a1,int N,int m){
	if(N>1){
	int j=m-1;
	int k=a1.size();
	int h=m;
	double temp=0;
		while(j>=0){
			do{
				k--;
			temp+=a1[k].probablity;
			a1[k].code=char(48+j)+a1[k].code;
			}while(a1[k-1].connect==true&&k>=1);
			j--;
			if(j>=0&&k>=1)a1[k-1].connect=true;
		}
		move(a1,locate_a(temp,a1));
		coding_a(a1,N-m+1,m);
	}
}

void coding_b(Arrary1 &a1,int N,int m){
	if(N>1){
	int j=m-1;
	int k=a1.size();
	int h=m;
	double temp=0;
		while(j>=0){
			do{
				k--;
			temp+=a1[k].probablity;
			a1[k].code=char(48+j)+a1[k].code;
			}while(a1[k-1].connect==true&&k>=1);
			j--;
			if(j>=0&&k>=1)a1[k-1].connect=true;
		}
		move(a1,locate_b(temp,a1));
		coding_b(a1,N-m+1,m);
	}
}

bool sortsp(H_coding cod1,H_coding cod2){
	if(cod1.probablity>cod2.probablity)
		return true;
	else
		if(cod1.probablity=cod2.probablity)
			return cod1.code.size()<cod2.code.size();
		else
			return false;
}

void display(Arrary1 a1){
	cout<<"符號       概率               碼字              碼長"<<endl;
	string s1;
	sort(a1.begin(),a1.end(),sortsp);
	for(int i=0;i<a1.size();i++){
		s1="u";
		s1+=char(49+i);
		cout<<s1<<"      "<<a1[i].probablity<<"               "<<a1[i].code<<"           "<<a1[i].code.size()<<endl;
	}
}

int main(){
	H_coding cod2;
	
	double a[5]={0.4,0.2,0.2,0.1,0.1};
	
	int m;
	for(;;){
		cout<<"                      H碼編碼                   "<<endl;
		cout<<"                     =========                  "<<endl;
		cout<<"                     1.方法A                    "<<endl;
		cout<<"                     2.方法B                    "<<endl;
		cout<<"                 請選擇(1或2,0:退出):           "<<endl;
		int j;
		cin>>j;
		switch(j){
		case 1 :{ 
			Arrary1 a1;
			for(int i=0;i<5;i++){
		cod2.probablity=a[i];
		a1.push_back(cod2);
	}
			cout<<"輸入碼元數:"<<endl;
			cin>>m;
			adding(m,a1);
			int l=a1.size();
			coding_a(a1,l,m);
			display(a1);
				break;}
		case 2 :{
			Arrary1 a1;
			for(int i=0;i<5;i++){
		cod2.probablity=a[i];
		a1.push_back(cod2);
	}
			cout<<"輸入碼元數:"<<endl;
			cin>>m;
			adding(m,a1);
			int l=a1.size();
			coding_b(a1,l,m);
			display(a1);
				break;}
		case 0 :
			return 0;
		}
}
}