/******************************************
   ADDITION & TRANSPOSE OF SPARSE MATRIX
	Gaurang Sinha
	    Visit
	http://gaurang.cjb.net
	    -OR-
	http://gaurang85.tripod.com
*******************************************/
#include<stdio.h>
#include<conio.h>

void check(int row,int col,int d);

int flg[20][20],flag,add[20][3];
int pos[]={1,1},term[20],poss[20];

int main()
{
int matrix[2][10][10],spa[2][20][3],i,j,k,r,c,s=0,tmp=1,count[]={0,0},t;
while(s!=3)
{
//////////////////////REFRESH
/*pos[0]=1;pos[1]=1;
s=0;tmp=1;
for(i=0;i<20;i++)
	for(j=0;j<20;j++)
		flg[i][j]=0;
for(i=0;i<20;i++)
	for(j=0;j<=2;j++)
		add[i][j]=0;*/
/////////////////////////////
clrscr();
printf("\n \t\tMENU");
printf("\n 1. Find Transpose Of Sparse Matrix");
printf("\n 2. Add To Sparse Matrices");
printf("\n 3. Exit");
printf("\n ::> ");
scanf("%d",&s);
if(s==3)return 0;
printf("\n Enter Rows And Columns : ");
scanf("%d%d",&r,&c);
//Enter Matrices
for(k=0;k<s;k++)
{
	printf("\nEnter %d Matrix\n",k+1);
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
		{
			printf("Enter %d %d : ",i+1,j+1);
			scanf("%d",&matrix[k][i][j]);
		}
	}
}
//Display Matrices
for(k=0;k<s;k++)
{
	printf("\nMATRIX - %d",k+1);
	for(i=0;i<r;i++)
	{
		printf("\n");
		for(j=0;j<c;j++)
		{
			printf(" %d ",matrix[k][i][j]);
		}
	}
}
//Finding Sparse Matrix / Representation
for(k=0;k<s;k++)
{
	spa[k][0][0]=r;
	spa[k][0][1]=c;
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
		{
			if(matrix[k][i][j]!=0)
			{
				spa[k][pos[k]][0]=i;
				spa[k][pos[k]][1]=j;
				spa[k][pos[k]][2]=matrix[k][i][j];
				pos[k]++;
			}
		}
	}
	spa[k][0][2]=pos[k]-1;
}
//Displaying Sparse
for(k=0;k<s;k++)
{
	printf("\nMatrix %d Sparse Representation",k+1);
	printf("\n Row\tCol\tValue");
	for(i=0;i<pos[k];i++)
	{
		printf("\n");
		for(j=0;j<=2;j++)
		{
			printf(" %d\t",spa[k][i][j]);
		}
	}
}
//Adding Sparse Matrix
if(s==2)
{
	add[0][0]=r;
	add[0][1]=c;
	for(i=1;i<pos[0];i++)
	{
		for(j=1;j<pos[1];j++)
		{
			if(spa[0][i][0]==spa[1][j][0]&&spa[0][i][1]==spa[1][j][1])
			{
				check(spa[0][i][0],spa[0][i][1],1);
				if(flag==1)
				{
					add[tmp][0]=spa[0][i][0];
					add[tmp][1]=spa[0][i][1];
					add[tmp][2]=spa[0][i][2]+spa[1][j][2];
					tmp++;
				}
			}
		}
	}
	for(k=0;k<s;k++)
	{
		for(i=1;i<pos[k];i++)
		{
			check(spa[k][i][0],spa[k][i][1],1);
			if(flag==1)
			{
				add[tmp][0]=spa[k][i][0];
				add[tmp][1]=spa[k][i][1];
				add[tmp][2]=spa[k][i][2];
				tmp++;
			}
		}
	}
	add[0][2]=tmp-1;
	//Sorting
	for(i=1;i<tmp;i++)
	{
		for(j=1;j<tmp;j++)
		{
			if(add[i][0]<add[j][0])
			{
				for(k=0;k<=2;k++)
				{
					t=add[i][k];
					add[i][k]=add[j][k];
					add[j][k]=t;
				}
			}
		}
	}
	printf("\nAdded Sparse Matrix");
	printf("\n Row\tCol\tValue");
	for(i=0;i<tmp;i++)
	{
		printf("\n");
		for(j=0;j<=2;j++)
		{
			printf(" %d\t",add[i][j]);
		}
	}
}
//Transpose Of A Matrix
if(s==1)
{
	printf("\n\n \tMENU");
	printf("\n 1. Fast Transpose");
	printf("\n 2. Normal Transpose");
	printf("\n ::>");
	scanf("%d",&s);
if(s==2)	//Normal Transpose
{
	for(i=0;i<spa[0][0][2]+1;i++)
	{
		t=spa[0][i][0];
		spa[0][i][0]=spa[0][i][1];
		spa[0][i][1]=t;
	}
	//Sorting Numbers
	for(i=1;i<pos[0];i++)
	{
		for(j=1;j<pos[0];j++)
		{
			if(spa[0][i][0]<spa[0][j][0])
			{
				for(k=0;k<=2;k++)
				{
					t=spa[0][i][k];
					spa[0][i][k]=spa[0][j][k];
					spa[0][j][k]=t;
				}
			}
		}
	}
	printf("\n Normal Transpose\n");
	printf("\n Row\tCol\tValue");
	for(i=0;i<pos[0];i++)
	{
		printf("\n");
		for(j=0;j<=2;j++)
		{
			printf(" %d\t",spa[0][i][j]);
		}
	}
}
if(s==1)	//Fast Transpose
{
	for(i=0;i<pos[0];i++)
	{
		term[spa[0][i][1]] ++;
	}
	poss[0] = 1;
	for(i=1;i<=c;i++)
	{
		poss[i] = poss[i-1] + term[i-1];
	}
	for(i=0;i<pos[0];i++)
	{
		j = poss[spa[0][i][1]];
		spa[1][j][0] = spa[0][i][1];
		spa[1][j][1] = spa[0][i][0];
		spa[1][j][2] = spa[0][i][2];
		poss[spa[0][i][1]] = j+1;
	}
	spa[1][0][0] = spa[0][0][1];
	spa[1][0][1] = spa[0][0][0];
	spa[1][0][2] = spa[0][0][2];
	printf("\n\n Fast Transpose : \n");
	printf("\n Row\tCol\tValue\n");
	for(i=0;i<pos[0];i++)
	{
		for(j=0;j<=2;j++)
		{
			printf(" %d\t", spa[1][i][j]);
		}
		printf("\n");
	}
}
}
getch();
}
return 0;
}

void check(int row,int col,int d)
{
	if(d==0)
	{
		flg[row][col]=1;
	}
	if(d==1)
	{
		if(flg[row][col]==1)
		{
			flag=0;
		}
		else
		{
			flag=1;
			flg[row][col]=1;
		}
	}
}