Recipe9.3.Determining Set Equality by Value


Recipe 9.3. Determining Set Equality by Value

Problem

You need to determine if the nodes in one node set are equal (by value) to the nodes in another node set (ignoring order).

Solution

This problem is slightly more subtle than it appears on the surface. Consider an obvious solution that works in many cases:

<xsl:template name="vset:equal-text-values">   <xsl:param name="nodes1" select="/.."/>   <xsl:param name="nodes2" select="/.."/>   <xsl:choose>    <!--Empty node-sets have equal values -->     <xsl:when test="not($nodes1) and not($nodes2)">       <xsl:value-of select="true( )"/>       </xsl:when>     <!--Node sets of unequal sizes cannot have equal values -->     <xsl:when test="count($nodes1) != count($nodes2)"/>     <!--If an element of nodes1 is present in nodes2 then the node sets       have equal values if the node sets without the common element have equal       values -->     <xsl:when test="$nodes1[1] = $nodes2">       <xsl:call-template name="vset:equal-text-values">           <xsl:with-param name="nodes1" select="$nodes1[position( )>1]"/>           <xsl:with-param name="nodes2"                           select="$nodes2[not(. = $nodes1[1])]"/>       </xsl:call-template>     </xsl:when>     <xsl:otherwise/>   </xsl:choose> </xsl:template>

We have chosen a name for this equality test to emphasize the context in which it should be applied. That is when value equality indicate string-value equality. Clearly, this template will not give the correct result if equality is based on attributes or criteria that are more complex. However, this template has a more subtle problem. It tacitly assumes that the compared node sets are proper sets (i.e., they contain no duplicates) under string-value equality. In some circumstances, this may not be the case. Consider the following XML representing the individuals who borrowed books from a library:

<?xml version="1.0" encoding="UTF-8"?> <library>   <book>     <name>High performance Java programming.</name>     <borrowers>       <borrower>James Straub</borower>      </borrowers>   </book>   <book>     <name>Exceptional C++</name>     <borrowers>       <borrower>Steven Levitt</borower>      </borrowers>   </book>   <book>     <name>Design Patterns</name>     <borrowers>       <borrower>Steven Levitt</borower>        <borrower>James Straub</borower>        <borrower>Steven Levitt</borower>      </borrowers>   </book>   <book>     <name>The C++ Programming Language</name>     <borrowers>       <borrower>James Straub</borower>        <borrower>James Straub</borower>        <borrower>Steven Levitt</borower>      </borrowers>   </book> </library>

If an individual's name appears more than once, it simply means he borrowed the book more than once. Now, if you wrote a query to determine all books borrowed by the same people, most would agree that Design Patterns and The C++ Programming Language qualify as two such books. However, if you used vset:equal-text-values in the implementation of that query, you would not get this result because it assumes that sets do not contain duplicates. You can alter vset:equal-text-values to tolerate duplicates with the following changes:

<xsl:template name="vset:equal-text-values-ignore-dups">   <xsl:param name="nodes1" select="/.."/>   <xsl:param name="nodes2" select="/.."/>   <xsl:choose>    <!--Empty node-sets have equal values -->     <xsl:when test="not($nodes1) and not($nodes2)">       <xsl:value-of select="true( )"/>       </xsl:when>     <!--If an element of nodes1 is present in nodes2 then the node sets       have equal values if the node sets without the common element have equal       values -->     <!--delete this line            <xsl:when test="count($nodes1) != count($nodes2)"/> -->     <xsl:when test="$nodes1[1] = $nodes2">       <xsl:call-template name="vset:equal-text-values">           <xsl:with-param name="nodes1"                           select="$nodes1[not(. = $nodes1[1])]"/>           <xsl:with-param name="nodes2"                 select="$nodes2[not(. = $nodes1[1])]"/>      </xsl:call-template>     </xsl:when>     <xsl:otherwise/>   </xsl:choose> </xsl:template>

