Module BatFingerTree.Generic

module Generic: sig .. end

include BatFingerTree.S

val lookup : (('m -> bool) -> ('a, 'm) fg -> 'a, 'a, 'm) wrap

lookup p t, when p is monotonic, returns the first element of the sequence for which the measure of its predecessors in the sequence (itself included) satisfies p.

Raises Empty is there is no such element. O(log(n)). When p is not monotonic, take a look at the code or at the paper cited above and see if you understand something (lookup is a specialized version of splitTree that returns the element without building the left and right tree).

val measure : (('a, 'm) fg -> 'm, 'a, 'm) wrap

measure m gives the measure of the whole tree, whose meaning depends on the measure chosen.

O(1).

val split : (('m -> bool) -> ('a, 'm) fg -> ('a, 'm) fg * ('a, 'm) fg, 'a, 'm) wrap

split p t, when p is monotonic, returns (t1, t2) where t1 is the longest prefix of t whose measure does not satisfies p, and t2 is the rest of t.

Raises Empty is there is no such element O(log(n)). When p is not monotonic, take a look at the code or at the paper cited above and see if you understand something.