/* Routines on Sparse Matrices  to perform addition and  multiplication of two sparse matrices,  and

to find  transpose of a given matrix*/

#include<iostream.h>

#include<stdlib.h>

class SparseMatrix

{

 int r,c;

 int **ele;

 public:

 SparseMatrix() { }

 SparseMatrix(int , int);

 void readSparseMatrix(int , int, int);

 void printSparseMatrix();

 void addSparseMatrices(SparseMatrix *, SparseMatrix *);

 void mulSparseMatrices(SparseMatrix *, SparseMatrix *);

 void transpose(SparseMatrix *);

};

void SparseMatrix :: mulSparseMatrices(SparseMatrix *S1, SparseMatrix *S2)

{

    int i,j,k, fnv, snv, tnv, temp, temp1, temp2,m;

    fnv=S1->ele[2][0];

    snv=S2->ele[2][0];

    tnv=fnv*snv;

    k=0;

    for(i=0;i<=tnv;i++) { ele[0][i]=-1; ele[1][i]=-1; ele[2][i]=-1; }

    for(i=1;i<=fnv;i++)

    {

            temp=S1->ele[1][i];

            for(j=1;j<=snv;j++)

            {

                     if(temp==S2->ele[0][j])

                     {

                            temp1=S1->ele[0][i]; temp2=S2->ele[1][j];

                            m=1;

                            while((m<=k)&&!((temp1==ele[0][m])&&(temp2==ele[1][m])))

                            {

                                            m++;

                                            //cout<<"\n hello";

                            }

                            if(m>k) {

                            k++;

                            ele[0][k]=S1->ele[0][i];

                            ele[1][k]=S2->ele[1][j];

                            ele[2][k]=(S1->ele[2][i])*(S2->ele[2][j]);

                            }

                            else

                            {

                            //ele[0][m]=S1->ele[0][i];

                            //ele[1][m]=S2->ele[1][j];

                            ele[2][m]=ele[2][m] + ((S1->ele[2][i])*(S2->ele[2][j]));

                            }

             }

            }

    }

    for(i=k+1; i<=tnv; i++) { delete(ele[i]); }

    ele[0][0]=S1->ele[0][0];

    ele[1][0]=S2->ele[1][0];

    ele[2][0]=k;

}

void SparseMatrix :: transpose(SparseMatrix *S1)

{

 int temp1, temp2,temp3, i,j, nv;

 nv=S1->ele[2][0];

    for(i=0;i<=nv;i++)

    {

            ele[0][i]= S1->ele[1][i];

            ele[1][i]= S1->ele[0][i];

            ele[2][i]= S1->ele[2][i];

    }

    /* Insertion Sort */

    for(i=2;i<=nv;i++)

    {

            temp1=ele[0][i];

            temp2=ele[1][i];

            temp3=ele[2][i];

     for(j=i-1; (j>=1)&&(temp1<ele[0][j]); j--)

     {

              ele[0][j+1]=ele[0][j];

              ele[1][j+1]=ele[1][j];

              ele[2][j+1]=ele[2][j];

     }

                    ele[0][j+1]=temp1;

                    ele[1][j+1]=temp2;

                    ele[2][j+1]=temp3;

    }

}

void SparseMatrix :: addSparseMatrices(SparseMatrix *S1, SparseMatrix *S2)

{

  int i, fnv, j,snv, k;

            fnv=S1->ele[2][0];

            snv=S2->ele[2][0];

            ele[0][0]=S1->ele[0][0];

            ele[1][0]=S1->ele[1][0];

             i=1; j=1; k=1;

             while((i<=fnv)&&(j<=snv))

             {

                      if((S1->ele[0][i])==(S2->ele[0][j]))

                      {

                                    ele[0][k]=S1->ele[0][i];

                                    if((S1->ele[1][i])==(S2->ele[1][j]))

                                    {

                                            ele[1][k]=S1->ele[1][i];

                                            ele[2][k]=(S1->ele[2][i])+(S2->ele[2][j]);

                                            i++; j++; k++;

                                    }

                                    else if((S1->ele[1][i])<(S2->ele[1][j]))

                                    {

                                              ele[1][k]=S1->ele[1][i];

                                              ele[2][k]=S1->ele[2][i];

                                              i++; k++;

                                    }

                                    else

                                    {

                                            ele[1][k]=S2->ele[1][j];

                                            ele[2][k]=S2->ele[2][j];

                                            j++; k++;

                                    }

                            }

                            else

                            {

                                    if((S1->ele[0][i])<(S2->ele[0][j]))

                                    {

                                              ele[0][k]=S1->ele[0][i];

                                              ele[1][k]=S1->ele[1][i];

                                              ele[2][k]=S1->ele[2][i];

                                              i++; k++;

                                    }

                                    else

                                    {

                                            ele[0][k]=S1->ele[0][j];

                                            ele[1][k]=S2->ele[1][j];

                                            ele[2][k]=S2->ele[2][j];

                                            j++; k++;

                                    }

                            }

             }

             while(j<=snv)

             {

                            ele[0][k]=S2->ele[0][j];

                            ele[1][k]=S2->ele[1][j];

                            ele[2][k]=S2->ele[2][j];

                            j++; k++;

             }

             while(i<=fnv)

             {

                            ele[0][k]=S1->ele[0][i];

                            ele[1][k]=S1->ele[1][i];

                            ele[2][k]=S1->ele[2][i];

                            i++; k++;

             }

             ele[2][0]=k-1;

             c=k;

}

SparseMatrix :: SparseMatrix(int m, int n)

{

    r=m; c=n;

    ele= new int *[m];

            for(int i=0;i<m;i++) { ele[i]= new int[n]; }

}

void SparseMatrix :: readSparseMatrix(int omr, int omc, int nov)

{

    int i,j;

                            ele[0][0]= omr; ele[1][0]= omc; ele[2][0]=nov;

                            for(j=1;j<=nov;j++)

                            {

                                    i=0;

                                            while(i<3)

                                            {

                                                    cout<<"\n enter element["<<i<<"]["<<j<<"]:";

                                                    cin>>ele[i][j];

                                                    i++;

                                            }

                            }

  }

void SparseMatrix :: printSparseMatrix()

{

    c=ele[2][0];

    for(int i=0;i<r;i++)

    {

            cout<<"\n";

            for(int j=0;j<=c;j++)

            {

              cout<<"\t"<<ele[i][j];

            }

    }

}