#include<malloc.h>
#include<stdio.h>
#define MAX 9

int getCnt(int p[][3],int r,int c);
int** getSparse(int cnt);
int** consSparse(int mat[][3],int r,int c);
void fillSparse(int mat[][3],int r,int c,int **sp,int cnt);
void print(int mat[][3],int r,int c);
void printSparse(int **sp,int cnt);
int** ConsAddSparse(int mat1[][3],int mat2[][3],int r,int c,int *num);
int** ConsProdSparse(int mat1[][3],int mat2[][3],int r,int c,int *num);

int main()
{
    int a[3][3] = {{1,0,7},{0,0,8},{9,0,0}};
    int b[3][3] = {{0,0,8},{1,0,3},{0,4,5}};

    int **aS,**bS,**sum,**prod,cnt=0;
//Print A and its Sparse

        print(a,3,3);
        printf("\n------ \n");
        print(b,3,3);
        
    //sum = ConsAddSparse(a,b,3,3,&cnt);
    prod = ConsProdSparse(a,b,3,3,&cnt);
    getchar();
    return 0;
}


int getCnt(int p[][3],int r,int c)
{
    int cnt = 0;
    for(int i=0;i<r;i++)
    {
     for(int j=0;j<c;j++)
       if(p[i][j] != 0 )
         cnt++;        
    }
    return cnt;
}

int** getSparse(int cnt)
{
    int **sp,i=0,j=0;
    sp = (int**) malloc(sizeof(int) * cnt);
    for(i=0;i<cnt;i++)
            sp[i] = (int*)malloc(sizeof(int) * 3);
            
    for(i=0;i<cnt;i++)
            {
                for(j=0;j<3;j++)
                  sp[i][j] = 0;
            }
     printf("\n\t Init Sparse Filled..\n");        
    return sp;
}

void fillSparse(int mat[][3],int r,int c,int** sp,int cnt)
{
     int flag=0,ind =0;
     for(int i=0;i<r;i++)
      {
        for(int j=0;j<c;j++)
        {
          if(mat[i][j] != 0 )
           {
             sp[ind][0] = i;
             sp[ind][1] = j;
             sp[ind][2] = mat[i][j];
             ind++;
           }
           if(ind >= cnt)
            {
            flag = 1;
            break;
            } 
        } 
        if(flag == 1)
          break;
      }
      printf("\n\t Sparse Filled..\n");
      return;
}


int** consSparse(int mat[][3],int r,int c)
{
      int cnt = getCnt(mat,r,c);
      int **sp;
      sp = getSparse(cnt);
      
      printf(" \n Cnt =  %d \n",cnt);
      fillSparse(mat,r,c,sp,cnt);
      printSparse(sp,cnt);
}

void printSparse(int **sp,int cnt)
{
 printf("\n-------------------\n");
 for(int i=0;i<cnt;i++)
  {
    for(int j=0;j<3;j++)
      printf("%d ",sp[i][j]);
    printf("\n");
  }    
}

void print(int mat[][3],int r,int c)
{
 for(int i=0;i<r;i++)
  {
    for(int j=0;j<c;j++)
      printf("%d ",mat[i][j]);
    printf("\n");
  }    
}

