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

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
>>>     std::copy().
>>>
>>>
>>> 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 
>> iterators.
>>
>> 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
> 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 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() )
>         break;
> }
>
> Regards,
> Adam

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 
differently?

Regards,
Adam