-- |
-- 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
(PrimeIntSet -> PrimeIntSet -> Bool)
-> (PrimeIntSet -> PrimeIntSet -> Bool) -> Eq PrimeIntSet
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
Eq PrimeIntSet
-> (PrimeIntSet -> PrimeIntSet -> Ordering)
-> (PrimeIntSet -> PrimeIntSet -> Bool)
-> (PrimeIntSet -> PrimeIntSet -> Bool)
-> (PrimeIntSet -> PrimeIntSet -> Bool)
-> (PrimeIntSet -> PrimeIntSet -> Bool)
-> (PrimeIntSet -> PrimeIntSet -> PrimeIntSet)
-> (PrimeIntSet -> PrimeIntSet -> PrimeIntSet)
-> Ord 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
$cp1Ord :: Eq PrimeIntSet
Ord, Typeable PrimeIntSet
DataType
Constr
Typeable PrimeIntSet
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> PrimeIntSet -> c PrimeIntSet)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c PrimeIntSet)
-> (PrimeIntSet -> Constr)
-> (PrimeIntSet -> DataType)
-> (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))
-> ((forall b. Data b => b -> b) -> PrimeIntSet -> PrimeIntSet)
-> (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 u. (forall d. Data d => d -> u) -> PrimeIntSet -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> PrimeIntSet -> u)
-> (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 (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> PrimeIntSet -> m PrimeIntSet)
-> Data PrimeIntSet
PrimeIntSet -> DataType
PrimeIntSet -> Constr
(forall b. Data b => b -> b) -> PrimeIntSet -> PrimeIntSet
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> PrimeIntSet -> c PrimeIntSet
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c 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)
$cPrimeIntSet :: Constr
$tPrimeIntSet :: DataType
gmapMo :: (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 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 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 :: Int -> (forall d. Data d => d -> u) -> PrimeIntSet -> u
$cgmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> PrimeIntSet -> u
gmapQ :: (forall d. Data d => d -> u) -> PrimeIntSet -> [u]
$cgmapQ :: forall u. (forall d. Data d => d -> u) -> PrimeIntSet -> [u]
gmapQr :: (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 :: (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 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 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 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 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
$cp1Data :: Typeable PrimeIntSet
Data, Int -> PrimeIntSet -> ShowS
[PrimeIntSet] -> ShowS
PrimeIntSet -> String
(Int -> PrimeIntSet -> ShowS)
-> (PrimeIntSet -> String)
-> ([PrimeIntSet] -> ShowS)
-> Show PrimeIntSet
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, b -> PrimeIntSet -> PrimeIntSet
NonEmpty PrimeIntSet -> PrimeIntSet
PrimeIntSet -> PrimeIntSet -> PrimeIntSet
(PrimeIntSet -> PrimeIntSet -> PrimeIntSet)
-> (NonEmpty PrimeIntSet -> PrimeIntSet)
-> (forall b. Integral b => b -> PrimeIntSet -> PrimeIntSet)
-> Semigroup 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 :: 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
Semigroup PrimeIntSet
-> PrimeIntSet
-> (PrimeIntSet -> PrimeIntSet -> PrimeIntSet)
-> ([PrimeIntSet] -> PrimeIntSet)
-> Monoid 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
$cp1Monoid :: Semigroup PrimeIntSet
Monoid, PrimeIntSet -> ()
(PrimeIntSet -> ()) -> NFData 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 = ([Int] -> IntSet) -> [Prime Int] -> PrimeIntSet
coerce [Int] -> IntSet
IS.fromList
  toList :: PrimeIntSet -> [Item PrimeIntSet]
toList = (IntSet -> [Int]) -> PrimeIntSet -> [Prime Int]
coerce IntSet -> [Int]
IS.toList

-- | Build a singleton set.
singleton :: Prime Int -> PrimeIntSet
singleton :: Prime Int -> PrimeIntSet
singleton = (Int -> IntSet) -> Prime Int -> PrimeIntSet
coerce Int -> IntSet
IS.singleton

-- | Build a set from a list of primes.
fromList :: [Prime Int] -> PrimeIntSet
fromList :: [Prime Int] -> PrimeIntSet
fromList = ([Int] -> IntSet) -> [Prime Int] -> PrimeIntSet
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 = ([Int] -> IntSet) -> [Prime Int] -> PrimeIntSet
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 = ([Int] -> IntSet) -> [Prime Int] -> PrimeIntSet
coerce [Int] -> IntSet
IS.fromDistinctAscList

-- | Insert a prime into the set.
insert :: Prime Int -> PrimeIntSet -> PrimeIntSet
insert :: Prime Int -> PrimeIntSet -> PrimeIntSet
insert = (Int -> IntSet -> IntSet)
-> Prime Int -> PrimeIntSet -> PrimeIntSet
coerce Int -> IntSet -> IntSet
IS.insert

-- | Delete an integer from the set.
delete :: Int -> PrimeIntSet -> PrimeIntSet
delete :: Int -> PrimeIntSet -> PrimeIntSet
delete = (Int -> IntSet -> IntSet) -> Int -> PrimeIntSet -> PrimeIntSet
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 = (Int -> IntSet -> Bool) -> Prime Int -> PrimeIntSet -> Bool
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 = (Int -> IntSet -> Bool) -> Prime Int -> PrimeIntSet -> Bool
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
  | (Prime Int -> PrimeIntSet -> Bool) -> Int -> PrimeIntSet -> Bool
coerce Prime Int -> PrimeIntSet -> Bool
member Int
x PrimeIntSet
xs = Prime Int -> Maybe (Prime Int)
forall a. a -> Maybe a
Just (Int -> Prime Int
forall a. a -> Prime a
Prime Int
x)
  | Bool
otherwise          = Maybe (Prime Int)
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 = (Int -> IntSet -> Maybe Int)
-> Int -> PrimeIntSet -> Maybe (Prime Int)
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 = (Int -> IntSet -> Maybe Int)
-> Int -> PrimeIntSet -> Maybe (Prime Int)
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 = (Int -> IntSet -> Maybe Int)
-> Int -> PrimeIntSet -> Maybe (Prime Int)
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 = (Int -> IntSet -> Maybe Int)
-> Int -> PrimeIntSet -> Maybe (Prime Int)
coerce Int -> IntSet -> Maybe Int
IS.lookupGE

-- | Check whether the set is empty.
null :: PrimeIntSet -> Bool
null :: PrimeIntSet -> Bool
null = (IntSet -> Bool) -> PrimeIntSet -> Bool
coerce IntSet -> Bool
IS.null

-- | Cardinality of the set.
size :: PrimeIntSet -> Int
size :: PrimeIntSet -> Int
size = (IntSet -> Int) -> PrimeIntSet -> Int
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 = (IntSet -> IntSet -> Bool) -> PrimeIntSet -> PrimeIntSet -> Bool
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 = (IntSet -> IntSet -> Bool) -> PrimeIntSet -> PrimeIntSet -> Bool
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 = (IntSet -> IntSet -> Bool) -> PrimeIntSet -> PrimeIntSet -> Bool
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 = (IntSet -> IntSet -> IntSet)
-> PrimeIntSet -> IntSet -> PrimeIntSet
coerce IntSet -> IntSet -> IntSet
IS.difference

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

infixl 9 \\{- -}

-- | Symmetric difference of two sets of primes.
symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
symmetricDifference = (IntSet -> IntSet -> IntSet)
-> PrimeIntSet -> PrimeIntSet -> PrimeIntSet
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 = (IntSet -> IntSet -> IntSet)
-> PrimeIntSet -> IntSet -> PrimeIntSet
coerce IntSet -> IntSet -> IntSet
IS.intersection

-- | Filter primes satisfying a predicate.
filter :: (Prime Int -> Bool) -> PrimeIntSet -> PrimeIntSet
filter :: (Prime Int -> Bool) -> PrimeIntSet -> PrimeIntSet
filter = ((Int -> Bool) -> IntSet -> IntSet)
-> (Prime Int -> Bool) -> PrimeIntSet -> PrimeIntSet
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 = ((Int -> Bool) -> IntSet -> (IntSet, IntSet))
-> (Prime Int -> Bool) -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)
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 = (Int -> IntSet -> (IntSet, IntSet))
-> Int -> PrimeIntSet -> (PrimeIntSet, PrimeIntSet)
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 = (Int -> IntSet -> (IntSet, Bool, IntSet))
-> Prime Int -> PrimeIntSet -> (PrimeIntSet, Bool, PrimeIntSet)
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 Prime Int -> Maybe (Prime Int)
forall a. a -> Maybe a
Just (Int -> Prime Int
forall a. a -> Prime a
Prime Int
x) else Maybe (Prime Int)
forall a. Maybe a
Nothing, PrimeIntSet
gt)
  where
    (PrimeIntSet
lt, Bool
eq, PrimeIntSet
gt) = (Int -> IntSet -> (IntSet, Bool, IntSet))
-> Int -> PrimeIntSet -> (PrimeIntSet, Bool, PrimeIntSet)
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 = (IntSet -> [IntSet]) -> PrimeIntSet -> [PrimeIntSet]
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 :: (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
foldr = ((Int -> b -> b) -> b -> IntSet -> b)
-> (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
coerce ((Int -> b -> b) -> b -> IntSet -> b
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 :: (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
foldl = ((a -> Int -> a) -> a -> IntSet -> a)
-> (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
coerce ((a -> Int -> a) -> a -> IntSet -> a
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' :: (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
foldr' = ((Int -> b -> b) -> b -> IntSet -> b)
-> (Prime Int -> b -> b) -> b -> PrimeIntSet -> b
coerce ((Int -> b -> b) -> b -> IntSet -> b
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' :: (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
foldl' = ((a -> Int -> a) -> a -> IntSet -> a)
-> (a -> Prime Int -> a) -> a -> PrimeIntSet -> a
coerce ((a -> Int -> a) -> a -> IntSet -> a
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 = (IntSet -> IntSet) -> PrimeIntSet -> PrimeIntSet
coerce IntSet -> IntSet
IS.deleteMin

-- | Delete the largest prime in the set.
deleteMax :: PrimeIntSet -> PrimeIntSet
deleteMax :: PrimeIntSet -> PrimeIntSet
deleteMax = (IntSet -> IntSet) -> PrimeIntSet -> PrimeIntSet
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 = (IntSet -> Maybe (Int, IntSet))
-> PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)
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 = (IntSet -> Maybe (Int, IntSet))
-> PrimeIntSet -> Maybe (Prime Int, PrimeIntSet)
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 = (IntSet -> [Int]) -> PrimeIntSet -> [Prime Int]
coerce IntSet -> [Int]
IS.toAscList

-- | Convert the set to a list of descending primes.
toDescList :: PrimeIntSet -> [Prime Int]
toDescList :: PrimeIntSet -> [Prime Int]
toDescList = (IntSet -> [Int]) -> PrimeIntSet -> [Prime Int]
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 Int -> Int -> Bool
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 Int -> Int -> Bool
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 Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
m1 Int -> Int -> Bool
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 Int -> Int -> Bool
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 Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
m2 Int -> Int -> Bool
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 BitMap
bm -> Int -> BitMap -> IntSet -> IntSet
symmDiffBM Int
kx BitMap
bm IntSet
t1
    IntSet
IS.Nil -> IntSet
t1
  IS.Tip Int
kx BitMap
bm -> Int -> BitMap -> IntSet -> IntSet
symmDiffBM Int
kx BitMap
bm IntSet
t2
  IntSet
IS.Nil -> IntSet
t2

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

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

link :: Int -> IntSet -> Int -> IntSet -> IntSet
link :: Int -> IntSet -> Int -> IntSet -> IntSet
link Int
p1 IntSet
t1 Int
p2 IntSet
t2
  | Int
p1 Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
m Int -> Int -> Bool
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 = BitMap -> Int
wordToInt (BitMap -> BitMap
highestBitMask (Int -> BitMap
intToWord Int
p1 BitMap -> BitMap -> BitMap
forall a. Bits a => a -> a -> a
`xor` Int -> BitMap
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 Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. (Int -> Int
forall a. Bits a => a -> a
complement (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> a -> a
`xor` Int
m)
{-# INLINE mask #-}