-- |
-- Module:      Math.NumberTheory.Primes.IntSet
-- Copyright:   (c) 2020 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- A newtype wrapper around 'IntSet'.
--
-- This module is intended to be imported qualified, e. g.,
--
-- > import Math.NumberTheory.Primes.IntSet (PrimeIntSet)
-- > import qualified Math.NumberTheory.Primes.IntSet as PrimeIntSet
--

{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DeriveDataTypeable         #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeFamilies               #-}

module Math.NumberTheory.Primes.IntSet
  ( -- * Set type
    PrimeIntSet
  , unPrimeIntSet
  -- * Construction
  -- | Use 'Data.Monoid.mempty' to create an empty set.
  , singleton
  , fromList
  , fromAscList
  , fromDistinctAscList
  -- * Insertion
  , insert
  -- * Deletion
  , delete
  -- * Query
  , member
  , notMember
  , lookupEQ
  , lookupLT
  , lookupGT
  , lookupLE
  , lookupGE
  , null
  , size
  , isSubsetOf
  , isProperSubsetOf
  , disjoint
  -- * Combine
  -- | Use 'Data.Semigroup.<>' for unions.
  , difference
  , (\\)
  , symmetricDifference
  , intersection
  -- * Filter
  , filter
  , partition
  , split
  , splitMember
  , splitLookupEQ
  , splitRoot
  -- * Folds
  , foldr
  , foldl
  , foldr'
  , foldl'
  -- * Min/Max
  , deleteMin
  , deleteMax
  , minView
  , maxView
  -- * Conversion
  , toAscList
  , toDescList
  ) where

import Prelude ((>), (/=), (==), (-), Eq, Ord, Show, Monoid, Bool, Maybe(..), Int, Word, otherwise)
import Control.DeepSeq (NFData)
import Data.Coerce (coerce)
import Data.Data (Data)
import Data.Function (on)
import Data.IntSet (IntSet)
import qualified Data.IntSet.Internal as IS
import Data.Semigroup (Semigroup)
import qualified GHC.Exts (IsList(..))

import Math.NumberTheory.Primes.Types (Prime(..))
import Math.NumberTheory.Utils.FromIntegral (wordToInt, intToWord)
import Data.Bits (Bits(..))
import Utils.Containers.Internal.BitUtil (highestBitMask)

-- | A set of 'Prime' integers.
newtype PrimeIntSet = PrimeIntSet {
  -- | Convert to a set of integers.
  PrimeIntSet -> IntSet
unPrimeIntSet :: IntSet
  }
  deriving (PrimeIntSet -> PrimeIntSet -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PrimeIntSet -> PrimeIntSet -> Bool
$c/= :: PrimeIntSet -> PrimeIntSet -> Bool
== :: PrimeIntSet -> PrimeIntSet -> Bool
$c== :: PrimeIntSet -> PrimeIntSet -> Bool
Eq, Eq PrimeIntSet
PrimeIntSet -> PrimeIntSet -> Bool
PrimeIntSet -> PrimeIntSet -> Ordering
PrimeIntSet -> PrimeIntSet -> PrimeIntSet
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 :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
$cmin :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
max :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
$cmax :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
>= :: PrimeIntSet -> PrimeIntSet -> Bool
$c>= :: PrimeIntSet -> PrimeIntSet -> Bool
> :: PrimeIntSet -> PrimeIntSet -> Bool
$c> :: PrimeIntSet -> PrimeIntSet -> Bool
<= :: PrimeIntSet -> PrimeIntSet -> Bool
$c<= :: PrimeIntSet -> PrimeIntSet -> Bool
< :: PrimeIntSet -> PrimeIntSet -> Bool
$c< :: PrimeIntSet -> PrimeIntSet -> Bool
compare :: PrimeIntSet -> PrimeIntSet -> Ordering
$ccompare :: PrimeIntSet -> PrimeIntSet -> Ordering
Ord, Typeable PrimeIntSet
PrimeIntSet -> DataType
PrimeIntSet -> Constr
(forall b. Data b => b -> b) -> PrimeIntSet -> PrimeIntSet
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> PrimeIntSet -> u
forall u. (forall d. Data d => d -> u) -> PrimeIntSet -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PrimeIntSet -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PrimeIntSet -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PrimeIntSet
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PrimeIntSet -> c PrimeIntSet
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PrimeIntSet)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c PrimeIntSet)
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
$cgmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
$cgmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
$cgmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PrimeIntSet -> u
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PrimeIntSet -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> PrimeIntSet -> [u]
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> PrimeIntSet -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PrimeIntSet -> r
$cgmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> PrimeIntSet -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PrimeIntSet -> r
$cgmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> PrimeIntSet -> r
gmapT :: (forall b. Data b => b -> b) -> PrimeIntSet -> PrimeIntSet
$cgmapT :: (forall b. Data b => b -> b) -> PrimeIntSet -> PrimeIntSet
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c PrimeIntSet)
$cdataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c PrimeIntSet)
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PrimeIntSet)
$cdataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c PrimeIntSet)
dataTypeOf :: PrimeIntSet -> DataType
$cdataTypeOf :: PrimeIntSet -> DataType
toConstr :: PrimeIntSet -> Constr
$ctoConstr :: PrimeIntSet -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PrimeIntSet
$cgunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c PrimeIntSet
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PrimeIntSet -> c PrimeIntSet
$cgfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PrimeIntSet -> c PrimeIntSet
Data, Int -> PrimeIntSet -> ShowS
[PrimeIntSet] -> ShowS
PrimeIntSet -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PrimeIntSet] -> ShowS
$cshowList :: [PrimeIntSet] -> ShowS
show :: PrimeIntSet -> String
$cshow :: PrimeIntSet -> String
showsPrec :: Int -> PrimeIntSet -> ShowS
$cshowsPrec :: Int -> PrimeIntSet -> ShowS
Show, NonEmpty PrimeIntSet -> PrimeIntSet
PrimeIntSet -> PrimeIntSet -> PrimeIntSet
forall b. Integral b => b -> PrimeIntSet -> PrimeIntSet
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
stimes :: forall b. Integral b => b -> PrimeIntSet -> PrimeIntSet
$cstimes :: forall b. Integral b => b -> PrimeIntSet -> PrimeIntSet
sconcat :: NonEmpty PrimeIntSet -> PrimeIntSet
$csconcat :: NonEmpty PrimeIntSet -> PrimeIntSet
<> :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
$c<> :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
Semigroup, Semigroup PrimeIntSet
PrimeIntSet
[PrimeIntSet] -> PrimeIntSet
PrimeIntSet -> PrimeIntSet -> PrimeIntSet
forall a.
Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
mconcat :: [PrimeIntSet] -> PrimeIntSet
$cmconcat :: [PrimeIntSet] -> PrimeIntSet
mappend :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
$cmappend :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
mempty :: PrimeIntSet
$cmempty :: PrimeIntSet
Monoid, PrimeIntSet -> ()
forall a. (a -> ()) -> NFData a
rnf :: PrimeIntSet -> ()
$crnf :: PrimeIntSet -> ()
NFData)

