4

I need to be able to create nested lists from a flat tree. For example, the input might be something like this:

<root>
    <h1>text</h1>
    <list level="1">num1</list>
    <list level="1">num2</list>
    <list level="2">sub-num1</list>
    <list level="2">sub-num2</list>
    <list level="3">sub-sub-num1</list>
    <list level="1">num3</list>
    <p>text</p>
    <list>num1</list>
    <list>num2</list>
    <h2>text</h2>
</root>

and the output should be nested as follows:

<root>
<h1>text</h1>
    <ol>
        <li>num1</li>
        <li>num2
             <ol>
                <li>sub-num1</li>
                <li>sub-num2
                    <ol>
                        <li>sub-sub-num1</li>
                    </ol>
                </li>
            </ol>
        </li>
        <li>num3</li>
    </ol>
    <p>text</p>
    <ol>
        <li>num1</li>
        <li>num2</li>
    </ol>
    <h2>text</h2>
</root>

I've tried a few approaches but just can't seem to get it. Any help is greatly appreciated. Note: I need to do this using XSLT 1.0.

Jacqueline
  • 193
  • 1
  • 15
  • possible duplicate of [Creating a nested tree structure from a path in XSLT](http://stackoverflow.com/questions/872067/creating-a-nested-tree-structure-from-a-path-in-xslt) – Phrogz Jan 10 '11 at 20:56
  • @Phrog: Not really. The tree there is defined by the structure a value. This uses node order and a depth attribute. – Ishmael Jan 10 '11 at 22:06
  • 1
    Excellent question, +1. See my answer, which is simpler than that of @Flack (no calling of templates and no passing of parameters) and may be shorter than the answer of @Flack, (mine 66 lines, his 53, but his is much wider and requires horizontal scrolling). – Dimitre Novatchev Jan 11 '11 at 04:45

4 Answers4

6

It almost drove me mad, but I finished it. Took me almost 2 hours.

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" indent="yes"/>
<xsl:strip-space elements="*"/>

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

<xsl:template match="list[not(preceding-sibling::*[1][self::list])]">
    <ol>
        <xsl:variable name="selfId" select="generate-id()"/>
        <xsl:call-template name="recurseItems"/>
        <xsl:apply-templates select="
            following-sibling::list
            [@level = 1 or not(@level)]
            [preceding-sibling::*[1][self::list]]
            [$selfId = generate-id(
                preceding-sibling::list[not(preceding-sibling::*[1][self::list])][1]
                )
            ]
            [not(position() = 1)]
            " mode="recurse"/>
    </ol>
</xsl:template>

<xsl:template name="recurseItems">
    <xsl:param name="nodes" select="."/>
    <xsl:variable name="nextStep" select="$nodes/following-sibling::*[1][self::list]"/>
    <xsl:choose>
        <xsl:when test="$nodes/@level and ($nodes/@level &lt; $nextStep/@level)">
            <li>
                <xsl:value-of select="$nodes"/>
                <ol>
                    <xsl:call-template name="recurseItems">
                        <xsl:with-param name="nodes" select="$nextStep"/>
                    </xsl:call-template>
                </ol>
            </li>
        </xsl:when>
        <xsl:when test="$nodes/@level and ($nodes/@level > $nextStep/@level)">
            <xsl:apply-templates select="$nodes" mode="create"/>
        </xsl:when>
        <xsl:when test="$nextStep">
            <xsl:apply-templates select="$nodes" mode="create"/>
            <xsl:call-template name="recurseItems">
                <xsl:with-param name="nodes" select="$nextStep"/>
            </xsl:call-template>
        </xsl:when>
        <xsl:when test="not($nextStep)">
            <xsl:apply-templates select="$nodes" mode="create"/>
        </xsl:when>
    </xsl:choose>
</xsl:template>

<xsl:template match="list" mode="recurse">
    <xsl:call-template name="recurseItems"/>
</xsl:template>

<xsl:template match="list" mode="create">
    <li>
        <xsl:value-of select="."/>
    </li>
</xsl:template>

<xsl:template match="list"/>

</xsl:stylesheet>

Applied to a slightly more complicated document:

<root>
    <h1>text</h1>
    <list level="1">1.1</list>
    <list level="1">1.2</list>
    <list level="2">1.2.1</list>
    <list level="2">1.2.2</list>
    <list level="3">1.2.2.1</list>
    <list level="1">1.3</list>
    <p>text</p>
    <list>2.1</list>
    <list>2.2</list>
    <h2>text</h2>
    <h1>text</h1>
    <list level="1">3.1</list>
    <list level="1">3.2</list>
    <list level="2">3.2.1</list>
    <list level="2">3.2.2</list>
    <list level="3">3.2.2.1</list>
    <list level="1">3.3</list>
    <list level="2">3.3.1</list>
    <list level="2">3.3.2</list>
    <p>text</p>
</root>

It produces this result:

<?xml version="1.0" encoding="UTF-8"?>
<root>
    <h1>text</h1>
    <ol>
        <li>1.1</li>
        <li>1.2
            <ol>
                <li>1.2.1</li>
                <li>1.2.2
                    <ol>
                        <li>1.2.2.1</li>
                    </ol>
                </li>
            </ol>
        </li>
        <li>1.3</li>
    </ol>
    <p>text</p>
    <ol>
        <li>2.1</li>
        <li>2.2</li>
    </ol>
    <h2>text</h2>
    <h1>text</h1>
    <ol>
        <li>3.1</li>
        <li>3.2
            <ol>
                <li>3.2.1</li>
                <li>3.2.2
                    <ol>
                        <li>3.2.2.1</li>
                    </ol>
                </li>
            </ol>
        </li>
        <li>3.3
            <ol>
                <li>3.3.1</li>
                <li>3.3.2</li>
            </ol>
        </li>
    </ol>
    <p>text</p>
</root>

Applied to your sample it also produces the correct result:

<?xml version="1.0" encoding="UTF-8"?>
<root>
    <h1>text</h1>
    <ol>
        <li>num1</li>
        <li>num2
            <ol>
                <li>sub-num1</li>
                <li>sub-num2
                    <ol>
                        <li>sub-sub-num1</li>
                    </ol>
                </li>
            </ol>
        </li>
        <li>num3</li>
    </ol>
    <p>text</p>
    <ol>
        <li>num1</li>
        <li>num2</li>
    </ol>
    <h2>text</h2>
</root>
Flack
  • 5,862
  • 2
  • 23
  • 27
4

This XSLT 1.0 stylesheet:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:key name="kListByParent"
             match="list"
             use="concat(generate-id(preceding-sibling::*
                                        [not(self::list)][1]),
                         '+',
                         generate-id(preceding-sibling::list
                                        [current()/@level > @level][1]))"/>
    <xsl:template match="node()|@*">
        <xsl:copy>
            <xsl:apply-templates select="node()|@*"/>
        </xsl:copy>
    </xsl:template>
    <xsl:template match="list[preceding-sibling::*[1]/self::list]"/>
    <xsl:template match="list">
        <xsl:variable name="vListMark"
                      select="generate-id(preceding-sibling::*[1])"/>
        <ol>
            <xsl:apply-templates select="key('kListByParent',
                                             concat($vListMark,'+'))"
                                 mode="makeLi">
                <xsl:with-param name="pListMark" select="$vListMark"/>
            </xsl:apply-templates>
        </ol>
    </xsl:template>
    <xsl:template match="list" mode="makeLi">
        <xsl:param name="pListMark"/>
        <xsl:variable name="vChilds"
                      select="key('kListByParent',
                                  concat($pListMark,'+',generate-id()))"/>
        <li>
            <xsl:value-of select="."/>
            <xsl:if test="$vChilds">
                <ol>
                    <xsl:apply-templates select="$vChilds"
                                         mode="makeLi">
                        <xsl:with-param name="pListMark"
                                        select="$pListMark"/>
                    </xsl:apply-templates>
                </ol>
            </xsl:if>
        </li>
    </xsl:template>
