diff options
author | pacien | 2017-12-02 01:10:02 +0100 |
---|---|---|
committer | pacien | 2017-12-02 01:10:02 +0100 |
commit | 650c4400c63d8ec8473321862046240cb873ec8d (patch) | |
tree | 4d1a0a6de3491046062efe4b06e71be56bbc3d0b | |
parent | c65669a785fba9b1f0f7539f47a677035ea06229 (diff) | |
download | morpher-650c4400c63d8ec8473321862046240cb873ec8d.tar.gz |
Add matrix op impl. and test, minor spec change
Signed-off-by: pacien <pacien.trangirard@pacien.net>
-rw-r--r-- | include/common/matrix.h | 15 | ||||
-rw-r--r-- | src/common/matrix.c | 63 | ||||
-rw-r--r-- | test/common/matrix.c | 21 |
3 files changed, 98 insertions, 1 deletions
diff --git a/include/common/matrix.h b/include/common/matrix.h index 6c35cc0..726a8ab 100644 --- a/include/common/matrix.h +++ b/include/common/matrix.h | |||
@@ -3,6 +3,7 @@ | |||
3 | 3 | ||
4 | /** | 4 | /** |
5 | * File: matrix.h | 5 | * File: matrix.h |
6 | * Matrices representation and useful operations. | ||
6 | * | 7 | * |
7 | * See also: | 8 | * See also: |
8 | * The film | 9 | * The film |
@@ -15,7 +16,7 @@ | |||
15 | * Represents a square integer matrix. | 16 | * Represents a square integer matrix. |
16 | */ | 17 | */ |
17 | typedef struct { | 18 | typedef struct { |
18 | IntVector *elements; | 19 | IntVector **elements; |
19 | IntVector dim; | 20 | IntVector dim; |
20 | } IntSquareMatrix; | 21 | } IntSquareMatrix; |
21 | 22 | ||
@@ -31,4 +32,16 @@ typedef struct { | |||
31 | */ | 32 | */ |
32 | IntVector matrix_int_det(IntSquareMatrix *matrix); | 33 | IntVector matrix_int_det(IntSquareMatrix *matrix); |
33 | 34 | ||
35 | /** | ||
36 | * Function: matrix_reshape | ||
37 | * Reshapes a flat vector into a bi-dimensional row pointer array. | ||
38 | * | ||
39 | * Parameters: | ||
40 | * **bi_dim - pointer to the result row array | ||
41 | * *flat - flat vector | ||
42 | * width - number of elements per row | ||
43 | * height - number of rows | ||
44 | */ | ||
45 | void matrix_reshape(IntVector **bi_dim, IntVector *flat, int width, int height); | ||
46 | |||
34 | #endif | 47 | #endif |
diff --git a/src/common/matrix.c b/src/common/matrix.c new file mode 100644 index 0000000..60f9afb --- /dev/null +++ b/src/common/matrix.c | |||
@@ -0,0 +1,63 @@ | |||
1 | #include "common/matrix.h" | ||
2 | #include <assert.h> | ||
3 | #include <memory.h> | ||
4 | #include <stdlib.h> | ||
5 | #include "common/mem.h" | ||
6 | |||
7 | static inline IntSquareMatrix *matrix_without_row(IntSquareMatrix *target, IntSquareMatrix *origin, | ||
8 | IntVector omitted_row) { | ||
9 | int origin_row, target_row; | ||
10 | |||
11 | for (origin_row = 0, target_row = 0; origin_row < origin->dim; ++origin_row) | ||
12 | if (origin_row != omitted_row) | ||
13 | target->elements[target_row++] = origin->elements[origin_row]; | ||
14 | |||
15 | return target; | ||
16 | } | ||
17 | |||
18 | static inline IntVector det_dev_sign(IntVector row, IntVector col) { | ||
19 | assert(row > 0 && col > 0); | ||
20 | return ((row + col) % 2 == 0) ? 1 : -1; | ||
21 | } | ||
22 | |||
23 | static inline IntVector det_reduce(IntSquareMatrix *matrix) { | ||
24 | IntSquareMatrix sub_matrix; | ||
25 | int row; | ||
26 | IntVector det = 0; | ||
27 | |||
28 | assert(matrix->dim > 2); | ||
29 | |||
30 | sub_matrix.dim = matrix->dim - 1; | ||
31 | sub_matrix.elements = malloc_or_die(sub_matrix.dim * sizeof(IntVector *)); | ||
32 | |||
33 | for (row = 0; row < matrix->dim; ++row) | ||
34 | det += matrix->elements[row][matrix->dim - 1] | ||
35 | * det_dev_sign(row + 1, matrix->dim) | ||
36 | * matrix_int_det(matrix_without_row(&sub_matrix, matrix, row)); | ||
37 | |||
38 | |||
39 | free(sub_matrix.elements); | ||
40 | return det; | ||
41 | } | ||
42 | |||
43 | IntVector matrix_int_det(IntSquareMatrix *matrix) { | ||
44 | assert(matrix->dim > 0); | ||
45 | switch (matrix->dim) { | ||
46 | case 1: | ||
47 | return matrix->elements[0][0]; | ||
48 | |||
49 | case 2: | ||
50 | return matrix->elements[0][0] * matrix->elements[1][1] - matrix->elements[0][1] * matrix->elements[1][0]; | ||
51 | |||
52 | default: | ||
53 | return det_reduce(matrix); | ||
54 | } | ||
55 | } | ||
56 | |||
57 | void matrix_reshape(IntVector **bi_dim, IntVector *flat, int width, int height) { | ||
58 | int row; | ||
59 | assert(width > 0 && height > 0); | ||
60 | |||
61 | for (row = 0; row < height; ++row) | ||
62 | bi_dim[row] = flat + row * width; | ||
63 | } | ||
diff --git a/test/common/matrix.c b/test/common/matrix.c new file mode 100644 index 0000000..6d85304 --- /dev/null +++ b/test/common/matrix.c | |||
@@ -0,0 +1,21 @@ | |||
1 | #include "common/matrix.h" | ||
2 | #include <assert.h> | ||
3 | |||
4 | static void test_matrix_int_det() { | ||
5 | IntSquareMatrix matrix; | ||
6 | IntVector *elements[3]; | ||
7 | |||
8 | matrix_reshape(elements, (IntVector[]) {-2, +2, -3, | ||
9 | -1, +1, +3, | ||
10 | +2, +0, -1}, 3, 3); | ||
11 | |||
12 | matrix.dim = 3; | ||
13 | matrix.elements = elements; | ||
14 | |||
15 | assert(matrix_int_det(&matrix) == 18); | ||
16 | } | ||
17 | |||
18 | int main(int argc, char **argv) { | ||
19 | test_matrix_int_det(); | ||
20 | return 0; | ||
21 | } | ||