instance GHC.Exts.IsList PrimeIntSet where
  type Item PrimeIntSet = Prime Int
  fromList :: [Item PrimeIntSet] -> PrimeIntSet
fromList = coerce :: forall a b. Coercible a b => a -> b
coerce [Int] -> IntSet
IS.fromList
  toList :: PrimeIntSet -> [Item PrimeIntSet]
toList = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> [Int]
IS.toList

-- | Build a singleton set.
singleton :: Prime Int -> PrimeIntSet
singleton :: Prime Int -> PrimeIntSet
singleton = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet
IS.singleton

-- | Build a set from a list of primes.
fromList :: [Prime Int] -> PrimeIntSet
fromList :: [Prime Int] -> PrimeIntSet
fromList = coerce :: forall a b. Coercible a b => a -> b
coerce [Int] -> IntSet
IS.fromList

-- | Build a set from an ascending list of primes
-- (the precondition is not checked).
fromAscList :: [Prime Int] -> PrimeIntSet
fromAscList :: [Prime Int] -> PrimeIntSet
fromAscList = coerce :: forall a b. Coercible a b => a -> b
coerce [Int] -> IntSet
IS.fromAscList

-- | Build a set from an ascending list of distinct primes
-- (the precondition is not checked).
fromDistinctAscList :: [Prime Int] -> PrimeIntSet
fromDistinctAscList :: [Prime Int] -> PrimeIntSet
fromDistinctAscList = coerce :: forall a b. Coercible a b => a -> b
coerce [Int] -> IntSet
IS.fromDistinctAscList