</xsl:stylesheet>

Output: 

<root>
    <h1>text</h1>
    <ol>
        <li>num1</li>
        <li>num2
            <ol>
                <li>sub-num1</li>
                <li>sub-num2
                    <ol>
                        <li>sub-sub-num1</li>
                    </ol>
                </li>
            </ol>
        </li>
        <li>num3</li>
    </ol>
    <p>text</p>
    <ol>
        <li>num1</li>
        <li>num2</li>
    </ol>
    <h2>text</h2>
</root>

Note: The use of current() XSLT function in xsl:key/@use

  • +1 for a good answer -- it is very difficult to say that one of the answers is better than any other. – Dimitre Novatchev Jan 11 '11 at 13:37
  • @Dimitre: You are right! I think we already answer this but I can't find the question... –  Jan 11 '11 at 13:40
  • +1. It was another WebStorm bug. I already hate this IDE. Removing previous comment. – Flack Jan 11 '11 at 14:59
  • @Flack: Why don't you try [XSelerator](http://sourceforge.net/projects/xselerator/)? –  Jan 11 '11 at 18:38
  • @Alejandro, UI's bad and some poblems with Win 7. Like exception on start, no undo after file save, buggy autocomplete. – Flack Jan 11 '11 at 19:00
1

This transformation:

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

 <xsl:key name="kListGroup" match="list"
  use="generate-id(
          preceding-sibling::node()[not(self::list)][1]
                   )"/>

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

 <xsl:template match=
  "list[preceding-sibling::node()[1][not(self::list)]]">

  <ol>
    <xsl:apply-templates mode="listgroup" select=
     "key('kListGroup',
          generate-id(preceding-sibling::node()[1])
          )
          [not(@level) or @level = 1]
     "/>
  </ol>
  <xsl:apply-templates select=
   "following-sibling::node()[not(self::list)][1]"/>
 </xsl:template>

 <xsl:template match="list" mode="listgroup">
  <li>
    <xsl:value-of select="."/>

    <xsl:variable name="vNext" select=
     "following-sibling::list
            [not(@level > current()/@level)][1]
     |
      following-sibling::node()[not(self::list)][1]
     "/>

     <xsl:variable name="vNextLevel" select=
     "following-sibling::list
     [@level = current()/@level +1]
      [generate-id(following-sibling::list
            [not(@level > current()/@level)][1]
           |
             following-sibling::node()[not(self::list)][1]
                  )
      =
       generate-id($vNext)
      ]
     "/>

     <xsl:if test="$vNextLevel">
     <ol>
      <xsl:apply-templates mode="listgroup"
        select="$vNextLevel"/>
     </ol>
     </xsl:if>
  </li>
 </xsl:template>