Notice that we have commented out the test for unequal sizes because that test is not valid in the presence of duplicates. For example, one set might have three occurrences of an element with string value foo, while the other has a single element foo. These sets should be equal when duplicates are ignored. You also must do more than remove just the first element on the recursive step; you should remove all elements with the same value as the first element, just as you do for the second set. This will ensure that duplicates are fully accounted for on each recursive pass. These changes make all equality tests based on text value come out correct, but at the cost of doing additional work on sets that are obviously unequal.

These equality tests are not as general as the value-set operations produced in Recipe 9.2 because they presume that the only notion of equality you care about is text-value equality. You can generalize them by reusing the same technique you used for testing membership based on a test of element equality that can be overridden by an importing stylesheet:

<xsl:template name="vset:equal">   <xsl:param name="nodes1" select="/.."/>   <xsl:param name="nodes2" select="/.."/>   <xsl:if test="count($nodes1) = count($nodes2)">     <xsl:call-template name="vset:equal-impl">       <xsl:with-param name="nodes1" select="$nodes1"/>       <xsl:with-param name="nodes2" select="$nodes2"/>     </xsl:call-template>   </xsl:if> </xsl:template>     <!-- Once we know the sets have the same number of elements --> <!-- we only need to test that every member of the first set is --> <!-- a member of the second --> <xsl:template name="vset:equal-impl">   <xsl:param name="nodes1" select="/.."/>   <xsl:param name="nodes2" select="/.."/>   <xsl:choose>     <xsl:when test="not($nodes1)">       <xsl:value-of select="true( )"/>     </xsl:when>     <xsl:otherwise>       <xsl:variable name="test">         <xsl:apply-templates select="$nodes2" mode="vset:member-of">           <xsl:with-param name="elem" select="$nodes1[1]"/>         </xsl:apply-templates>       </xsl:variable>       <xsl:if test="string($test)">         <xsl:call-template name="vset:equal-impl">           <xsl:with-param name="nodes1" select="$nodes1[position( ) > 1]"/>           <xsl:with-param name="nodes2" select="$nodes2"/>         </xsl:call-template>       </xsl:if>     </xsl:otherwise>   </xsl:choose> </xsl:template>

If you want generalized equality that works in the presence of duplicates, then you must apply a more brute-force approach that makes two passes over the sets:

<xsl:template name="vset:equal-ignore-dups">   <xsl:param name="nodes1" select="/.."/>   <xsl:param name="nodes2" select="/.."/>      <xsl:variable name="mismatch1">     <xsl:for-each select="$nodes1">       <xsl:variable name="test-elem">         <xsl:apply-templates select="$nodes2" mode="vset:member-of">           <xsl:with-param name="elem" select="."/>         </xsl:apply-templates>       </xsl:variable>       <xsl:if test="not(string($test-elem))">         <xsl:value-of select=" 'false' "/>       </xsl:if>     </xsl:for-each>   </xsl:variable>   <xsl:if test="not($mismatch1)">     <xsl:variable name="mismatch2">       <xsl:for-each select="$nodes2">         <xsl:variable name="test-elem">           <xsl:apply-templates select="$nodes1" mode="vset:member-of">             <xsl:with-param name="elem" select="."/>           </xsl:apply-templates>         </xsl:variable>         <xsl:if test="not(string($test-elem))">           <xsl:value-of select=" 'false' "/>         </xsl:if>       </xsl:for-each>     </xsl:variable>     <xsl:if test="not($mismatch2)">       <xsl:value-of select="true( )"/>     </xsl:if>   </xsl:if> </xsl:template>

This template works by iterating over the first set and looking for elements that are not a member of the second. If no such element is found, the variable $mismatch1 will be null. In that case, it must repeat the test in the other direction by iterating over the second set.

Discussion

The need to test set equality comes up often in queries. Consider the following tasks:

  • Find all books having the same authors.

  • Find all suppliers who stock the same set of parts.

  • Find all families with same-age children.

Whenever you encounter a one-to-many relationship and you are interested in elements that have the same set of associated elements, the need to test set equality will arise.




XSLT Cookbook
XSLT Cookbook: Solutions and Examples for XML and XSLT Developers, 2nd Edition
ISBN: 0596009747
EAN: 2147483647
Year: 2003
Pages: 208
Authors: Sal Mangano

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net