Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-09-10 05:39:16

Duzy Chan wrote:
> It's undefined:
>
> struct base
> {
> };
>
> struct derived : base
> {
>      void blah() { /* ... */ }
> };
>
> base obj;
>
> void foo()
> {
>      base * o = &obj;
>
>      derived * p = (derived*) o;
>      p->blah();     //<--------------------------- undefined behavior
> }
>
> --
> Duzy Chan
> http://duzy.info
>
>
> On Fri, Sep 10, 2010 at 8:06 AM, Simonson, Lucanus J
> <lucanus.j.simonson_at_[hidden] <mailto:lucanus.j.simonson_at_[hidden]>> wrote:
>
>     Adam Wulkiewicz wrote:
>      > Barend Gehrels wrote:
>      >> hi Adam,
>      >>
>      >>>
>      >>>
>      >>> Yes, I'm using the old version, thanks. But I don't know if I'll
>      >>> make corrections now. It seems that dynamic self balancing spacial
>      >>> index is desirable. What do you think about it?
>      >>>
>      >>
>      >> I don't know, it (whether or not self balancing) is probably
>      >> dependent on the situation and should ideally be configurable.
>      >>
>      >> It is of course no problem not making the corrections instantly, I
>      >> however cannot have a thorough look then (this is usually how I do
>      >> it, walking through). At least the main program should compile, and
>      >> I can use the old version, the last time it was sent in two mails,
>      >> can you send one consistent (compiling) set again?
>      >
>      > Hi,
>      >
>      > Sorry that I haven't written to you sooner. I'd like to show you
>      > something else instead of kd-tree.
>      > The community said that spacial index should work like std::set and
>      > even
>      > if I feel different the first data structure should be implemented
>      > this way. The spacial index may be e.g. a dynamic AABBTree. Leaf and
>      > internal
>      > nodes should be different classes derived from one Node class and
>      > created by allocator or possibly two different allocators defined by
>      > the user.
>      >
>      > I've implemented a generic tree which I'd like to use as a base of
>      > this container. I've taken the idea from "Game programming gems 4"
>      > but my version is an intrusive container without memory allocation.
>      > It's not
>      > the 'final' container it's just an implementation of some needed
>      > algorithms and iterators. Users could use this generic tree class to
>      > build their own trees.
>      >
>      > I had two designs in mind. First one was the tree which contains
>      > pointer
>      > to root. The tree structure would be defined only by nodes. Nodes
>      > could
>      > be manipulated only by use of the tree class and an iterator to node:
>      >
>      > child_iterator begin_child(Iter nodeit)
>      > void push_back_child(node *n, Iter nodeit)
>      >
>      > tree t;
>      > node *n = (node*)create_internal_node();
>      > t.push_back(n);
>      > n = (node*)create_leaf_node();
>      > t.push_back_child(n, t.root());
>      >
>      > The second one is a tree derived from node, which I've chosen. The
>      > main drawbacks are that the tree creation isn't intuitive, there is
>      > more pointers casting and in this case the tree isn't a container
>      > actually:
>      >
>      > node *n = (node*)create_internal_node();
>      > tree *t = (tree*)n;
>      > n = create_leaf_node();
>      > t.push_back_child((tree*)n);
>
>     This syntax isn't technially "legal" because the C++ standard says
>     that the results of casting a pointer of base type to a pointer of
>     derived type if the object pointed to is of base type is undefined.
>       That means there is no guarentee that the code will do what you
>     expect even if it compiles.  In reality it does compile and usually
>     does what you expect, but it is against boost coding standards to do
>     with sort of thing.  I'm not sure what type your
>     create_internal_node() returns, but I assume it is not tree*.  I
>     also don't think the public interface should provide access to
>     internal nodes, but regardless, the design of the internals cannot
>     rely on undefined behavior.
>
>     Regards,
>     Luke_______________________________________________
>     ggl mailing list
>     ggl_at_[hidden] <mailto:ggl_at_[hidden]>
>     http://lists.osgeo.org/mailman/listinfo/ggl
>

Is it undefined even if the object of derived class was created in the 
first place and the pointer casted to the base type? Isn't it used in 
Boost.Intrusive?

struct node {}
struct internal_node : public node {}
struct leaf_node : public node {}

internal_node *in = new internal_node();

node *n = static_cast<node*>(in);
/* do something with node n */

internal_node *in2 = static_cast<internal_node*>(n);
/* do something with internal node n2 */

leaf_node *ln = new leaf_node();

node *n2 = static_cast<node*>(ln);
/* do something with node n2 */

leaf_node *ln2 = static_cast<leaf_node*>(n2);
/* do something with leaf node ln2 */

I have objections about following code where object of derived type 1 is 
created, and the pointer is casted to the base class and then to the 
derived type 2 extending the interface of the base class.

struct tree : public node
{
     void foo()
     {
         do_something_with_node(static_cast<node*>(this));
     }	
     /* no atributes */
}

internal_node *in = new internal_node();
tree *t = static_cast<tree*>(static_cast<node*>(in));
t->foo();

Regards,
Adam