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