vector-algorithms-0.3.2: Efficient algorithms for vector arrays Source code Contents Index

Data.Vector.Algorithms.Search Portability Non-portable (bang patterns) Stability Experimental Maintainer Dan Doel <dan.doel@gmail.com>

Description

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

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 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 givesn sorted array at which the given element could be inserted while maintaining the sortedness of the array.

binarySearchBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> m Int Source

Finds an index in a given array, which must be sorted with respect to the given comparison function, at which the given element could be inserted while preserving the array's sortedness.

binarySearchByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> e -> Int -> Int -> m Int Source

Given an array 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 array 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 array, 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 an array 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.

type Comparison e = e -> e -> Ordering Source

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

Produced by Haddock version 2.6.0