Terminal Merge

Chris 2012-02-24

The recursive merge might be faster if both sequences were teminated with high-value keys so empty conditions dont need to be tested. This was a typical device used in batch processing. However the performance is actually worse not better.

XQuery

declare function local:merge($source,$target) {
  let $lastkey := "zzzzzzzzzzzz"
  let $last := element last { attribute id {$lastkey}}
  return local:merge(($source,$last), ($target,$last),$lastkey)
};
declare function local:merge($source, $target,$lastkey)  {
    if ($source[1]/@id = $target[1]/@id)
    then 
        if ($source[1]/@id = $lastkey)
        then ()
        else (element match {$source[1], $target[1]},  local:merge(subsequence($source,2), subsequence($target,2)))
    else if ($source[1]/@id lt $target[1]/@id)
    then (element new {$source[1]}, local:merge(subsequence($source, 2), $target))
    else (element delete {$target[1]},local:merge($source, subsequence($target,2)))           
     };


let $list1 :=
<list>
   <item id="a">A</item>
   <item id="b">B</item>
   <item id="d">D</item>
</list>
 
let $list2 :=
<list>
   <item id="a">a</item>
   <item id="b">b</item>
   <item id="c">c</item>
   <item id="e">e</item>
</list>
  
return
  element merge {local:merge($list1/*,$list2/*)}
 

Result

<merge>
    <match>
        <item id="a">A</item>
        <item id="a">a</item>
    </match>
    <match>
        <item id="b">B</item>
        <item id="b">b</item>
    </match>
    <delete>
        <item id="c">c</item>
    </delete>
    <new>
        <item id="d">D</item>
    </new>
    <delete>
        <item id="e">e</item>
    </delete>
</merge>