-- | Insert a prime into the set.
insert :: Prime Int -> PrimeIntSet -> PrimeIntSet
insert :: Prime Int -> PrimeIntSet -> PrimeIntSet
insert = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> IntSet
IS.insert

-- | Delete an integer from the set.
delete :: Int -> PrimeIntSet -> PrimeIntSet
delete :: Int -> PrimeIntSet -> PrimeIntSet
delete = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> IntSet
IS.delete

-- | Check whether the given prime is a member of the set.
member :: Prime Int -> PrimeIntSet -> Bool
member :: Prime Int -> PrimeIntSet -> Bool
member = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> Bool
IS.member

-- | Check whether the given prime is not a member of the set.
notMember :: Prime Int -> PrimeIntSet -> Bool
notMember :: Prime Int -> PrimeIntSet -> Bool
notMember = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> Bool
IS.notMember

-- | Find a prime in the set,
-- equal to the given integer, if any exists.
lookupEQ :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupEQ :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupEQ Int
x PrimeIntSet
xs
  | coerce :: forall a b. Coercible a b => a -> b
coerce Prime Int -> PrimeIntSet -> Bool
member Int
x PrimeIntSet
xs = forall a. a -> Maybe a
Just (forall a. a -> Prime a
Prime Int
x)
  | Bool
otherwise          = forall a. Maybe a
Nothing

-- | Find the largest prime in the set,
-- smaller than the given integer, if any exists.
lookupLT :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupLT :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupLT = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> Maybe Int
IS.lookupLT

-- | Find the smallest prime in the set,
-- greater than the given integer, if any exists.
lookupGT :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupGT :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupGT = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> Maybe Int
IS.lookupGT

-- | Find the largest prime in the set,
-- smaller or equal to the given integer, if any exists.
lookupLE :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupLE :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupLE = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> Maybe Int
IS.lookupLE

-- | Find the smallest prime in the set,
-- greater or equal to the given integer, if any exists.
lookupGE :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupGE :: Int -> PrimeIntSet -> Maybe (Prime Int)
lookupGE = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> Maybe Int
IS.lookupGE

-- | Check whether the set is empty.
null :: PrimeIntSet -> Bool
null :: PrimeIntSet -> Bool
null = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> Bool
IS.null

-- | Cardinality of the set.
size :: PrimeIntSet -> Int
size :: PrimeIntSet -> Int
size = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> Int
IS.size

-- | Check whether the first argument is a subset of the second one.
isSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool
isSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool
isSubsetOf = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet -> Bool
IS.isSubsetOf

-- | Check whether the first argument is a proper subset of the second one.
isProperSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool
isProperSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool
isProperSubsetOf = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet -> Bool
IS.isProperSubsetOf

#if MIN_VERSION_containers(0,5,11)
-- | Check whether two sets are disjoint.
disjoint :: PrimeIntSet -> PrimeIntSet -> Bool
disjoint :: PrimeIntSet -> PrimeIntSet -> Bool
disjoint = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet -> Bool
IS.disjoint
#else
-- | Check whether two sets are disjoint.
disjoint :: PrimeIntSet -> PrimeIntSet -> Bool
disjoint (PrimeIntSet x) (PrimeIntSet y) = IS.null (IS.intersection x y)
#endif

-- | Difference between a set of primes and a set of integers.
difference :: PrimeIntSet -> IntSet -> PrimeIntSet
difference :: PrimeIntSet -> IntSet -> PrimeIntSet
difference = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet -> IntSet
IS.difference

-- | An alias to 'difference'.
(\\) :: PrimeIntSet -> IntSet -> PrimeIntSet
\\ :: PrimeIntSet -> IntSet -> PrimeIntSet
(\\) = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet -> IntSet
(IS.\\)

infixl 9 \\{- -}

