#include <stdio.h>

#define MAX_COL 100

typedef struct {
    int row;
    int col;
    int value;
} term;


/* 빠른 전치 */
void fast_transpose(term a[], term b[])
{
    int row_terms[MAX_COL];
    int starting_pos[MAX_COL];

    int i, j;
    int num_cols = a[0].col;
    int num_terms = a[0].value;

    /* 1. 전치 후 행렬 정보 */
    // b[0].row = num_cols;
    b[0].row = a[0].col;
    b[0].col = a[0].row;
    b[0].value = a[0].value;
    // b[0].value = num_terms;


    // if (num_terms > 0) {
    if (a[0].value > 0) {

        /* 2. row_terms 초기화 */
        // for (i = 0; i < num_cols; i++)
        for (i = 0; i < a[0].col; i++)
            row_terms[i] = 0;


        /* 3. 각 열에 값이 몇 개 있는지 계산 */
        for (i = 1; i <= num_terms; i++)
        for (i = 1; i <= a[0].value; i++)
            row_terms[a[i].col]++;


        /* 4. 각 열의 시작 위치 계산 */
        starting_pos[0] = 1;

        // for (i = 1; i < num_cols; i++)
        for (i = 1; i < a[0].col; i++)
            starting_pos[i]
                = starting_pos[i - 1] + row_terms[i - 1];


        /* 5. 실제 전치 */
        // for (i = 1; i <= num_terms; i++) {
        for (i = 1; i <= a[0].value; i++) {

            j = starting_pos[a[i].col]++;

            b[j].row = a[i].col;
            b[j].col = a[i].row;
            b[j].value = a[i].value;
        }
    }
}


int main()
{
    /* 첨부 그림의 희소행렬 A */
    term a[] = {
        {6, 6, 8},      // a[0] : 6행 6열, 실제 값 8개
        {0, 0, 15},
        {0, 3, 22},
        {0, 5, -15},
        {1, 1, 11},
        {1, 2, 3},
        {2, 3, -6},
        {4, 0, 91},
        {5, 2, 28}
    };

    term b[100];

    /* 빠른 전치 함수 호출 */
    fast_transpose(a, b);


    /* 결과 출력 */
    printf("   row col value\n");

    for (int i = 0; i <= b[0].value; i++) {
        printf("b[%d] %3d %3d %5d\n",
               i,
               b[i].row,
               b[i].col,
               b[i].value);
    }

    return 0;
}