Re: XPath expression to check that there are no inter

Assuming naive implementations, a lot of these expressions will be slow,
O(n^2) or worse in the number of siblings.

Certainly anything that does following-sibling::*/following-sibling::Y is
likely to be O(n^2) without some smart optimization.

If we're looking at performance, then I think the best solution is likely to
be a finite state machine.

We have the following states and transitions:

In state 0, a B takes us to state 1
In state 1, a non-B takes us to state 2
In state 2, a B takes us to state 3
In state 3, nothing changes.

If we end up in state 3, we have failed.

The finite state machine can be coded as:

let $fsm := map{
  0: function($x) {if ($x[self::B]) then 1 else 0},
  1: function($x) {if ($x[self::B]) then 1 else 2),
  2: function($x) {if ($x[self::B]) then 3 else 2},
  3: function($x) {3}
}

and we can then run the machine with

if (fold-left(*, 0, function($state, $node){$fsm($state)($node)}) = 3)
then "invalid"
else "valid"

(This could also be refined by throwing an error as soon as we reach state 3,
avoiding the need in that case to scan to the end).

Another approach would be to use a regular expression:

not(matches(string-join(* ! (if (self::B) then "B" else "A"), ""), "BAB"))

Michael Kay
Saxonica

> On 19 Jul 2016, at 17:44, G. Ken Holman g.ken.holman@xxxxxxxxx
<xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
>
> Okay ... I wonder if this might be fastest of all:
>
>  B  and  not(
B[1]/following-sibling::*[not(self::B)][1]/following-sibling::B )
>
> for "there is a B, and starting from it there is no following sibling non-B
that has a following sibling B.  No counting and no looking backwards.
>
> . . . . . . Ken
>
> At 2016-07-19 16:36 +0000, Dimitre Novatchev dnovatchev@xxxxxxxxx wrote:
>
>> To avoid the false true when there are no Bs at all:
>>
>>
>> XPath 1.0:
>> B and not(B[1]/following-sibling::node()[not(position()  >
>> ../count(B))][not(self::B)])
>>
>>
>> XPath 2.0:
>> B and not(node()[. >> ../B[1] and . << ../B[last()]][not(self::B)])
>>
>> On Tue, Jul 19, 2016 at 9:29 AM, Dimitre Novatchev <dnovatchev@xxxxxxxxx>
wrote:
>> > XPath 1.0:
>> >
>> >  not(B[1]/following-sibling::node()[not(position() >
>> > ../count(B))][not(self::B)])
>> >
>> > XPath 2.0:
>> >
>> > not(node()[. >> ../B[1] and . << ../B[last()]][not(self::B)])
>> >
>> > Cheers,
>> > Dimitre
>> >
>> > On Tue, Jul 19, 2016 at 9:16 AM, G. Ken Holman g.ken.holman@xxxxxxxxx
>> > <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
>> >> I like Mike's answer for XSLT 2.
>> >>
>> >> Your XSLT 1 solution can be improved by reducing the number of counting
>> >> actions.  Your solution has three uses of count() ... this has only
two:
>> >>
>> >>   count(B[last()]/preceding-sibling::*[not(self::B)]) =
>> >>   count(B[1]/preceding-sibling::*[not(self::B)])
>> >>
>> >> Avoiding the use of counting you could do the following:
>> >>
>> >>   string( generate-id( B[1]/preceding-sibling::*[not(self::B)][1] ) ) =
>> >>   string( generate-id( B[last()]/preceding-sibling::*[not(self::B)][1] )
)
>> >>
>> >> The use of string() is necessary in case the sequence of children
starts
>> >> with B.
>> >>
>> >> Come to think of it, neither your answer, Mike's answer nor my answer
will
>> >> work if there are no B children at all.  You will get a false positive.
>> >> Does your test need to accommodate that situation?
>> >>
>> >> . . . . . . . . Ken
>> >>
>> >> At 2016-07-19 15:44 +0000, Costello, Roger L. costello@xxxxxxxxx wrote:
>> >>>
>> >>> Hi Folks,
>> >>>
>> >>> This XML has a solid block of <B> elements:
>> >>>
>> >>> <Document>
>> >>>     <A/>
>> >>>     <B/>
>> >>>     <B/>
>> >>> </Document>
>> >>>
>> >>> This XML has an intervening <C> element:
>> >>>
>> >>> <Document>
>> >>>     <A/>
>> >>>     <B/>
>> >>>     <C/>
>> >>>     <B/>
>> >>> </Document>
>> >>>
>> >>> I need an XPath expression to return a Boolean value:
>> >>>
>> >>>         Return true if there is one solid block of <B> elements
>> >>>                 (no intervening elements).
>> >>>         Otherwise, return false.
>> >>>
>> >>> I created a horrendous XPath expression to solve it:
>> >>>
>> >>> count(B) eq (B[last()]/count(preceding-sibling::*)+1 -
>> >>> B[1]/count(preceding-sibling::*))
>> >>>
>> >>> Can you provide a better (simpler, more efficient) XPath expression?
>> >>>
>> >>> /Roger
>> >>>
>
>
> --
> Check our site for free XML, XSLT, XSL-FO and UBL developer resources |
> Streaming hands-on XSLT/XPath 2 training @US$45: http://goo.gl/Dd9qBK |
> Crane Softwrights Ltd. _ _ _ _ _ _ http://www.CraneSoftwrights.com/s/ |
> G Ken Holman _ _ _ _ _ _ _ _ _ _ mailto:gkholman@xxxxxxxxxxxxxxxxxxxx |
> Google+ blog _ _ _ _ _ http://plus.google.com/+GKenHolman-Crane/posts |
> Legal business disclaimers: _ _ http://www.CraneSoftwrights.com/legal |
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus