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

Subject: Re: [geometry] Are all query iterators const?
From: Hal Clark (hdeanclark_at_[hidden])
Date: 2015-09-04 13:02:00

> Date: Wed, 2 Sep 2015 23:36:39 +0200
> From: Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]>
> To: "Boost.Geometry library mailing list" <geometry_at_[hidden]>
> Subject: Re: [geometry] Are all query iterators const?
> Message-ID: <55E76BE7.4000804_at_[hidden]>
> Content-Type: text/plain; charset=windows-1252; format=flowed
>
> 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.
>

Thanks for the clear, informative response Adam. I'm primarily
interested in attaching arbitrary data to the point class in order to
also cluster non-spatial attributes. For example, using GDBSCAN
(http://link.springer.com/article/10.1023%2FA%3A1009745219419). The
crux of my issue is that the R*-tree may or may not need to index the
non-spatial attributes in addition to spatial coordinates. I'm still
toying with the idea of making these de-facto spatial ("virtual" or
"phony") coordinates, but some clustering algorithms require a clear
distinction. Also, defining a custom distance metric seems a bit
involved.

Your suggestion to make a mapping from some token to external data is
probably the most reliable means of including attributes, but would
result in lots of cache misses and make it hard to index attributes.
At the moment I'm simply giving the user a template to decide whether
they want to pay for fat attribute members.

You mentioned std::multiset which means duplicates are accepted and
indexed properly. This is great! Most R*-trees I've seen do not do
this. Is this a property that is guaranteed into the future? Other
than a post you made in 2014 for Boost 1.55
(http://stackoverflow.com/questions/22920055/boostgeometryrtreecontains-return-multiple-identical-results),
I do not see any claims in the documentation.

Also, not that my implementation is suitable at the moment, but are
you accepting pull requests for clustering algorithms? I see a
suspicious lack of them...

> 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.
>

Neat trick!

Thanks,
-hal clark