vector-algorithms-0.6.0.2: Efficient algorithms for vector arrays

Portability Non-portable (bang patterns) Experimental Dan Doel None

Data.Vector.Algorithms.Search

Description

This module implements several methods of searching for indicies to insert elements into a sorted vector.

Synopsis

# 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.

binarySearchP :: (PrimMonad m, MVector v e) => (e -> Bool) -> v (PrimState m) e -> m IntSource

Given a predicate that is guaraneteed 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 IntSource

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

type Comparison e = e -> e -> OrderingSource

A type of comparisons between two values of a given type.