Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-09 14:15:58

Bruno Lalande wrote:
> Hi,
>
>
>     The current implementation of the spatial index is, if I'm right,
>     full of virtual functions and shared ptr's, which I would like to
>     limit to the minimum... If possible, of course.
>
>
> I see your point. A quick glance at the source code indeed shows a few
> things that should not be there. The fact of using a shared_ptr to
> manage tree elements is probably not the most efficient way to do, for
> instance. I would say shared_ptr is more for high level code. At low
> level within a library, performance should be the priority. Virtual
> functions like is_leaf must go away as well (as discussed).
>
> That said, we must keep in mind that such a tree cannot be obtained only
> by compile-time techniques, since it is dynamic. If STL or Boost don't
> use much dynamic polymorphism, it is simply because they are all about
> adapting some metalibrary to a client code at compile-time. Here, we are
> talking about the guts of a machine. If the guts in question take input
> only at run-time, obviously they will use run-time techniques. Even a
> book like "C++ Template Meta-programming", which is almost all about
> compile-time computations, talks about and uses virtuality when it comes
> to "cross the run-time boundary" (see "Type Erasure"). And the few Boost
> library which are more about applicative tasks than library writing
> tools definitely use dynamic polymorphism (e.g. Filesystem, Format,
> Wave, Serialization, ProgramOptions...) and dynamic memory allocation
> (e.g. Iostream, DateTime...).
>
> So to summarize: we should avoid confusing interaction between library
> and client code (which typically involves compile-time techniques), and
> core guts implementation (which possibly involves a lot of runtime stuff).

Yes, rtree must be dynamic. Yes, code should be redesigned.

To keep it short, this is what it should be done:

1.
- leave current nodes hierarchy (node, internal_node, leaf),
- remove as much virtual functions as possible, functionalities of 
specific type of node will be implemented in this node's class only,
- use visitors instead of virtual functions to reduce vtable to minimum.

2.
- replace shared_ptr(s) with simple pointers,
- replace memory allocation done by operator new with some allocator 
(std::allocator by default).

3.
- remove equals() from translator, since it should just translate from 
Value to Indexable and define operator== for geometry::point, geometry::box.

Is it all for now or am I missing something?

Regards,
Adam