{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE TypeFamilies #-}

module Data.BitSet where

import Data.Bits
import Data.Coerce
import qualified Data.Foldable as F
import qualified Data.List as L
import qualified Data.Vector.Fusion.Stream.Monadic as MS
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed as U
import GHC.Exts

{- $setup
>>> :set -XOverloadedLists
-}

newtype BitSet = BitSet {BitSet -> Int
getBitSet :: Int}
  deriving (BitSet -> BitSet -> Bool
(BitSet -> BitSet -> Bool)
-> (BitSet -> BitSet -> Bool) -> Eq BitSet
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: BitSet -> BitSet -> Bool
== :: BitSet -> BitSet -> Bool
$c/= :: BitSet -> BitSet -> Bool
/= :: BitSet -> BitSet -> Bool
Eq, Eq BitSet
Eq BitSet =>
(BitSet -> BitSet -> Ordering)
-> (BitSet -> BitSet -> Bool)
-> (BitSet -> BitSet -> Bool)
-> (BitSet -> BitSet -> Bool)
-> (BitSet -> BitSet -> Bool)
-> (BitSet -> BitSet -> BitSet)
-> (BitSet -> BitSet -> BitSet)
-> Ord BitSet
BitSet -> BitSet -> Bool
BitSet -> BitSet -> Ordering
BitSet -> BitSet -> BitSet
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
$ccompare :: BitSet -> BitSet -> Ordering
compare :: BitSet -> BitSet -> Ordering
$c< :: BitSet -> BitSet -> Bool
< :: BitSet -> BitSet -> Bool
$c<= :: BitSet -> BitSet -> Bool
<= :: BitSet -> BitSet -> Bool
$c> :: BitSet -> BitSet -> Bool
> :: BitSet -> BitSet -> Bool
$c>= :: BitSet -> BitSet -> Bool
>= :: BitSet -> BitSet -> Bool
$cmax :: BitSet -> BitSet -> BitSet
max :: BitSet -> BitSet -> BitSet
$cmin :: BitSet -> BitSet -> BitSet
min :: BitSet -> BitSet -> BitSet
Ord)
  deriving newtype (Integer -> BitSet
BitSet -> BitSet
BitSet -> BitSet -> BitSet
(BitSet -> BitSet -> BitSet)
-> (BitSet -> BitSet -> BitSet)
-> (BitSet -> BitSet -> BitSet)
-> (BitSet -> BitSet)
-> (BitSet -> BitSet)
-> (BitSet -> BitSet)
-> (Integer -> BitSet)
-> Num BitSet
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
$c+ :: BitSet -> BitSet -> BitSet
+ :: BitSet -> BitSet -> BitSet
$c- :: BitSet -> BitSet -> BitSet
- :: BitSet -> BitSet -> BitSet
$c* :: BitSet -> BitSet -> BitSet
* :: BitSet -> BitSet -> BitSet
$cnegate :: BitSet -> BitSet
negate :: BitSet -> BitSet
$cabs :: BitSet -> BitSet
abs :: BitSet -> BitSet
$csignum :: BitSet -> BitSet
signum :: BitSet -> BitSet
$cfromInteger :: Integer -> BitSet
fromInteger :: Integer -> BitSet
Num, Eq BitSet
BitSet
Eq BitSet =>
(BitSet -> BitSet -> BitSet)
-> (BitSet -> BitSet -> BitSet)
-> (BitSet -> BitSet -> BitSet)
-> (BitSet -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> BitSet
-> (Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> Bool)
-> (BitSet -> Maybe Int)
-> (BitSet -> Int)
-> (BitSet -> Bool)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int -> BitSet)
-> (BitSet -> Int)
-> Bits BitSet
Int -> BitSet
BitSet -> Bool
BitSet -> Int
BitSet -> Maybe Int
BitSet -> BitSet
BitSet -> Int -> Bool
BitSet -> Int -> BitSet
BitSet -> BitSet -> BitSet
forall a.
Eq a =>
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> a
-> (Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> Bool)
-> (a -> Maybe Int)
-> (a -> Int)
-> (a -> Bool)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int -> a)
-> (a -> Int)
-> Bits a
$c.&. :: BitSet -> BitSet -> BitSet
.&. :: BitSet -> BitSet -> BitSet
$c.|. :: BitSet -> BitSet -> BitSet
.|. :: BitSet -> BitSet -> BitSet
$cxor :: BitSet -> BitSet -> BitSet
xor :: BitSet -> BitSet -> BitSet
$ccomplement :: BitSet -> BitSet
complement :: BitSet -> BitSet
$cshift :: BitSet -> Int -> BitSet
shift :: BitSet -> Int -> BitSet
$crotate :: BitSet -> Int -> BitSet
rotate :: BitSet -> Int -> BitSet
$czeroBits :: BitSet
zeroBits :: BitSet
$cbit :: Int -> BitSet
bit :: Int -> BitSet
$csetBit :: BitSet -> Int -> BitSet
setBit :: BitSet -> Int -> BitSet
$cclearBit :: BitSet -> Int -> BitSet
clearBit :: BitSet -> Int -> BitSet
$ccomplementBit :: BitSet -> Int -> BitSet
complementBit :: BitSet -> Int -> BitSet
$ctestBit :: BitSet -> Int -> Bool
testBit :: BitSet -> Int -> Bool
$cbitSizeMaybe :: BitSet -> Maybe Int
bitSizeMaybe :: BitSet -> Maybe Int
$cbitSize :: BitSet -> Int
bitSize :: BitSet -> Int
$cisSigned :: BitSet -> Bool
isSigned :: BitSet -> Bool
$cshiftL :: BitSet -> Int -> BitSet
shiftL :: BitSet -> Int -> BitSet
$cunsafeShiftL :: BitSet -> Int -> BitSet
unsafeShiftL :: BitSet -> Int -> BitSet
$cshiftR :: BitSet -> Int -> BitSet
shiftR :: BitSet -> Int -> BitSet
$cunsafeShiftR :: BitSet -> Int -> BitSet
unsafeShiftR :: BitSet -> Int -> BitSet
$crotateL :: BitSet -> Int -> BitSet
rotateL :: BitSet -> Int -> BitSet
$crotateR :: BitSet -> Int -> BitSet
rotateR :: BitSet -> Int -> BitSet
$cpopCount :: BitSet -> Int
popCount :: BitSet -> Int
Bits)

