module Utils
 ( module Test.Tasty
 , module Data.Bool
 , Applicative(..)
 , Monad(..), forM, replicateM, unless, when
 , Eq(..)
 , Either(..), either, isLeft, isRight
 , ($), (.), id, const, flip
 , (<$>)
 , Int
 , Maybe(..)
 , Monoid(..), Semigroup(..)
 , Ord(..)
 , String
 , Text
 , Word8
 , Num, Fractional(..), Integral(..), Integer, fromIntegral
 , Show(..)
 , MonadTrans(..)
 , ExceptT
 , runExcept
 , throwE
 , StateT
 , evalStateT
 , mkStdGen
 , debug
 , nCk
 , combinOfRank
 ) where

import Control.Applicative (Applicative(..))
import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.Except
import Control.Monad.Trans.State.Strict
import Data.Bool
import Data.Either (Either(..), either, isLeft, isRight)
import Data.Eq (Eq(..))
import Data.Function
import Data.Functor ((<$>))
import Data.Int (Int)
import Data.Maybe (Maybe(..))
import Data.Monoid (Monoid(..))
import Data.Ord (Ord(..))
import Data.Semigroup (Semigroup(..))
import Data.String (String)
import Data.Text (Text)
import Data.Word (Word8)
import Debug.Trace
import Prelude (Num(..), Fractional(..), Integral(..), Integer, undefined, fromIntegral)
import System.Random (mkStdGen)
import Test.Tasty
import Text.Show (Show(..))

debug msg x = trace (msg<>": "<>show x) x

-- | @'nCk' n k@ returns the number of combinations
-- of size 'k' from a set of size 'n'.
--
-- Computed using the formula:
-- @'nCk' n (k+1) == 'nCk' n (k-1) * (n-k+1) / k@
nCk :: Integral i => i -> i -> i
n`nCk`k | n<0||k<0||n<k = undefined
        | otherwise     = go 1 1
        where
        go i acc = if k' < i then acc else go (i+1) (acc * (n-i+1) `div` i)
        -- Use a symmetry to compute over smaller numbers,
        -- which is more efficient and safer
        k' = if n`div`2 < k then n-k else k

-- | @'combinOfRank' n k r@ returns the @r@-th combination
-- of @k@ elements from a set of @n@ elements.
-- DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.26
combinOfRank :: Integral i => i -> i -> i -> [i]
combinOfRank n k rk | rk<0||n`nCk`k<rk = undefined
                    | otherwise = for1K 1 1 rk
	where
	for1K i j r | i <  k    = uptoRank i j r
	            | i == k    = [j+r] -- because when i == k, nbCombs is always 1
	            | otherwise = []
	uptoRank i j r | nbCombs <- (n-j)`nCk`(k-i)
	               , nbCombs <= r = uptoRank i (j+1) (r-nbCombs)
	               | otherwise    = j : for1K (i+1) (j+1) r