CGAL 4.14 - Monotone and Sorted Matrix Search
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>
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...

deletes the rightmost columns, such that m becomes quadratic. More...

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

deletes the rightmost columns, such that m becomes quadratic.
number_of_columns() $$\ge$$ number_of_rows().
number_of_rows() $$==$$ number_of_columns().