{-# LANGUAGE CPP, BangPatterns #-}

module Data.RangeMin.Int.NearLinear (rangeMin) where

import Data.RangeMin.Common
import qualified Data.RangeMin.Fusion as F
import qualified Data.RangeMin.Int.Linearithmic as Nlogn

import Prelude hiding (drop)

-- | This implements the /O(n)/ precomputation, /O(log n)/ query algorithm.
-- It precomputes block-mins for blocks of size /log n \/ 2/, uses the
-- /O(n log n)/ algorithm for multi-block queries, and explicitly computes
-- internal block queries.
rangeMin :: PVector Value -> RM
rangeMin !xs = let
	!multiBlockRM0 = Nlogn.rangeMin blockMinVals
	multiBlockRM !bI !bM = blockMins ! runRM multiBlockRM0 bI bM
	in toRM $ \ i m -> let
		(bI, xI) = i `divMod'` bS
		(bJ, rJ, xJ) = (i+m) `divRoundMod'` bS
		bD = bJ - bI
		explicit = rM' i m
		left = rM' i (bS - xI)
		right = rM' rJ xJ
		in case (xI, xJ) of
		 	(0, 0)	-> multiBlockRM bI bD
			(0, _)	| m < bS	-> explicit
				| otherwise	-> multiBlockRM bI bD `mix` right
			(_, 0)	| m < bS	-> explicit
				| otherwise	-> multiBlockRM (bI+1) (bD-1) `mix` left
			(_, _)	| bD <= 1	-> explicit
				| otherwise	-> left `mix` right `mix` multiBlockRM (bI + 1) (bD - 1)
	where	!bS = ceilLog n `div'` 2 + 1
		blockMins :: PVector Index
		!(!blockMins, !blockMinVals) = F.unzip (F.map (\ (P i xi) -> (i, xi)) 
			(F.generate mm (\ b -> rM (b * bS) bS) `F.snoc'` (let !z = mm * bS in rM z (n-z))))
		!n = vlength xs
		!m = (n + bS - 1) `div'` bS
		!mm = m - 1
		rM = explicitRM xs
		rM' = pIx .: explicitRM xs
		mix = minIndex xs

data P = P {pIx :: {-# UNPACK #-} !Index, _pVal :: {-# UNPACK #-} !Value}

explicitRM :: PVector Value -> Index -> Length -> P
explicitRM !xs !i !m = case F.ifoldl suc (P (-1) (split ! 0)) (drop 1 split) of
		P j xj -> P ((i + 1) + j) xj
 where	!split = slice i m xs
 	suc (P j xj) k xk
	  | xj <= xk	= P j xj
	  | otherwise	= P k xk