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>