0
\$\begingroup\$

I have written a function in XQuery 3.0 (using BaseX) which tests a base sequence against a test sequence, with the goal of determining if the items in the test sequence appear in the same order as the base sequence.

This is best illustrated with an example

E.G. let $baseSequence := ('a','b','c'..'x','y','z')

Tested against

('a','b','c') => true appears in the same order in $baseSequence

('a','b','a') => false is not in the same order in $baseSequence

('c','h','x','y') => true appears in the same order in $baseSequence

I would like to know if there are any improvements on the function I have written for this, or is there a better way of doing this?

declare function local:testOrder($baseSequence, $testSequence, $position) {
    let $itemPosition := 
    if(count($testSequence) = 0) then (32768) else (index-of($baseSequence, head($testSequence)))
  return
    if ($itemPosition > $position) then (
      local:testOrder($baseSequence, tail($testSequence), $itemPosition)
    ) else (
      count($testSequence) = 0
    )
};

(:Test cases:)
let $baseSequence := ('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z')
let $testAgainst := ('a','c','e','h','w')
return local:testOrder($baseSequence, $testAgainst, 0)

Would return true

let $baseSequence := ('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z')
    let $testAgainst := ('f','d','l','m','n')
    return local:testOrder($baseSequence, $testAgainst, 0)

Would return false

\$\endgroup\$
1
\$\begingroup\$

There is a more concise possible approach if you, first, convert the test sequence into the corresponding positions in the base sequence, then, substract each position to the next one (replace "ge 0" with "gt 0" if duplicates are not allowed):

declare function local:testOrder2($baseSequence, $testSequence) {
    let $positions := $testSequence ! index-of($baseSequence, .)
    return min(for $pos at $index in tail($positions) return $pos - $positions[$index]) ge 0
};

Your recursive approach will stop at the first disorder detection so, depending on inputs, it might be faster!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.