#include <malloc.h> // malloc(), free()
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;

struct Entry
{
    int row;
    int col;
    int value;
};

void readMatrix(struct Entry matrix[]);
int equalMatrix(const struct Entry A[], const struct Entry B[]);
void printMatrix(struct Entry matrix[]);
void transposeMatrix(const struct Entry A[], struct Entry B[]);
void multiplyMatrix(const struct Entry A[], const struct Entry B[], struct Entry C[]);

int main()
{
    struct Entry A[100]={0}, At[100]={0}, B[100]={0}, Bt[100]={0}, C[100]={0};

    struct Entry C0[] = {{5,3,7},{0,0,3},{0,1,-1},{0,2,5},{1,0,1},{1,2,2},{3,1,2},{4,2,-1}};
    struct Entry C1[] = {{3,3,7},{0,0,3},{0,1,2},{0,2,6},{1,0,3},{1,1,7},{1,2,5},{2,2,-2}};
    struct Entry C2[] = {{5,5,14}, {0,0,-1},{0,3,2},{1,0,9},{1,1,3},{2,0,-13},
                                   {2,1,-4},{2,3,6},{2,4,2},{3,0,-1},{3,1,1},
                                   {3,3,8},{4,0,10},{4,1,4},{4,4,-2}};
    readMatrix(A);
    A[A[0].value+1].row = -1; // extra entry for multiply()

    readMatrix(B);
    B[B[0].value+1].row = -1; // extra entry for multiply()

    if ((A[0].row != B[0].row)||(A[0].col != B[0].col))
    {
        cout << "Matrix A and B are not of the same dimension!\n";
        return 1;
    }

    cout << "\n";
    cout << "Matrix A:\n";
    printMatrix(A);

    cout << "Matrix B:\n";
    printMatrix(B);

    transposeMatrix(B, Bt);
    assert(equalMatrix(Bt, C0));
    cout << "Transpose Matrix B:\n";
    printMatrix(Bt);

    multiplyMatrix(A, Bt, C);
    assert(equalMatrix(C, C1));

    cout << "Matrix A * Matrix B':\n";
    printMatrix(C);

    transposeMatrix(A, At);
    cout << "Transpose Matrix A:\n";
    printMatrix(At);

    multiplyMatrix(At, B, C);
    assert(equalMatrix(C, C2));

    cout << "Matrix A' * Matrix B:\n";
    printMatrix(C);

    cin.get(); cin.get();
    return 0;
}

void readMatrix(struct Entry matrix[])
{
    int i;
    cin >> matrix[0].row >> matrix[0].col >> matrix[0].value;
    for (i=1; i<=matrix[0].value; i++)
        cin >> matrix[i].row >> matrix[i].col >> matrix[i].value;
}

void printMatrix(struct Entry matrix[])
{
    int i;
    cout << matrix[0].row << " * " << matrix[0].col << " matrix with "
         << matrix[0].value << " non-zero item:\n";
    for (i=1; i<=matrix[0].value; i++)
        cout << '<' << matrix[i].row << ',' << matrix[i].col << ':' << matrix[i].value << ">\n";
    cout << "====================\n";
}

int equalMatrix(const struct Entry A[], const struct Entry B[])
{
    int i;
    if ((A[0].row!=B[0].row)||(A[0].col!=B[0].col)||(A[0].value!=B[0].value))
        return 0;
    for (i=1; i<=A[0].value; i++)
        if ((A[i].row!=B[i].row)||(A[i].col!=B[i].col)||(A[i].value!=B[i].value))
            return 0;
    return 1;
}

void transposeMatrix(const struct Entry A[], struct Entry B[])
{
    int i, iB=0;
    vector<int> start(A[0].col+1);

    B[iB].row = A[0].col; B[iB].col = A[0].row; B[iB++].value = A[0].value;

    for (start[0]=1, i=1; i<=A[0].col; i++)
        start[i] = 0;
    for (i=1; i<=A[0].value; i++)
        start[A[i].col+1]++; // counting element's in a row
    for (i=1; i<=A[0].col; i++)
        start[i] += start[i-1]; // accumulating

    for (i=1; i<=A[0].value; i++)
    {
        iB = start[A[i].col]++;
        B[iB].row = A[i].col;
        B[iB].col = A[i].row;
        B[iB].value = A[i].value;
    }
    B[B[0].value+1].row = -1; // extra entry for multiply to test end of B1's row
}

void multiplyMatrix(const struct Entry A[], const struct Entry B[],
                    struct Entry C[])
{
    int iA, iC, iA1, iB1, iA1row, iB1row, sum;
    struct Entry *B1 = new struct Entry[B[0].value+2];

    transposeMatrix(B, B1);

    C[0].row = A[0].row;
    C[0].col = B[0].col;
    C[0].value = 0;
    iA = iC = 1;
    while (iA <= A[0].value)
    {
        sum = 0;
        iA1 = iA; iB1 = 1;
        iA1row = A[iA1].row; iB1row = B1[iB1].row;
        while (iB1 <= B1[0].value)
        {
            if (A[iA1].col == B1[iB1].col)
            {
                sum += A[iA1].value * B1[iB1].value;
                iA1++; iB1++;
            }
            else if (A[iA1].col > B1[iB1].col)
                iB1++;
            else // if (A[iA1].col < B1[iB1].col)
                iA1++;
            if (A[iA1].row != iA1row)
                while (B1[iB1].row == iB1row) iB1++;
            if (B1[iB1].row != iB1row)
            {
                if (iB1 <= B1[0].value)
                    iA1 = iA;
                else
                    while (A[iA1].row == iA1row) iA1++;
                if (sum!=0)
                {
                    C[0].value++;
                    C[iC].row = iA1row;
                    C[iC].col = iB1row;
                    C[iC++].value = sum;
                    sum = 0;
                }
                iB1row = B1[iB1].row;
            }
        }
        iA = iA1;
    }
    delete[] B1;
}