Subject: Re: [geometry] [index] rtree iterative queries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-09-08 18:49:48
Adam Wulkiewicz wrote:
> Adam Wulkiewicz wrote:
>> Bruno Lalande wrote:
>>> 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
>>> This sounds a bit unusual. What I've seen done so far is that the
>>> same iterator type is used and it simply as a no parameter
>>> constructor, and flags itself as end-iterator/default-constructed if
>>> constructed this way. Was it really an issue to do like that?
>>> Otherwise, sounds like a useful addition, thanks for that.
>> The problem is that the Predicates are stored inside the iterator
>> which means that they're a part of the iterator type. To construct
>> the end iterator of the same type the Predicates must also be known.
>> Additionally, the type of this raw iterator can't be defined in the
>> container because it depends on the Predicates expression. And yes a
>> default-constructed iterator is an end iterator. These iterators can
>> be obtained by:
>> tree.qbegin(/*predicates*/) and tree.qend(/*predicates*/)
>> For convinience I've added tree.qend() but it returns an iterator of
>> different type.
>> To allow less experienced users to use those iterators e.g. in a for
>> loop I've defined a type-erased const_iterator_type.
>> I also think that this is quite complicated and if we found a better
>> solution I'd gladly change the existing one.
>> One possible solution would be the implementation of qbegin() and
>> qend() returning type-erased iterators and e.g. some other methods
>> like qbegin_xxx() and qend_xxx() returning raw Predicates-dependent
>> Or maybe do you have some other ideas?
>> One thing you should probably know is that those raw
>> Predicates-dependent iterators are fat iterators, tree traversing
>> stack is stored inside so they're quite big.
> I could also remove non-parameter qend().
> So what do you think about all those solutions? Maybe we should not
> release it yet? I'm asking because the deadline for 1.55 is approaching.
> As a reminder this is how it looks now:
> // Store the result in the container using std::copy() - it requires
> both iterators of the same type
> tree.qend(bgi::intersects(box)), std::back_inserter(result));
> // Store the result in the container using std::copy() and type-erased
> 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 and non-parameter qend()
> 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() )
After some thinking I propose to change qbegin() and qend() to return
type-erased const_query_iterators and leave only non-parameter qend().
As Bruno have written this will be the closest to the other solutions
where iterators are involved. Later we may add a way to obtain those
faster 'raw' iterators. For now I'd add qbegin_() and qend_() returning
them and shield those functions with
BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL. Are you ok with that or see it
Geometry list run by mateusz at loskot.net