
Boost : 
From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 20061109 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 leftbalanced, 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 treeshaped 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 rightbalanced tree structure instead of a leftbalanced one (like our imaginary tree), we implement traversal from righttoleft.
Does that work?
Regards,
Tobias
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk