-- | Manipulation de bits.
module Htirage.Bits where

import Data.Bits
import Data.List

import Htirage.Combinatorics

-- | @nbBits n@ retourne le nombre de bits servant à encoder 'n'.
nbBits :: FiniteBits i => i -> Int
nbBits n = finiteBitSize n - countLeadingZeros n

-- | @intOfBits bs@ retourne le nombre encodé par les bits 'bs'.
intOfBits :: (FiniteBits i, Num i) => [Bool] -> i
intOfBits bs = foldr (.|.) 0 (zipWith (\i b -> if b then bit i else 0) [0..] bs)

-- | @bitsOfInt m n@ retourne les 'm' premiers bits de poids faible encodant le nombre 'n'.
bitsOfInt :: FiniteBits i => Int -> i -> [Bool]
bitsOfInt m n = [testBit n i | i <- [0..m-1]]

-- | @equiprobableBits n@ retourne l’exposant
-- de la plus grande puissance de 2 inférieure ou égale 'n'.
equiprobableBits :: (FiniteBits i, Num i) => i -> Int
equiprobableBits n | n == 2 ^ b = b
                   | otherwise  = b - 1
                   where b = nbBits n

-- | @bitsOfComb n k c@ retourne des bits équiprobables donnés
-- par la combinaison 'c' obtenue par tirage équiprobable
-- d’une combinaison de 'k' entiers parmi @[1..n]@.
-- 
-- Pour que les bits retournés aient chacun
-- la même probabilité d’être à 'True' ou à 'False',
-- seulement les combinaisons de rang lexicographique inférieur ou égal
-- à la plus grande puissance de 2 inférieure ou égal à @k`combsIn`n@
-- sont considérées comme valides ; les autres donnant des doublons.
--
-- Dans le cas où survient une combinaison invalide,
-- aucun bit n’est extrait du tirage 'c'.
bitsOfComb :: (FiniteBits i, Integral i) => i -> i -> [i] -> [Bool]
bitsOfComb n k c =
	case rankOfComb n (sort c) of
	 r | nbBits r <= epBits -> epBits `bitsOfInt` r
	 _ -> []
	where epBits = equiprobableBits (n`nCk`k)