Sorted Matrix Search

More exactly, a matrix (over a totally ordered set S) is sorted, iff

Now let be a set of n sorted matrices over S and f be a monotone predicate on S, i.e.

If we assume there is any feasible element in one of the matrices in , there certainly is a smallest such element. This is the one we are searching for.

The feasibility test as well as some other parameters can (and have to) be customized through a traits class. The requirements for this class are described in section .

#include <CGAL/sorted_matrix_search.h>

template < class RandomAccessIC, class Traits >
Traits::Value	sorted_matrix_search ( RandomAccessIC f, RandomAccessIC l, Traits t)

returns the element x in one of the sorted matrices from the range $$[ f, l ), for which t.is_feasible( x) is true and t.compare( x, y) is true for all other y values from any matrix for which t.is_feasible( y) is true.

Precondition

1. Traits satisfies the requirements for sorted matrix search traits classes stated in section ,
2. Value type of RandomAccessIC is Traits::Matrix,
3. All matrices in $$[ f, l ) are sorted according to Traits::compare_non_strictly and
4. there is at least one entry $$x in a matrix $$M [ f, l ) for which Traits::is_feasible( x) is true.

Implementation

(n · k + f ·

Example

a_i + a_j, i,j {1,...,5}

#include <CGAL/Random.h>
#include <CGAL/function_objects.h>
#include <CGAL/Cartesian_matrix.h>
#include <CGAL/sorted_matrix_search.h>
#include <vector>

using namespace std;
using namespace CGAL;

typedef int                              Value;
typedef vector< Value >                  Vector;
typedef Vector::iterator                 Value_iterator;
typedef vector< Vector >                 Vector_cont;
typedef Cartesian_matrix<
  plus< int >,
  Value_iterator,
  Value_iterator >                       Matrix;

int main() {
  // set of vectors the matrices are build from:
  Vector_cont vectors;

  // generate a random vector and sort it:
  Vector a;
  int i;
  cout << "a = ( ";
  for ( i = 0; i < 5; ++i) {
    a.push_back( default_random( 100));
    cout << a.back() << " ";
  }
  cout << ")" << endl;
  sort( a.begin(), a.end(), less< Value >());

  // build a cartesian from a:
  Matrix M( a.begin(), a.end(), a.begin(), a.end());

  // search an upper bound for max(a):
  Value bound( a[4]);
  Value upper_bound(
    sorted_matrix_search(
      &M,
      &M + 1,
      sorted_matrix_search_traits_adaptor(
        bind2nd( greater_equal< Value >(), bound),
        M)));
  cout << "upper bound for " << bound << " is "
       << upper_bound << endl;

  return 0;
}