[stringtemplate-interest] [ST4] Help needed with recursive template to traverse a tree

[Udo Borkowski]

I finally found a solution (requires ST4 Beta-4). 

The following template can be used to write the pathes of all nodes:

allTreeNodePathes(node,prefix="",
			newPrefix={«({«prefix»«node.name»/})»}) ::= <<
«prefix»«node.name»
«node.children:
    {child|«allTreeNodePathes(
               node=child,
               prefix=newPrefix)»}»
>>

main(p) ::= <<
«allTreeNodePathes(node=p)»
>>


I.e. it will write

A
A/B1
A/B1/C1
A/B1/C2
A/B2
A/B2/C3
A/B2/C4


You will notice the template is very similar to my original attempt that led to cycles. 

To get rid of the cycle I "pre-calculated" the argument value {«prefix»«node.name»/}, that led to the cycle.

For the pre-calculation I introduced an extra parameter newPrefix with the evaluated argument value {«prefix»«node.name»/} as the default value. Callers will never set values to newPrefix but it will always use its default value. So newPrefix is more a (final) "helper variable" for internal use than a real parameter.

This "trick" may also be helpful in other cases.

Udo



On 01.02.2011, at 16:26, Udo Borkowski wrote:

> I need some help with a recursive template.
> 
> Assume you have a tree like this:
> 
>       A
>      / \
>     /   \
>   B1     B2
>  /  \   /  \
> C1  C2 C3  C4
> 
> A node is implemented as a map with a "name" key (String) and a "children" key (list of node objects).
> 
> How to get a list of all "pathes" to the nodes (in preorder)?
> 
> I.e. I want this output:
> A
> A/B1
> A/B1/C1
> A/B1/C2
> A/B2
> A/B2/C3
> A/B2/C4
> 
> I tried things like the following but run into problems with cycles. E.g. I need to refer to the "outer" prefix and node.name to build the new prefix and assign it to the argument:
> 
> allTreeNodePathes(node,prefix) ::= <<
> «prefix»«node.name»
> «node.children:
>     {child|«allTreeNodePathes(
>                node=child,
>                prefix={«prefix»«node.name»/})»}»
> >>
> 
> 
> main(p) ::= <<
> «(allTreeNodePathes(node=p,prefix=""))»
> >>
> 
> 
> Any suggestions?
> 
> Udo
> 
> _______________________________________________
> stringtemplate-interest mailing list
> stringtemplate-interest at antlr.org
> http://www.antlr.org/mailman/listinfo/stringtemplate-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/stringtemplate-interest/attachments/20110207/680eaf0d/attachment.html