Geometry Boost List: Re: [geometry] Are all query iterators const?

Subject: Re: [geometry] Are all query iterators const?
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2015-09-02 17:36:39

Hi Hal,

Hal Clark wrote:
> I'm new to Boost.Geometry and have recently discovered the
> rtree::qbegin()/qend() mechanism. It is useful (thanks!) but the
> iterators are all marked const. Is it possible to get non-const
> iterators without mucking about with const_cast? (I see
> rtree::begin()/end() are new between 1.57.0 and 1.58.0 -- hopefully
> non-const qbegin()/qend() follow more easily.)

All rtree iterators are const iterators. The rationale behind it is 
similar to the rationale behind the constness of std::multiset 
iterators. If it was possible to modify the value it would be very easy 
to break the index. In the case of the rtree it's even more 
understandable since by definition it's an index, not a container. So 
it's a data structure, typically containing only some simple geometrical 
representation and an ID, which is kept aside of some container storing 
the actual data.

That said, we could of course think about relaxing this requirement. The 
rtree taking a ValueType is similar to std::multiset. But in the STL 
there is also std::multimap storing std::pair<const Key, T>. If we could 
ensure that the geometrical part of the value couldn't be changed by the 
user we could implement mutable interators.  For instance, mutable 
iterators could be enabled only for some specific ValueTypes, e.g. 
std::pair<const Box, T>, boost::tuple<const Box, T>, etc. But this could 
be not intuitive for the users. An alternative would be to add an rtree 
version similar to std::multimap (e.g. rtree_map or soem other name). 
Instead of a single ValueType template parameter it could take two: 
Indexable and some type T. Then it'd require to insert objects of 
ValueType std::pair<const Indexable, T> exactly like the std::multimap.

> ---
>
> My use case is as follows. I'm implementing some point clustering
> algorithms. My point primitive has a 'ClusterID' attribute member, and
> something like a (fat) user-defined boost::any. Because the point is
> not cheap to copy, I'm iterating over nearest neighbours and marking
> the ClusterID in-place using something like this:
>
>          //Using Boost version 1.57.0.
>          ...
>          RTree_t::const_query_iterator it;
>          it = rtree.qbegin(boost::geometry::index::satisfies(
>              [](const MyPoint &) -> bool { return true; } )
>          );
>          for( ; it != rtree.qend(); ++it){
>              //it->ClusterID = -1; //Compilation error: disregards const.
>              const_cast<MyPoint &>(*it).ClusterID = -1;
>          }

You should know that the Values can be heavily copied during the 
insertion and removal.

Have you considered keeping the points as small as possible and keeping 
the rest (boost::any) in some container outside the rtree? In general 
using objects containing cold data for indexing is not a good idea 
because of increased number of cache misses, so worse performance.

> First: my understanding is that because the spatial coordinates are
> not altered the const_cast is valid. Is this correct?

Yes.

> Second: can something like the back_inserter interface be created that
> won't copy the matching points?

Do you have the query() member function in mind? But instead of copying 
the Values into the output iterator (so working like std::copy()) 
calling some Function for all Values meeting predicates (so working like 
std::for_each())?

I wouldn't recommend it but actually you could do it even now by passing 
Function/UnaryPredicate into bgi::satisfies() and then into query() 
method. This predicate would be called for all Values meeting other 
predicates. To prevent copying you could pass some kind of dummy output 
iterator (dev_null_iterator). But this code wouldn't be clear. And the 
catch is that also in this case the const reference to Value is passed 
into the UnaryPredicate taken by the bgi::satisfies(). The reason is the 
same, to not allow the user to modify the Indexable part by mistake.

> non-const query_iterators would be
> nice. I don't understand the rationale for, or distinction between,
> query_iterator, spatial_query_iterator, distance_query_iterator, but
> presumably they are all non-const candidates.

The kind of an iterator is not a problem here, all of them could be made 
mutable. The problem is, how to design an interface dissallowing the 
users to modify an Indexable part of a ValueType object stored in the 
rtree index.
But your solution seems to be ok (const_cast). It's the same as if 
someone wanted to do a similar thing with std::set. And const_cast is a 
nice warning sign.

Regards,
Adam