Sum of independent diagonal in a matrix

Question

I'm currently studying for an exam and I'm trying to deal with dynamical matrix. I've come across a problem regarding calculating the sum of every diagonal of a matrix whose values and size are chosen by the user. The intent of my program is to print, thanks to a function, whose parameters are the matrix and its size, the value of every diagonal sum. I'll show you the code and describe it in depth.

----------------
| 52 | 35 | 5  |  Example of matrix.
----------------  Imagine the first diagonal to be the one which goes right-to-left
| 2  | 71 | 1  |  and only consists in the number "47".
----------------  The second diagonal would be the one which goes right-to-left and
| 3  | 60 | 25 |  consists in the number "15" and "79".
----------------  So to get the sum of the second diagonal it would be:
| 79 | 55 | 98 |     
----------------  sum = m[n_rows - 1][diag - 2] + m[n_rows - 2][diag - 1]
| 47 | 15 | 66 | 
----------------  When diag > columns, in order to avoid error regarding matrix size,
                  I should lower the quantity "n_rows - 1" by the quantity "diag - n_columns".

This is what I thought to do, according to my description:

void diag_matrix(int** m, int righe, int colonne){//righe = rows, colonne = columns. 
//M is the matrix.

// diag is the number of the diagonal I'm considering.
    for(int diag = 1; diag < (righe + colonne); diag++){ 

        int sum = 0;// the sum
        int i = 0;// the counter of the cicle
        int l = 0;// this is the value to riallign the row in case diag > column
        int temp = diag;//I use this variable not to modify the value of diag.

        // What I want is: when the column-index/row-index of the matrix reaches 0, the cicle will interrupt (after final iteration);
        while(righe - i - l - 1 > 0 || diag - 1 - i > 0){

            if (diag > colonne){//this condition changes l-value only if diag value is greater than column. Explanation outside the code
                l = diag - colonne;//this is the value to subtract to row-index
                temp = colonne;//this position is necessary to set column-index to its maxium.
            }

            sum = sum + m[righe - 1 - l - i][temp -1 - i];//pretty clear I think.
            i++;//the i is incremented by one.

        }// end of while-statement

        cout << "Somma Diagonale " << diag << " = " << sum << ".\n";

    }// end of for-statement

}//end of function declaration

Obviously it does not work, but I can't figure out the problem.

Answer 1

(There used to be a paragraph here, but on a second look, you didn’t make the mistake it was talking about.)

Since you didn’t post to Code Reviews, here’s a solution instead of a detailed code review. (If you want to make the original approach work, I’d suggest single-stepping through it in a debugger and checking where your variables first get the wrong value.) It’s got a lot of boilerplate to make it compile and run, but the part you’ll be most interested in is diag_sums() and its comments.

One idea here is to use OOP to automatically check the bounds of your array accesses. The latter is very important for catching off-by-one errors and the like. You can turn it off in production if you want, but you really don’t want to silence warnings when your program has a buffer overrun. Other optimizations here include locality of access for the data, and strength reduction on the operations: rather than check on each iteration whether we’ve hit the right edge and the bottom edge, we can simply calculate the length of each diagonal in advance.

Since the definition of diagonal number k of matrix a with M rows is equivalent to: all elements a[i][j] such that such that M - k = i - j, the algorithm ensures correctness by maintaining the invariant, which holds whenever we add 1 to both i and j, starting when either i or j is 0, and stopping whenever i = M or j = N, that is, traversing each step of the diagonal from the left or top edge to the right or bottom edge, whichever comes first.

#include <assert.h>
#include <iostream>
#include <stddef.h>
#include <stdlib.h>
#include <utility>
#include <vector>

using std::cin;
using std::cout;

template <typename T>
  class matrix {
    public:
      matrix( const ptrdiff_t rows,
              const ptrdiff_t cols,
              std::vector<T>&& elems )
        : rows_(rows), cols_(cols), elems_(elems)
      {
        assert( rows_ > 0 );
        assert( cols_ > 0 );
        assert( elems_.size() == static_cast<size_t>(rows_*cols_) );
      }

      matrix( const ptrdiff_t rows,
              const ptrdiff_t cols,
              const std::vector<T>& elems )
        : matrix( rows, cols, std::move(std::vector<T>(elems)) )
      {}

      matrix( const matrix<T>& ) = default;
      matrix( matrix<T>&& ) = default;
      matrix& operator= ( const matrix<T>& ) = default;
      matrix& operator= ( matrix<T>&& ) = default;

      T& operator() ( const ptrdiff_t m, const ptrdiff_t n )
      {
        assert( m >= 0 && m < rows_ );
        assert( n >= 0 && n < cols_ );
        return elems_[static_cast<size_t>(m*cols_ + n)];
      }

      const T& operator() ( const ptrdiff_t m, const ptrdiff_t n ) const
      {
       /* Because this call does not modify any data, and the only reason the
        * member function above cannot be const is that it returns a non-const
        * reference to an element of elems, casting away the const qualifier
        * internally and then returning a const reference is a safe way to
        * re-use the code.
        */
        matrix<T>& nonconst = *const_cast<matrix<T>*>(this);
        return nonconst(m,n);
      }

      ptrdiff_t rows() const { return rows_; }
      ptrdiff_t cols() const { return cols_; }

    private:
      ptrdiff_t rows_;
      ptrdiff_t cols_;
      std::vector<T> elems_;
  };

