xsl-list
[Top] [All Lists]

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

2008-04-27 08:25:40
Here is a working version. But, David's solution is nicer (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::*[(_at_)id=
$target-id]/@name | following-sibling::*[(_at_)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:
<node name="foo" id="x">
  <node name="bar" id="b1">
    <node>
      <node/>
      <node/>
    </node>
    <node name="baz" id="b2">
      <node name="bat" id="b3"/>
      <node name="bat" id="b4"/>
    </node>
    <node>
    <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 (unique)
attributes
- you are in the context of node[(_at_)id='a3'] and you want to build a path
from the name attribute to node[(_at_)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[(_at_)id='c3'] and you
want the shortest path to node[(_at_)id='b3'], which would be:

../../baz/bat

- and in another case you are in the context of node[(_at_)id='b4'] and you
want the shortest path to node[(_at_)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.



--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--