</xsl:stylesheet>

when applied on this XML document (intentionally complicated to show that the solution works in many edge cases):

<root>
    <h1>text</h1>
    <list level="1">1.1</list>
    <list level="1">1.2</list>
    <list level="2">1.2.1</list>
    <list level="2">1.2.2</list>
    <list level="3">1.2.2.1</list>
    <list level="1">1.3</list>
    <p>text</p>
    <list>2.1</list>
    <list>2.2</list>
    <h2>text</h2>
    <h1>text</h1>
    <list level="1">3.1</list>
    <list level="1">3.2</list>
    <list level="2">3.2.1</list>
    <list level="2">3.2.2</list>
    <list level="3">3.2.2.1</list>
    <list level="1">3.3</list>
    <list level="2">3.3.1</list>
    <list level="2">3.3.2</list>
    <p>text</p>
</root>

produces the wanted, correct result:

<root>
   <h1>text</h1>
   <ol>
      <li>1.1</li>
      <li>1.2<ol>
            <li>1.2.1</li>
            <li>1.2.2<ol>
                  <li>1.2.2.1</li>
               </ol>
            </li>
         </ol>
      </li>
      <li>1.3</li>
   </ol>
   <p>text</p>
   <ol>
      <li>2.1</li>
      <li>2.2</li>
   </ol>
   <h2>text</h2>
   <h1>text</h1>
   <ol>
      <li>3.1</li>
      <li>3.2<ol>
            <li>3.2.1</li>
            <li>3.2.2<ol>
                  <li>3.2.2.1</li>
               </ol>
            </li>
         </ol>
      </li>
      <li>3.3<ol>
            <li>3.3.1</li>
            <li>3.3.2</li>
         </ol>
      </li>
   </ol>
   <p>text</p>
</root>

or as displayed by the browser:

text

  1. 1.1
  2. 1.2
    1. 1.2.1
    2. 1.2.2
      1. 1.2.2.1
  3. 1.3

text

  1. 2.1
  2. 2.2

text

text

  1. 3.1
  2. 3.2
    1. 3.2.1
    2. 3.2.2
      1. 3.2.2.1
  3. 3.3
    1. 3.3.1
    2. 3.3.2

text

Dimitre Novatchev
  • 240,661
  • 26
  • 293
  • 431
  • 1
    @Dimitre, you at least own me an upvote for the xml sample :)) – Flack Jan 11 '11 at 10:33
  • @Flack: I don't have any problem upvoting your answer, but as I commented on @Alejandro's answer, it is difficult for me to clearly decide which of our three answers is the best. People shouldn't think one answer is better than the others, when it isn't. Therefore, I will upvote you if as result all three answers will have the same number of upvotes. Of course, this is the ideal case. Let's wait a little while, then we'll see. – Dimitre Novatchev Jan 11 '11 at 13:45
  • I've just tried both Flack's and Dimitre's answers and both work really well. And best of all, I learned something new (I'd never used the current() function before). Thanks all! – Jacqueline Jan 11 '11 at 14:42
  • I tried to do some numbers, but relative in XSlerator is too big. May be someone would profile all solutions? – Flack Jan 11 '11 at 15:12
  • @Jacqueline: You are always welcome. And thanks for the excellent question -- it was more fun than fiendish sudoku :) – Dimitre Novatchev Jan 11 '11 at 15:28
0

You'll find a worked solution to a very similar problem in this paper

http://www.saxonica.com/papers/ideadb-1.1/mhk-paper.xml

Note: it's XSLT 2.0.

Michael Kay
  • 156,231
  • 11
  • 92
  • 164