{-# 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.Primitive 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