instance Show BitSet where
  showsPrec :: Int -> BitSet -> ShowS
showsPrec Int
p BitSet
xs =
    Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> ShowS
forall a. Show a => a -> ShowS
shows (BitSet -> [Item BitSet]
forall l. IsList l => l -> [Item l]
toList BitSet
xs)

instance IsList BitSet where
  type Item BitSet = Int
  fromList :: [Item BitSet] -> BitSet
fromList = Int -> BitSet
BitSet (Int -> BitSet) -> ([Int] -> Int) -> [Int] -> BitSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int -> Int) -> Int -> [Int] -> Int
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' (\Int
acc Int
x -> Int
acc Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftL Int
1 Int
x) Int
0
  toList :: BitSet -> [Item BitSet]
toList = BitSet -> [Int]
BitSet -> [Item BitSet]
toListBS

emptyBS :: BitSet
emptyBS :: BitSet
emptyBS = Int -> BitSet
BitSet Int
0

singletonBS :: Int -> BitSet
singletonBS :: Int -> BitSet
singletonBS (I# Int#
i#) = Int -> BitSet
BitSet (Int# -> Int
I# (Int# -> Int# -> Int#
uncheckedIShiftL# Int#
1# Int#
i#))

{- |
>>> insertBS 0 []
fromList [0]
>>> insertBS 0 [0]
fromList [0]
-}
insertBS :: Int -> BitSet -> BitSet
insertBS :: Int -> BitSet -> BitSet
insertBS (I# Int#
i#) (BitSet (I# Int#
bs#)) =
  Int -> BitSet
BitSet (Int# -> Int
I# (Int# -> Int# -> Int#
uncheckedIShiftL# Int#
1# Int#
i# Int# -> Int# -> Int#
`orI#` Int#
bs#))

{- |
>>> deleteBS 2 [1,2,3]
fromList [1,3]
>>> deleteBS 10 [1,2,3]
fromList [1,2,3]
>>> deleteBS 0 []
fromList []
-}
deleteBS :: Int -> BitSet -> BitSet
deleteBS :: Int -> BitSet -> BitSet
deleteBS (I# Int#
i#) (BitSet (I# Int#
bs#)) =
  Int -> BitSet
BitSet (Int# -> Int
I# (Int# -> Int#
notI# (Int# -> Int# -> Int#
uncheckedIShiftL# Int#
1# Int#
i#) Int# -> Int# -> Int#
`andI#` Int#
bs#))

memberBS :: Int -> BitSet -> Bool
memberBS :: Int -> BitSet -> Bool
memberBS (I# Int#
i#) (BitSet (I# Int#
bs#)) =
  Int# -> Bool
isTrue# (Int# -> Int# -> Int#
uncheckedIShiftRL# Int#
bs# Int#
i# Int# -> Int# -> Int#
`andI#` Int#
1#)

notMemberBS :: Int -> BitSet -> Bool
notMemberBS :: Int -> BitSet -> Bool
notMemberBS Int
i = Bool -> Bool
not (Bool -> Bool) -> (BitSet -> Bool) -> BitSet -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> BitSet -> Bool
memberBS Int
i

nullBS :: BitSet -> Bool
nullBS :: BitSet -> Bool
nullBS = (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0) (Int -> Bool) -> (BitSet -> Int) -> BitSet -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. Coercible a b => a -> b
forall a b. Coercible a b => a -> b
coerce @BitSet @Int

sizeBS :: BitSet -> Int
sizeBS :: BitSet -> Int
sizeBS = (Int -> Int) -> BitSet -> Int
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> Int
popCount @Int)

{- |
>>> isSubsetOfBS [] [1,2,3]
True
>>> isSubsetOfBS [1] []
False
>>> isSubsetOfBS [1,2,3] [1,2,3]
True
-}
isSubsetOfBS :: BitSet -> BitSet -> Bool
isSubsetOfBS :: BitSet -> BitSet -> Bool
isSubsetOfBS BitSet
x BitSet
y = BitSet -> BitSet -> BitSet
intersectionBS BitSet
x BitSet
y BitSet -> BitSet -> Bool
forall a. Eq a => a -> a -> Bool
== BitSet
x

unionBS :: BitSet -> BitSet -> BitSet
unionBS :: BitSet -> BitSet -> BitSet
unionBS = (Int -> Int -> Int) -> BitSet -> BitSet -> BitSet
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> a -> a
(.|.) @Int)

complementBS :: BitSet -> BitSet
complementBS :: BitSet -> BitSet
complementBS = (Int -> Int) -> BitSet -> BitSet
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> a
complement @Int)

{-
>>> differenceBS [1,2,3] [1,2]
fromList [3]
>>> differenceBS [1,2] [1,2,3]
fromList []
-}
differenceBS :: BitSet -> BitSet -> BitSet
differenceBS :: BitSet -> BitSet -> BitSet
differenceBS BitSet
x BitSet
y = BitSet -> BitSet -> BitSet
intersectionBS BitSet
x (BitSet -> BitSet
complementBS BitSet
y)

intersectionBS :: BitSet -> BitSet -> BitSet
intersectionBS :: BitSet -> BitSet -> BitSet
intersectionBS = (Int -> Int -> Int) -> BitSet -> BitSet -> BitSet
forall a b. Coercible a b => a -> b
coerce (forall a. Bits a => a -> a -> a
(.&.) @Int)

{- |
>>> findMinBS [1,2,3]
1
>>> findMinBS []
64
-}
findMinBS :: BitSet -> Int
findMinBS :: BitSet -> Int
findMinBS = (Int -> Int) -> BitSet -> Int
forall a b. Coercible a b => a -> b
coerce (forall b. FiniteBits b => b -> Int
countTrailingZeros @Int)

{- |
>>> findMaxBS [1,2,3]
3
>>> findMaxBS []
-1
-}
findMaxBS :: BitSet -> Int
findMaxBS :: BitSet -> Int
findMaxBS = (Int
63 -) (Int -> Int) -> (BitSet -> Int) -> BitSet -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int) -> BitSet -> Int
forall a b. Coercible a b => a -> b
coerce (forall b. FiniteBits b => b -> Int
countLeadingZeros @Int)

{- |
>>> deleteMinBS [1,2,3]
fromList [2,3]
>>> deleteMinBS []
fromList []
-}
deleteMinBS :: BitSet -> BitSet
deleteMinBS :: BitSet -> BitSet
deleteMinBS (BitSet Int
x) = Int -> BitSet
BitSet (Int
x Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1))

{- |
>>> deleteMaxBS [1,2,3]
fromList [1,2]
>>> deleteMaxBS []
fromList []
-}
deleteMaxBS :: BitSet -> BitSet
deleteMaxBS :: BitSet -> BitSet
deleteMaxBS BitSet
x = Int -> BitSet -> BitSet
deleteBS (BitSet -> Int
findMaxBS BitSet
x) BitSet
x

deleteFindMinBS :: BitSet -> (Int, BitSet)
deleteFindMinBS :: BitSet -> (Int, BitSet)
deleteFindMinBS BitSet
x = (BitSet -> Int
findMinBS BitSet
x, BitSet -> BitSet
deleteMinBS BitSet
x)

deleteFindMaxBS :: BitSet -> (Int, BitSet)
deleteFindMaxBS :: BitSet -> (Int, BitSet)
deleteFindMaxBS BitSet
x =
  let i :: Int
i = BitSet -> Int
findMaxBS BitSet
x
   in (Int
i, Int -> BitSet -> BitSet
deleteBS Int
i BitSet
x)

minViewBS :: BitSet -> Maybe (Int, BitSet)
minViewBS :: BitSet -> Maybe (Int, BitSet)
minViewBS BitSet
x
  | BitSet
x BitSet -> BitSet -> Bool
forall a. Eq a => a -> a -> Bool
/= Int -> BitSet
BitSet Int
0 = (Int, BitSet) -> Maybe (Int, BitSet)
forall a. a -> Maybe a
Just ((Int, BitSet) -> Maybe (Int, BitSet))
-> (Int, BitSet) -> Maybe (Int, BitSet)
forall a b. (a -> b) -> a -> b
$ BitSet -> (Int, BitSet)
deleteFindMinBS BitSet
x
  | Bool
otherwise = Maybe (Int, BitSet)
forall a. Maybe a
Nothing

maxViewBS :: BitSet -> Maybe (Int, BitSet)
maxViewBS :: BitSet -> Maybe (Int, BitSet)
maxViewBS BitSet
x
  | BitSet
x BitSet -> BitSet -> Bool
forall a. Eq a => a -> a -> Bool
/= Int -> BitSet
BitSet Int
0 = (Int, BitSet) -> Maybe (Int, BitSet)
forall a. a -> Maybe a
Just ((Int, BitSet) -> Maybe (Int, BitSet))
-> (Int, BitSet) -> Maybe (Int, BitSet)
forall a b. (a -> b) -> a -> b
$ BitSet -> (Int, BitSet)
deleteFindMaxBS BitSet
x
  | Bool
otherwise = Maybe (Int, BitSet)
forall a. Maybe a
Nothing

{- |
>>> import Data.Functor.Identity
>>> runIdentity . MS.toList $ powersetBS [0,1,2]
[fromList [0,1,2],fromList [1,2],fromList [0,2],fromList [2],fromList [0,1],fromList [1],fromList [0],fromList []]
>>> runIdentity . MS.toList $ powersetBS []
[fromList []]
-}
powersetBS :: (Monad m) => BitSet -> MS.Stream m BitSet
powersetBS :: forall (m :: * -> *). Monad m => BitSet -> Stream m BitSet
powersetBS BitSet
s0 = (BitSet -> m (Step BitSet BitSet)) -> BitSet -> Stream m BitSet
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream BitSet -> m (Step BitSet BitSet)
step (BitSet
s0 BitSet -> BitSet -> BitSet
forall a. Num a => a -> a -> a
+ BitSet
1)
  where
    step :: BitSet -> m (Step BitSet BitSet)
step BitSet
s
      | BitSet
s' BitSet -> BitSet -> Bool
forall a. Ord a => a -> a -> Bool
< BitSet
s = Step BitSet BitSet -> m (Step BitSet BitSet)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step BitSet BitSet -> m (Step BitSet BitSet))
-> Step BitSet BitSet -> m (Step BitSet BitSet)
forall a b. (a -> b) -> a -> b
$ BitSet -> BitSet -> Step BitSet BitSet
forall a s. a -> s -> Step s a
MS.Yield BitSet
s' BitSet
s'
      | Bool
otherwise = Step BitSet BitSet -> m (Step BitSet BitSet)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step BitSet BitSet
forall s a. Step s a
MS.Done
      where
        !s' :: BitSet
s' = (BitSet
s BitSet -> BitSet -> BitSet
forall a. Num a => a -> a -> a
- BitSet
1) BitSet -> BitSet -> BitSet
forall a. Bits a => a -> a -> a
.&. BitSet
s0
    {-# INLINE [0] step #-}
{-# INLINE [1] powersetBS #-}

{- |
>>> import Data.Functor.Identity
>>> runIdentity . MS.toList $ strictPowersetBS [0,1,2]
[fromList [1,2],fromList [0,2],fromList [2],fromList [0,1],fromList [1],fromList [0],fromList []]
>>> runIdentity . MS.toList $ strictPowersetBS []
[]
-}
strictPowersetBS :: (Monad m) => BitSet -> MS.Stream m BitSet
strictPowersetBS :: forall (m :: * -> *). Monad m => BitSet -> Stream m BitSet
strictPowersetBS BitSet
s0 = (BitSet -> m (Step BitSet BitSet)) -> BitSet -> Stream m BitSet
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream BitSet -> m (Step BitSet BitSet)
step BitSet
s0
  where
    step :: BitSet -> m (Step BitSet BitSet)
step BitSet
s
      | BitSet
s' BitSet -> BitSet -> Bool
forall a. Ord a => a -> a -> Bool
< BitSet
s = Step BitSet BitSet -> m (Step BitSet BitSet)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step BitSet BitSet -> m (Step BitSet BitSet))
-> Step BitSet BitSet -> m (Step BitSet BitSet)
forall a b. (a -> b) -> a -> b
$ BitSet -> BitSet -> Step BitSet BitSet
forall a s. a -> s -> Step s a
MS.Yield BitSet
s' BitSet
s'
      | Bool
otherwise = Step BitSet BitSet -> m (Step BitSet BitSet)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step BitSet BitSet
forall s a. Step s a
MS.Done
      where
        !s' :: BitSet
s' = (BitSet
s BitSet -> BitSet -> BitSet
forall a. Num a => a -> a -> a
- BitSet
1) BitSet -> BitSet -> BitSet
forall a. Bits a => a -> a -> a
.&. BitSet
s0
    {-# INLINE [0] step #-}
{-# INLINE [1] strictPowersetBS #-}

{- |
>>> toListBS [0,1,63]
[0,1,63]
>>> toListBS [0]
[0]
>>> toListBS []
[]
-}
toListBS :: BitSet -> [Int]
toListBS :: BitSet -> [Int]
toListBS = (BitSet -> Maybe (Int, BitSet)) -> BitSet -> [Int]
forall b a. (b -> Maybe (a, b)) -> b -> [a]
L.unfoldr BitSet -> Maybe (Int, BitSet)
minViewBS

{- |
>>> import Data.Functor.Identity
>>> runIdentity . MS.toList $ toStreamBS [3,1,4]
[1,3,4]
-}
toStreamBS :: (Monad m) => BitSet -> MS.Stream m Int
toStreamBS :: forall (m :: * -> *). Monad m => BitSet -> Stream m Int
toStreamBS = (BitSet -> m (Step BitSet Int)) -> BitSet -> Stream m Int
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream BitSet -> m (Step BitSet Int)
forall {m :: * -> *}. Monad m => BitSet -> m (Step BitSet Int)
step
  where
    step :: BitSet -> m (Step BitSet Int)
step BitSet
s
      | BitSet
s BitSet -> BitSet -> Bool
forall a. Eq a => a -> a -> Bool
/= Int -> BitSet
BitSet Int
0 = Step BitSet Int -> m (Step BitSet Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step BitSet Int -> m (Step BitSet Int))
-> Step BitSet Int -> m (Step BitSet Int)
forall a b. (a -> b) -> a -> b
$ Int -> BitSet -> Step BitSet Int
forall a s. a -> s -> Step s a
MS.Yield (BitSet -> Int
findMinBS BitSet
s) (BitSet -> BitSet
deleteMinBS BitSet
s)
      | Bool
otherwise = Step BitSet Int -> m (Step BitSet Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step BitSet Int
forall s a. Step s a
MS.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] toStreamBS #-}

newtype instance U.MVector s BitSet = MV_BitSet (U.MVector s Int)
newtype instance U.Vector BitSet = V_BitSet (U.Vector Int)
deriving newtype instance GM.MVector U.MVector BitSet
deriving newtype instance G.Vector U.Vector BitSet
instance U.Unbox BitSet