Geometry Boost List: [geometry] Rtree interface and translator

Subject: [geometry] Rtree interface and translator
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-02-18 10:58:08

Hi,

I've got some question regarding the rtree interface. The new rtree may 
store arbitrary values as long as there is passed an object which is 
able to extract Indexable (Point or Box) from the Value. It is the 
Translator and it's type is passed as the 3rd template parameter. I'm 
thinking about removing the Translator from the rtree because of the 
following reasons:
1. It's confusing for some people.
2. It may be replaced by some traits outside the rtree (then there would 
be not possible to pass a Translator into the rtree)
3. It may be used to store value which may be changed outside the 
spatial index, e.g. when someone wants to store shared_ptr<Something>, 
the Translator may return some Box from Something but it's possible to 
modify it outside the rtree. If we wanted to prevent this the translator 
should probably be entirely removed and only two forms of the rtree 
should be there for you:

setlike_rtree<Indexable, Parameters, Allocator>
maplike_rtree<Indexable, Data, Parameters, Allocator>

So what are your types? Should

1. rtree stay as it is with arbitrary value type and Translator object 
stored in the rtree.

typedef rtree<Value, Parameters, Translator> Rt;
Rt tree(Parameters(...), Translator(...));
tree.insert(Value(...));

+ the most flexible solution allowing e.g. to store just some IDs and 
the reference to the container in the Translator.
- additional parameter
- the user may mess up the internal structure of the rtree when only ID 
is stored (as an index or pointer)

2. rtree capable to store arbitrary value type and Translator traits 
defined outside the spatial index.

typedef rtree<Value, Parameters> Rt;
Rt tree(Parameters(...));
tree.insert(Value(...));

+ less parameters
- the user may still mess up the internal structure of the rtree when 
some pointer/iterator/reference_wrapper is stored.

3. rtree capable to store only those objects which are currently defined 
by the default translator, i.e. Indexable, std::pair<>, boost::tuple<>. 
Translator traits moved to the detail.

typedef rtree<Pair, Parameters> Rt;
Rt tree(Parameters(...));
tree.insert(Pair(...));

+ less parameters
+ the user may not mess up with the internal rtree structure
- arbitrary values can't be stored, to store pointers one must use e.g. 
std::pair<Box, shared_ptr<MyType> > as a Value type

4. rtree divided into 2 classes like STL's set and map therefore capable 
to store only Indexable or std::pair<>

typedef maplike_rtree<Indexable, Something, Parameters> Rt;
Rt tree(Parameters(...));
tree.insert(std::make_pair(Indexable, Something));

+ well known STL interface
+ the user may not mess up with the internal rtree structure
- arbitrary values can't be stored, to store pointers one must use e.g. 
std::pair<Box, shared_ptr<MyType> >
- can't store tuples

The last one has also another advantage which I'll describe in the next 
email. For now I'll just say that if we implemented also a container 
version of an rtree (e.g. capable to store big move-only objects) 
probably this interface would be used. Then the spatial index version 
would have the same interface. But this is not a requirement.

So what do you think?

Regards,
Adam