{-# LANGUAGE CPP, BangPatterns #-} -- | Consider the following function, which, given 'i' and 'k', finds the index of -- the minimum element in the range @i..i+k-1@. -- -- @ -- rangeMin :: 'G.Vector' v a => (a -> a -> 'Ordering') -> v a -> 'Int' -> 'Int' -> 'Int' -- rangeMin cmp xs i k = i + 'G.minIndexBy' cmp ('G.slice' i k xs) -- @ -- -- This module implements functions which, given a fixed comparison function, preprocess -- an array in /O(n)/ time to support queries of this form in /O(1)/ time. -- -- For all methods in this module, ties are broken by which element comes first in the array. -- -- When certain methods are called on an element type which has a natural, order-preserving -- injection into 'Int' -- specifically, on instances of 'Injective' -- this module is -- smart enough to (fusibly) convert the vector into a @'PV.Vector' 'Int'@, and to use -- 'unsafeIntRangeMin' or 'intRangeMin' as appropriate. Though you cannot make your -- own instances of 'Injective', 'unsafeInjectRangeMin' and 'injectRangeMin' work the same -- way. module Data.RangeMin ( -- * Utility types RangeMin, LEq, Index, Length, -- * Specialized range-mins unsafeIntRangeMin, intRangeMin, -- * @Vector@ range-mins unsafeVecRangeMinBy, unsafeVecRangeMin, unsafeVecRangeMax, vecRangeMinBy, vecRangeMin, vecRangeMax, -- * General range-mins unsafeRangeMinBy, unsafeRangeMin, unsafeRangeMax, rangeMinBy, rangeMin, rangeMax, -- * Specialized types Injective, unsafeInjectRangeMin, unsafeInjectRangeMax, injectRangeMin, injectRangeMax) where import qualified Data.Vector.Generic as G import qualified Data.Vector.Primitive as PV import Data.RangeMin.Common import Data.RangeMin.Int import Data.RangeMin.Vector import Data.RangeMin.Generic import Data.RangeMin.Inject