Re: XSLT 2.0 function - fastest node comparison

On Thu, 10 Mar 2005 15:09:24 -0000, Michael Kay <mike@xxxxxxxxxxxx> wrote:

> If there are many ranges and you need it to go at better than linear speed,
> you could code a binary-chop. I think Dimitre has done this in the past, I
> don't know if it's available in packaged form.

Here are two XSLT 2.0 solutions: a DVC (Divide and Conquer) and BS
(Binary Search):

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:f="http://fxsl.sf.net/"
 xmlns:t="http://fxsl.sf.net/test"
 exclude-result-prefixes="f xs t"
 >
  <xsl:output method="text"/>
  
  <xsl:variable name="vRanges" as="element()+">
    <range from="988" to="989"/>
    <range from="1008" to="1009"/>
    <range from="1014" to="1014"/>
    <range from="1025" to="1036"/>
    <range from="1038" to="1103"/>
    <range from="1105" to="1116"/>
    <range from="1118" to="1119"/>
    <range from="4150" to="4150"/>
    <range from="8194" to="8197"/>
  </xsl:variable>
  
  <xsl:template match="/">
    <xsl:value-of select="t:inRangeDVC($vRanges, 8195)"/>, <xsl:text/>
    <xsl:value-of select="t:inRangeBS($vRanges, 8195, 1, count($vRanges))"/>
  </xsl:template>
  
  <xsl:function name="t:inRangeDVC" as="xs:boolean">
    <xsl:param name="pRanges" as="element()*"/>
    <xsl:param name="pVal"/>
  
    <xsl:sequence select=
    "if(empty($pRanges))
       then false()
       else for $cnt in count($pRanges)
               return if($cnt = 1)
                        then $pVal ge xs:integer($pRanges[1]/@from)
                            and 
                              $pVal le xs:integer($pRanges[1]/@to)
                        else for $vHalf in $cnt idiv 2
                          return
                            if(t:inRangeDVC($pRanges[position() le
$vHalf], $pVal))
                               then true()
                               else 
                                    t:inRangeDVC($pRanges[position()
gt $vHalf], $pVal)
                    "
    />
  </xsl:function>
  
  <xsl:function name="t:inRangeBS" as="xs:boolean">
    <xsl:param name="pRanges" as="element()*"/>
    <xsl:param name="pVal"/>
    <xsl:param name="pLow" as="xs:integer"/>
    <xsl:param name="pUp" as="xs:integer"/>

    <xsl:sequence select=
    "if($pLow gt $pUp)
       then false()
       else for $mid in ($pLow + $pUp) idiv 2,
                $v in $pRanges[$mid]
               return
                  if($pVal ge xs:integer($v/@from) and $pVal le
xs:integer($v/@to))
                     then true()
                     else if($pVal lt xs:integer($v/@from))
                               then t:inRangeBS($pRanges, $pVal,
$pLow, $mid - 1)
                              else t:inRangeBS($pRanges, $pVal, $mid+1, $pUp)
                        
    "/>
  </xsl:function>
</xsl:stylesheet>


Cheers,
Dimitre Novatchev