Build a "path" with XSLT Recursion

Question

I have a problem an at the moment no idea to solve it ;-(

I have a category structure as input document (xml) and want to build a path structure. I can only use xslt and want to generate a new xml structure.

The input structure looks like this:

<?xml version="1.0" encoding="UTF-8"?>
<Positions>
    <Positionen>
        <ID>1</ID>
        <Parent></Parent>
    </Positionen>

    <Positionen>
        <ID>2</ID>
        <Parent>1</Parent>
    </Positionen>

    <Positionen>
        <ID>3</ID>
        <Parent>1</Parent>
    </Positionen>

    <Positionen>
        <ID>4</ID>
        <Parent>2</Parent>
    </Positionen>

    <Positionen>
        <ID>5</ID>
        <Parent>4</Parent>
    </Positionen>

    <Positionen>
        <ID>6</ID>
        <Parent>2</Parent>
    </Positionen>

</Positions>

The output structure should be this:

<?xml version="1.0" encoding="UTF-8"?>
<Positions>
    <Positionen>
        <ID>1</ID>
        <Parent></Parent>
        <Path>1</Path>
    </Positionen>

    <Positionen>
        <ID>2</ID>
        <Parent>1</Parent>
        <Path>1/2</Path>
    </Positionen>

    <Positionen>
        <ID>3</ID>
        <Parent>1</Parent>
        <Path>1/3</Path>
    </Positionen>

    <Positionen>
        <ID>4</ID>
        <Parent>2</Parent>
        <Path>1/2/4</Path>
    </Positionen>

    <Positionen>
        <ID>5</ID>
        <Parent>4</Parent>
        <Path>1/2/4/5</Path>
    </Positionen>

    <Positionen>
        <ID>6</ID>
        <Parent>2</Parent>
        <Path>1/2/6</Path>
    </Positionen>

</Positions>

How can I do this with xslt with a recursion? Hoping fore some help. Thanks in advance. LStrike

Dimitre Novatchev Dimitre Novatchev · Accepted Answer · 2012-04-12T12:26:26

Some answers to this question are good but rather inefficient (O(N^2)).

This is so, because the path is constructed from scratch for every Positionen element. The average path length is N/2 and there are N Positionen elements. That means that N*N/2 operations are needed as minimum to construct all paths -- and this is quadratical time complexity.

Here is a more efficient O(N*log(N)) -- could be even (O(N) -- linear) solution in case it is acceptable for the Positionen elements in the output to be unsorted:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:ext="http://exslt.org/common" exclude-result-prefixes="ext">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>
 <xsl:strip-space elements="*"/>

 <xsl:key name="kChildren" match="Positionen" use="Parent"/>

 <xsl:template match="node()|@*">
     <xsl:copy>
       <xsl:apply-templates select="node()|@*"/>
     </xsl:copy>
 </xsl:template>

 <xsl:template match="/">
  <xsl:variable name="vrtfPass1">
    <xsl:apply-templates select="node()|@*"/>
  </xsl:variable>

  <xsl:variable name="vPass1" select="ext:node-set($vrtfPass1)"/>

  <xsl:apply-templates select="$vPass1/*" mode="pass2"/>
 </xsl:template>

 <xsl:template match="/*">
  <xsl:copy>
    <xsl:apply-templates select="Positionen[not(number(Parent))]" mode="path"/>
  </xsl:copy>
 </xsl:template>

 <xsl:template match="Positionen" mode="path">
  <xsl:param name="pPath"/>

  <xsl:copy>
    <xsl:apply-templates select="node()|@*"/>
    <Path><xsl:value-of select="concat($pPath, ID)"/></Path>
  </xsl:copy>
  <xsl:apply-templates select="key('kChildren', ID)" mode="path">
   <xsl:with-param name="pPath" select="concat($pPath, ID, '/')"/>
  </xsl:apply-templates>
 </xsl:template>

 <xsl:template match="/*" mode="pass2">
  <xsl:copy>
       <xsl:apply-templates select="node()|@*">
         <xsl:sort select="ID" data-type="number"/>
       </xsl:apply-templates>
  </xsl:copy>
 </xsl:template>
</xsl:stylesheet>

when this transformation is applied on the provided XML document:

<Positions>
    <Positionen>
        <ID>1</ID>
        <Parent></Parent>
    </Positionen>
    <Positionen>
        <ID>2</ID>
        <Parent>1</Parent>
    </Positionen>
    <Positionen>
        <ID>3</ID>
        <Parent>1</Parent>
    </Positionen>
    <Positionen>
        <ID>4</ID>
        <Parent>2</Parent>
    </Positionen>
    <Positionen>
        <ID>5</ID>
        <Parent>4</Parent>
    </Positionen>
    <Positionen>
        <ID>6</ID>
        <Parent>2</Parent>
    </Positionen>
</Positions>

the wanted, correct result is produced:

<Positions>
   <Positionen>
      <ID>1</ID>
      <Parent/>
      <Path>1</Path>
   </Positionen>
   <Positionen>
      <ID>2</ID>
      <Parent>1</Parent>
      <Path>1/2</Path>
   </Positionen>
   <Positionen>
      <ID>3</ID>
      <Parent>1</Parent>
      <Path>1/3</Path>
   </Positionen>
   <Positionen>
      <ID>4</ID>
      <Parent>2</Parent>
      <Path>1/2/4</Path>
   </Positionen>
   <Positionen>
      <ID>5</ID>
      <Parent>4</Parent>
      <Path>1/2/4/5</Path>
   </Positionen>
   <Positionen>
      <ID>6</ID>
      <Parent>2</Parent>
      <Path>1/2/6</Path>
   </Positionen>
</Positions>

Do Note:

Every Path is produced by adding the current ID to the path of the parent (which is calculated only once) -- an O(1) operation. Fot the total of N paths this is O(N).

The final sorting makes the time complexity O(N*log(N)) -- still much better than quadratical.

Build a "path" with XSLT Recursion

2 Answers