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