/****************************************************************************
**
*A  matrix.c                    ANUPQ source                   Eamonn O'Brien
**
*Y  Copyright 1995-2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
*Y  Copyright 1995-2001,  School of Mathematical Sciences, ANU,     Australia
**
*/

#include "pq_defs.h"
#include "pq_functions.h"

/* read an n x matrix, a */

void read_matrix(int **a, int n, int m)
{
   register int i, j;

   for (i = 0; i < n; ++i) {
      for (j = 0; j < m - 1; ++j)
         read_value(FALSE, "", &a[i][j], 0);
      read_value(TRUE, "", &a[i][j], 0);
   }
   printf("\n");
}

/* print an n x m matrix a */

void print_matrix(int **a, int n, int m)
{
   register int i, j;

   for (i = 0; i < n; ++i) {
      for (j = 0; j < m; ++j)
         printf("%d ", a[i][j]);
      printf("\n");
   }
}

/* modulo p, multiply the n x m matrix a by the m x q matrix b */

int **multiply_matrix(int **a, int n, int m, int **b, int q, int p)
{
   register int i, j, k;
   int **product = allocate_matrix(n, q, 0, 1);

   for (i = 0; i < n; ++i)
      for (j = 0; j < q; ++j) {
         for (k = 0; k < m; ++k)
            product[i][j] += a[i][k] * b[k][j];
         product[i][j] %= p;
      }

   return product;
}

int **transpose(int **a, int n, int m)
{
   register int i, j;
   int **transpose = allocate_matrix(m, n, 0, 0);

   for (i = 0; i < m; ++i)
      for (j = 0; j < n; ++j)
         transpose[i][j] = a[j][i];

   return transpose;
}

/* check if the n x n matrix a is the identity;
   start is its first index position */

Logical is_identity(int **a, int n, int start)
{
   int identity = 1;
   register int i = start;
   register int j;

   while (i < n + start && identity) {
      j = start;
      while (j < n + start && identity) {
         identity = (i == j) ? a[i][j] == 1 : a[i][j] == 0;
         ++j;
      }
      ++i;
   }

   return identity;
}

/* check if each row of the n x n matrix a has a non-zero
   entry and whether its entries lie between 0 and p - 1;
   start is its first index position */

Logical valid_matrix(int **a, int n, int p, int start)
{
   register int i, j;
   int non_zero = 0;
   Logical valid = TRUE;
   Logical first;

   for (i = start; i < n + start && valid; ++i) {
      first = TRUE;
      for (j = start; j < n + start && valid; ++j) {
         valid = (a[i][j] >= 0 && a[i][j] < p);
         if (a[i][j] > 0 && first) {
            ++non_zero;
            first = FALSE;
         }
      }
   }

   if (valid && non_zero == n)
      return TRUE;
   else
      return FALSE;
}