toy-lib-0.1.0.0
Safe HaskellSafe-Inferred
LanguageHaskell2010

Algorithm.Bisect

Description

\(O(\log N)\) bisection method for sorted items in an inclusive range (from left to right only).

bisect returns an (yes, no) index pair at the boundary. bisectL and bisectR returns one of the pair. bisectM is a monadic variant of bisect.

Example

With an yes predicate (<= 5), list [0..9] can be seen as:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 <-------------->  <-------->
        yes             no

In the preceding example, bisect returns the (yes, no) = (Just 5, Just 6) pair at the boundary:

>>> :{
let xs = [0 :: Int .. 9]
 in bisect 0 9 (\i -> xs !! i <= 5)
:}
(Just 5,Just 6)

bisectL returns Just 5 and bisectR returns Just 6.

Synopsis

Common bisection method implementation

bisectImpl :: forall i m. (Eq i, Monad m) => (i -> i -> Maybe i) -> i -> i -> i -> i -> (i -> m Bool) -> m (Maybe i, Maybe i) #

\(O(f \log N)\) Bisection method implementation. It's generalized over both the index type and the monad.

Parameters

  • getMid: Returns the mid index between two. Returns Nothing if the two indices are close enough.
  • lowOut: Nearest low index that is NOT included in the range.
  • highOut: Nearest high index that is NOT included in the range.

getMidInt :: Int -> Int -> Maybe Int #

getMid parameter of bisectImpl for Int indices.

getMidDouble :: Double -> Double -> Double -> Maybe Double #

getMid parameter of bisectImpl for Double indices.

Bisection method for Int range

bisectM :: forall m. Monad m => Int -> Int -> (Int -> m Bool) -> m (Maybe Int, Maybe Int) #

\(O(f \log N)\) Monadic binary search for an Int range.

bisectML :: forall m. Monad m => Int -> Int -> (Int -> m Bool) -> m (Maybe Int) #

\(O(f \log N)\)

bisectMR :: forall m. Monad m => Int -> Int -> (Int -> m Bool) -> m (Maybe Int) #

\(O(f \log N)\)

bisect :: Int -> Int -> (Int -> Bool) -> (Maybe Int, Maybe Int) #

\(O(f \log N)\) Pure binary search for an Int range.

bisectL :: Int -> Int -> (Int -> Bool) -> Maybe Int #

\(O(f \log N)\) Also known as lower bound.

bisectR :: Int -> Int -> (Int -> Bool) -> Maybe Int #

\(O(f \log N)\) Also known as upper bound.

Bisection method for Double range

bisectMF64 :: forall m. Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double, Maybe Double) #

\(O(f \log N)\) Monadic binary search for an Double range.

bisectMLF64 :: forall m. Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double) #

\(O(f \log N)\)

bisectMRF64 :: forall m. Monad m => Double -> Double -> Double -> (Double -> m Bool) -> m (Maybe Double) #

\(O(f \log N)\)

bisectF64 :: Double -> Double -> Double -> (Double -> Bool) -> (Maybe Double, Maybe Double) #

\(O(f \log N)\) Pure binary search for an Double range.

bisectLF64 :: Double -> Double -> Double -> (Double -> Bool) -> Maybe Double #

\(O(f \log N)\) Also known as lower bound.

bisectRF64 :: Double -> Double -> Double -> (Double -> Bool) -> Maybe Double #

\(O(f \log N)\) Also known as upper bound.

Binary search over a vector

bsearchM :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> Bool) -> m (Maybe Int, Maybe Int) #

\(O(f \log N)\) bisectM over a vector.

bsearchML :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> Bool) -> m (Maybe Int) #

\(O(f \log N)\) bisectML over a vector.

bsearchMR :: (PrimMonad m, MVector v a) => v (PrimState m) a -> (a -> Bool) -> m (Maybe Int) #

\(O(f \log N)\) bisectMR over a vector.

bsearchMExact :: (PrimMonad m, MVector v a, Ord b) => v (PrimState m) a -> (a -> b) -> b -> m (Maybe Int) #

\(O(\log N)\) bsearchMExact over a vector, searching for a specific value. FIXME: It's slower than bsearchL.

bsearch :: Vector v a => v a -> (a -> Bool) -> (Maybe Int, Maybe Int) #

\(O(f \log N)\) bisect over a vector.

bsearchL :: Vector v a => v a -> (a -> Bool) -> Maybe Int #

\(O(f \log N)\) bisectL over a vector.

bsearchR :: Vector v a => v a -> (a -> Bool) -> Maybe Int #

\(O(f \log N)\) bisectR over a vector.

bsearchExact :: (Vector v a, Ord b) => v a -> (a -> b) -> b -> Maybe Int #

\(O(\log N)\) bsearchExact over a vector, searching for a specific value. FIXME: It's slower than bsearchL.

isqrtSlow :: Int -> Int #

Retrieves square root of an Int.