hjugement-protocol/tests/Utils.hs

   1 module Utils
   2  ( module Test.Tasty
   3  , module Data.Bool
   4  , module Voting.Protocol.Utils
   5  , Applicative(..)
   6  , Monad(..), forM, mapM, replicateM, unless, when
   7  , Eq(..)
   8  , Either(..), either, isLeft, isRight
   9  , ($), (.), id, const, flip
  10  , (<$>)
  11  , Int
  12  , Maybe(..)
  13  , Monoid(..), Semigroup(..)
  14  , Ord(..)
  15  , String
  16  , Text
  17  , Word8
  18  , Num, Fractional(..), Integral(..), Integer, fromIntegral
  19  , Show(..)
  20  , MonadTrans(..)
  21  , ExceptT
  22  , runExcept
  23  , throwE
  24  , StateT(..)
  25  , evalStateT
  26  , modify'
  27  , mkStdGen
  28  , debug
  29  , nCk
  30  , combinOfRank
  31  ) where
  32
  33 import Control.Applicative (Applicative(..))
  34 import Control.Monad
  35 import Control.Monad.Trans.Class
  36 import Control.Monad.Trans.Except
  37 import Control.Monad.Trans.State.Strict
  38 import Data.Bool
  39 import Data.Either (Either(..), either, isLeft, isRight)
  40 import Data.Eq (Eq(..))
  41 import Data.Function
  42 import Data.Functor ((<$>))
  43 import Data.Int (Int)
  44 import Data.Maybe (Maybe(..))
  45 import Data.Monoid (Monoid(..))
  46 import Data.Ord (Ord(..))
  47 import Data.Semigroup (Semigroup(..))
  48 import Data.String (String)
  49 import Data.Text (Text)
  50 import Data.Word (Word8)
  51 import Debug.Trace
  52 import Prelude (Num(..), Fractional(..), Integral(..), Integer, undefined, fromIntegral)
  53 import System.Random (mkStdGen)
  54 import Test.Tasty
  55 import Text.Show (Show(..))
  56
  57 import Voting.Protocol.Utils
  58
  59 debug msg x = trace (msg<>": "<>show x) x
  60
  61 -- | @'nCk' n k@ returns the number of combinations
  62 -- of size 'k' from a set of size 'n'.
  63 --
  64 -- Computed using the formula:
  65 -- @'nCk' n (k+1) == 'nCk' n (k-1) * (n-k+1) / k@
  66 nCk :: Integral i => i -> i -> i
  67 n`nCk`k | n<0||k<0||n<k = undefined
  68         | otherwise     = go 1 1
  69         where
  70         go i acc = if k' < i then acc else go (i+1) (acc * (n-i+1) `div` i)
  71         -- Use a symmetry to compute over smaller numbers,
  72         -- which is more efficient and safer
  73         k' = if n`div`2 < k then n-k else k
  74
  75 -- | @'combinOfRank' n k r@ returns the @r@-th combination
  76 -- of @k@ elements from a set of @n@ elements.
  77 -- DOC: <http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf>, p.26
  78 combinOfRank :: Integral i => i -> i -> i -> [i]
  79 combinOfRank n k rk | rk<0||n`nCk`k<rk = undefined
  80                     | otherwise = for1K 1 1 rk
  81         where
  82         for1K i j r | i <  k    = uptoRank i j r
  83                     | i == k    = [j+r] -- because when i == k, nbCombs is always 1
  84                     | otherwise = []
  85         uptoRank i j r | nbCombs <- (n-j)`nCk`(k-i)
  86                        , nbCombs <= r = uptoRank i (j+1) (r-nbCombs)
  87                        | otherwise    = j : for1K (i+1) (j+1) r