Monotone Matrix Search

Let K be a totally ordered set, a matrix over K and for :

the (leftmost) column containing the maximum entry in row i. M is called monotone, iff

M is totally monotone, iff all of its submatrices are monotone (or equivalently: iff all submatrices are monotone).

#include <CGAL/monotone_matrix_search.h>

template < class Matrix, class RandomAccessIC, class Compare_strictly >
void	monotone_matrix_search ( Matrix m, RandomAccessIC t, Compare_strictly compare_strictly = less< Matrix::Value >())

computes the maximum (as specified bycompare_strictly) entry for each row of m and writes the corresponding column to t, i.e. t[i] is set to the index of the column containing the maximum element in row i. The maximum $$m_r of a row $$r is the leftmost element for which compare_strictly$$(m_r,x) is false for all elements $$x in $$r.

Precondition

1. Matrix satisfies the requirements stated in section ,
2. Value type of RandomAccessIC is int,
3. t points to a structure of size at least m.number_of_rows() and
4. if compare_strictly is defined, it has to be an adaptable binary function: Matrix::Value $$ × Matrix::Value $$ bool describing a strict (non-reflexive) total ordering on Matrix::Value.

Implementation