{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
module Math.NumberTheory.Primes.IntSet
(
PrimeIntSet
, unPrimeIntSet
, singleton
, fromList
, fromAscList
, fromDistinctAscList
, insert
, delete
, member
, notMember
, lookupEQ
, lookupLT
, lookupGT
, lookupLE
, lookupGE
, null
, size
, isSubsetOf
, isProperSubsetOf
, disjoint
, difference
, (\\)
, symmetricDifference
, intersection
, filter
, partition
, split
, splitMember
, splitLookupEQ
, splitRoot
, foldr
, foldl
, foldr'
, foldl'
, deleteMin
, deleteMax
, minView
, maxView
, 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)
newtype PrimeIntSet = PrimeIntSet {
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
singleton :: Prime Int -> PrimeIntSet
singleton :: Prime Int -> PrimeIntSet
singleton = (Int -> IntSet) -> Prime Int -> PrimeIntSet
coerce Int -> IntSet
IS.singleton
fromList :: [Prime Int] -> PrimeIntSet
fromList :: [Prime Int] -> PrimeIntSet
fromList = ([Int] -> IntSet) -> [Prime Int] -> PrimeIntSet
coerce [Int] -> IntSet
IS.fromList
fromAscList :: [Prime Int] -> PrimeIntSet
fromAscList :: [Prime Int] -> PrimeIntSet
fromAscList = ([Int] -> IntSet) -> [Prime Int] -> PrimeIntSet
coerce [Int] -> IntSet
IS.fromAscList
fromDistinctAscList :: [Prime Int] -> PrimeIntSet
fromDistinctAscList :: [Prime Int] -> PrimeIntSet
fromDistinctAscList = ([Int] -> IntSet) -> [Prime Int] -> PrimeIntSet
coerce [Int] -> IntSet
IS.fromDistinctAscList
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 :: Int -> PrimeIntSet -> PrimeIntSet
delete :: Int -> PrimeIntSet -> PrimeIntSet
delete = (Int -> IntSet -> IntSet) -> Int -> PrimeIntSet -> PrimeIntSet
coerce Int -> IntSet -> IntSet
IS.delete
member :: Prime Int -> PrimeIntSet -> Bool
member :: Prime Int -> PrimeIntSet -> Bool
member = (Int -> IntSet -> Bool) -> Prime Int -> PrimeIntSet -> Bool
coerce Int -> IntSet -> Bool
IS.member
notMember :: Prime Int -> PrimeIntSet -> Bool
notMember :: Prime Int -> PrimeIntSet -> Bool
notMember = (Int -> IntSet -> Bool) -> Prime Int -> PrimeIntSet -> Bool
coerce Int -> IntSet -> Bool
IS.notMember
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
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
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
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
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
null :: PrimeIntSet -> Bool
null :: PrimeIntSet -> Bool
null = (IntSet -> Bool) -> PrimeIntSet -> Bool
coerce IntSet -> Bool
IS.null
size :: PrimeIntSet -> Int
size :: PrimeIntSet -> Int
size = (IntSet -> Int) -> PrimeIntSet -> Int
coerce IntSet -> Int
IS.size
isSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool
isSubsetOf :: PrimeIntSet -> PrimeIntSet -> Bool
isSubsetOf = (IntSet -> IntSet -> Bool) -> PrimeIntSet -> PrimeIntSet -> Bool
coerce IntSet -> IntSet -> Bool
IS.isSubsetOf
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)
disjoint :: PrimeIntSet -> PrimeIntSet -> Bool
disjoint :: PrimeIntSet -> PrimeIntSet -> Bool
disjoint = (IntSet -> IntSet -> Bool) -> PrimeIntSet -> PrimeIntSet -> Bool
coerce IntSet -> IntSet -> Bool
IS.disjoint
#else
disjoint :: PrimeIntSet -> PrimeIntSet -> Bool
disjoint (PrimeIntSet x) (PrimeIntSet y) = IS.null (IS.intersection x y)
#endif
difference :: PrimeIntSet -> IntSet -> PrimeIntSet
difference :: PrimeIntSet -> IntSet -> PrimeIntSet
difference = (IntSet -> IntSet -> IntSet)
-> PrimeIntSet -> IntSet -> PrimeIntSet
coerce IntSet -> IntSet -> IntSet
IS.difference
(\\) :: PrimeIntSet -> IntSet -> PrimeIntSet
\\ :: PrimeIntSet -> IntSet -> PrimeIntSet
(\\) = (IntSet -> IntSet -> IntSet)
-> PrimeIntSet -> IntSet -> PrimeIntSet
coerce IntSet -> IntSet -> IntSet
(IS.\\)
infixl 9 \\
symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
symmetricDifference :: PrimeIntSet -> PrimeIntSet -> PrimeIntSet
symmetricDifference = (IntSet -> IntSet -> IntSet)
-> PrimeIntSet -> PrimeIntSet -> PrimeIntSet
coerce IntSet -> IntSet -> IntSet
symmDiff
intersection :: PrimeIntSet -> IntSet -> PrimeIntSet
intersection :: PrimeIntSet -> IntSet -> PrimeIntSet
intersection = (IntSet -> IntSet -> IntSet)
-> PrimeIntSet -> IntSet -> PrimeIntSet
coerce IntSet -> IntSet -> IntSet
IS.intersection
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 :: (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 :: 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
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
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
splitRoot :: PrimeIntSet -> [PrimeIntSet]
splitRoot :: PrimeIntSet -> [PrimeIntSet]
splitRoot = (IntSet -> [IntSet]) -> PrimeIntSet -> [PrimeIntSet]
coerce IntSet -> [IntSet]
IS.splitRoot
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)
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)
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)
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)
deleteMin :: PrimeIntSet -> PrimeIntSet
deleteMin :: PrimeIntSet -> PrimeIntSet
deleteMin = (IntSet -> IntSet) -> PrimeIntSet -> PrimeIntSet
coerce IntSet -> IntSet
IS.deleteMin
deleteMax :: PrimeIntSet -> PrimeIntSet
deleteMax :: PrimeIntSet -> PrimeIntSet
deleteMax = (IntSet -> IntSet) -> PrimeIntSet -> PrimeIntSet
coerce IntSet -> IntSet
IS.deleteMax
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
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
toAscList :: PrimeIntSet -> [Prime Int]
toAscList :: PrimeIntSet -> [Prime Int]
toAscList = (IntSet -> [Int]) -> PrimeIntSet -> [Prime Int]
coerce IntSet -> [Int]
IS.toAscList
toDescList :: PrimeIntSet -> [Prime Int]
toDescList :: PrimeIntSet -> [Prime Int]
toDescList = (IntSet -> [Int]) -> PrimeIntSet -> [Prime Int]
coerce IntSet -> [Int]
IS.toDescList
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 #-}