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

-- | @nbBits n@ retourne le nombre de bits servant à encoder 'n'.
nbBits :: Integer -> Int
nbBits n | 0<=n      = go n
         | otherwise = undefined
         where go 0 = 0
               go i = 1 + go (i`div`2)

-- | @integerOfBits bs@ retourne le nombre encodé par les bits 'bs'.
integerOfBits :: [Bool] -> Integer
integerOfBits []     = 0
integerOfBits (b:bs) = integerOfBits bs * 2 + (if b then 1 else 0)

-- | @bitsOfInteger m n@ retourne les 'm' premiers bits de poids faible
-- encodant le nombre 'n'.
bitsOfInteger :: Int -> Integer -> [Bool]
bitsOfInteger m n | 0<=m,0<=n = go m n
                  | otherwise = undefined
                  where go 0 _ = []
                        go i j = (r==1) : go (i-1) q
                               where (q,r) = j`divMod`2

-- | @randomIntOfBits n bs@ retourne le premier entier 'i' formé par les bits 'bs'
-- qui a le potentiel d’atteindre un entier dans @[0..n-1]@,
-- ou recommence en ignorant le premier bit si @n < i@.
randomIntegerOfBits :: Integer -> [Bool] -> Integer
randomIntegerOfBits n bs | given < enough = error (show (enough - given) ++ " bits missing")
                         | n < i          = randomIntegerOfBits n (tail bits ++ bs')
                         | otherwise      = i
	where (bits, bs') = splitAt enough bs
	      i           = integerOfBits bits
	      given       = length bits
	      enough      = nbBits n