Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Barend Gehrels (barend)
Date: 2011-03-08 13:30:57

On 8-3-2011 10:50, Bruno Lalande wrote:
>
>
>     2. One virtual function is_leaf()
>
>
> This should really be avoided as much as possible. Type testing is the 
> most common antipattern is dynamic polymorphism, for known reasons.
>
> I should have been clearer in my previous email about double-dispatch. 
> First just to clarify, this has nothing to do with tag dispatching. 
> It's a dynamic, runtime mechanism. Second, the specific application of 
> multiple dispatching I was talking about was the Visitor pattern. 
> Typically in your program you will need to traverse your tree, doing 
> different things depending on whether you are on a node or a leaf, 
> potentially calling specific non virtual functions on them. Visitor 
> allows a class to visit each instance of a class hierarchy and do 
> specific things of each specific class of that hierarchy. The design 
> you are describing is clearly a Composite pattern, and if I refer to 
> the schema at the end of the GoF book showing how patterns relate to 
> each other, there's a "adding operations" relation from Composite to 
> Visitor. I fully agree with that view: the standard way to add 
> operations (algorithms, whatever you call that) on a composite 
> structure is to use a Visitor. We should really try to stick to that 
> before going further.

This sounds very good.

>
>     3. No virtuals. Unused data.
>
>
> That's the other solution I had described, but only possible if your 
> node and leaf classes have no specific operation. Is that the case? 
> (my understanding was that no)
>
> Besides that, the pros and cons I can see are:
> - Pro: faster. Testing for vector<T>::empty() is faster than a v-table 
> lookup.
> - Cons: space in memory. An empty vector<T> is larger than a v-table 
> (in my GCC: 24 bytes vs 7 bytes). BUT the internal nodes will 
> necessarily be smaller (because in the virtual approach they have both 
> a vector AND a v-table). So it mostly depends on the proportion of 
> nodes vs leaves in the tree.
>
>
>  Let me be clear: I am NOT asking you to avoid virtuality (Visitor is 
> all about virtuality). Just asking to use it properly by going for the 
> "state-of-the-art" way about manipulating composite structures, and to 
> avoid making virtual some functions which are only supposed to live in 
> one specific child class.

One of the things is virtuality. The other thing is dynamic memory, I 
forgot to mention this yesterday. If I'm correct each node contains a 
vector of boxes/node pointers and each note pointer is a dynamically 
allocated shared ptr. This all together is too much dynamic behaviour, 
to my intuition. In the whole Boost.Geometry we don't use any shared 
ptr, no call to new, no virtual functions. Beside to the projections 
where it is optional (they can be instantiated staticly and dynamicly) 
and incidental (only one per projection).

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.

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110308/833d759d/attachment.html