{-# LANGUAGE BangPatterns #-}

module Data.RangeMin.Linearithmic (rangeMin) where

import Data.Bits (bit)

import Data.RangeMin.Common
import qualified Data.Vector.Unboxed as UV
-- import qualified Data.Vector.Fusion.Stream.Monadic as S

rangeMin :: MinIx -> Int -> RM
rangeMin mIx !n = 
	toRM $ \ i j -> if i == j - 1 then i else let 
		!k = intLog (j - i)
		row = lookupTable k
		in pickMinIx mIx (row i) (row (j - bit k))
 where	!m = ceilLog n
	lookupTable k i = table ! (k * n + i)
	!table = buildTable m n mIx

buildTable :: Int -> Int -> MinIx -> UV.Vector Int
buildTable !m !n mIx = buildSliced (m+1) n Nothing (UV.enumFromStepN 0 1 n) $ \ i prev -> 
	let !k = bit (i-1) in UV.zipWith (pickMinIx mIx) prev (UV.unsafeDrop k prev)