#include<stdio.h>

typedef struct
{
    int r, c, v;
} term;

/* Simple Transpose Method */
void simpleTranspose(term a[], term t[])
{
    int i, j, k = 1;
    int numrows = a[0].r;
    int numcols = a[0].c;
    int numterms = a[0].v;

    t[0].r = numcols;
    t[0].c = numrows;
    t[0].v = numterms;

    if (numterms > 0)
    {
        for (i = 0; i < numcols; i++)
        {
            for (j = 1; j <= numterms; j++)
            {
                if (a[j].c == i)
                {
                    t[k].r = a[j].c;
                    t[k].c = a[j].r;
                    t[k].v = a[j].v;
                    k++;
                }
            }
        }
    }

    printf("\n=== SIMPLE TRANSPOSE RESULT ===\n");
    printf("Row\tCol\tVal\n");
    for (i = 1; i <= t[0].v; i++)
        printf("%d\t%d\t%d\n", t[i].r, t[i].c, t[i].v);
}

/* Fast Transpose Method */
void fastTranspose(term a[], term t[])
{
    int rt[20], sp[20];
    int i, j;
    int numcols = a[0].c;
    int numterms = a[0].v;

    t[0].r = numcols;
    t[0].c = a[0].r;
    t[0].v = numterms;

    if (numterms > 0)
    {
        for (i = 0; i < numcols; i++)
            rt[i] = 0;

        for (i = 1; i <= numterms; i++)
            rt[a[i].c]++;

        sp[0] = 1;
        for (i = 1; i < numcols; i++)
            sp[i] = sp[i - 1] + rt[i - 1];

        for (i = 1; i <= numterms; i++)
        {
            j = sp[a[i].c]++;
            t[j].r = a[i].c;
            t[j].c = a[i].r;
            t[j].v = a[i].v;
        }
    }

    printf("\n=== FAST TRANSPOSE RESULT ===\n");
    printf("Row\tCol\tVal\n");
    for (i = 1; i <= t[0].v; i++)
        printf("%d\t%d\t%d\n", t[i].r, t[i].c, t[i].v);
}

int main()
{
    term a[20], ts[20], tf[20];
    int i;

    printf("=== SPARSE MATRIX TRANSPOSE ===\n");

    printf("\nEnter number of rows and columns: ");
    scanf("%d%d", &a[0].r, &a[0].c);

    printf("Enter number of non-zero values: ");
    scanf("%d", &a[0].v);

    for (i = 1; i <= a[0].v; i++)
    {
        printf("Enter %dth (row col value): ", i);
        scanf("%d%d%d", &a[i].r, &a[i].c, &a[i].v);
    }

    printf("\n=== ORIGINAL SPARSE MATRIX ===\n");
    printf("Row\tCol\tVal\n");
    for (i = 1; i <= a[0].v; i++)
        printf("%d\t%d\t%d\n", a[i].r, a[i].c, a[i].v);

    /* Simple method output */
    simpleTranspose(a, ts);

    /* Fast method output */
    fastTranspose(a, tf);
    return 0;
}