Building a tree from path-like strings

Hi there,

I'm trying to make a tree-hierarchic document from a flat
list of elements which have id-like values which define
the hierarchy I need.

So here is simplified version of the source document:

<btc>
<record table="works">
  <record table="external_records">
    <field name="external_id"><value>FOO/1</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/1/1</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/1/2</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/2</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/2/1</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/2/1/1</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/2/1/2</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/2/2</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
  <record table="external_records">
    <field name="external_id"><value>FOO/3</value></field>
    <field name="ds_name"><value>ms-sources</value></field>
  </record>
</record>
</btc>

which should become this after transformation:

<ol>
  <li id="FOO/1">
    FOO/1
    <ol>
      <li id="FOO/1/1">
        FOO/1/1
      </li>
      <li id="FOO/1/2">
        FOO/1/2
      </li>
    </ol>
  </li>
  <li id="FOO/2">
    FOO/2
    <ol>
      <li id="FOO/2/1">
        FOO/2/1
        <ol>
          <li id="FOO/2/1/1">
            FOO/2/1/1
          </li>
          <li id="FOO/2/1/2">
            FOO/2/1/2
          </li>
        </ol>
      </li>
      <li id="FOO/1/2">
        FOO/2/2
      </li>
    </ol>
  </li>
  <li id="FOO/2">
    FOO/3
  </li>
</ol>

So far I have the following:

<?xml version="1.0" encoding="utf-8" ?>

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

<xsl:output method="xml" />

<xsl:template name="count-slashes">
  <!-- this template counts the number of '/' characters in a string -->
  <xsl:param name="str" />
  <xsl:param name="current-count" select="0" />
  <xsl:choose>
    <xsl:when test="contains($str, '/')">
      <xsl:call-template name="count-slashes">
        <xsl:with-param name="str"><xsl:value-of select="substring-after($str, '/')" /></xsl:with-param>
        <xsl:with-param name="current-count" select="number($current-count) + 1" />
      </xsl:call-template>
    </xsl:when>
    <xsl:otherwise>
      <xsl:value-of select="$current-count" />
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

<xsl:template match="/">
  <xsl:apply-templates select="//record[@table='works']" />
</xsl:template>

<xsl:template match="record[@table='works']">
  <ol>
    <xsl:apply-templates select="//record[@table='external_records'
                                          and field[@name='ds_name']/value='ms-sources']">
      <xsl:with-param name="at-top-level">1</xsl:with-param>
    </xsl:apply-templates>
  </ol>
</xsl:template>

<xsl:template match="record[@table='external_records' and field[@name='ds_name']/value='ms-sources']">
  <xsl:param name="at-top-level" select="0" />

  <xsl:variable name="id" select="field[@name='external_id']/value" />
  <xsl:variable name="level"><xsl:call-template name="count-slashes"><xsl:with-param name="str"><xsl:value-of 
select="$id" /></xsl:with-param></xsl:call-template></xsl:variable>

  <xsl:if test="($at-top-level='1' and number($level)=1) or ($at-top-level!='1' and number($level)&gt;1)">
    <li id="{$id}">
      <xsl:value-of select="$id" />

      <!-- apply sub-records -->
      <xsl:if test="count(//record[@table='external_records'
                                   and field[@name='ds_name']/value='ms-sources'
                                   and field[@name='external_id']/value!=$id
                                   and contains(field[@name='external_id']/value, $id)])&gt;0">
        <ol>
          <xsl:apply-templates select="//record[@table='external_records'
                                                and field[@name='ds_name']/value='ms-sources'
                                                and field[@name='external_id']/value!=$id
                                                and contains(field[@name='external_id']/value, $id)]" />
        </ol>
      </xsl:if>
    </li>
  </xsl:if>
</xsl:template>

</xsl:stylesheet>

The basic idea is that it goes through these record[@table="external_records"]
elements but then subverts the normal processing order by calling
<xsl:apply-templates> in the middle of the <record>-matching template selecting
any other record[@table="external_records"] which having id values which match
the beginning of the current id value (e.g. selecting FOO/1/1 from inside FOO/1).

Of course, XSLT will still process all the elements in document order so I've
tried to avoid it processing the, e.g., FOO/1/1 elements twice with the
condition that it may only process the element if the parameter $at-top-level
has the value "1" and the current id value is of level "1" (i.e. it has one '/'
in it) or if $at-top-level is not "1" (i.e. the template is being recusively
called) and the current id value is of a level greater than 1.

This attempt at a solution is not only protracted and incomprehensible, it
doesn't actually work either.

The elements end up being processing in document order as well as being
processed recursively. One possible solution I started on was having it find
the previous element's id and only processing the element if that previous
id is of the same or a higher level.

I got as far as attempting to select the previous record's id with this
monstrosity:

<xsl:variable name="prev-record-level-str">
  <xsl:choose>
    <xsl:when test="count(preceding-sibling::record)=0">0</xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="count-slashes">
        <xsl:with-param name="str">
          <xsl:value-of select="preceding-sibling::record[@table='external_records' 
field[@name='ds_name']/value='ms-sources'][1]/field[@name='external_id']/value" />
        </xsl:with-param>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:variable>

<xsl:variable name="prev-record-level">
  <xsl:value-of select="number($prev-record-level-str)" />
</xsl:variable>

But it doesn't seem to work.

Can anyone think of a solution to this? Preferably disregarding my
existing attempt.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Richard Lewis
ISMS, Computing
Goldsmiths, University of London
Tel: +44 (0)20 7078 5134
Skype: richardjlewis
JID: ironchicken@xxxxxxxxxxxxxxx
http://www.richard-lewis.me.uk/
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
+-------------------------------------------------------+
|Please avoid sending me Word or PowerPoint attachments.|
|http://www.gnu.org/philosophy/no-word-attachments.html |
+-------------------------------------------------------+