int** ConsAddSparse(int mat1[][3],int mat2[][3],int r,int c,int *num)
{
       int cnt1 = getCnt(mat1,r,c);
       int cnt2 = getCnt(mat2,r,c);
       
       int **asp,**bsp,**sum,k=0,ind1=0,ind2=0;
       
       printf(" \n Cnt1 =  %d \n",cnt1);
       printf(" \n Cnt2 =  %d \n",cnt2);
       
       asp = getSparse(cnt1);
       bsp = getSparse(cnt2);
      fillSparse(mat1,r,c,asp,cnt1);
      fillSparse(mat2,r,c,bsp,cnt2);

      printSparse(asp,cnt1);
      printSparse(bsp,cnt2);
       sum = getSparse(cnt1+cnt2);
             
      //Check for Common i and j
      ind1 = 0;
      ind2 = 0;
      k = 0;
      while(1)
      {
           printf("\n\t\tSt : Ind1 : %d  Ind2 : %d \n",ind1,ind2);
           if((ind1 == cnt1) & (ind2 == cnt2))
              break;
           else if ((ind1 >= cnt1) && (ind2 < cnt2) )
             {
             printf("\n\t\t >> Mat 2 %d ",cnt2);
                   for(;ind2 != cnt2;ind2++)
                   {                   
                      sum[k][0] = bsp[ind2][0];
                      sum[k][1] = bsp[ind2][1];
                      sum[k][2] = bsp[ind2][2];
                      k++;
                   }
                   break;
              }
           else if ((ind2 >= cnt2) && (ind1 < cnt1) )
             {
                   printf("\n\t\t >> Mat 1 %d ",cnt1);
                   for(;ind1<cnt1;ind1++)
                   {
                      sum[k][0] = asp[ind1][0];
                      sum[k][1] = asp[ind1][1];
                      sum[k][2] = asp[ind1][2];
                      k++;
                   }
                   break;
             } 
           else
           {   
            if((asp[ind1][0] ==  bsp[ind2][0]) && (asp[ind1][1] ==  bsp[ind2][1]))
              {
                sum[k][0] = asp[ind1][0];
                sum[k][1] = asp[ind1][1];
                sum[k][2] = asp[ind1][2] + bsp[ind2][2];
                ind1++;
                ind2++;
                k++;
              }
             else if( (asp[ind1][0] <  bsp[ind2][0]) || ( (asp[ind1][0] ==  bsp[ind2][0]) && (asp[ind1][1] <  bsp[ind2][1]) ) )
             {
                sum[k][0] = asp[ind1][0];
                sum[k][1] = asp[ind1][1];
                sum[k][2] = asp[ind1][2];
                ind1++;
                k++;
             }
             else if( (asp[ind1][0] >  bsp[ind2][0]) || ( (asp[ind1][0] ==  bsp[ind2][0]) && (asp[ind1][1] >  bsp[ind2][1]) ) )
             {
                sum[k][0] = bsp[ind2][0];
                sum[k][1] = bsp[ind2][1];
                sum[k][2] = bsp[ind2][2];
                ind2++;
                k++;
             }
           }
           printf("\n\t\t\tEnd : Ind1 : %d  Ind2 : %d \n",ind1,ind2);     
      }     
      printSparse(sum,k);
      return sum;
}

int** ConsProdSparse(int mat1[][3],int mat2[][3],int r,int c,int *num)
{
      int cnt1 = getCnt(mat1,r,c);
      int cnt2 = getCnt(mat2,r,c);
       
       int **asp,**bsp,**prod,flag =0,k=0,i=0,j=0,l;
       
       printf(" \n Cnt1 =  %d \n",cnt1);
       printf(" \n Cnt2 =  %d \n",cnt2);
       
       asp = getSparse(cnt1);
       bsp = getSparse(cnt2);
       
      fillSparse(mat1,r,c,asp,cnt1);
      fillSparse(mat2,r,c,bsp,cnt2);

      printSparse(asp,cnt1);
      printSparse(bsp,cnt2);
      
      prod = getSparse(MAX);
       
      for(i=0;i<cnt1;i++)
       {
            for(j=0;j<cnt2;j++)
            {
               if (asp[i][1] == bsp[j][0])
                  {
                    flag = 0;
                    for(l=0;l<k;l++)
                      {
                         if((prod[l][0] == asp[i][0]) && (prod[l][1] == bsp[j][1]))
                           {
                             flag = 1;
                             break;          
                           }
                      }
                      
                    if(!flag)
                      {
                        prod[k][0] = asp[i][0];
                        prod[k][1] = bsp[j][1];
                        prod[k][2] = (asp[i][2] * bsp[j][5]);
                        k++;
                      } 
                    else
                      prod[l][2] += (asp[i][2] * bsp[j][2]);
                  }
            }
       }
      printSparse(prod,k);
      return prod;
}