| Copyright | (c) 2009-2015 Dan Doel 2015 Tim Baumann |
|---|---|
| Maintainer | Dan Doel <dan.doel@gmail.com> |
| Stability | Experimental |
| Portability | Non-portable (bang patterns) |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Data.Vector.Algorithms.Search
Description
This module implements several methods of searching for indicies to insert elements into a sorted vector.
Synopsis
- 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
- binarySearchP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int
- binarySearchPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int
- gallopingSearchLeftP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int
- gallopingSearchLeftPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int
- gallopingSearchRightP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int
- gallopingSearchRightPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) 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 Int Source #
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 Int Source #
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 Int Source #
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 Int Source #
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 Int Source #
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 Int Source #
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 Int Source #
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 Int Source #
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 Int Source #
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.
binarySearchP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int Source #
Given a predicate that is guaranteed to be monotone on the given vector, finds the first index at which the predicate returns True, or the length of the array if the predicate is false for the entire array.
binarySearchPBounds :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> Int -> Int -> m Int Source #
Given a predicate that is guaranteed to be monotone on the indices [l,u) in a given vector, finds the index in [l,u] at which the predicate turns from False to True (yielding u if the entire interval is False).
gallopingSearchLeftP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int Source #
Given a predicate that is guaranteed to be monotone on the vector elements in order, finds the index at which the predicate turns from False to True. The length of the vector is returned if the predicate is False for the entire vector.
Begins searching at the start of the vector, in increasing steps of size 2^n.
gallopingSearchLeftPBounds Source #
Given a predicate that is guaranteed to be monotone on the indices [l,u) in a given vector, finds the index in [l,u] at which the predicate turns from False to True (yielding u if the entire interval is False). Begins searching at l, going right in increasing (2^n)-steps.
gallopingSearchRightP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m Int Source #
Given a predicate that is guaranteed to be monotone on the vector elements in order, finds the index at which the predicate turns from False to True. The length of the vector is returned if the predicate is False for the entire vector.
Begins searching at the end of the vector, in increasing steps of size 2^n.
gallopingSearchRightPBounds Source #
Given a predicate that is guaranteed to be monotone on the indices [l,u) in a given vector, finds the index in [l,u] at which the predicate turns from False to True (yielding u if the entire interval is False). Begins searching at u, going left in increasing (2^n)-steps.
type Comparison e = e -> e -> Ordering Source #
A type of comparisons between two values of a given type.