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

import Data.Bool
import Data.Eq (Eq(..))
import Data.Int (Int)
import Data.List ((++), foldr, length, splitAt, tail)
import Data.Ord (Ord(..))
import Prelude (Integer, Integral(..), Num(..), error, undefined)
import Text.Show (Show(..))

-- | @bitSize n@ retourne le nombre de bits servant à encoder 'n'.
bitSize :: Integer -> Int
bitSize 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

-- | @interleaveBits bs@ retourne les bits de @bs@
-- en consommant un bit de chaque liste à chaque passe.
interleaveBits :: [[Bool]] -> [Bool]
interleaveBits [] = []
interleaveBits bss =
	let (hs,ts) = unzip bss in
	hs ++ interleaveBits ts
	where
	unzip = foldr (\bits ~(hs,ts) ->
		case bits of
		 [] -> (hs,ts)
		 b:bs -> (b:hs,bs:ts)
	 ) ([], [])

-- | @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      = bitSize (n - 1)