MonotoneMatrixSearchTraits Concept Reference

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.

Has Models:

CGAL::Dynamic_matrix<M>

See also

CGAL::monotone_matrix_search()

Types
typedef unspecified_type	Value
	The type of a matrix entry.

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

extract_all_even_rows()

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

Precondition

number_of_rows() \( > 0\).

operator()()

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

replace_column()

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

replace column old with column number new.

Precondition

\( 0 \le\) old, new \( <\) number_of_columns().

shrink_to_quadratic_size()

void MonotoneMatrixSearchTraits::shrink_to_quadratic_size

(

)

deletes the rightmost columns, such that m becomes quadratic.

Precondition

number_of_columns() \( \ge\) number_of_rows().

Postcondition

number_of_rows() \( ==\) number_of_columns().