Thursday, August 14, 2008

Transforming tree structure from one format into another

An interesting question was asked on xsl-list,

The input XML file is something as:

<Objs>
<obj name="a" child="b"/>
<obj name="b" child="c"/>
<obj name="b" child="d"/>
<obj name="c" child="e"/>
</Objs>

Let's say that XML file has only one root node.

The output XML file would be:

<Obj name="a">
<Obj name="b">
<Obj name="c">
<Obj name="e"/>
</Obj>
<Obj name="d"/>
</Obj>
</Obj>


A tree structure is defined in input XML, by the 'name' and 'child' attributes. The output represents a true logical tree. We should be able to cater to unlimited number of tree nodes.

We need to write a XSLT stylesheet for this.

At first thought, I imagined that this could be a tough problem. But a little bit of patience helped me to write the stylesheet for this. The solution is presented below.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
version="1.0">

<xsl:output method="xml" indent="yes" />

<xsl:template match="Objs">
<xsl:variable name="start" select="obj[not(@name = ../obj/@child)]" />
<xsl:variable name="startName" select="$start[1]/@name" />
<Obj name="{$startName}">
<xsl:for-each select="obj[(@name = $startName) and not(../obj/@name = @child)]">
<Obj name="{@child}" />
</xsl:for-each>
<xsl:call-template name="makeTree">
<xsl:with-param name="list" select="obj[@name = $start/@child]" />
</xsl:call-template>
</Obj>
</xsl:template>

<xsl:template name="makeTree">
<xsl:param name="list" />

<Obj name="{$list[1]/@name}">
<xsl:for-each select="$list">
<xsl:variable name="child" select="@child" />
<xsl:choose>
<xsl:when test="not(../obj[@name = $child])">
<Obj name="{$child}" />
</xsl:when>
<xsl:otherwise>
<xsl:call-template name="makeTree">
<xsl:with-param name="list" select="../obj[@name = $child]" />
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:for-each>
</Obj>
</xsl:template>

</xsl:stylesheet>

At first thought, I felt that XSLT 2.0 constructs will be required to solve this problem. But the problem can be solved completely with a XSLT 1.0 stylesheet.

My belief that XSLT is a wonderful language for processing XML data, became stronger after solving this problem.

No comments: