module Jikka.Common.ModInt
  ( ModInt,
    toModInt,
    fromModInt,
    moduloOfModInt,
  )
where

import Data.Monoid

data ModInt = ModInt Integer (Maybe Integer)
  deriving (ModInt -> ModInt -> Bool
(ModInt -> ModInt -> Bool)
-> (ModInt -> ModInt -> Bool) -> Eq ModInt
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ModInt -> ModInt -> Bool
$c/= :: ModInt -> ModInt -> Bool
== :: ModInt -> ModInt -> Bool
$c== :: ModInt -> ModInt -> Bool
Eq, Eq ModInt
Eq ModInt
-> (ModInt -> ModInt -> Ordering)
-> (ModInt -> ModInt -> Bool)
-> (ModInt -> ModInt -> Bool)
-> (ModInt -> ModInt -> Bool)
-> (ModInt -> ModInt -> Bool)
-> (ModInt -> ModInt -> ModInt)
-> (ModInt -> ModInt -> ModInt)
-> Ord ModInt
ModInt -> ModInt -> Bool
ModInt -> ModInt -> Ordering
ModInt -> ModInt -> ModInt
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: ModInt -> ModInt -> ModInt
$cmin :: ModInt -> ModInt -> ModInt
max :: ModInt -> ModInt -> ModInt
$cmax :: ModInt -> ModInt -> ModInt
>= :: ModInt -> ModInt -> Bool
$c>= :: ModInt -> ModInt -> Bool
> :: ModInt -> ModInt -> Bool
$c> :: ModInt -> ModInt -> Bool
<= :: ModInt -> ModInt -> Bool
$c<= :: ModInt -> ModInt -> Bool
< :: ModInt -> ModInt -> Bool
$c< :: ModInt -> ModInt -> Bool
compare :: ModInt -> ModInt -> Ordering
$ccompare :: ModInt -> ModInt -> Ordering
$cp1Ord :: Eq ModInt
Ord, ReadPrec [ModInt]
ReadPrec ModInt
Int -> ReadS ModInt
ReadS [ModInt]
(Int -> ReadS ModInt)
-> ReadS [ModInt]
-> ReadPrec ModInt
-> ReadPrec [ModInt]
-> Read ModInt
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [ModInt]
$creadListPrec :: ReadPrec [ModInt]
readPrec :: ReadPrec ModInt
$creadPrec :: ReadPrec ModInt
readList :: ReadS [ModInt]
$creadList :: ReadS [ModInt]
readsPrec :: Int -> ReadS ModInt
$creadsPrec :: Int -> ReadS ModInt
Read, Int -> ModInt -> ShowS
[ModInt] -> ShowS
ModInt -> String
(Int -> ModInt -> ShowS)
-> (ModInt -> String) -> ([ModInt] -> ShowS) -> Show ModInt
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ModInt] -> ShowS
$cshowList :: [ModInt] -> ShowS
show :: ModInt -> String
$cshow :: ModInt -> String
showsPrec :: Int -> ModInt -> ShowS
$cshowsPrec :: Int -> ModInt -> ShowS
Show)

toModInt :: Integer -> Integer -> ModInt
toModInt :: Integer -> Integer -> ModInt
toModInt Integer
_ Integer
m | Integer
m Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = String -> ModInt
forall a. HasCallStack => String -> a
error (String -> ModInt) -> String -> ModInt
forall a b. (a -> b) -> a -> b
$ String
"Jikka.Common.ModInt.toModInt: modulo must be positive, but m = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
m
toModInt Integer
a Integer
m = Integer -> Maybe Integer -> ModInt
ModInt (Integer
a Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m) (Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
m)

fromModInt :: ModInt -> Integer
fromModInt :: ModInt -> Integer
fromModInt (ModInt Integer
a Maybe Integer
_) = Integer
a

moduloOfModInt :: ModInt -> Maybe Integer
moduloOfModInt :: ModInt -> Maybe Integer
moduloOfModInt (ModInt Integer
_ Maybe Integer
m) = Maybe Integer
m

instance Num ModInt where
  ModInt Integer
_ (Just Integer
m1) + :: ModInt -> ModInt -> ModInt
+ ModInt Integer
_ (Just Integer
m2) | Integer
m1 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
m2 = String -> ModInt
forall a. HasCallStack => String -> a
error (String -> ModInt) -> String -> ModInt
forall a b. (a -> b) -> a -> b
$ String
"Jikka.Common.ModInt.(+): modulo must be the same, but m1 = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
m1 String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" and m2 = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
m2
  ModInt Integer
a Maybe Integer
m1 + ModInt Integer
b Maybe Integer
m2 = case First Integer -> Maybe Integer
forall a. First a -> Maybe a
getFirst (Maybe Integer -> First Integer
forall a. Maybe a -> First a
First Maybe Integer
m1 First Integer -> First Integer -> First Integer
forall a. Semigroup a => a -> a -> a
<> Maybe Integer -> First Integer
forall a. Maybe a -> First a
First Maybe Integer
m2) of
    Maybe Integer
Nothing -> Integer -> Maybe Integer -> ModInt
ModInt (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
b) Maybe Integer
forall a. Maybe a
Nothing
    Just Integer
m -> Integer -> Maybe Integer -> ModInt
ModInt (let c :: Integer
c = Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
b in if Integer
c Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
m then Integer
c Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
m else Integer
c) (Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
m)
  ModInt Integer
_ (Just Integer
m1) * :: ModInt -> ModInt -> ModInt
* ModInt Integer
_ (Just Integer
m2) | Integer
m1 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
m2 = String -> ModInt
forall a. HasCallStack => String -> a
error (String -> ModInt) -> String -> ModInt
forall a b. (a -> b) -> a -> b
$ String
"Jikka.Common.ModInt.(*): modulo must be the same, but m1 = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
m1 String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" and m2 = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
m2
  ModInt Integer
a Maybe Integer
m1 * ModInt Integer
b Maybe Integer
m2 = case First Integer -> Maybe Integer
forall a. First a -> Maybe a
getFirst (Maybe Integer -> First Integer
forall a. Maybe a -> First a
First Maybe Integer
m1 First Integer -> First Integer -> First Integer
forall a. Semigroup a => a -> a -> a
<> Maybe Integer -> First Integer
forall a. Maybe a -> First a
First Maybe Integer
m2) of
    Maybe Integer
Nothing -> Integer -> Maybe Integer -> ModInt
ModInt (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
b) Maybe Integer
forall a. Maybe a
Nothing
    Just Integer
m -> Integer -> Maybe Integer -> ModInt
ModInt ((Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
b) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m) (Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
m)
  abs :: ModInt -> ModInt
abs = String -> ModInt -> ModInt
forall a. HasCallStack => String -> a
error String
"Jikka.Common.ModInt.fromInteger: cannot call abs for modint"
  signum :: ModInt -> ModInt
signum = String -> ModInt -> ModInt
forall a. HasCallStack => String -> a
error String
"Jikka.Common.ModInt.fromInteger: cannot signum for modint"
  fromInteger :: Integer -> ModInt
fromInteger Integer
a = Integer -> Maybe Integer -> ModInt
ModInt Integer
a Maybe Integer
forall a. Maybe a
Nothing
  negate :: ModInt -> ModInt
negate (ModInt Integer
a Maybe Integer
m) = case Maybe Integer
m of
    Maybe Integer
Nothing -> Integer -> Maybe Integer -> ModInt
ModInt (- Integer
a) Maybe Integer
m
    Just Integer
m -> Integer -> Maybe Integer -> ModInt
ModInt (if Integer
a Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 then Integer
0 else Integer
m Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
a) (Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
m)