Boost logo

Geometry :

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


Geometry list run by mateusz at loskot.net