Re: [boost] [proprocessor] PP challenge!

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2006-11-09 04:40:07

David Abrahams wrote:
> Tobias Schwinger <tschwinger_at_[hidden]> writes:
> 
> 
>>Well then, (it was actually half a joke, but) time to attend to duty
>>(: I tried a different algorithm: Traversal of an imaginary,
>>linearized tree.
> 
> 
> Looks interesting... but I don't get it :)

OK, here is the description of the algorithm.

A linearized tree is inherently left-balanced, since it fills from top to bottom, left to right. E.g:

                    a
a b c ... ->       / \
                  b   c
                ...

The structure of such a tree can be represented by a single integer (number of nodes).
So we first have to calculate the total number of nodes given the number of leafes.

When traversing our "imaginary" (I use this adjective because there is no tree-shaped data structure, just an integer) we can emit code based on the node type and the steps performed during traversal (in detail: 'p ## n' for leafes, 'mpl::and<' when descending, '>' when ascending).

There's no recursion in the PP, so we throw a state machine and a stack at the problem.
Since we want to generate a right-balanced tree structure instead of a left-balanced one (like our imaginary tree), we implement traversal from right-to-left.

Does that work?

Regards,

Tobias