## [xsl] Re: HOWTO: convert flat list w/ level information to a hierarchial one?

 Subject: [xsl] Re: HOWTO: convert flat list w/ level information to a hierarchial one? From: "Dimitre Novatchev" Date: Tue, 2 Dec 2003 23:43:04 +0100
```"David Tolpin" <dvd@xxxxxxxxxxxxxx> wrote in message
news:200312021756.hB2HuwoY060207@xxxxxxxxxxxxxxxxxxxxxx
> An algorithm that solves the problem is (in Haskell):
>
> data Hier a = List [Hier a]|Leaf a deriving Show
>
> hier::[Integer]->[Hier Integer]
> hier [] = []
> hier al@(a:as) = group al 0 [] []
>
> group::[Integer]->Integer->[Integer]->[Hier Integer]->[Hier Integer]
> group (i:is) base al res
>   | i > base = group is base (al++[i]) res
>   | otherwise = res
>     ++ (case al of
>   a:as -> [List (group al (base+1) [] [])]
>   _ -> []) ++ [Leaf i] ++ (group is base [] [])
> group [] base al@(a:as) res = res ++ [List (group al (base+1) [] [])]
> group [] base _ res = res
>
> Since all definitions have res as the left operand of list concatenation,
it can be
> implemented in XSLT. The code in XSLT is below. By the way, no need for
item/container tags;
> besides, the algorithm can as well handle non-contiguous nesting, such as:
>
> <node level="1"/>
> <node level="3"/>
> <node level="5"/>
>
> etc.
>
> <xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
version="1.0">
>
>   <xsl:template match="/node">
>     <xsl:copy>
>       <xsl:call-template name="hier">
> <xsl:with-param name="set" select="node"/>
>       </xsl:call-template>
>     </xsl:copy>
>   </xsl:template>
>
>   <xsl:template name="hier">
>     <xsl:param name="set"/>
>     <xsl:param name="base">0</xsl:param>
>
>     <xsl:if test="\$set">
>       <xsl:call-template name="hier-rec">
> <xsl:with-param name="tail" select="\$set[position()>1]"/>
> <xsl:with-param name="base" select="\$base"/>
> <xsl:with-param name="accu" select="/.."/>
>       </xsl:call-template>
>     </xsl:if>
>
>   </xsl:template>
>
>   <xsl:template name="hier-rec">
>     <xsl:param name="tail"/>
>     <xsl:param name="base"/>
>     <xsl:param name="accu"/>
>
>     <xsl:choose>
> <xsl:choose>
>   <xsl:when test="\$tail and \$tail[1]/@level>\$base">
>      <xsl:call-template name="hier-rec">
>        <xsl:with-param name="tail" select="\$tail[position()>1]"/>
>        <xsl:with-param name="base" select="\$base"/>
>        <xsl:with-param name="accu" select="\$accu|\$tail[1]"/>
>      </xsl:call-template>
>   </xsl:when>
>   <xsl:otherwise>
>       <xsl:copy>
> <xsl:call-template name="hier">
>   <xsl:with-param name="set" select="\$accu"/>
>   <xsl:with-param name="base" select="\$base+1"/>
>                 </xsl:call-template>
>       </xsl:copy>
>     </xsl:for-each>
>     <xsl:if test="\$tail">
>       <xsl:call-template name="hier">
> <xsl:with-param name="set" select="\$tail"/>
> <xsl:with-param name="base" select="\$base"/>
>       </xsl:call-template>
>             </xsl:if>
>   </xsl:otherwise>
> </xsl:choose>
>       </xsl:when>
>     </xsl:choose>
>
>   </xsl:template>
> </xsl:transform>
>
> David Tolpin
> http://davidashen.net/

The following transformation achieves the same (level values are monotonous
but not strictly consecutive, container/item info not used) and at the same
time is twice shorter and considerably less complex.

It is just 33 lines (compared to 66 lines) and consists of just two
templates one of which has one parameter and the other no parameters
(compared to three templates one of which takes two parameters and another
which takes four parameters):

<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:template match="/node">
<node>
<xsl:apply-templates select="node[1]">
<xsl:with-param name="pParentLevel"
select="-1"/>
</xsl:apply-templates>
</node>
</xsl:template>

<xsl:template match="node">
<xsl:param name="pParentLevel"/>
<xsl:copy>
<xsl:copy-of select="@*"/>
<xsl:apply-templates
select="following-sibling::node[1]
[@level > current()/@level]">
<xsl:with-param name="pParentLevel" select="@level"/>
</xsl:apply-templates>
</xsl:copy>
<xsl:apply-templates
select="following-sibling::node
[not(@level > current()/@level)
and
@level > \$pParentLevel
]
[1]">
<xsl:with-param name="pParentLevel" select="\$pParentLevel"/>
</xsl:apply-templates>
</xsl:template>
</xsl:stylesheet>

When applied on this source.xml:

<node>
<node level="0" type="c" name="toplevel"/>
<node level="3" type="i" name="1. item"/>
<node level="3" type="c" name="2. container"/>
<node level="4" type="i" name="2.1 item"/>
<node level="4" type="i" name="2.2 item"/>
<node level="2" type="i" name="3. item"/><!-- implicit close of previous
container -->
<node level="2" type="c" name="4. container"/>
<node level="3" type="i" name="4.1 item"/>
<node level="3" type="c" name="4.2 container"/>
<node level="5" type="i" name="4.2.1 item"/>
</node>

the wanted result is produced:

<node>
<node level="0" type="c" name="toplevel">
<node level="3" type="i" name="1. item"/>
<node level="3" type="c" name="2. container">
<node level="4" type="i" name="2.1 item"/>
<node level="4" type="i" name="2.2 item"/>
</node>
<node level="2" type="i" name="3. item"/>
<node level="2" type="c" name="4. container">
<node level="3" type="i" name="4.1 item"/>
<node level="3" type="c" name="4.2 container">
<node level="5" type="i" name="4.2.1 item"/>
</node>
</node>
</node>
</node>

=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL

XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list

```