EuclideanTests.hs

-- |
-- Module:      Math.NumberTheory.EuclideanTests
-- Copyright:   (c) 2016 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Tests for Math.NumberTheory.Euclidean.Coprimes
--

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications    #-}

{-# OPTIONS_GHC -fno-warn-type-defaults  #-}
{-# OPTIONS_GHC -fno-warn-unused-imports #-}

module Math.NumberTheory.EuclideanTests
  ( testSuite
  ) where

import Prelude hiding (gcd)
import Test.Tasty
import Test.Tasty.HUnit
import Test.Tasty.QuickCheck as QC hiding (Positive(..), NonZero(..))

import Control.Arrow
import Data.Bits
import Data.Euclidean
import Data.Maybe
import Data.Semigroup
import Data.List (tails, sort)
import Numeric.Natural

import Math.NumberTheory.Euclidean.Coprimes
import Math.NumberTheory.Quadratic.GaussianIntegers
import Math.NumberTheory.TestUtils

-- | Check that numbers are coprime iff their gcd equals to 1.
coprimeProperty :: (Eq a, Num a, GcdDomain a, Euclidean a) => AnySign a -> AnySign a -> Bool
coprimeProperty (AnySign a) (AnySign b) = coprime a b == (gcd a b == 1)

splitIntoCoprimesProperty1
  :: (Eq a, Num a, GcdDomain a)
  => [(a, Power Word)]
  -> Bool
splitIntoCoprimesProperty1 fs' = factorback fs == factorback (unCoprimes $ splitIntoCoprimes fs)
  where
    fs = map (second getPower) fs'
    factorback = abs . product . map (uncurry (^))

splitIntoCoprimesProperty2
  :: (Eq a, Num a, GcdDomain a)
  => [(NonZero a, Power Word)]
  -> Bool
splitIntoCoprimesProperty2 fs' = multiplicities fs <= multiplicities (unCoprimes $ splitIntoCoprimes fs)
  where
    fs = map (getNonZero *** getPower) fs'
    multiplicities = sum . map snd . filter ((/= 1) . abs . fst)

splitIntoCoprimesProperty3
  :: (Eq a, Num a, GcdDomain a)
  => [(a, Power Word)]
  -> Bool
splitIntoCoprimesProperty3 fs' = and [ coprime x y | (x : xs) <- tails fs, y <- xs ]
  where
    fs = map fst $ unCoprimes $ splitIntoCoprimes $ map (second getPower) fs'

-- | Check that evaluation never freezes.
splitIntoCoprimesProperty4
  :: (Eq a, Num a, GcdDomain a)
  => [(a, Word)]
  -> Bool
splitIntoCoprimesProperty4 fs' = fs == fs
  where
    fs = splitIntoCoprimes fs'

splitIntoCoprimesProperty5
  :: (Eq a, Num a, GcdDomain a)
  => [(a, Word)]
  -> Bool
splitIntoCoprimesProperty5 =
  all ((/= 1) . abs . fst) . unCoprimes . splitIntoCoprimes

-- | This is an undefined behaviour, but at least it should not
-- throw exceptions or loop forever.
splitIntoCoprimesSpecialCase1 :: Assertion
splitIntoCoprimesSpecialCase1 =
  assertBool "should not fail" $ splitIntoCoprimesProperty4 @Integer [(0, 0), (0, 0)]

-- | This is an undefined behaviour, but at least it should not
-- throw exceptions or loop forever.
splitIntoCoprimesSpecialCase2 :: Assertion
splitIntoCoprimesSpecialCase2 =
  assertBool "should not fail" $ splitIntoCoprimesProperty4 @Integer [(0, 1), (-2, 0)]

toListReturnsCorrectValues :: Assertion
toListReturnsCorrectValues = assertEqual
  "should be equal"
  (sort $ unCoprimes $ splitIntoCoprimes [(140, 1), (165, 1)])
  ([(5,2),(28,1),(33,1)] :: [(Integer, Word)])

unionReturnsCorrectValues :: Assertion
unionReturnsCorrectValues = assertEqual "should be equal" expected actual
  where
    a :: Coprimes Integer Word
    a = splitIntoCoprimes [(700, 1), (165, 1)] -- [(5,3),(28,1),(33,1)]
    b = splitIntoCoprimes [(360, 1), (210, 1)] -- [(2,4),(3,3),(5,2),(7,1)]
    expected = [(2,6),(3,4),(5,5),(7,2),(11,1)]
    actual = sort $ unCoprimes (a <> b)

insertReturnsCorrectValuesWhenCoprimeBase :: Assertion
insertReturnsCorrectValuesWhenCoprimeBase =
  let a = insert 5 2 (singleton 4 3)
      expected = [(4,3), (5,2)]
      actual = sort $ unCoprimes a :: [(Int, Int)]
  in assertEqual "should be equal" expected actual

insertReturnsCorrectValuesWhenNotCoprimeBase :: Assertion
insertReturnsCorrectValuesWhenNotCoprimeBase =
  let a = insert 2 4 (insert 7 1 (insert 5 2 (singleton 4 3)))
      actual = sort $ unCoprimes a :: [(Int, Int)]
      expected = [(2,10), (5,2), (7,1)]
  in assertEqual "should be equal" expected actual

unionProperty1
  :: (Ord a, GcdDomain a)
  => [(a, Power Word)]
  -> [(a, Power Word)]
  -> Bool
unionProperty1 xs ys
  =  sort (unCoprimes (splitIntoCoprimes (xs' <> ys')))
  == sort (unCoprimes (splitIntoCoprimes xs' <> splitIntoCoprimes ys'))
  where
    xs' = map (second getPower) xs
    ys' = map (second getPower) ys

testSuite :: TestTree
testSuite = testGroup "Euclidean"
  [ testSameIntegralProperty "coprime"     coprimeProperty
  , testGroup "splitIntoCoprimes"
    [ testGroup "preserves product of factors"
      [ testSmallAndQuick "Natural" (splitIntoCoprimesProperty1 @Natural)
      , testSmallAndQuick "Integer" (splitIntoCoprimesProperty1 @Integer)
      , testSmallAndQuick "Gaussian" (splitIntoCoprimesProperty1 @GaussianInteger)
      ]
    , testGroup "number of factors is non-decreasing"
      [ testSmallAndQuick "Natural" (splitIntoCoprimesProperty2 @Natural)
      , testSmallAndQuick "Integer" (splitIntoCoprimesProperty2 @Integer)
      , testSmallAndQuick "Gaussian" (splitIntoCoprimesProperty2 @GaussianInteger)
      ]
    , testGroup "output factors are coprime"
      [ testSmallAndQuick "Natural" (splitIntoCoprimesProperty3 @Natural)
      , testSmallAndQuick "Integer" (splitIntoCoprimesProperty3 @Integer)
      , testSmallAndQuick "Gaussian" (splitIntoCoprimesProperty3 @GaussianInteger)
      ]
    , testGroup "does not freeze"
      [ testCase          "case 1"                   splitIntoCoprimesSpecialCase1
      , testCase          "case 2"                   splitIntoCoprimesSpecialCase2
      , testSmallAndQuick "Natural" (splitIntoCoprimesProperty4 @Natural)
      -- smallcheck for Integer and GaussianInteger takes too long
      , QC.testProperty "Integer" (splitIntoCoprimesProperty4 @Integer)
      , QC.testProperty "Gaussian" (splitIntoCoprimesProperty4 @GaussianInteger)
      ]
    , testGroup "output factors are non-unit"
      [ testSmallAndQuick "Natural" (splitIntoCoprimesProperty5 @Natural)
      -- smallcheck for Integer and GaussianInteger takes too long
      , QC.testProperty "Integer" (splitIntoCoprimesProperty5 @Integer)
      , QC.testProperty "Gaussian" (splitIntoCoprimesProperty5 @GaussianInteger)
      ]
    ]
  , testGroup "Coprimes"
    [  testCase         "test equality"                       toListReturnsCorrectValues
    ,  testCase         "test union"                          unionReturnsCorrectValues
    ,  testCase         "test insert with coprime base"       insertReturnsCorrectValuesWhenCoprimeBase
    ,  testCase         "test insert with non-coprime base"   insertReturnsCorrectValuesWhenNotCoprimeBase
    ,  testGroup "property union"
      [ testSmallAndQuick "Natural" (unionProperty1 @Natural)
      -- smallcheck for Integer takes too long
      , QC.testProperty "Integer" (unionProperty1 @Integer)
      ]
    ]
  ]