#include"iostream.h"
#include<iomanip.h>
#include"stdlib.h"
#include"vector"
#include"algorithm"
#include"math.h"
using namespace std;
struct data			
{//用于存儲碼字及其編碼結果
	int mz;
	vector <char> code;
};
struct rle			
{//用于存儲每個碼字及其個數
	int length;
	int mz;
};
int get_gd(int n)	
{//用于求出編碼的長度
	int i=0;
	int j=n-1;
	while(j>0)
	{
		j=(j-j%2)/2;
		i++;
	}
	return i;
}
void Creadmz(int hd,vector<data>& vd,int hs)	
{//用于構建碼字
	int w=0;
	int ws=get_gd(hd);
	for(int i=0;i<hd;i++)
	{
		data d;
		d.mz=i+hs;
		w=i;
		while(w>0)
		{
			if(w % 2  == 1)
				d.code.push_back('1');
			else d.code.push_back('0');
			w=(w-w%2)/2.0;
		}
		for(int m = d.code.size();m <ws;m++)
			d.code.push_back('0');
		vd.push_back(d);
	}
}
void print( vector<data>vd)		
{//用于輸出編碼結果表明
	for(int i=0;i<vd.size();i++)
	{
		cout<<vd[i].mz<<" ";
		for(int j=vd[i].code.size()-1;j>=0;j--)
			cout<<vd[i].code[j];
		cout<<endl;
	}
}
void print1( vector <rle> re)		
{//輸出碼及其個數的組合
	for(int i=0;i<re.size();i++)
	{
		cout<<"<"<<re[i].mz<<","<<re[i].length<<">"<<" ";
	}
}
template <typename elem> 
void print2(vector <elem> cd,int n)	
{//輸出編,解碼結果
	int num=0;
	for(int i=0;i<cd.size();i++)
	{
		cout<<cd[i];
		num++;
		if(num%n==0) cout<<endl;
	}
	cout<<endl;
}

