#include <stdio.h>
#include <time.h>

typedef struct {
   int val;
   int idx;
} element;

typedef struct {
   int dim;
   int *nent;
   element **data;
} matrix;

matrix genMatrix ( int n , int l )
{
   int i, j, k, s, t, done;
   matrix M;
   element E;

   M.dim = n;
   M.data = (element **)malloc(n * sizeof(element *));
   M.nent = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
      s = 1 + rand() % l;
      M.nent[i] = s;
      M.data[i] = (element *)malloc(s * sizeof(element));
      for (j=0; j<s; ++j) {
         do {
            t = rand() % n;
            done = 1;
            for (k=0; k<j; ++k) if (M.data[i][k].idx == t) done = 0;
         } while (!done);
         M.data[i][j].idx = t;
         M.data[i][j].val = 1 + rand() % 9;
      }
      for (j=s-2; j>=0; --j) for (k=0; k<=j; ++k) {
         if (M.data[i][k].idx > M.data[i][k+1].idx) {
            E = M.data[i][k];
            M.data[i][k] = M.data[i][k+1];
            M.data[i][k+1] = E;
         }
      }
   }
   return M;
}

void addMatrix ( matrix A , matrix B , int l )
{
   int i, j, k, s, t;
   element *T;

   if (A.dim != B.dim) {
      fprintf(stderr,"Error : incompatible dimension\n");
      return;
   }

   T = (element *)malloc(2*l*sizeof(element));
   for (i=0; i<A.dim; ++i) {
      j = s = t = 0;
      while ((s < A.nent[i]) || (t < B.nent[i])) {
         if (s >= A.nent[i]) T[j] = B.data[i][t++];
         else if (t >= B.nent[i]) T[j] = A.data[i][s++];
         else if (A.data[i][s].idx < B.data[i][t].idx) T[j] = A.data[i][s++];
         else if (A.data[i][s].idx > B.data[i][t].idx) T[j] = B.data[i][t++];
         else {
            T[j].idx = A.data[i][s].idx;
            T[j].val = A.data[i][s++].val + B.data[i][t++].val;
         }
         ++j;
      }
      A.nent[i] = j;
      free(A.data[i]);
      A.data[i] = (element *)malloc(j * sizeof(element));
      while (j>=1) { --j; A.data[i][j] = T[j]; }
   }
   free(T);
}

void prnMatrix ( matrix A )
{
   int i,j;

   for (i=0; i<A.dim; ++i) {
      printf("Row %4d : ", i);
      for (j=0; j<A.nent[i]; ++j)
         printf("(%2d,%2d) ",A.data[i][j].val,A.data[i][j].idx);
      printf("\n");
   }
   printf("\n");
}

int main ()
{
   matrix A, B;

   srand((unsigned int)time(NULL));

   A = genMatrix(10,5); printf("Matrix A\n"); prnMatrix(A);
   B = genMatrix(10,5); printf("Matrix B\n"); prnMatrix(B);
   addMatrix(A,B,5); printf("Matrix A+B\n"); prnMatrix(A);
}