{-# LANGUAGE BangPatterns #-}

module Data.RangeMin.Quadratic (rangeMin) where

-- import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Unboxed as UV
import Data.RangeMin.Common

rangeMin :: MinIx -> Int -> RM
rangeMin mIx !n = 
	let 	!table = quadTable mIx n
		!m = 2 * n - 1
		encode !i !j = (i * (m - i)) `div'` 2 + j - 1
		in toRM $ \ i j -> table ! encode i j

data Q = Q {-# UNPACK #-} !Int {-# UNPACK #-} !Int {-# UNPACK #-} !Int

{-# INLINE [1] quadTable #-}
quadTable :: MinIx -> Int -> UV.Vector Int
quadTable mIx !n = UV.unfoldrN ((n * (n + 1)) `div'` 2) suc (Q 0 0 0) where
	suc (Q i j x)
	  | j == n	= let i' = i + 1 in
		if i' == n then Nothing else Just (i', Q i' (i' + 1) i')
	  | otherwise	= let x' = pickMinIx mIx x j in
		Just (x', Q i (j + 1) x')