advanced

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 monotone_matrix_search.

Types

MonotoneMatrixSearchTraits::Value
	The type of a matrix entry.

Operations

int	m.number_of_columns () const	returns the number of columns.
int	m.number_of_rows () const	returns the number of rows.
Entry	m.operator() ( int row, int column) const
		returns the entry at position (row, column). Precondition:  $$0 row $$< number_of_rows() and $$0 column $$< number_of_columns().
void	m.replace_column ( int old, int new)
		replace column old with column number new. Precondition:  $$0 old, new $$< number_of_columns().
Matrix*	m.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.). Precondition:  number_of_rows() $$> 0.
void	m.shrink_to_quadratic_size ()	deletes the rightmost columns, such that m becomes quadratic. Precondition:  number_of_columns() $$ number_of_rows(). Postcondition:  number_of_rows() $$== number_of_columns().

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.

Has Models

CGAL::Dynamic_matrix<M>

See Also

CGAL::monotone_matrix_search

advanced