Geometry Boost List: [geometry] [index] rtree iterative queries

Subject: [geometry] [index] rtree iterative queries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-08-28 21:17:00

Hi,

I've just added query iterators to the rtree. They can be used to 
perform iterative queries. Typical use cases:

- pause querying if it takes too long and resume it later,
- stop querying at some point, e.g. when we store bounding boxes of some
   geometries but want to find the nearest geometry, not bounding box.
   The iterative query will iterate through Values which boxes are
   closest to some point. Each iteration we can check if the geometry
   corresponding to the Value is the closest one and break the loop
   when needed.
- do something with only those Values which correspond to geometries
   meeting some predicates, similar to the previous point.
- probably more...

Those iterators may be returned by qbegin() and qend() methods.

DETAILS:

Of course there is a catch! The type of iterator returned by those 
methods depends on the type of passed Predicates. And to get the end 
iterator of the same type as the begin iterator, the predicates must be 
passed to the qend().

There is also a no-parameter qend() which return a special 
end_query_iterator which may be compared with arbitrary iterator 
returned by qbegin() to check if the query has ended. But since it has 
different type it can't be used in STL algorithms like std::copy().

But! Additionally in the rtree there is a definition of a type of 
type-erased const_query_iterator to which all of the above iterators may 
be assigned.

The reason why I just don't return type-erased iterators from qbegin() 
and qend() to get rid of qend() taking predicates is that they're 
slower. Furthermore the type of the returned iterator may be obtained 
using one of C++11 features like decltype or auto or Boost.Typeof library.

EXAMPLE:

// Store the result in the container using std::copy()
//   it requires both iterators of the same type
std::copy(tree.qbegin(bgi::intersects(box)),
           tree.qend(bgi::intersects(box)),
           std::back_inserter(result));

// Store the result in the container using std::copy()
//   and type-erased iterators
Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box));
Rtree::const_query_iterator last = tree.qend();
std::copy(first, last, std::back_inserter(result));

// Boost.Typeof
typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ;
       it != tree.qend() ;
       ++it )
{
     // do something with value
     if ( has_enough_nearest_values() )
         break;
}

Thoughts?

Regards,
Adam