Data.Sequence.Util

Documentation

binarySearchSeq :: (a -> Bool) -> Seq a -> Maybe Int

Get the index h such that everything strictly smaller than h has: p i = False, and all i >= h, we have p h = True

returns Nothing if no element satisfies p

running time: $O(log^2 n + T*log n)$, where $T$ is the time to execute the predicate.

splitMonotone :: (a -> Bool) -> Seq a -> (Seq a, Seq a)

Partition the seq s given a monotone predicate p into (xs,ys) such that

all elements in xs do *not* satisfy the predicate p all elements in ys do satisfy the predicate p

all elements in s occur in either xs or ys.

running time: $O(log^2 n + T*log n)$, where $T$ is the time to execute the predicate.

binarySearch :: Integral a => (a -> Bool) -> a -> a -> a

Given a monotonic predicate p, a lower bound l, and an upper bound u, with: p l = False p u = True l < u.

Get the index h such that everything strictly smaller than h has: p i = False, and all i >= h, we have p h = True

running time: $O(log(u - l))$