Definition

The concept MonotoneMatrixSearchTraits is a refinement of BasicMatrix and defines types and operations needed to compute the maxima for all rows of a totally monotone matrix using the function CGAL::monotone_matrix_search.

Notes

For the sake of efficiency (and in order to achieve the time bounds claimed for monotone_matrix_search), all these operations have to be realized in constant time - except for extract_all_even_rows which may take linear time.
There is an adaptor Dynamic_matrix that can be used to add most of the functionality described above to arbitrary matrix classes.

Operations
int	number_of_columns () const
	returns the number of columns.
int	number_of_rows () const
	returns the number of rows.
Entry	operator() (int row, int column) const
	returns the entry at position (row, column).
void	replace_column (int old, int new)
	replace column old with column number new.
Matrix *	extract_all_even_rows () const
	returns a new Matrix consisting of all rows of m with even index, (i.e. first row is row \( 0\) of m, second row is row \( 2\) of m etc.).
void	shrink_to_quadratic_size ()
	deletes the rightmost columns, such that m becomes quadratic.

Member Function Documentation

Matrix * MonotoneMatrixSearchTraits::extract_all_even_rows ( ) const

returns a new Matrix consisting of all rows of m with even index, (i.e. first row is row \( 0\) of m, second row is row \( 2\) of m etc.).

Entry MonotoneMatrixSearchTraits::operator()	(	int	row,
		int	column ) const

returns the entry at position (row, column).

Precondition: \( 0 \le\) row \( <\) number_of_rows(), and \( 0 \le\) column \( <\) number_of_columns().

void MonotoneMatrixSearchTraits::replace_column	(	int	old,
		int	new )

replace column old with column number new.

void MonotoneMatrixSearchTraits::shrink_to_quadratic_size ( )

deletes the rightmost columns, such that m becomes quadratic.