#include"iostream.h"
#include<iomanip.h>
#include"vector"
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)
{
	for(int i=0;i<cd.size();i++)
	{
		cout<<cd[i];
	}
	cout<<endl;
}
void read(vector<rle> &vr,int hd,int & cor)
{
	int row,acr;
	rle re;
	cout<<"請輸入矩陣的行列數(shù):"<<endl;
	cin>>row;
	cin>>acr;
	cor=acr;
	cout<<"請輸入灰度值矩陣:"<<endl;
	for(int i=0;i<row;i++)
	{
		int n;
		n=re.mz=0;
		if(n==re.mz)
		{	
			cin>>n;
		}
		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!=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);
		}
	}
}
bool read1(vector <char>& vc,int num)
{
	cout<<"請輸入你要解碼的序列(以'#'號結(jié)束):"<<endl;
	char ch;
	cin>>ch;
	while(ch!='#')
	{
		vc.push_back(ch);
		cin>>ch;
	}
	if(vc.size()%num!=0)
	{
		cout<<"你輸入的碼序列不正確請較正后再輸入。";
		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)
{
	int mc=0;
	int len=0;
	for(int i=0;i<vr.size();i++)
	{
		mc=find(vd,vr[i].mz);
		for(int j=vd[mc].code.size()-1;j>=0;j--)
			cd.push_back(vd[mc].code[j]);
		len=find(vh,vr[i].length);
		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);
	}
}
int main()
{
	int n=0;
	cout<<"請輸入灰度值：";
	cin>>n;
	int cor;
	int j,k;
	vector<data>vd;
	vector<data>vh;
	vector<char>cd;
	vector<rle>re;
	vector<char> vc;
	vector<int> vi;
	Creadmz(n,vd,0);
	print(vd);
	read(re,n,cor);
	j=get_gd(cor);
	k=get_gd(n);
	Creadmz(cor,vh,1);
	print(vh);
	print1(re);
	Encode(re,vd,vh,cd);
	cout<<endl;
	cout<<"編碼結(jié)果:"<<endl;
	print2(cd);
	if(read1(vc,j+k))
		coding(vc,vi,k,j);
	print2(vi);
	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
*/