{-# LANGUAGE BangPatterns #-}

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

import Data.RangeMin.Common.Types (RM, toRM)
import Data.RangeMin.Common.Math (bit', intLog)
import Data.RangeMin.Common.Vector
import Data.RangeMin.Common.Unf
import Data.RangeMin.Common.Unf.Slice
import qualified Data.Vector.Unboxed as UV
import Prelude hiding (drop)

rangeMin :: UV.Vector Int -> RM
rangeMin !xs = toRM $ \ i d -> case d of
  1	-> i
  2	-> table ! i
  _	-> let
    !k = intLog d 
    row = getRow nn table (k-1)
    in minIndex xs (row i) (row (i + d - bit' k))
 where	!n = UV.length xs
 	!m = intLog n
 	!nn = n - 1
	!table = buildTable m n xs

buildTable :: Int -> Int -> UV.Vector Int -> UV.Vector Int
buildTable !m !n !xs = buildRowsUnf m (n-1) Nothing row0 sucRow
	where	row0 = Unf (n-1) (xs ! 0) (\ i xi -> let
			i' = i + 1
			xi' = xs ! i'
			in Just (if xi <= xi' then i else i', xi'))
		sucRow !k !prev = let
			!prev' = drop (bit' k) prev
			mix i = minIndex xs (prev ! i) (prev' ! i)
			in generateUnf (UV.length prev') mix