-- | Symmetric difference of two sets of primes.
symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
symmetricDifference = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet -> IntSet
symmDiff

-- | Intersection of a set of primes and a set of integers.
intersection :: PrimeIntSet -> IntSet -> PrimeIntSet
intersection :: PrimeIntSet -> IntSet -> PrimeIntSet
intersection = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet -> IntSet
IS.intersection

-- | Filter primes satisfying a predicate.
filter :: (Prime Int -> Bool) -> PrimeIntSet -> PrimeIntSet
filter :: (Prime Int -> Bool) -> PrimeIntSet -> PrimeIntSet
filter = coerce :: forall a b. Coercible a b => a -> b
coerce (Int -> Bool) -> IntSet -> IntSet
IS.filter

-- | Partition primes according to a predicate.
partition :: (Prime Int -> Bool) -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)
partition :: (Prime Int -> Bool) -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)
partition = coerce :: forall a b. Coercible a b => a -> b
coerce (Int -> Bool) -> IntSet -> (IntSet, IntSet)
IS.partition

-- | Split into primes strictly less and strictly greater
-- than the first argument.
split :: Int -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)
split :: Int -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)
split = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> (IntSet, IntSet)
IS.split

-- | Simultaneous 'split' and 'member'.
splitMember :: Prime Int -> PrimeIntSet -> (PrimeIntSet, Bool, PrimeIntSet)
splitMember :: Prime Int -> PrimeIntSet -> (PrimeIntSet, Bool, PrimeIntSet)
splitMember = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> (IntSet, Bool, IntSet)
IS.splitMember

-- | Simultaneous 'split' and 'lookupEQ'.
splitLookupEQ :: Int -> PrimeIntSet -> (PrimeIntSet, Maybe (Prime Int), PrimeIntSet)
splitLookupEQ :: Int -> PrimeIntSet -> (PrimeIntSet, Maybe (Prime Int), PrimeIntSet)
splitLookupEQ Int
x PrimeIntSet
xs = (PrimeIntSet
lt, if Bool
eq then forall a. a -> Maybe a
Just (forall a. a -> Prime a
Prime Int
x) else forall a. Maybe a
Nothing, PrimeIntSet
gt)
  where
    (PrimeIntSet
lt, Bool
eq, PrimeIntSet
gt) = coerce :: forall a b. Coercible a b => a -> b
coerce Int -> IntSet -> (IntSet, Bool, IntSet)
IS.splitMember Int
x PrimeIntSet
xs

-- | Decompose a set into pieces based on the structure of the underlying tree.
splitRoot :: PrimeIntSet -> [PrimeIntSet]
splitRoot :: PrimeIntSet -> [PrimeIntSet]
splitRoot = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> [IntSet]
IS.splitRoot

