# C program of Matrix Transpose and Matrix Multiplication

//Code for Program of matrix transpose and matrix multiplication in C Programming

#include <stdio.h>

#define M 10
#define P 7
#define N 8

void ftrans( int a[][3], int b[][3] ) {
/*
* finds fast-transpose of a in b.
*/
int t[P+1];
int i, j, n, terms;
int temp, temp2;

n = a[0][1];
terms = a[0][2];
b[0][0] = n;
b[0][1] = a[0][0];
b[0][2] = terms;

if( terms <= 0 )
return;
for( i=0; i<n; ++i )
t[i] = 0;
for( i=1; i<=terms; ++i )
t[a[i][1]]++;
temp = t[0];
t[0] = 1;
for( i=1; i<n; ++i ) {
temp2 = t[i], t[i] = t[i-1]+temp, temp = temp2;
//printf( "t[%d] = %d.\n", i, t[i] );
}
for( i=1; i<=terms; ++i ) {
j = t[a[i][1]];
b[j][0] = a[i][1], b[j][1] = a[i][0], b[j][2] = a[i][2];
t[a[i][1]] = j+1;
}
}

void printMatrix( int a[][3] ) {
/*
* prints the matrix in the form of 3-tuples.
*/
int i;
int nterms = a[0][2];

printf( "rows=%d cols=%d vals=%d.\n", a[0][0], a[0][1], a[0][2] );
for( i=1; i<=nterms; ++i )
printf( "a[%d][%d] = %d.\n", a[i][0], a[i][1], a[i][2] );
putchar( '\n' );
}

void insert( int c[][3], int row, int col, int val ) {
/*
* insert or add the triplet (row,col,val) in c.
* update c[0][2] is necessary.
*/
int i, terms = c[0][2];

for( i=1; i<=terms && c[i][0]<row; ++i )
;
for( ; i<=terms && c[i][1]<col; ++i )
;
if( i<=terms && c[i][1] == col )    // already inserted.
c[i][2] += val;
else {                    // a new entry should be inserted at i.
c[i][0] = row; c[i][1] = col; c[i][2] = val;
c[0][2]++;
}
}

void mmult( int a[][3], int b[][3], int c[][3] ) {
/*
* c = a*b;
*/
int i, j, mn = M*N;
int aterms = a[0][2], bterms = b[0][2];
int rowsofb = b[0][0];
int *t = (int *)malloc( rowsofb*sizeof(int) );
int temp, temp2;
int arow, acol, aval, brow, browstart, browend;

c[0][0] = a[0][0];
c[0][1] = b[0][1];

// init c.for( i=0; i<=mn; ++i )
c[i][2] = 0;

// fill t[] : t[i] points to row of b where actual row i starts.// last+1 entry is also maintained for easing loops.for( i=0; i<=rowsofb; ++i )
t[i] = 0;
for( i=1; i<=bterms; ++i )
t[b[i][0]]++;
temp = t[0];
t[0] = 1;
for( i=1; i<=rowsofb; ++i )
temp2 = t[i], t[i] = t[i-1]+temp, temp = temp2;

// now start mult.for( i=1; i<=aterms; ++i ) {
arow = a[i][0]; acol = a[i][1]; aval = a[i][2];
brow = acol;
browstart = t[brow]; browend = t[brow+1];
for( j=browstart; j<browend; ++j )
insert( c, arow, b[j][1], aval*b[j][2] );
}
}

int main() {
int a[][3] =    {
{4,2,3},
{0,1,2},
{1,0,3},
{3,1,4}
};
int b[][3] =    {
{2,3,3},
{0,2,5},
{1,0,7},
{1,1,6}
};
int c[M*N+1][3];

printMatrix(a);
//ftrans( a, b );
printMatrix(b);
mmult( a, b, c );
printMatrix(c);

return 0;
}