Boost logo

Geometry :

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:

- 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.

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

- 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?


Geometry list run by mateusz at