-- | Fold a set using the given right-associative operator.
foldr :: forall b. (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
foldr :: forall b. (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
foldr = coerce :: forall a b. Coercible a b => a -> b
coerce (forall b. (Int -> b -> b) -> b -> IntSet -> b
IS.foldr @b)

-- | Fold a set using the given left-associative operator.
foldl :: forall a. (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
foldl :: forall a. (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
foldl = coerce :: forall a b. Coercible a b => a -> b
coerce (forall a. (a -> Int -> a) -> a -> IntSet -> a
IS.foldl @a)

-- | A strict version of 'foldr'.
foldr' :: forall b. (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
foldr' :: forall b. (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
foldr' = coerce :: forall a b. Coercible a b => a -> b
coerce (forall b. (Int -> b -> b) -> b -> IntSet -> b
IS.foldr' @b)

-- | A strict version of 'foldl'.
foldl' :: forall a. (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
foldl' :: forall a. (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
foldl' = coerce :: forall a b. Coercible a b => a -> b
coerce (forall a. (a -> Int -> a) -> a -> IntSet -> a
IS.foldl' @a)

-- | Delete the smallest prime in the set.
deleteMin :: PrimeIntSet -> PrimeIntSet
deleteMin :: PrimeIntSet -> PrimeIntSet
deleteMin = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet
IS.deleteMin

-- | Delete the largest prime in the set.
deleteMax :: PrimeIntSet -> PrimeIntSet
deleteMax :: PrimeIntSet -> PrimeIntSet
deleteMax = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> IntSet
IS.deleteMax

-- | Split a set into the smallest prime and the rest, if non-empty.
minView :: PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)
minView :: PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)
minView = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> Maybe (Int, IntSet)
IS.minView

-- | Split a set into the largest prime and the rest, if non-empty.
maxView :: PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)
maxView :: PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)
maxView = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> Maybe (Int, IntSet)
IS.maxView

-- | Convert the set to a list of ascending primes.
toAscList :: PrimeIntSet -> [Prime Int]
toAscList :: PrimeIntSet -> [Prime Int]
toAscList = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> [Int]
IS.toAscList

-- | Convert the set to a list of descending primes.
toDescList :: PrimeIntSet -> [Prime Int]
toDescList :: PrimeIntSet -> [Prime Int]
toDescList = coerce :: forall a b. Coercible a b => a -> b
coerce IntSet -> [Int]
IS.toDescList

-------------------------------------------------------------------------------
-- IntSet helpers

-- | Symmetric difference of two sets.
-- Implementation is inspired by 'Data.IntSet.union'
-- and 'Data.IntSet.difference'.
symmDiff :: IntSet -> IntSet -> IntSet
symmDiff :: IntSet -> IntSet -> IntSet
symmDiff IntSet
t1 IntSet
t2 = case IntSet
t1 of
  IS.Bin Int
p1 Int
m1 IntSet
l1 IntSet
r1 -> case IntSet
t2 of
    IS.Bin Int
p2 Int
m2 IntSet
l2 IntSet
r2
      | Int -> Int -> Bool
shorter Int
m1 Int
m2 -> IntSet
symmDiff1
      | Int -> Int -> Bool
shorter Int
m2 Int
m1 -> IntSet
symmDiff2
      | Int
p1 forall a. Eq a => a -> a -> Bool
== Int
p2      -> Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p1 Int
m1 (IntSet -> IntSet -> IntSet
symmDiff IntSet
l1 IntSet
l2) (IntSet -> IntSet -> IntSet
symmDiff IntSet
r1 IntSet
r2)
      | Bool
otherwise     -> Int -> IntSet -> Int -> IntSet -> IntSet
link Int
p1 IntSet
t1 Int
p2 IntSet
t2
      where
        symmDiff1 :: IntSet
symmDiff1
          | Int -> Int -> Int
mask Int
p2 Int
m1 forall a. Eq a => a -> a -> Bool
/= Int
p1 = Int -> IntSet -> Int -> IntSet -> IntSet
link Int
p1 IntSet
t1 Int
p2 IntSet
t2
          | Int
p2 forall a. Bits a => a -> a -> a
.&. Int
m1 forall a. Eq a => a -> a -> Bool
== Int
0   = Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p1 Int
m1 (IntSet -> IntSet -> IntSet
symmDiff IntSet
l1 IntSet
t2) IntSet
r1
          | Bool
otherwise        = Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p1 Int
m1 IntSet
l1 (IntSet -> IntSet -> IntSet
symmDiff IntSet
r1 IntSet
t2)
        symmDiff2 :: IntSet
symmDiff2
          | Int -> Int -> Int
mask Int
p1 Int
m2 forall a. Eq a => a -> a -> Bool
/= Int
p2 = Int -> IntSet -> Int -> IntSet -> IntSet
link Int
p1 IntSet
t1 Int
p2 IntSet
t2
          | Int
p1 forall a. Bits a => a -> a -> a
.&. Int
m2 forall a. Eq a => a -> a -> Bool
== Int
0   = Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p2 Int
m2 (IntSet -> IntSet -> IntSet
symmDiff IntSet
t1 IntSet
l2) IntSet
r2
          | Bool
otherwise        = Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p2 Int
m2 IntSet
l2 (IntSet -> IntSet -> IntSet
symmDiff IntSet
t1 IntSet
r2)
    IS.Tip Int
kx Word
bm -> Int -> Word -> IntSet -> IntSet
symmDiffBM Int
kx Word
bm IntSet
t1
    IntSet
IS.Nil -> IntSet
t1
  IS.Tip Int
kx Word
bm -> Int -> Word -> IntSet -> IntSet
symmDiffBM Int
kx Word
bm IntSet
t2
  IntSet
IS.Nil -> IntSet
t2

shorter :: Int -> Int -> Bool
shorter :: Int -> Int -> Bool
shorter = forall a. Ord a => a -> a -> Bool
(>) forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Int -> Word
intToWord

symmDiffBM :: Int -> Word -> IntSet -> IntSet
symmDiffBM :: Int -> Word -> IntSet -> IntSet
symmDiffBM !Int
kx !Word
bm IntSet
t = case IntSet
t of
  IS.Bin Int
p Int
m IntSet
l IntSet
r
    | Int -> Int -> Int
mask Int
kx Int
m forall a. Eq a => a -> a -> Bool
/= Int
p -> Int -> IntSet -> Int -> IntSet -> IntSet
link Int
kx (Int -> Word -> IntSet
IS.Tip Int
kx Word
bm) Int
p IntSet
t
    | Int
kx forall a. Bits a => a -> a -> a
.&. Int
m forall a. Eq a => a -> a -> Bool
== Int
0  -> Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p Int
m (Int -> Word -> IntSet -> IntSet
symmDiffBM Int
kx Word
bm IntSet
l) IntSet
r
    | Bool
otherwise      -> Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p Int
m IntSet
l (Int -> Word -> IntSet -> IntSet
symmDiffBM Int
kx Word
bm IntSet
r)
  IS.Tip Int
kx' Word
bm'
    | Int
kx' forall a. Eq a => a -> a -> Bool
== Int
kx -> if Word
bm' forall a. Eq a => a -> a -> Bool
== Word
bm then IntSet
IS.Nil else Int -> Word -> IntSet
IS.Tip Int
kx (Word
bm' forall a. Bits a => a -> a -> a
`xor` Word
bm)
    | Bool
otherwise -> Int -> IntSet -> Int -> IntSet -> IntSet
link Int
kx (Int -> Word -> IntSet
IS.Tip Int
kx Word
bm) Int
kx' IntSet
t
  IntSet
IS.Nil -> Int -> Word -> IntSet
IS.Tip Int
kx Word
bm

link :: Int -> IntSet -> Int -> IntSet -> IntSet
link :: Int -> IntSet -> Int -> IntSet -> IntSet
link Int
p1 IntSet
t1 Int
p2 IntSet
t2
  | Int
p1 forall a. Bits a => a -> a -> a
.&. Int
m forall a. Eq a => a -> a -> Bool
== Int
0 = Int -> Int -> IntSet -> IntSet -> IntSet
IS.Bin Int
p Int
m IntSet
t1 IntSet
t2
  | Bool
otherwise     = Int -> Int -> IntSet -> IntSet -> IntSet
IS.Bin Int
p Int
m IntSet
t2 IntSet
t1
  where
    m :: Int
m = Word -> Int
wordToInt (Word -> Word
highestBitMask (Int -> Word
intToWord Int
p1 forall a. Bits a => a -> a -> a
`xor` Int -> Word
intToWord Int
p2))
    p :: Int
p = Int -> Int -> Int
mask Int
p1 Int
m
{-# INLINE link #-}

bin :: Int -> Int -> IntSet -> IntSet -> IntSet
bin :: Int -> Int -> IntSet -> IntSet -> IntSet
bin Int
p Int
m IntSet
l IntSet
r = case IntSet
r of
  IntSet
IS.Nil -> IntSet
l
  IntSet
_ -> case IntSet
l of
    IntSet
IS.Nil -> IntSet
r
    IntSet
_ -> Int -> Int -> IntSet -> IntSet -> IntSet
IS.Bin Int
p Int
m IntSet
l IntSet
r
{-# INLINE bin #-}

mask :: Int -> Int -> Int
mask :: Int -> Int -> Int
mask Int
i Int
m = Int
i forall a. Bits a => a -> a -> a
.&. (forall a. Bits a => a -> a
complement (Int
m forall a. Num a => a -> a -> a
- Int
1) forall a. Bits a => a -> a -> a
`xor` Int
m)
{-# INLINE mask #-}