Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Hartmut Kaiser (hartmut.kaiser)
Date: 2010-09-11 13:58:28

> Maby I'll describe the original idea. There may be a lot of different tree
> structures so I'd like to design a generic tree template which might be
> used as an internal structure of various containers. This tree should
> probably be the intrusive container. Base node structure I've used has 4
> pointers:
> 
> struct node
> {
>    node *next;
>    node *parent;
>    node *previous_sibling;
>    node *last_descendant;
> };
> 
> Various types of trees may be created using this node, all navigation
> algorithms has constant complexity, pre-order iterator is very fast (one
> redirection), post-order and child iterators are fast. Tree container
> works on objects of node class. Node may have arbitrary structure. User
> must only implement some node traits and pass it to the tree template.

That looks like an attempt to build a kitchen sink. Different tree
structures/iteration strategies require only part of those pointers to be
present. Why not leave the decision what's actually required to construct an
adequate tree to the user? If the user knows she needs pre-order traversal,
well, add the proper pointers. If pre-order traversal is not needed, those
additional pointers are a waste... Have a look at the Boost intrusive
containers library for an example of fine grained composition policies
allowing to build exactly the data structures one might need.

> To define leaf and internal nodes one may derive from some basic node and
> wrapp the creation and manipulation of two types of nodes inside some
> container(e.g. AABBTree). Following code presents how to create nodes and
> manipulate them inside two containers (generic tree and some container
> using it) not the real internals of any of them.

Virtual functions should be utilized as a last resort only. Admittedly,
sometimes it's just the only way to do things, but most of the time you can
do without virtual functions.

Regards Hartmut
---------------
http://boost-spirit.com

> // user defined types
> struct node { node *n1, *n2, *n3, *n4; }; struct node_traits { /*...*/ };
> 
> struct internal_node : public node {/*...*/}; struct leaf_node : public
> node {/*...*/};
> 
> // tree creation
> typedef node_algorithms<node_traits> na;
> 
> node *root = create_internal_node();
> leaf_node *l = create_leaf_node();
> na::push_back_as_child(root, l);
> 
> // pre order iteration
> for(node *n = root; n; n = na::next(n))
> {
>    if ( na::is_leaf(n) )
>    {
>      leaf_node *ln = static_cast<leaf_node*>(n);
>      // do something
>    }
>    else
>    {
>      internal_node *in = static_cast<internal_node*>(n);
>      // do something
>    }
> }
> 
> The nodes might have different structure e.g.:
> 
> struct leaf;
> struct node;
> 
> struct node_base
> {
>    union next_
>    {
>      leaf *l;
>      node *n;
>    } next;
> 
>    node *parent;
> 
>    union previous_sibling_
>    {
>      leaf *l;
>      node *n;
>    } previous_sibling;
> 
>    struct are_leafs_
>    {
>      unsigned char next             : 1;
>      unsigned char previous_sibling : 1;
>    } are_leafs;
> };
> 
> template <typename T>
> struct node : public node_base
> {
>    leaf *last_descendant;
>    T value;
> };
> 
> template <typename T>
> struct leaf : public node_base
> {
>    // leaf node's last descendant is equal to this pointer
>    // so it musn't be stored in this case
>    T value;
> };
> 
> But I think the previous design is more 'elegant' and effective.
> 
> Regards,
> Adam
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl