hgeometry-0.5.0.0: Geometric Algorithms, Data structures, and Data types.

Data.Sequence.Util

Synopsis

# Documentation

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

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) Source

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 Source

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))\$