bool read(vector<rle> &vr,int hd,int & cor,int &rows)		
{//讀入要編碼的灰度矩陣
	int row,acr;
	rle re;
	cout<<"請輸入矩陣的行列數:"<<endl;
	cin>>row;
	cin>>acr;
	cor=acr;
	rows=row;
	cout<<"請輸入灰度值矩陣:"<<endl;
	for(int i=0;i<row;i++)
	{
		int n;
		n=re.mz=0;
		if(n==re.mz)
		{	
			cin>>n;
			if(n>=hd){vr.clear();  return false;}
		}
		for(int j=1;j<acr;)
		{
			re.mz=n;
			re.length=0;
			while(n==re.mz&&j<acr)
			{
				re.length++;
				j++;
				cin>>n;
				if(n>=hd){vr.clear();  return false;}
			}
			if(n!=re.mz)
			{
				vr.push_back(re);
				if(j==acr)
				{
					re.mz=n;
					re.length=1;
					vr.push_back(re);
				}
			}
			else if(j==acr)
			{
				if(n==re.mz)
				{
					re.length++;
					vr.push_back(re);
				}
				else {
					re.mz=n;
					re.length=1;
					vr.push_back(re);
				}
			}
			else vr.push_back(re);
		}
	}return true;
}
bool read1(vector <char>& vc,int num)
{//用于讀取要解碼的序列
	cout<<"請輸入你要解碼的序列(以'#'號結束):"<<endl;
	char ch;
	cin>>ch;
	while(ch!='#')
	{
		vc.push_back(ch);
		cin>>ch;
		if(ch!='0'&&ch!='1'&&ch!='#') {
			cout<<"你輸入的碼序列不正確請較正后rr再輸入。";
			vc.clear();
			return false;
		}
	}
	if(vc.size()%num!=0)
	{
		cout<<"你輸入的碼序列不正確請較正后再輸入。";
		vc.clear();
		return false;
	}
	return true;

}
int find(vector <data> vd,int x)
{//用于查找要編碼的灰度值是否在灰度級范圍內如果在反回相應碼在編碼序列中的位置
	int low=0;
	int high=vd.size()-1;
	int mid=0;
	while(low<=high)
	{
		mid = (low + high)/2;
		if(vd[mid].mz==x) return mid;
		else if(x<vd[mid].mz) high = mid-1;
		else low = mid +1;
	}
	cout<<"the element '"<<x<<"'not find."<<endl;
	return -1;
}
void Encode(vector <rle> vr,vector <data> vd,vector<data> vh,vector<char> &cd)
{//對灰度矩陣進行編碼操作成功則通過cd將其值代回
	int mc=0;
	int len=0;
	for(int i=0;i<vr.size();i++)
	{
		if((mc=find(vd,vr[i].mz))!=-1)
		for(int j=vd[mc].code.size()-1;j>=0;j--)
			cd.push_back(vd[mc].code[j]);
		else {
			cout<<"你要編碼的元素不在灰度級范圍內,編碼失敗."<<endl;
			exit(0);
		}
		if((len=find(vh,vr[i].length))!=-1)
		for(int k=vh[len].code.size()-1;k>=0;k--)
			cd.push_back(vh[len].code[k]);
	}
}
void coding(vector<char> vc,vector<int> &vi,int gd,int gds)
{//對輸入要解碼的序列進行解碼操作
	for(int i = 0;i<vc.size();)
	{
		int sum=0, sub=1;
		for(int j=0;j<gd;j++)
		{
			switch(vc[i])
			{
				case '1': sum +=pow(2,gd-j-1); i++;break;
				case '0': i++; break;
			}
		}
		for(int k=0;k<gds;k++)
		{
			switch(vc[i])
			{
				case '1': {sub +=pow(2,gds-k-1); i++;}break;
				case '0': i++; break;
			}
		}
		for(int s= 0;s<sub;s++)
			vi.push_back(sum);
	}
}
void efficiency(int cl,int ml,int col,int row)
{
	double ef;
	ef=1-(double)cl/(col*row*ml);
	cout<<"此游程碼的編碼效率為:"<<ef<<endl;
}
int main()
{
	int n=0;
	cout<<"請輸入灰度值：";
	cin>>n;
	int cor,row;
	int j,k;
	int judge=0;
	int code_judge=0;
	vector<data>vd;
	vector<data>vh;
	vector<char>cd;
	vector<rle>re;
	vector<char> vc;
	vector<int> vi;
	Creadmz(n,vd,0);
	cout<<"灰度級編碼結果："<<endl;
	print(vd);
	while(judge==0&&!read(re,n,cor,row))
	{
		cout<<"你輸入的中的灰度值不符合要求請輸入'0'后重新輸入,或輸入'1'退出."<<endl;
		cin>>judge;
			if(judge!=0) exit(0);
	}
	j=get_gd(cor);
	k=get_gd(n);
	Creadmz(cor,vh,1);
	cout<<"元素個數編碼結果："<<endl;
	print(vh);
	Encode(re,vd,vh,cd);
	cout<<"統計結果:";
	print1(re);
	cout<<endl;
	cout<<"編碼結果:"<<endl;
	print2(cd,(j+k)*cor);
	efficiency(cd.size(),k,cor,row);
	cout<<"你是否想要進行解碼演示,如果是請輸入'1',否則輸入'0'."<<endl;
	cin>>code_judge;
	if(code_judge==1)
	{
		while(!read1(vc,j+k)&&code_judge==1){}
			coding(vc,vi,k,j);
		print2(vi,cor);
	}
	return 0;
}
/*
1 1 1 1 1 1 1
2 1 3 7 7 7 7
6 5 4 3 6 4 4
1 2 3 7 7 5 6
3 3 3 3 4 4 4
6 5 4 1 2 5 3
6 5 7 4 1 2 3

00111001000000100001100011101111000010100010000001100011000010000100100001000001
10001110011010001100000110111000101100001010001000000010000100001010000110001100
00101000111000100000001000010000011000
*/