Re: [xsl] building hierarchy from path string

[Jeni Tennison <jeni at jenitennison dot com>]

Hi John-Mason,

> I use the depth & path attributes to tell me how the hierarchy is to
> be built. The path attribute is a sort order and the depth attribute
> (actually just durived from the path) tells me how deep in the
> hierarchy the particular node is. The approach I have been working
> with uses for-next & recursion, and while it will build the
> hierarchy properly 'til snake, I am having trouble figuring out how
> to make the recusion unwind properly and pick up the shallower
> elements. Should I be using the Muenchian technique? How would I
> implement it here?

It seems to me that you can work out a parent/child relationship by
looking at the paths. The start of the parent path must be the same as
the start of the child path. In fact, the first N characters of the
paths must match, where N is twice
the-depth-of-the-node-you're-on-plus-one.

So if you take:

  <node depth="1" OID="2" name="Reptile" path="102000" />

then the children of the Reptile element must all have paths starting
with '1020'. You can get this string with:

  substring(@path, 1, (@depth + 1) * 2)

Or, if you are on a node and want to figure out what it's parent is,
you can look at the first N characters of the path where N is twice
the depth of the node (for Reptile that's '10'):

  substring(@path, 1, @depth * 2)

OK, so now you can index each of the nodes by that string in a key, so
that you can quickly get the children of the node that you're on:

<xsl:key name="children"
         match="node"
         use="substring(@path, 1, @depth * 2)" />

The first step is to apply templates to the node(s) at the top of the
hierarchy, which you can do using the key, finding those whose 'first
part of the path' is an empty string (i.e. the Animals node, whose
depth is 0 and therefore gives you an empty value for the key):

<xsl:template match="tree">
  <tree>
    <xsl:apply-templates select="key('children', '')" />
  </tree>
</xsl:template>

Now for a node, you want to create a node element with a name
attribute equal to the name attribute on the node. For its content,
you need to apply templates to the children of that node, which means
working out its 'ID' and passing that to the key() function. Oh, and
you want to sort them by their @path attribute so that they appear in
order (although if you want them to be ordered as per the source
document then you don't have to worry about that):

<xsl:template match="node">
  <node name="{@name}">
    <xsl:apply-templates
        select="key('children', substring(@path, 1, (@depth + 1) * 2))">
      <xsl:sort select="@path" />
    </xsl:apply-templates>
  </node>
</xsl:template>

I hope that helps,

Jeni

---
Jeni Tennison
http://www.jenitennison.com/


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list