search package:fingertree

O(log(min(i,n-i))). Search a sequence for a point where a predicate on splits of the sequence changes from False to True. The argument p is a relation between the measures of the two sequences that could be appended together to form the sequence t. If the relation is False at the leftmost split and True at the rightmost split, i.e.

not (p mempty (measure t)) && p (measure t) mempty

then there must exist an element x in the sequence such that p is False for the split immediately before x and True for the split just after it: In this situation, search p t returns such an element x and the pieces l and r of the sequence to its left and right respectively. That is, it returns Position l x r such that

• l >< (x <| r) = t

• not (p (measure l) (measure (x <| r))

• p (measure (l |> x)) (measure r)

For predictable results, one should ensure that there is only one such point, i.e. that the predicate is monotonic on t.

O(k log (n/k)). All intervals that contain the given point, in lexicographical order.

A result of search, attempting to find a point where a predicate on splits of the sequence changes from False to True.