The function monotone_matrix_search
computes the maxima for all
rows of a totally monotone matrix.
More precisely, monotony for matrices is defined as follows.
Let K be a totally ordered set, a matrix over K and
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).
template < class Matrix, class RandomAccessIC, class Compare_strictly >
monotone_matrix_search ( |
Compare_strictly compare_strictly = less< Matrix::Value >())
computes the maximum (as specified by compare_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
of a row is the leftmost element for which
compare_strictly is false for all elements in
points to a structure of size at least
- Matrix is a model for
- Value type of RandomAccessIC is int.
- If compare_strictly is defined, it is an adaptable
binary function: Matrix::Value
Matrix::Value bool describing a strict
(non-reflexive) total ordering on Matrix::Value.
The implementation uses an algorithm by Aggarwal
]. The runtime is linear in the number
of rows and columns of the matrix.