{-# 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.Int.Linearithmic.Combinators
import qualified Data.RangeMin.Fusion as F
-- 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	!nn = n - 1
  	row0 = F.iunfoldN nn (\ i xi -> let
	  i' = i + 1
	  xi' = xs ! i'
	  in if i < nn then Just (if xi <= xi' then i else i', xi') else Nothing) (xs ! 0) 
	sucRow !k !prev = let
	  !prev' = drop (bit' k) prev
	  in F.imap (\ i -> minIndex xs (prev ! i)) prev'