| Portability | Non-portable (bang patterns) |
|---|---|
| Stability | Experimental |
| Maintainer | Dan Doel <dan.doel@gmail.com> |
| Safe Haskell | Safe-Infered |
Data.Vector.Algorithms.Search
Description
This module implements several methods of searching for indicies to insert elements into a sorted vector.
- binarySearch :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int
- binarySearchBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int
- binarySearchByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int
- binarySearchL :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int
- binarySearchLBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int
- binarySearchLByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int
- binarySearchR :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m Int
- binarySearchRBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int
- binarySearchRByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int
- type Comparison e = e -> e -> Ordering
Documentation
binarySearch :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m IntSource
Finds an index in a given sorted vector at which the given element could be inserted while maintaining the sortedness of the vector.
binarySearchBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m IntSource
Finds an index in a given vector, which must be sorted with respect to the given comparison function, at which the given element could be inserted while preserving the vector's sortedness.
binarySearchByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m IntSource
Given a vector sorted with respect to a given comparison function in indices in [l,u), finds an index in [l,u] at which the given element could be inserted while preserving sortedness.
binarySearchL :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m IntSource
Finds the lowest index in a given sorted vector at which the given element could be inserted while maintaining the sortedness.
binarySearchLBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m IntSource
Finds the lowest index in a given vector, which must be sorted with respect to the given comparison function, at which the given element could be inserted while preserving the sortedness.
binarySearchLByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m IntSource
Given a vector sorted with respect to a given comparison function on indices in [l,u), finds the lowest index in [l,u] at which the given element could be inserted while preserving sortedness.
binarySearchR :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> e -> m IntSource
Finds the greatest index in a given sorted vector at which the given element could be inserted while maintaining sortedness.
binarySearchRBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m IntSource
Finds the greatest index in a given vector, which must be sorted with respect to the given comparison function, at which the given element could be inserted while preserving the sortedness.
binarySearchRByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m IntSource
Given a vector sorted with respect to the given comparison function on indices in [l,u), finds the greatest index in [l,u] at which the given element could be inserted while preserving sortedness.
type Comparison e = e -> e -> OrderingSource
A type of comparisons between two values of a given type.