Performing Set Operations When Querying XML

(Page 1 of 4 )

In this second part to a five-part series on using XSLT as an XML query language, we pick up where we left off last week, with how to perform set operations on node sets using value semantics. It is excerpted from chapter nine of the XSLT Cookbook, Second Edition, written by Sal Mangano (O'Reilly; ISBN: 0596009747). Copyright © 2007 O'Reilly Media, Inc. All rights reserved. Used with permission from the publisher. Available from booksellers or direct from O'Reilly Media.

Performing Set Operations on Node Sets Using Value Semantics continued

The following stylesheet provides a reusable implementation of union, intersection, and set difference based on value semantics. The idea is that a stylesheet importing this one will override the template whosemode="vset:element-equality". This allows the importing stylesheet to define whatever equality semantics make sense for the given input:

  <xsl:stylesheet version="1.0"  
xmlns:xsl="http://www.w3.org/1999/XSL/ Transform"
   xmlns:vset="http:/www.ora.com/ XSLTCookbook/namespaces/vset">

  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>

  <!-- The default implementation of element equality. Override in the importing
  stylesheet as necessary. -->

  <xsl:template match="node() | @*" mode="vset:element-equality">
    <xsl:param name="other"/>
    <xsl:if test=". = $other">
      <xsl:value-of select="true()"/>
    </xsl:if>
  </xsl:template>

  <!-- The default set membership test uses element equality. You will rarely need to
  override this in the importing stylesheet. -->
  <xsl:template match="node() | @*" mode="vset:member-of">
    <xsl:param name="elem"/>
    <xsl:variable name="member-of">
      <xsl:for-each select=".">
        <xsl:apply-templates select="." mode="vset:element-equality">
          <xsl:with-param name="other" select="$elem"/>
        </xsl:apply-templates>
      </xsl:for-each>
    </xsl:variable>
    <xsl:value-of select="string($member-of)"/>
  </xsl:template>

  <!-- Compute the union of two sets using "by value" equality. -->
  <xsl:template name="vset:union">
    <xsl:param name="nodes1" select="/.." />
    <xsl:param name="nodes2" select="/.." />
    <!-- for internal use -->
    <xsl:param name="nodes" select="$nodes1 | $nodes2" />
    <xsl:param name="union" select="/.." />
    <xsl:choose>
      <xsl:when test="$nodes">
        <xsl:variable name="test">
          <xsl:apply-templates select="$union" mode="vset:member-of">
            <xsl:with-param name="elem" select="$nodes[1]" />
          </xsl:apply-templates>
        </xsl:variable>
        <xsl:call-template name="vset:union">
          <xsl:with-param name="nodes" select="$nodes[position() > 1]" />
          <xsl:with-param name="union"
                          select="$union | $nodes[1][not(string($test))]" />
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:apply-templates select="$union" mode="vset:union" />
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <!-- Return a copy of union by default. Override in importing stylesheet to receive
  reults as a "callback"-->
  <xsl:template match="/ | node() | @*" mode="vset:union">
    <xsl:copy-of select="."/>
  </xsl:template>

  <!-- Compute the intersection of two sets using "by value" equality. -->
  <xsl:template name="vset:intersection">
    <xsl:param name="nodes1" select="/.."/>
    <xsl:param name="nodes2" select="/.."/>
    <!-- For internal use -->
    <xsl:param name="intersect" select="/.."/>

    <xsl:choose>
      <xsl:when test="not($nodes1)">
        <xsl:apply-templates select="$intersect" mode="vset:intersection"/>
      </xsl:when>
      <xsl:when test="not($nodes2)">
        <xsl:apply-templates select="$intersect" mode="vset:intersection"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="test1">
          <xsl:apply-templates select="$nodes2" mode="vset:member-of">
            <xsl:with-param name="elem" select="$nodes1[1]"/>
          </xsl:apply-templates>
        </xsl:variable>
        <xsl:variable name="test2">
          <xsl:apply-templates select="$intersect" mode="vset:member-of">
            <xsl:with-param name="elem" select="$nodes1[1]"/>
          </xsl:apply-templates> 
        </xsl:variable>
        <xsl:choose>
          <xsl:when test="string($test1) and not(string($test2))">
            <xsl:call-template name="vset:intersection">
              <xsl:with-param name="nodes1"
                      select="$nodes1[position() > 1]"/>
              <xsl:with-param name="nodes2" select="$nodes2"/>
              <xsl:with-param name="intersect"
                      select="$intersect | $nodes1[1]"/>
            </xsl:call-template>
          </xsl:when>
          <xsl:otherwise>
            <xsl:call-template name="vset:intersection">
              <xsl:with-param name="nodes1"
                      select="$nodes1[position() > 1]"/>
              <xsl:with-param name="nodes2" select="$nodes2"/>
              <xsl:with-param name="intersect" select="$intersect"/>
            </xsl:call-template>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <!-- Return a copy of intersection by default. Override in importing stylesheet to
  receive results as a "callback"-->
  <xsl:template match="/ | node() | @*" mode="vset:intersection">
    <xsl:copy-of select="."/>
  </xsl:template>

  <!-- Compute the differnce between two sets (node1 - nodes2) using "by value"
  equality. -->
  <xsl:template name="vset:difference">
    <xsl:param name="nodes1" select="/.."/>
    <xsl:param name="nodes2" select="/.."/>
    <!-- For internal use -->
    <xsl:param name="difference" select="/.."/>

    <xsl:choose>
      <xsl:when test="not($nodes1)">
        <xsl:apply-templates select="$difference" mode="vset:difference"/>
      </xsl:when>
      <xsl:when test="not($nodes2)">
        <xsl:apply-templates select="$nodes1" mode="vset:difference"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="test1">
          <xsl:apply-templates select="$nodes2" mode="vset:member-of">
            <xsl:with-param name="elem" select="$nodes1[1]"/>
          </xsl:apply-templates>
        </xsl:variable>
        <xsl:variable name="test2">
          <xsl:apply-templates select="$difference" mode="vset:member-of">
            <xsl:with-param name="elem" select="$nodes1[1]"/>
          </xsl:apply-templates>
        </xsl:variable>
        <xsl:choose>
          <xsl:when test="string($test1) or string($test2)">
            <xsl:call-template name="vset:difference">
              <xsl:with-param name="nodes1"
                      select="$nodes1[position() > 1]"/>
              <xsl:with-param name="nodes2" select="$nodes2"/>
              <xsl:with-param name="difference" select="$difference"/>
            </xsl:call-template>
          </xsl:when>
          <xsl:otherwise>
            <xsl:call-template name="vset:difference">
              <xsl:with-param name="nodes1"
                      select="$nodes1[position() > 1]"/>
              <xsl:with-param name="nodes2" select="$nodes2"/>
              <xsl:with-param name="difference"
                      select="$difference | $nodes1[1]"/>
            </xsl:call-template>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <!-- Return a copy of difference by default. Override in importing stylesheet to
  receive results as a "callback"-->
  <xsl:template match="/ | node() | @*" mode="vset:difference">
    <xsl:copy-of select="."/>
  </xsl:template>

Next: Implementing the Recursive Templates >>
 

More XML Tutorials Articles
More By O'Reilly Media

blog comments powered by Disqus