Add matrix op impl. and test, minor spec change

Signed-off-by: pacien <pacien.trangirard@pacien.net>

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 @@
 
 /**
  * File: matrix.h
+ * Matrices representation and useful operations.
  *
  * See also:
  *   The film
@@ -15,7 +16,7 @@
  * Represents a square integer matrix.
  */
 typedef struct {
-  IntVector *elements;
+  IntVector **elements;
   IntVector dim;
 } IntSquareMatrix;
 
@@ -31,4 +32,16 @@ typedef struct {
  */
 IntVector matrix_int_det(IntSquareMatrix *matrix);
 
+/**
+ * Function: matrix_reshape
+ * Reshapes a flat vector into a bi-dimensional row pointer array.
+ *
+ * Parameters:
+ *   **bi_dim - pointer to the result row array
+ *   *flat    - flat vector
+ *   width    - number of elements per row
+ *   height   - number of rows
+ */
+void matrix_reshape(IntVector **bi_dim, IntVector *flat, int width, int height);
+
 #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 @@
+#include "common/matrix.h"
+#include <assert.h>
+#include <memory.h>
+#include <stdlib.h>
+#include "common/mem.h"
+
+static inline IntSquareMatrix *matrix_without_row(IntSquareMatrix *target, IntSquareMatrix *origin,
+                                                  IntVector omitted_row) {
+  int origin_row, target_row;
+
+  for (origin_row = 0, target_row = 0; origin_row < origin->dim; ++origin_row)
+    if (origin_row != omitted_row)
+      target->elements[target_row++] = origin->elements[origin_row];
+
+  return target;
+}
+
+static inline IntVector det_dev_sign(IntVector row, IntVector col) {
+  assert(row > 0 && col > 0);
+  return ((row + col) % 2 == 0) ? 1 : -1;
+}
+
+static inline IntVector det_reduce(IntSquareMatrix *matrix) {
+  IntSquareMatrix sub_matrix;
+  int row;
+  IntVector det = 0;
+
+  assert(matrix->dim > 2);
+
+  sub_matrix.dim = matrix->dim - 1;
+  sub_matrix.elements = malloc_or_die(sub_matrix.dim * sizeof(IntVector *));
+
+  for (row = 0; row < matrix->dim; ++row)
+    det += matrix->elements[row][matrix->dim - 1]
+           * det_dev_sign(row + 1, matrix->dim)
+           * matrix_int_det(matrix_without_row(&sub_matrix, matrix, row));
+
+
+  free(sub_matrix.elements);
+  return det;
+}
+
+IntVector matrix_int_det(IntSquareMatrix *matrix) {
+  assert(matrix->dim > 0);
+  switch (matrix->dim) {
+    case 1:
+      return matrix->elements[0][0];
+
+    case 2:
+      return matrix->elements[0][0] * matrix->elements[1][1] - matrix->elements[0][1] * matrix->elements[1][0];
+
+    default:
+      return det_reduce(matrix);
+  }
+}
+
+void matrix_reshape(IntVector **bi_dim, IntVector *flat, int width, int height) {
+  int row;
+  assert(width > 0 && height > 0);
+
+  for (row = 0; row < height; ++row)
+    bi_dim[row] = flat + row * width;
+}
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 @@
+#include "common/matrix.h"
+#include <assert.h>
+
+static void test_matrix_int_det() {
+  IntSquareMatrix matrix;
+  IntVector *elements[3];
+
+  matrix_reshape(elements, (IntVector[]) {-2, +2, -3,
+                                          -1, +1, +3,
+                                          +2, +0, -1}, 3, 3);
+
+  matrix.dim = 3;
+  matrix.elements = elements;
+
+  assert(matrix_int_det(&matrix) == 18);
+}
+
+int main(int argc, char **argv) {
+  test_matrix_int_det();
+  return 0;
+}