xsl-list
[Top] [All Lists]

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

2003-12-02 15:43:04

"David Tolpin" <dvd(_at_)davidashen(_dot_)net> wrote in message
news:200312021756(_dot_)hB2HuwoY060207(_at_)adat(_dot_)davidashen(_dot_)net(_dot_)(_dot_)(_dot_)
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="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:call-template>
    </xsl:if>

  </xsl:template>

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

    <xsl:choose>
      <xsl:when test="$head">
<xsl:choose>
  <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:call-template>
  </xsl:when>
  <xsl:otherwise>
    <xsl:for-each select="$head">
      <xsl:copy>
<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: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]
                       [(_at_)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