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-02 19:40:55

Hi,

Bruno Lalande wrote:
> Hi Adam,
>
>     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.

For example qbegin() and qend() could return type-erased iterators, then 
the interface would become like in the STL containers but since memory 
allocation and virtual methods are involved in the process those 
iterators are slower.
E.g. on VS2010 those are the times of some queries:

// 1M boxes stored, linear<16>, times of 100k queries
0.920406 seconds - tree.query(B)
0.936006 seconds - std::copy(tree | queried(B))
1.20121 seconds - std::copy(tree.qbegin(B), tree.qend(B))
1.15441 seconds - my_copy(tree.qbegin(B), tree.qend())
1.23241 seconds - boost::copy(std::make_pair(tree.qbegin(B), tree.qend(B)))
1.27921 seconds - type-erased std::copy(tree.qbegin(B), tree.qend(B))
1.21681 seconds - type-erased std::copy(tree.qbegin(B) tree.qend())
1.34161 seconds - type-erased boost::copy(std::make_pair(tree.qbegin(B) 
tree.qend(B)))
1.23241 seconds - type-erased boost::copy(std::make_pair(tree.qbegin(B) 
tree.qend()))

// 1M boxes stored, linear<16>, times of 20k queries
0.795605 seconds - tree.query(N)
0.858006 seconds - std::copy(tree.qbegin(N) tree.qend(N))
0.842405 seconds - my_copy(tree.qbegin(N) tree.qend())
0.951606 seconds - type-erased std::copy(tree.qbegin(N)) tree.qend(N))
0.967206 seconds - type-erased std::copy(tree.qbegin(N) tree.qend())

The above code is pseudocode:
- B means intersects(box)
- N means nearest(point, 10)
- to erase a type of an iterator one must convert it to 
Rtree::const_query_iterator first.
- all calls lack the last output iterator parameter

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.

Regards,
Adam