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.