Geometry Boost List: Re: [geometry] [index] r-tree concerns

Subject: Re: [geometry] [index] r-tree concerns
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2012-06-23 06:52:49

feverzsj wrote:
W dniu 2012-06-23 08:13, feverzsj napisal(a):
> hi, Adam
>  > 1. Should MAX and MIN be compile-time? rtree.v2.01 took run-time MAX and
>  > MIN. It was just a little slower but took more space than the current
>  > one because static size nodes were unable to use (vectors takes more
>  > space). But what are real-life use cases?
> If there is only slight impact on performance, I think a more dynamic
> way would be prefered for lib usage.
> The template <Max Min> can be still present for convenience, e.g.:
> template<..., int Max = defaultMax, int Min, defaultMin>
> struct rtree
> {
>      rtree(..., int max_ = Max, int min_ = Min );
> };

If someone want to use the most optimized version he should be able to 
use it. So the best thing to do will be providing two interfaces. 
Something you've proposed. Internally it isn't a problem because my 
implementation allows using of various types of nodes. But I don't know 
if it should look the way you've proposed because the user wouldn't know 
which values are used by the rtree. But maby something like this:

rtree<Value, AlgoStaticParams<Max, Min>, UseStatic>
   t(AlgoDynamicParams(max, min));

Or some wrapper

rtree_static<Value, AlgoStaticParams<Max, Min>> t;
rtree_dynamic<Value, AlgoStaticParams<> >
   t(AlgoDynamicParams(max, min));

The thing is more complicated because there are various creation 
algorithms. Each algorithm may take different compile- and run-time 
parameters. The interface in this case should be carefully designed. It 
would be confusing otherwise. Have to think about this.

>  > 2. Both versions' queries returns values by copy. This means that if you
>  > want to modify your values, you must store them somewhere else. When
>  > e.g. The difference is that rtree.v2 may take various value types. If
>  > e.g. Point is passed to the rtree.v2, the container behaves as std::set,
>  > it returns copies of Point. If std::pair<Point, Data> is passed it
>  > behaves as std::map. But the difference between the rtree and std
>  > container is that they returns iterators not copies. What is more from
>  > known reasons they make Keys const and returns iterator<const Point> and
>  > iterator<pair<Point, Data>> respectively.
>  >
>  > The main difference between std containers and rtree is that rtree's
>  > iterators probably won't be preserved after the modification of the
>  > rtree because internally values are stored in arrays/vectors. So, if the
>  > interface is too close to the std containers users may assume that it
>  > works exactly the same way.
>  >
>  > My questions are:
>  > Should rtree.v2 return some iterator<const Point> or
>  > iterator<std::pair<const Point, Data>> respectively?
>  > Maby there should be two query interfaces one returning copies, one
>  > returning iterators?
>  > What should be the interface of the rtree? Maby there shouldn't be only
>  > one rtree<Value> but rtree_set<KeyValue> and rtree_map<Kay, Value>?
> In old style, rtree (or query result) is traversed by visiter pattern.
> While in GP style, concerning the characteristic of rtree, the single
> pass range concept could be a good choice. But the implementation of
> this range and iterator may be complex.
> So, my suggestion is using the visiter pattern as the basic traverse
> concept, you or users may develope more complex usage based on this.
> For convenience, there may be a interface that return query results as a
> sequence of values(like rtree.v1 dose);

Yes was considering implementation of the single pass iterator but I 
have something else in mind here. Sorry, my use of the 'iterator' term 
was confusing. I'm considering some way to return a reference/pointer to 
objects stored in the rtree to use it as primary container.

In the old rtree result is returned as a std::deque of values copies. 
The same is in the new one. So in both cases it's not possible to modify 
some properties of values stored in the r-tree as it is possible with 
values stored in std::map. E.g. to find some objects in the area and 
change their color to red using only one container - the rtree. You may 
still store your objects in the std::vector and indexes in the rtree but 
you can't do it using only the rtree. And because you can't use it as 
your primary container, after removing some values from the std::vector 
you should rebuild the whole rtree because indexes will be broken. You 
could of course give them some IDs and search obejcts by ID but it would 
be a lot slower.

>  > 3. The reason why rtree takes rtree<Value> and dispatches it's type is
>  > that it allows to use user-defined value types. It uses a Translator
>  > object to get a Key from Value. The default one handles Points, Boxes,
>  > std::pairs, pointers and iterators. The user may provide whatever type
>  > he wants along with the translator. I now realized that this may be not
>  > safe because he may modify the Key outside the rtree after the
>  > insertion. Should this stay this way? or allow only predefined types
>  > e.g. Point, Box, pair<Point, T>, pair<Box, T> and tuples?
>  >
>  > Still, if someone wants to brake something he will do it. Even with std
>  > containers one may use some e.g. wraped pointer as a Key and mess up
>  > with it.
> Actually, my most concern is, besides in-memory rtree, if the rtree.v2
> is able to handle a external-memory rtree. All in all, that’s what
> R-tree for.
> So there should be more indirect concepts to be involved. Except this
> translator to exact bbox, there may be concept for access child nodes.

It is possible to provide your own types of nodes and adapt related 
concepts. You may specify how to visit nodes, how to get elements form 
them, how to allocate memory etc. So this isn't a problem.

The translator is at the upper level it translate between Values and 
r-tree internals. And now, the user may provide whatever class he want 
and he must be carefull to not modify the data related to key used by 
the r-tree.

>  > 4. It is related to the previous point
>  >
>  > Default translator uses SFINAE, which I believe won't work on all
>  > compilers. Should there be:
>  > - hard-coded types instead (less default functionality but someone may
>  > still write his translator and to be honest those additional types
>  > probably won't be used),
>  > - some #ifdef BOOST_SFINAE_SUPPORTED (different interface for some
>  > compilers),
>  > - as is (don't compilable on some compilers)?
> Generally, traits/policy class would be prefered. You could put the
> default behaviour in to a default transltor. All these default handled
> types should be handled there.

Yes but, do you think types should be hard-coded? Now I'm using SFINAE, 
e.g. all types with defined element_type will be supported by the rtree 
as a smart pointers to e.g. a Box.

Regards,
Adam