{-# LANGUAGE BangPatterns #-}

module Data.RangeMin.Linear where

import Data.RangeMin.Catalan
import Data.RangeMin.Common
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV
import qualified Data.RangeMin.Linearithmic as Nlogn

rangeMin :: SliceMin -> Int -> RM
rangeMin sM !n = 
	let	!multiBlockRM0 = if m <= 600 then Nlogn.rangeMin (mIx0 `minIxOn` (blockMins !)) m else
					rangeMin (toSliceMin $ \ !i -> let 
						!slice = UV.unsafeDrop i blockMins in
						mIx0 `minIxOn` (slice !)) m
		multiBlockRM !bI !bJ = blockMins ! runRM multiBlockRM0 bI bJ
	 in flip (foldr (\ i -> seq (blockMin i 0 bS))) [0..m-1] $ toRM $ \ i j ->
	 	let	bI = i `div'` bS
			bJ = j `div'` bS
			xI = i `mod'` bS
			xJ = j `mod'` bS
	 	 in case (xI, xJ) of
			(0, 0)	-> multiBlockRM bI bJ
			(0, _)	| j - i <= bS	-- from a block start to some fraction of the same block
					-> blockMin bI 0 (j - i)
			    	| otherwise	-- from a block start to some other point
					-> multiBlockRM bI bJ `mIx` blockMin bJ 0 xJ
			(_, 0)	| j - i <= bS	-- from mid-block to the end of the same block
			   		-> blockMin bI xI bS
				| otherwise	-- from mid-block to the end of another block
			    		-> blockMin bI xI bS `mIx` multiBlockRM (bI + 1) bJ
			_ -> case bJ - bI of
				0	-> blockMin bI xI xJ	-- in the same block
				1	-> blockMin bI xI bS `mIx` blockMin bJ 0 xJ
								-- in adjacent blocks
				_	-> blockMin bI xI bS `mIx` blockMin bJ 0 xJ `mIx`
						multiBlockRM (bI + 1) bJ
								-- in separated blocks
	where	!bS = ceilLog n `div'` 4 + 1
		!m = (n + bS - 1) `div'` bS
		blockMins :: UV.Vector Int
		blockMinTable :: V.Vector RM
		(!blockMinTable, !blockMins) = catalanIndexer sM n bS
		blockMin !b !i !j = runRM (blockMinTable ! b) i j + (bS * b)
		{-# NOINLINE mIx0 #-}
		mIx0 = runSliceMin sM 0
		{-# INLINE mIx #-}
		mIx = pickMinIx mIx0