\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - Monotone and Sorted Matrix Search
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
MonotoneMatrixSearchTraits Concept Reference
Concepts

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

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

Precondition
\( 0 \le\) old, new \( <\) number_of_columns().
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().