[xsl] Re: XSL/XPath 2.0 - most efficient way to find route to target element

[Robert Koberg <rob@xxxxxxxxxx>]

Here is a working version. But, David's solution is nicero;? (and much
shorter!) and will work if the preceding/following sibling check is
used.

thanks,
-Rob

XSL (followed by XML):
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
version="2.0">

  <xsl:key name="config" match="*" use="@id"/>

  <xsl:template match="/">
    
    <test>
      
      <xsl:apply-templates select="key('config', 'a3')" mode="path">
        <xsl:with-param name="target-id" select="'b3'"/>
      </xsl:apply-templates>
      
      <xsl:apply-templates select="key('config', 'c3')" mode="path">
        <xsl:with-param name="target-id" select="'b3'"/>
      </xsl:apply-templates>
      
      <xsl:apply-templates select="key('config', 'b4')" mode="path">
        <xsl:with-param name="target-id" select="'b3'"/>
      </xsl:apply-templates>
      
    </test>
  </xsl:template>
  
  <xsl:template match="*" mode="path">
    <xsl:param name="target-id"/>
    
    <xsl:variable name="path-to-target">
      <xsl:choose>
        <xsl:when test="preceding-sibling::*/@id=$target-id or
following-sibling::*/@id=$target-id">
          <xsl:value-of select="preceding-sibling::*[@id=
$target-id]/@name | following-sibling::*[@id=$target-id]/@name"/>
        </xsl:when>
        <xsl:otherwise>
          
          <xsl:variable name="target-anc-and-self" as="node()*">
            <xsl:apply-templates select="key('config', $target-id)"
mode="ancestry"/>
          </xsl:variable>
          
          <xsl:variable name="anc-and-self" as="node()*">
            <xsl:apply-templates select="." mode="ancestry"/>
          </xsl:variable>
          
          <xsl:variable name="common-ancestor" select="($anc-and-self
intersect $target-anc-and-self)[last()]"/>
          
          <xsl:apply-templates select="." mode="path-up">
            <xsl:with-param name="common-ancestor-id"
select="$common-ancestor/@id"/>
          </xsl:apply-templates>
          <xsl:apply-templates select="key('config', $target-id)"
mode="path-down">
            <xsl:with-param name="common-ancestor-id"
select="$common-ancestor/@id"/>
          </xsl:apply-templates>
          
        </xsl:otherwise>
      </xsl:choose>
    </xsl:variable>
    
    <path href="{$path-to-target}"/>
    
  </xsl:template>
  
  <xsl:template match="*" mode="ancestry">
    <xsl:sequence select="ancestor-or-self::*"/>
  </xsl:template>
  
  <xsl:template match="*" mode="path-up">
    <xsl:param name="common-ancestor-id"/>
    <xsl:choose>
      <xsl:when test="@id = $common-ancestor-id"/>
      <xsl:otherwise>
        <xsl:text>../</xsl:text>
        <xsl:apply-templates select="parent::*" mode="path-up">
          <xsl:with-param name="common-ancestor-id"
select="$common-ancestor-id"/>
        </xsl:apply-templates>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
  
  <xsl:template match="*" mode="path-down">
    <xsl:param name="common-ancestor-id"/>
    <xsl:choose>
      <xsl:when test="parent::*/@id = $common-ancestor-id">
        <xsl:value-of select="@name"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:apply-templates select="parent::*" mode="path-down">
          <xsl:with-param name="common-ancestor-id"
select="$common-ancestor-id"/>
        </xsl:apply-templates>
        <xsl:text>/</xsl:text>
        <xsl:value-of select="@name"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
  
</xsl:stylesheet>

The XML:
o;?<node name="foo" id="x">
  <node name="bar" id="b1">
    <node>
      <node/>
      <node/>
    </node>
    <node name="baz" id="b2">
      <node name="bat" id="b3"/>o;?
      <node name="bat" id="b4"/>
    </node>
    <node>o;?
    <node name="saz" id="c2">
      <node name="sat" id="c3"/>
    </node>
    </node>
  </node>
  <node name="gar" id="a1">
    <node name="gaz" id="a2">
      <node name="gat" id="a3"/>
      <node/>
    </node>
    <node>
      <node/>
    </node>
    <node>
      <node/>
    </node>
  </node>
</node>




On Sat, 2008-04-26 at 11:27 -0400, Robert Koberg wrote:
> Hi,
> 
> In the xml structure below, imagine:
> - all nodes have name (not necessarily unique) and id (o;?unique)
> attributes
> - you are in the context of node[@id='a3'] and you want to build a path
> from the name attribute to node[@id='b3'] that would result in the
> shortest path, which would be:
> 
> ../../../bar/baz/bat
> 
> - and in another case you are in the context of node[@id='c3'] and you
> want the shortest path to node[o;?@id='b3'], which would be:
> 
> ../../baz/bat
> 
> - and in another case you are in the context of node[@id='b4'] and you
> want the shortest path to o;?node[o;?@id='b3'], which would be:
> 
> bat
> 
> What is the most efficient to find those paths? (this is to create page
> relative links, rather than root relative, for html pages)
> 
> In the past I have just recursed up the ancestry of the calling node to
> the root element and for each of those added a '../'. Then used a key to
> find the target node and recurse up from that target to root prepending
> the name attribute. Now, using XSL and XPath version 2, I am hoping
> there is a clean, efficient way to find the shortest possible path
> rather than going all the way to the root when it is not necessary.