{-# LANGUAGE BangPatterns #-}
module Data.RangeMin.Int.Catalan (catalanIndexer) where

-- import Control.Monad
-- import Data.RangeMin.ST
-- import Data.RangeMin.Common
import Data.RangeMin.Common
import qualified Data.Vector as V
import qualified Data.Vector.Primitive as UV
-- import qualified Data.Vector.Fusion.Stream as S
import qualified Data.RangeMin.Int.Quadratic as N2 
import qualified Data.RangeMin.Int.Linearithmic as Nlogn
-- import qualified Data.Vector.Generic as G
-- import qualified Data.RangeMin.IPVector as IP
-- import qualified Data.Vector.Primitive as UV
-- import Data.RangeMin.IPVector (IP (..))
import Data.RangeMin.Int.Catalan.Combinators
import Data.RangeMin.Int.Catalan.Table
import Prelude hiding (drop, read)

data IL = {-# UNPACK #-} !Int :< IL | Nil

{-# INLINE [0] catalanIndex #-}
catalanIndex :: UV.Vector Int -> Int -> IP
catalanIndex !vec !bS = catalans `seq` scan 0 (bS-1) bS 0 0 Nil where
	!n = UV.length vec
	scan !y !p !q !cum !mi !ys
	  | y == n	= IP cum mi
	  | otherwise	= let
		vy = vec ! y
		catp = catalan p
		scan' !q !cum xs0@(vx :< xs)
			| vx > vy
			  = scan' (q-1) (cum + catp q) xs
			| otherwise
			  = scan (y+1) (p-1) q cum mi (vy :< xs0)
		scan' !q !cum ys
			= scan (y+1) (p-1) q cum y (vy :< ys)
		in scan' q cum ys

catalanIndexer :: UV.Vector Int -> Int -> (UV.Vector Int, V.Vector RM, UV.Vector Int)
catalanIndexer !xs !bS = catalans `seq` (catIxs0, typeRMs0, minIxs0)
	where	!typeRMs0 = equivClasses cat $ V.generate m (\ b -> 
			(catIxs0 ! b, if b == mm then rmAlgo lastBlock else rmAlgo (block b)))
		lastBlock = drop (bS * mm) xs
		block b = slice (bS * b) bS xs
		cat = catalan bS bS
		off b (IP cum mi) = IP cum (mi + bS * b)
		catIxs0 :: UV.Vector Int
		!(!catIxs0, !minIxs0) = unzipIPM $ unfoldM 
			(generateUnf m (\ b -> off b (catalanIndex (if b == mm then lastBlock else block b) bS)))
		!n = UV.length xs
		!m = (n + bS - 1) `div'` bS
		!mm = m - 1
		rmAlgo	| not forceBlockN2 && bS > n2Cross
				= Nlogn.rangeMin
			| otherwise
				= N2.rangeMin