Geometry Boost List: [ggl] rtree query interface

Subject: [ggl] rtree query interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-08-22 12:48:37

feverzsj wrote:
> hi:
>
> 1. IIRC, ggl still miss functor interfaces for predicates to use with
> boost.range.
> something like:
>
> template<class G1>
> struct Predicator
> {
> G1 const& g1;
>
> Predicator(G1 const& g) : g1(g) {}
>
> template<class G2>
> bool operator()(G2 const& g2) const
> {
> return predicate(g1, g2);
> }
> };
>
> such functor may be used with both boost.range and rtee;
>
>
> 2. rtree may be consider as either an index structure or a boost.range:
> while using with some predicates(e.g.
> equals/intersects/overlaps/within), rtree works faster as an index
> structure;
> while using with other predicates, rtree may be just taken as a
> boost.range.
> so: "t | index::filtered(within(g))" and "t | filtered(within(g))" give
> the same result but the previous one could be much more faster.
>
> as for chained case,
> t | pred1() | pred2()| ... | predN()
>
> Will it return a new rtree for index::filtered()?
> Well, I think this could be less efficient for most use case, and not
> work well with those predicates that rtree not good at.
> I'd prefer simply return a sequential range at the first place.
> so :
> only the first "t | index::filtered(pred(g))" makes use of index
> facility. The followed adaptors will just deal with normal sequential
> range;

First of all I'd like to clarify. I'll be writing about the original 
design of the query which probably will be changed. I wanted to use only 
the syntax of Boost.Range to build a Query/Expression object containing 
all predicates. This object would be passed to the rtree. So the line

tree | index::pred1() | index::pred2() | some_namespace::pred()

would compile and produce a range of objects returned by query filtered 
by some_namespace::pred(). But

tree | some_namespace::pred() | index::pred1()

wouldn't even compile.

I now realize that this may be confusing since everybody thinks that 
predicates works exactly like filters from Boost.Range but they 
shouldn't. They should work more like Expressions.

About the new design...

Using filtered() seems reasonable but I don't know if we need 2 of them. 
Type of a conteiner on the left of operator| should define the type of 
query. filtered() should take an Basic Expression as a parameter and 
return it inside a simple wrapper.
Next, for different containers/ranges this Basic Expression should be 
transformed to the right form.
E.g. for Geometry.Index container the Basic Expression should be passed 
to the container and transformed by the container. Rtree will transform 
it to the different form than Kd-tree.
For stl-like containers Basic Expression will be transformed to the 
different form, probably even wrapped inside a iterator of the resulting 
range.

Still, this may be confusing because filters will work differently for 
different sequences.

t | filtered(Expr) | something()

will produce optimized query but

t | something() | filtered(Expr)

won't and this is probably not how the user thinks about ranges. I don't 
even know if spatial index should expose iterators, begin(), end() etc. 
and compile in the second case.

Because everybody thinks: "Oh! Boost.Ranges. I know how it works!" maby 
it's better to use something else to distinguish between Geometry query 
and ranges. Function or operator different than.

index::filtered(t, Expr) | other_filter()
index::query(t, Expr) | other_filter()
t[Expr] | other_filter()
t(Expr) | other_filter()
t >> query(Expr) | other_filter()

Still, there is a problem with operators - they may be defined already. 
E.g. vect[Expr] | other_filter().

Thoughts?

About the Expression in the next email.

Regards,
Adam