{-# LANGUAGE ScopedTypeVariables, TupleSections, BangPatterns #-}
module Data.RangeMin.Catalan (catalanIndexer) where

-- import Control.Monad
import Data.RangeMin.Common
import qualified Data.Vector as V (Vector)
-- import qualified Data.Vector.Generic as G
-- import qualified Data.Vector.Generic.Mutable as GM
-- import qualified Data.RangeMin.Mixed as Mix
import qualified Data.Vector.Unboxed as UV
-- import qualified Data.Vector.Unboxed.Mutable as UM
-- import qualified Data.Vector.Unboxed as SV
-- import qualified Data.Vector.Fusion.Stream as Stream
-- import qualified Data.Vector.Fusion.Stream.Monadic as StreamM
-- import qualified Data.Vector.Fusion.Stream as S (replicate)
import qualified Data.RangeMin.Quadratic as N2 
import qualified Data.RangeMin.Linearithmic as Nlogn
-- import qualified Data.List as List

maxLog :: Int
maxLog = 17

catalans :: UV.Vector Int
catalans = buildSliced maxLog maxLog (Just 0) (UV.replicate maxLog 1) $
	const (UV.postscanl' (+) 0 . UV.unsafeTail)

catalan :: Int -> Int -> Int
catalan !p !q = catalans ! (p * (maxLog - 1) + q)

data IL = {-# UNPACK #-} !Int :< IL | Nil deriving (Show)
data IP = IP {-# UNPACK #-} !Int {-# UNPACK #-} !Int

{-# INLINE catalanIndex #-}
catalanIndex :: MinIx -> Int -> Int -> IP
catalanIndex mIx !bS !n = catalans `seq` scan 0 (bS-1) bS 0 0 Nil where
	scan !y !p !q !cum !mi !ys
	  | y == n	= IP cum mi
	  | otherwise	= let
		scan' !q !cum (x :< xs)
			| not (runMinIx mIx x y)
				= scan' (q-1) (cum + catalan p q) xs
			| otherwise
				= scan (y+1) (p-1) q cum mi (x :< xs)
		scan' !q !cum ys
			= scan (y+1) (p-1) q cum y (y :< ys)
		in scan' q cum ys

catalanIndexer :: SliceMin -> Int -> Int -> (V.Vector RM, UV.Vector Int)
catalanIndexer sM !n !bS = catalans `seq` (unsafeBackpermute' ixRMs catIxs, minIxs)
	where	!m = (n + bS - 1) `div'` bS
		!mm = m - 1
		!lastBS = n - mm * bS
		catIxs :: UV.Vector Int
		(!catIxs, !minIxs) = UV.unzip $ UV.generate m (\ b ->
			let !z = bS * b in
				case catalanIndex (runSliceMin sM z)
					bS (if b == mm then lastBS else bS) of
					IP i j -> (i, j + z))
		!ixRMs = unsafeVec (catalan bS bS) $ streamRI catIxs <$$>
				\ (b, ix) -> (ix, let i = bS * b in rmAlgo (runSliceMin sM i) (if b == mm then lastBS else bS))
-- 		rmAlgo = N2.rangeMin
		!rmAlgo = if bS <= 8 then N2.rangeMin else Nlogn.rangeMin