module Data.BitSet.Dynamic
(
FasterInteger
, BitSet
, (\\)
, empty
, singleton
, insert
, delete
, null
, size
, member
, notMember
, isSubsetOf
, isProperSubsetOf
, union
, unions
, difference
, intersection
, map
, filter
, toList
, fromList
) where
import Prelude hiding (null, map, filter)
import Data.Bits (Bits(..))
import GHC.Base (Int(..), divInt#, modInt#)
import GHC.Exts (popCnt#)
import GHC.Integer.GMP.Internals (Integer(..))
import GHC.Prim (Int#, Word#, (+#), (==#), (>=#),
word2Int#, int2Word#, plusWord#, indexWordArray#)
import GHC.Word (Word(..))
import Control.DeepSeq (NFData(..))
import Data.BitSet.Generic (GBitSet(..))
import qualified Data.BitSet.Generic as BS
newtype FasterInteger = FasterInteger { unFI :: Integer }
deriving (Read, Show, Eq, Ord, Enum, Integral, Num, Real, NFData)
instance Bits FasterInteger where
FasterInteger x .&. FasterInteger y = FasterInteger $ x .&. y
FasterInteger x .|. FasterInteger y = FasterInteger $ x .|. y
FasterInteger x `xor` FasterInteger y = FasterInteger $ x `xor` y
complement = FasterInteger . complement . unFI
shift (FasterInteger x) i = FasterInteger $ shift x i
rotate (FasterInteger x) i = FasterInteger $ rotate x i
bit = FasterInteger . bit
testBit (FasterInteger x) i = testBitInteger x i
popCount (FasterInteger x) = I# (word2Int# (popCountInteger x))
bitSize = bitSize . unFI
isSigned = isSigned . unFI
type BitSet = GBitSet FasterInteger
null :: BitSet a -> Bool
null = BS.null
size :: BitSet a -> Int
size = BS.size
member :: a -> BitSet a -> Bool
member = BS.member
notMember :: a -> BitSet a -> Bool
notMember = BS.notMember
isSubsetOf :: BitSet a -> BitSet a -> Bool
isSubsetOf = BS.isSubsetOf
isProperSubsetOf :: BitSet a -> BitSet a -> Bool
isProperSubsetOf = BS.isProperSubsetOf
empty :: Enum a => BitSet a
empty = BS.empty
singleton :: Enum a => a -> BitSet a
singleton = BS.singleton
insert :: a -> BitSet a -> BitSet a
insert = BS.insert
delete :: a -> BitSet a -> BitSet a
delete = BS.delete
union :: BitSet a -> BitSet a -> BitSet a
union = BS.union
unions :: Enum a => [BitSet a] -> BitSet a
unions = BS.unions
difference :: BitSet a -> BitSet a -> BitSet a
difference = BS.difference
(\\) :: BitSet a -> BitSet a -> BitSet a
(\\) = difference
intersection :: BitSet a -> BitSet a -> BitSet a
intersection = BS.intersection
map :: (Enum a, Enum b) => (a -> b) -> BitSet a -> BitSet b
map = BS.map
filter :: Enum a => (a -> Bool) -> BitSet a -> BitSet a
filter = BS.filter
toList :: BitSet a -> [a]
toList = BS.toList
fromList :: Enum a => [a] -> BitSet a
fromList = BS.fromList
popCountInteger :: Integer -> Word#
popCountInteger (S# i#) = popCnt# (int2Word# i#)
popCountInteger (J# s# d#) = go 0# (int2Word# 0#) where
go i acc =
if i ==# s#
then acc
else go (i +# 1#) $ acc `plusWord#` popCnt# (indexWordArray# d# i)
#include "MachDeps.h"
#ifndef WORD_SIZE_IN_BITS
#error WORD_SIZE_IN_BITS not defined!
#endif
testBitInteger :: Integer -> Int -> Bool
testBitInteger (S# i#) b = I# i# `testBit` b
testBitInteger (J# s# d#) (I# b#) =
if block# >=# s#
then False
else W# (indexWordArray# d# block#) `testBit` I# offset#
where
n# :: Int#
n# = WORD_SIZE_IN_BITS#
block# :: Int#
!block# = b# `divInt#` n#
offset# :: Int#
!offset# = b# `modInt#` n#