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`). More...

void	replace_column (int old, int new)
	replace column `old` with column number `new`. More...

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.). More...

void	shrink_to_quadratic_size ()
	deletes the rightmost columns, such that `m` becomes quadratic. More...

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.