CGAL 6.1.1 - Monotone and Sorted Matrix Search

Loading...
Searching...
No Matches
List of all members
MonotoneMatrixSearchTraits Concept Reference
Reference Manual » 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`).
void | replace_column (int old, int new)
| replace column `old` with column number `new`.
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.).
void | shrink_to_quadratic_size ()
| deletes the rightmost columns, such that `m` becomes quadratic.

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