#ifndef sparematrix_H_H_H
#define sparematrix_H_H_H
#include <iostream.h>
template<class R>
struct term
{
	int row,col;
	R value;
};


////////
//行三元組
////////
template<class R>
class r_SM
{
	private:
		term<R> *mat;
		int mr,mc;
		int length;	
		int pose(term<R> &ti){return (ti.row*mc+ti.col);};
        void SetT(term<R> *ti,int co,int _mr,int _mc);
	public:
		r_SM(int _mr,int _mc):mr(_mr),mc(_mc){mat=NULL;length=0;};
        r_SM():mr(0),mc(0){mat=NULL;length=0;};
//		r_SM(int size){mat=new term<R>[size];};
		~r_SM(){};
		void Create(int _mr,int _mc);  
		void Distory(){delete []mat;};
		void Add(r_SM<R> &B,r_SM<R> &C);
//		void Mul(r_SM<R> &B,r_SM<R> &C);
		void Transpose1(r_SM<R> &B);
		void Transpose2(r_SM<R> &B);
		void Transpose3(r_SM<R> &B);
		operator=(term<R> &b)
		{col=b.col;row=b.row;value=b.value;};
		void output(ostream &out)
		{int i;
		for(i=0;i<length;i++)
			out<<mat[i].row<<mat[i].col<<" "<<mat[i].value<<endl;
		};
};
template<class R>
void r_SM<R>::SetT(term<R> *ti,int co,int _mr,int _mc)
{
	mat=new term<R>[co];
	length=co;
	mr=_mr;mc=_mc;
	for(int t=0;t<co;t++)
	{mat[t]=ti[t];}
}
template<class R>
void r_SM<R>::Add(r_SM<R> &B,r_SM<R> &C)
{
term<R> *pb=new term<R>[length*B.length];
int count;
     if(mr!=B.mr||mc!=B.mc)
		 cout<<"行、列不同不能相加"<<endl;
	if(mr==B.mr&&mc==B.mc)
	{
	
	int i=0,j=0,m=0;
	int T,t;
	while(i<length)
	{
		T=pose(mat[i]);t=pose(B.mat[j]);
         if(T<t)
		 {pb[m++]=mat[i++];}
		 if(T==t) 
		 {
		 pb[m].row=mat[i].row;
		 pb[m].col=mat[i].col;
		 pb[m++].value=B.mat[j++].value+mat[i++].value;
		 }
		 while(T>t&&j<B.length)
		 {pb[m++]=B.mat[j++];t=pose(B.mat[j]);}
		if(j==B.length) break;
	}
	while(j<B.length) pb[m++]=B.mat[j++];
	while(i<length) pb[m++]=mat[i++];
	count=m;
	}
    C.SetT(pb,count,mr,mc);
	delete []pb;
}
template<class R>
void r_SM<R>::Create(int _mr,int _mc)
{
	mr=_mr;
	mc=_mc;
	int count=0;
    R *pd=new R[_mr*_mc];
	term<R> *tm=new term<R>[_mr*_mc];
	cout<<"intput the data:"<<endl;
	int i,j,m=0;
	for(i=0;i<mr;i++)
		for(j=0;j<mc;j++)
		{
//			cout<<i<<j<<":";
			cin>>pd[i*mc+j];
			if(pd[i*mc+j]!=0)
			{
			  count++;tm[m].row=i;tm[m].col=j;tm[m].value=pd[i*mc+j];
              m++;
			}
					length=count;
		}
mat=new term<R>[count];
for(m=0;m<count;m++)
{
		mat[m].row=tm[m].row;
		mat[m].col=tm[m].col;
		mat[m].value=tm[m].value;	
}
//for(m=0;m<count;m++)cout<<mat[m].row<<mat[m].col<<mat[m].value<<endl;
delete []tm;
}
template<class R>
void r_SM<R>::Transpose1(r_SM<R> &B)
{
	B.mat=new term<R>[length];
//	term<R> temp;
	int t=length;
	int i,j;
	for(i=0;i<t;i++)
	{
	   B.mat[i].row=mat[i].col;
       B.mat[i].col=mat[i].row;
	   B.mat[i].value=mat[i].value;
	}
	B.length=length;
	B.mc=mc;B.mr=mr;
	term<R> ti;
	for(i=1;i<t;i++)
	{
      j=i;
      ti=B.mat[i];
	  while(j>0&&pose(ti)<pose(B.mat[j-1]))
	  {
		  B.mat[j]=B.mat[j-1];
	      j--;
	  }
	  B.mat[j]=ti;
	}
}
template<class R>
void r_SM<R>::Transpose2(r_SM<R> &B)
{
	B.mat=new term<R>[length];
	B.length=length;
	B.mc=mc;B.mr=mr;	
	int k=0;
	int i,j;
	for(i=0;i<mc;i++)
	{for(j=0;j<length;j++)
		{if(mat[j].col==i)
	   B.mat[k].row=mat[j].col;
       B.mat[k].col=mat[j].row;
	   B.mat[k++].value=mat[j].value;}
	}
			
}
template<class R>
void r_SM<R>::Transpose3(r_SM<R> &B)
{
	int *num=new int[mc];
	int *k=new int[mc];
	int i,j;
    B.mat=new term<R>[length];
	B.length=length;
	B.mc=mc;B.mr=mr;
	if(length>0)
	{
		for(i=0;i<mc;i++) num[i]=0;
		for(i=0;i<length;i++) num[mat[i].col]++;
		k[0]=0;
		for(i=1;i<mc;i++) k[i]=k[i-1]+num[i-1];
		for(i=0;i<length;i++)
		{
		    j=k[mat[i].col]++;
	        B.mat[j].row=mat[i].col;
            B.mat[j].col=mat[i].row;
	        B.mat[j].value=mat[i].value;
		}
	}
}

#endif