template<typename T>
  std::ostream& operator<< ( std::ostream& out, const matrix<T>& x )
  /* Boilerplate to print a matrix. */
  {
    const ptrdiff_t m = x.rows(), n = x.cols();

    for ( ptrdiff_t i = 0; i < m; ++i ) {
      out << x(i,0);
      for ( ptrdiff_t j = 1; j < n; ++j )
        out << ' ' << x(i,j);

      out << '\n';
    } // end for

    return out;
  }

using elem_t = int;

std::vector<elem_t> diag_sums( const matrix<elem_t>& a )
/* Return a vector of all the diagonal sums of a.
 *
 * The first diagonal sum is a(rows-1,0)
 * The second is a(rows-2,0) + a(rows-1,1)
 * The third is a(rows-3,0) + a(rows-2,1) + a(rows-1,2)
 * And so on.  I.e., the kth diagonal is the sum of all elements a(i,j) such
 * that i - j == rows - k.
 *
 * If a is a M×N matrix, there are M diagonals starting in column zero, and
 * N-1 diagonals (excluding the one containing a(0,0) so we don't count it
 * twice) starting in row 0.  We process them bottom to top, then left to
 * right.
 *
 * The number of elements in a diagonal starting at a(i,0) is min{M-i, N}.  The
 * number of elements in a diagonal starting at a(0,j) is min{M, N-j}.  This is
 * because a diagonal stops at either the bottom edge or the left edge of a.
 */
{
  const ptrdiff_t m = a.rows(), n = a.cols();
  std::vector<elem_t> result;
  result.reserve( static_cast<size_t>(m + n - 1) );

  for ( ptrdiff_t i = m-1; i > 0; --i ) {
    elem_t sum = 0;

    const ptrdiff_t nk = (m-i) < n ? (m-i) : n;
    for ( ptrdiff_t k = 0; k < nk; ++k )
      sum += a(i+k, k);

    result.emplace_back(sum);
  } // end for i

  for ( ptrdiff_t j = 0; j < n; ++j ) {
    elem_t sum = 0;

    const ptrdiff_t nk = m < (n-j) ? m : (n-j);
    for ( ptrdiff_t k = 0; k < nk; ++k )
      sum += a(k, j+k);

    result.emplace_back(sum);
  } // end for j

  return result;
}

matrix<elem_t> read_input_matrix( const int row, const int column )
/* Reads in row*column consecutive elements from cin and packs them into a
 * matrix<elem_t>.
 */
{
  assert(row > 0);
  assert(column > 0);

  const ptrdiff_t nelements = row*column;
  assert(nelements > 0); // Check for overflow.

  std::vector<elem_t> result;
  result.reserve(static_cast<size_t>(nelements));

  for ( ptrdiff_t i = nelements; i > 0; --i ) {
    int x;
    cin >> x;
    assert(cin.good());
    result.push_back(x);
  }

  return matrix<elem_t>( row,
                         column,
                         std::move(result) );
}

template<typename T>
  bool print_sequence( const T& container )
  /* Prints the contents of a container in the format
   * "{47, 94, 124, 160, 148, 36, 5}".
   */
  {
    cout << "{";

    if ( container.begin() != container.end() )
      cout << *container.begin();

    for ( auto it = container.begin() + 1; it < container.end(); ++it )
      cout << ", " << *it;

    cout << "}\n";

    return cout.good();
  }

/* A simple test driver that reads in the number of rows, the number of
 * columns, and then row*columns int values, from standard input.  It
 * then passes the result to diag_matrix(), E.g.:
 *
 * 5 3
 * 52 35  5
 *  2 71  1
 *  3 60 25
 * 79 55 98
 * 47 15 66
 */
int main()
{
  int rows, columns;
  cin >> rows;
  cin >> columns;

  assert(cin.good());

  const matrix<elem_t> input_matrix = read_input_matrix( rows, columns );
  // cout << input_matrix; // Instrumentation.
  const std::vector<elem_t> sums = diag_sums(input_matrix);

  print_sequence(sums);

  return EXIT_SUCCESS;
}

You could also just do print_sequence(diag_sums(read_input_matrix( rows, columns ))).