// # CS1 u7_matrices.c
// Jonas Altrock <ew20b126@technikum-wien.at>
//
// [To overview](../).
//
// Alternative implementation with C99 dynamically sized arrays:
// [u7_matrices_c99.c](./u7_matrices_c99.html).
//
// [The whole source file `u7_matrices.c`.](./u7_matrices.c)
/* Compile with `clang -std=c99 -Wall -o u7_matrices u7_matrices.c` */
/* Test with `../checkproject u7_matrices` */

// Include C-libraries for input/output.
#include <stdio.h>
#include <stdlib.h>

// Exercise 7: Arrays
// ==================
//
// Implement matrix multiplication for square matrixes. You should first read
// the size of the matrixes and then enter the first matrix row-wise, then
// the second matrix. You may assume that the size will never exceed the value
// 50.
//
// ## Details
// If you are unfamiliar with matrices read below. In a nutshell, matrices are
// vectors extended by one additional dimension. They are of uttermost
// importance in mathematics and are part of the prerequisites for studies.
// The matrixes have the same number of rows and columns (ie square matrices).
//
// First, your program should read the size of the matrix (one single positive
// integer number that is guaranteed to be at least 1). Next, read the first
// matrix consisting of *size * size* integers, then the second one.
//
// Print the resulting matrix row-wise. Use integers and print them using
// `%3d` similar to exercise 5 (calendar).
//
// ### Hints
// You will definitely need multiple (possibly two-dimensional) arrays for this
// exercise. If necessary (C99 allows to set the bounds of an array at runtime)
// you may set an upper limit of 50 for the size, therefore, each matrix could
// simply be `matrix[50][50]`. The multiplication itself will consist of
// multiple nested loops.
//
// Use the convention that the row is the left index and the column the right
// one.
//
// ### Examples
// The input is formatted here to better depict where the first matrix starts
// and where it ends. All numbers could also be written in one single row,
// therefore simply use `scanf` for the input without consideration of the
// formatting.
//
// #### Example 1
// Input:
// ```
// 3
//
// 1 0 2
// 3 -1 4
// 5 1 0
//
// -2 0 3
// 1 0 -5
// 0 3 -4
// ```
// Output:
// ```
//  -2  6 -5
//  -7 12 -2
//  -9  0 10
// ```
// #### Example 2
// Matrix multiplication is not commutative. In this example, the matrices of
// Example 1 are swapped, the result is therefore different.
//
// Input:
// ```
// 3
//
// -2 0 3
// 1 0 -5
// 0 3 -4
//
// 1 0 2
// 3 -1 4
// 5 1 0
// ```
// Output:
// ```
//  13  3 -4
// -24 -5  2
// -11 -7 12
// ```
//
// (For more examples and explanations about the maths behind matrix
// multiplication, see the exercise PDF.)

// ## Forward declarations
// We split the problem into three chunks: reading a matrix from standard
// input, printing a matrix to standard output, and doing the matrix
// multiplication.
void read_matrix(int size, int *matrix);
void print_matrix(int size, int *matrix);
void matrix_multiply(int size, int *m1, int *m2, int *m3);

// ## main()
// The program should: read in the size of the square matrices, then read
// two of them, multiply, and print the result.
int main() {
    // We use 'pointer to int' as the type for the matrix variables,
    // and calculate the size of the contiguous memory region that contains
    // all ints of one matrix by multiplying the size of one int with the
    // square of the size.
    int size;
    int *matrix1, *matrix2, *matrix3;

    scanf("%d", &size);

    size_t mem_needed = sizeof(int) * size * size;

    // I used the `malloc` function from the C standard library
    // to allocate the chunk of memory with the correct size, we could
    // use the C99 feature of having dynamically sized arrays.
    //
    // To see how that looks like, I wrote the program in an alternative
    // way, [u7_matrices_c99.c](./u7_matrices_c99.html).
    matrix1 = malloc(mem_needed);
    matrix2 = malloc(mem_needed);
    matrix3 = malloc(mem_needed);

    // Read in both matrices, multiply into the third variable, and print.
    read_matrix(size, matrix1);
    read_matrix(size, matrix2);
    matrix_multiply(size, matrix1, matrix2, matrix3);
    print_matrix(size, matrix3);

    // Because we used `malloc`, we must use `free` when we no longer need
    // the allocated chunks of memory.
    free(matrix3);
    free(matrix2);
    free(matrix1);

    // Return code 0 to indicate everything went OK.
    return 0;
}

// ## read_matrix()
// Because we store the matrix as one continuous range of memory, we have
// to calculate the linear index from the `col` and `row` loop variables.
//
// We use what is called ['row-major' storage order](https://en.wikipedia.org/wiki/Row-_and_column-major_order).
void read_matrix(int size, int *matrix) {
    int row, col;

    for (row = 0; row < size; row++) {
        for (col = 0; col < size; col++) {
            scanf("%i", &matrix[row * size + col]);
        }
    }
}

// ## print_matrix()
// Print a matrix in row-major storage.
void print_matrix(int size, int *matrix) {
    int row, col;

    for (row = 0; row < size; row++) {
        for (col = 0; col < size; col++) {
            printf("% 3i", matrix[row * size + col]);
        }
        printf("\n");
    }
}

// ## matrix_multiply
// Multiplication of two square matrices, storing the result in the memory
// pointed at by the `m3` parameter.
void matrix_multiply(int size, int *m1, int *m2, int *m3) {
    int row, col, i;

    // For each of the matrix cells in m3,
    for (row = 0; row < size; row++) {
        for (col = 0; col < size; col++) {
            // calculate the scalar product of the row of m1 and column of m2
            int sum = 0;

            for (i = 0; i < size; i++) {
                sum += m1[row * size + i] * m2[i * size + col];
            }

            // and store it in the cell.
            m3[row * size + col] = sum;
        }
    }
}