Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-09-11 07:02:27

Simonson, Lucanus J wrote:
> Adam Wulkiewicz wrote:
>>> We should steer the discussion of design away from focusing on what
>>> is wrong and make constructive suggestions about what good
>>> alternatives might be.  Then we can discuss how various design
>>> options meet the design goals Adam may have, which is a much more
>>> interesting conversation.
>>
>> 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;
>> };
>
> Sorry, the design doesn't make sense to me.  I don't see the point of any of these four pointers.  Why wouldn't the node just have an array of N child nodes?  Why a base class not and not a template parameter and traits?  If you are inheriting without a virtual destructor people will ask why.  I can't see any answer.  Inheritance requires a strong rationale in boost and Liskov substitution principle gets thrown around a lot.  You never explained how your is_leaf and is_node traits work, but I see no obvious mechanism.

The original idea was presented in "Game programming gems 4" by Bill 
Budge from Electronic Arts. This tree is intended to be a multi-purpose 
generic tree which enables to traverse it in various ways. The original 
node has this structure:

template <typename T>
struct node
{
   /*four pointers*/
   T value;

   /*methods*/
};

I just thought, I'll do intrusive container. User musn't use 
inheritance. He must just implement some traits and may use arbitrary 
node e.g. described above. The inheritance is not required.

Deriving tree from node is not required. It was used in the original 
idea but tree may be just a container with pointer to root node and all 
iterators may work on nodes instead of trees.

Pros:
- pre-order iterator uses one redirection - next pointer,
- post-order iterator iterates in constant time,
- tree traversing doesn't require recursion, use of implicitly defined 
stack or skipping the nodes (the exception is level-order iterator but 
it's used rarely),
- node may have arbitrary number of children nodes.

Cons:
- children iterator is slower than in the case if node has just array of 
pointers to children nodes and it isn't random_access_iterator,
- inserting in top-bottom building algorithm may have non-constant 
complexity. If the node is inserted from the back, last_descendant 
pointers of parent nodes must be updated. Worst case scenario is if 
someone puts the node behind the root's last_descendant, all parents 
must be updated (but the user may build bottom-up or insert nodes from 
right to left in top-down algorithm).

The structure of the node:

next points to the node next in pre-order iteration.
previous_sibling points to the node if parent node has only one child.
previous_sibling of the first child points to the last child.
last_descendant of leaf node points to this node.

If we have a tree

      a
     / \
    b   d
   /   /|\
  c   e f g

pointers points to:

this             | a b c d e f g
parent           | 0 a b a d d d
next             | b c d e f g 0
previous_sibling | a d c b g e f
last_descendant  | g c c g e f g

Default node's values:

void init(node *n)
{
   n->parent = null_ptr;
   n->next = null_ptr;
   n->previous_sibling = n;
   n->last_descendant = n;
}

Navigational functions has constant complexity:

node * next(node * n)
{
   return n->next;
}

// next node in pre-order iteration
node * next(node * n)
{
   return n->next;
}

// previous node in pre-order iteration or
// next node in post-order iteration from right to left
node * previous(node * n)
{
   node *parent = n->parent;
   if ( parent )
     return parent->next == n ?
       parent :
       n->previous_sibling->last_descendant;
   else
     return null_ptr;
}

node * first_child(node *n)
{
   node *next = n->next;
   return (next && (next->parent == n)) ? next : null_ptr;
}

node * last_child(node *n)
{
   node *child = first_child(n);
   return child ? child->preious_sibling : null_ptr;
}

node * next_sibling(node *n)
{
   node *sibling = n->last_descendant->next;
   return (sibling && (sibling->parent != n->parent)) ?
     null_ptr : sibling;
}

node * previous_sibling(node *n)
{
   node *parent = n->parent;
   return (parent && (parent->next != n)) ?
     n->previous_sibling : null_ptr;
}

bool is_root(node *n) { return !n->parent; }
bool is_leaf(node *n) { return n->last_descendant == n; }

Spacial index will be used mainly for search and be updated rarely. 
Moreover, pre-order traverse algorithm will be used.

But spacial index should have children random access iterator because 
e.g. in quadtree or kd-tree there are often checks of certain nodes e.g. 
left or right. One of the nodes may even not be created. In the node 
which have previously described structure there must have been some flag 
describing which one child is it.

Recursion is slower than iteration and uses more memory. And there may 
be a tree with large number of children. Take e.g. this node:

template <typename T, size_t D>
struct n_tree_node
{
   boost::array<n_tree_node*, static_pow<2, D>::ret> children;
   T value;
}

The number of pointers in n-dimensional quadtree is 2^n, so for octree 
we have node with 8 pointers, 4d - 16 etc.

There is an overhead when using both types of nodes. Maby some hybrid of 
these two nodes would give us children random iterator and fast 
pre-order iterator. But then the node may be large.

Regards,
Adam