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

Subject: Re: [xsl] HOWTO: convert flat list w/ level information to a hierarchial one?
From: David Tolpin <dvd@xxxxxxxxxxxxxx>
Date: Tue, 2 Dec 2003 21:56:58 +0400 (AMT)
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"/>


<xsl:transform xmlns:xsl=""; version="1.0">

  <xsl:template match="/node">
      <xsl:call-template name="hier">
	<xsl:with-param name="set" select="node"/>

  <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="head" select="$set[1]"/>
	<xsl:with-param name="tail" select="$set[position()>1]"/>
	<xsl:with-param name="base" select="$base"/>
	<xsl:with-param name="accu" select="/.."/>

  <xsl:template name="hier-rec">
    <xsl:param name="head"/>
    <xsl:param name="tail"/>
    <xsl:param name="base"/>
    <xsl:param name="accu"/>

      <xsl:when test="$head">
	  <xsl:when test="$tail and $tail[1]/@level>$base">
	     <xsl:call-template name="hier-rec">
	       <xsl:with-param name="head" select="$head"/>
	       <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:for-each select="$head">
		<xsl:copy-of select="$head/@*"/>
		<xsl:call-template name="hier">
		  <xsl:with-param name="set" select="$accu"/>
		  <xsl:with-param name="base" select="$base+1"/>
	    <xsl:if test="$tail">
	      <xsl:call-template name="hier">
		<xsl:with-param name="set" select="$tail"/>
		<xsl:with-param name="base" select="$base"/>


David Tolpin

> Dear XSLT Community!
> I couldn't solve a problem of class "flat file transform".

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

@type = 'c' ... container
@type = 'i' ... Item
> transform to:
> <node>
>  <node type="c" name="toplevel">
>   <node type="i" name="1. item"/>
>   <node type="c" name="2. container"/>
>    <node type="i" name="2.1 item"/>
>    <node type="i" name="2.2 item"/>
>   </node>
>   <node type="i" name="3. item"/>
>   <node type="c" name="4. container">
>    <node type="i" name="4.1 item"/>
>    <node type="c" name="4.2 container"/>
>     <node type="i" name="4.2.1 item"/>
>    </node>
>   </node>
>  </node>
> </node>
> What I tried:
> Calling recursively a template with passing parameters $node, 
> $last-level, but I failed to leave recursion in a proper way;-(
> Any pointer|hint|solution for a (ideally) XSLT1.0 approach is 
> highly appreciated!

 XSL-List info and archive:

Current Thread