Requirements for Monotone Matrix Search Matrix Classes

Definition

Types

Mms_matrix::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 in section ), 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 (see section ) that can be used to add most of the functionality described above to arbitrary matrix classes.