| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
HGeometry.Algorithms.BinarySearch
Contents
Description
Synopsis
- binarySearchFirst :: Integral a => (a -> Bool) -> a -> a -> a
- binarySearchLast :: Integral a => (a -> Bool) -> a -> a -> a
- binarySearchUntil :: (Fractional r, Ord r) => r -> (r -> Bool) -> r -> r -> r
- data BinarySearchResult a
- firstTrue :: BinarySearchResult a -> Maybe a
- lastFalse :: BinarySearchResult a -> Maybe a
- class BinarySearch v where
- type Elem v :: Type
- type Index v :: Type
- binarySearchIn :: (Elem v -> Bool) -> v -> BinarySearchResult (Elem v)
- binarySearchIdxIn :: (Elem v -> Bool) -> v -> BinarySearchResult (Index v)
- binarySearchFirstIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Elem v)
- binarySearchFirstIdxIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Index v)
- binarySearchLastIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Elem v)
- binarySearchLastIdxIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Index v)
Generic Binary Search algorithms
binarySearchFirst :: 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:
- all indices i < h have p i = False, and
- all indices i >= h have p i = True
That is, find the first index h for which the predicate is True.
running time: \(O(\log(u - l))\)
binarySearchLast :: 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:
- all indices i <= h have p i = False, and
- all indices i > h have p i = True
That is, find the last index h for which the predicate is False.
running time: \(O(\log(u - l))\)
binarySearchUntil :: (Fractional r, Ord r) => r -> (r -> Bool) -> r -> r -> r Source #
Given a value \(\varepsilon\), a monotone predicate \(p\), and two values \(l\) and \(u\) with:
- \(p l\) = False
- \(p u\) = True
- \(l < u\)
we find a value \(h\) such that:
- \(p h\) = True
- \(p (h - \varepsilon)\) = False
>>>binarySearchUntil (0.1) (>= 0.5) 0 (1 :: Double)0.5>>>binarySearchUntil (0.1) (>= 0.51) 0 (1 :: Double)0.5625>>>binarySearchUntil (0.01) (>= 0.51) 0 (1 :: Double)0.515625
data BinarySearchResult a Source #
Data type representing the result of a binary search
Constructors
| AllTrue a | |
| FlipsAt a a | the last false elem and the first true elem |
| AllFalse (Maybe a) | A maybe, since the collection may be empty |
Instances
firstTrue :: BinarySearchResult a -> Maybe a Source #
lastFalse :: BinarySearchResult a -> Maybe a Source #
class BinarySearch v where Source #
Containers storing elements on which we can binary search.
Associated Types
The type of the elements of the container
The type of indices used in the container.
Methods
binarySearchIn :: (Elem v -> Bool) -> v -> BinarySearchResult (Elem v) Source #
Given a monotonic predicate p and a data structure v, find the pair of elements (v[h], v[h+1]) such that that
for every index i <= h we have p v[i] = False, and for every inedx i > h we have p v[i] = True
running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.
binarySearchIdxIn :: (Elem v -> Bool) -> v -> BinarySearchResult (Index v) Source #
Given a monotonic predicate p and a data structure v, find the index h such that that
for every index i <= h we have p v[i] = False, and for every inedx i > h we have p v[i] = True
running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.
Instances
| BinarySearch (Seq a) Source # | |
Defined in HGeometry.Algorithms.BinarySearch Methods binarySearchIn :: (Elem (Seq a) -> Bool) -> Seq a -> BinarySearchResult (Elem (Seq a)) Source # binarySearchIdxIn :: (Elem (Seq a) -> Bool) -> Seq a -> BinarySearchResult (Index (Seq a)) Source # | |
| BinarySearch (Set a) Source # | |
Defined in HGeometry.Algorithms.BinarySearch Methods binarySearchIn :: (Elem (Set a) -> Bool) -> Set a -> BinarySearchResult (Elem (Set a)) Source # binarySearchIdxIn :: (Elem (Set a) -> Bool) -> Set a -> BinarySearchResult (Index (Set a)) Source # | |
| Vector v a => BinarySearch (v a) Source # | |
Defined in HGeometry.Algorithms.BinarySearch Methods binarySearchIn :: (Elem (v a) -> Bool) -> v a -> BinarySearchResult (Elem (v a)) Source # binarySearchIdxIn :: (Elem (v a) -> Bool) -> v a -> BinarySearchResult (Index (v a)) Source # | |
binarySearchFirstIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Elem v) Source #
Given a monotonic predicate p and a data structure v, find the element v[h] such that that
for every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True
returns Nothing if no element satisfies p
running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.
binarySearchFirstIdxIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Index v) Source #
Given a monotonic predicate p and a data structure v, find the index h such that that
for every index i < h we have p v[i] = False, and for every inedx i >= h we have p v[i] = True
returns Nothing if no element satisfies p
running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.
binarySearchLastIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Elem v) Source #
Given a monotonic predicate p and a data structure v, find the element v[h] such that that
for every index i <= h we have p v[i] = False, and for every inedx i > h we have p v[i] = True
returns Nothing if no element satisfies p
running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.
binarySearchLastIdxIn :: BinarySearch v => (Elem v -> Bool) -> v -> Maybe (Index v) Source #
Given a monotonic predicate p and a data structure v, find the index h such that that
for every index i <= h we have p v[i] = False, and for every inedx i > h we have p v[i] = True
returns Nothing if no element satisfies p
running time: \(O(T*\log n)\), where \(T\) is the time to execute the predicate.