我需要一些保留顺序的XQuery序列合并的帮助

Question

我正在研究一个函数来合并一组序列，以尽可能地保留所有序列的顺序。在所有序列上执行不同值（$序列）不会保留顺序。

我有以下MarkLogic XQuery代码：

xquery version "1.0-ml"; 

declare function local:map-sequence($map, $list as xs:string*) { 
    let $count := fn:count($list) - 1 
    return for $idx in (1 to $count) 
        return if (map:contains($map, $list[$idx])) 
        then map:put($map, $list[$idx], fn:distinct-values((map:get($map, $list[$idx]), $list[$idx + 1]))) 
        else map:put($map, $list[$idx], $list[$idx + 1]) 
}; 

declare function local:first($map) { 
let $all-children := for $key in map:keys($map) return map:get($map, $key) 

return distinct-values(map:keys($map)[not(.=$all-children)]) 
}; 

declare function local:next($map, $key as xs:string) { 
    if (map:contains($map, $key)) 
    then if (fn:count(map:get($map, $key)) eq 1) 
     then map:get($map, $key) 
     else 
      let $children := map:get($map, $key) 
      return 
       for $next in $children 
       let $others := $children[fn:not(.=$next)] 
       let $descedents := local:descendents($map, $next) 
       return if ($descedents[.=$others]) 
        then $next 
        else() 
    else() 
}; 

declare function local:descendents($map, $key as xs:string) { 
    for $child in map:get($map, $key) 
    return ($child, local:descendents($map, $child)) 
}; 

declare function local:sequence($map, $key as xs:string) { 
    let $next := local:next($map, $key) 
    return if (fn:count($next) gt 1) 
      then 
        for $choice in $next 
        return $choice 

      else if (fn:count($next) eq 1) 
       then ($next, local:sequence($map, $next)) 
       else() 
}; 

let $map := map:map() 
let $seq1 := local:map-sequence($map, ('fred', 'barney', 'pebbles')) 
let $seq2 := local:map-sequence($map, ('fred', 'wilma', 'betty', 'pebbles')) 
let $seq3 := local:map-sequence($map, ('barney', 'wilma', 'betty')) 

let $first := local:first($map) 

return ($map, 
for $top in $first 
     return ($top, local:sequence($map, $top)) 
) 

返回

{"barney":["pebbles", "wilma"], "fred":["barney", "wilma"], "wilma":"betty", "betty":"pebbles"} 
fred 
barney 
wilma 
betty 
pebbles 

它仍然需要工作。如果您添加：

let $seq4 := local:map-sequence($map, ('fred', 'bambam')) 

bambam不显示。我仍在努力，但如果其他人有意见，那么我想听听他们。

感谢， 罗兰

Answer 1

据我理解您的问题，每个序列代表值的层次结构，所以从序列("foo", "bar", "baz")我们可以遵循"foo" < "bar"，"foo" < "baz"和"bar" < "baz"应在生成的顺序最好持有。

从你期望的输出似乎你想要的值从一个与（传递）的前辈（你的情况"fred"）的最小数量进行排序，以具有最多的人（"pebbles"四个前辈：("barney", "fred", "betty", "wilma")） 。

我没有访问MarkLogic和其独有的地图，所以我将使用标准的XQuery 3.0映射来代替。底层算法应该易于翻译。

作为第一步，我们建立了至少在一个输入序列中找到的每个唯一值的所有直接前辈的映射。由于XQuery 3.0地图无法在原地进行修改，因此我们使用fn:fold-left(...)逐步构建一个。还要注意的是，即使是每个列表的第一个元素也会被添加到映射中，并且前面有一个空序列。

declare function local:add-preds($map0, $list as xs:string*) { 
    fn:fold-left(
    1 to fn:count($list), 
    $map0, 
    function($map, $idx) { 
     map:put(
     $map, 
     $list[$idx], 
     (: add the current predecessor to the list :) 
     fn:distinct-values((map:get($map, $list[$idx]), $list[$idx - 1])) 
    ) 
    } 
) 
}; 

接下来，我们需要这个地图前辈的传递闭包，所以我们需要收集可以从前人链给定密钥可以到达的所有值。我们可以用一个简单的深度优先搜索做到这一点：

declare function local:transitive($preds) { 
    map:merge(
    for $key in map:keys($preds) 
    return map:entry($key, local:all-predecessors($preds, $key, $key)[not(. = $key)]) 
) 
}; 

declare function local:all-predecessors($succ, $key, $seen0) { 
    fold-left(
    map:get($succ, $key), 
    $seen0, 
    function($seen, $next) { 
     if($next = $seen) then $seen 
     else local:all-predecessors($succ, $next, ($seen, $next)) 
    } 
) 
}; 

这将您例如最初的前任图

map { 
    "bambam": "fred", 
    "pebbles": ("barney", "betty"), 
    "fred":(), 
    "wilma": ("fred", "barney"), 
    "barney": "fred", 
    "betty": "wilma" 
} 

并将其转换为

map { 
    "bambam": "fred", 
    "pebbles": ("barney", "fred", "betty", "wilma"), 
    "fred":(), 
    "wilma": ("fred", "barney"), 
    "barney": "fred", 
    "betty": ("wilma", "fred", "barney") 
} 

随着映射你的排序现在变得非常简单：只需将地图中的所有键都按其前辈的数量排序，然后输出：

let $map0 := map{} 
let $map1 := local:add-preds($map0, ('fred', 'barney', 'pebbles')) 
let $map2 := local:add-preds($map1, ('fred', 'wilma', 'betty', 'pebbles')) 
let $map3 := local:add-preds($map2, ('barney', 'wilma', 'betty')) 
let $map4 := local:add-preds($map3, ('fred', 'bambam')) 
let $trans := local:transitive($map4) 

for $key in map:keys($trans) 
order by count(map:get($trans, $key)) 
return $key 

这将返回您期望的结果："fred", "bambam", "barney", "wilma", "betty", "pebbles"