module Data.BitSet
(
BitSet
, (\\)
, null
, size
, member
, notMember
, isSubsetOf
, isProperSubsetOf
, empty
, singleton
, insert
, delete
, union
, unions
, difference
, intersection
, elems
, toList
, fromList
, toIntegral
, unsafeFromIntegral
) where
import Prelude hiding (null)
import Data.Bits (Bits, (.|.), (.&.), complement,
testBit, setBit, clearBit, shiftR, popCount)
import Data.Data (Data, Typeable)
import Data.List (foldl')
import Data.Monoid (Monoid(..))
import Control.DeepSeq (NFData(..))
data BitSet a = BitSet !Int !Integer
deriving (Eq, Ord, Data, Typeable)
instance Enum a => Monoid (BitSet a) where
mempty = empty
mappend = union
mconcat = unions
instance (Enum a, Show a) => Show (BitSet a) where
show bs = "fromList " ++ show (elems bs)
instance NFData (BitSet a) where
rnf (BitSet count i) = rnf count `seq` rnf i `seq` ()
null :: BitSet a -> Bool
null (BitSet _n i) = i == 0
size :: BitSet a -> Int
size (BitSet n _i) = n
member :: Enum a => a -> BitSet a -> Bool
member x (BitSet _n i) = testBit i (fromEnum x)
notMember :: Enum a => a -> BitSet a -> Bool
notMember bs = not . member bs
isSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool
isSubsetOf (BitSet n1 i1) (BitSet n2 i2) = n2 >= n1 && i2 .|. i1 == i2
isProperSubsetOf :: Enum a => BitSet a -> BitSet a -> Bool
isProperSubsetOf bs1 bs2 = bs1 `isSubsetOf` bs2 && bs1 /= bs2
empty :: BitSet a
empty = BitSet 0 0
singleton :: Enum a => a -> BitSet a
singleton x = insert x empty
insert :: Enum a => a -> BitSet a -> BitSet a
insert x (BitSet n i) = BitSet n' $ setBit i e where
n' = if testBit i e then n else n + 1
e = fromEnum x
delete :: Enum a => a -> BitSet a -> BitSet a
delete x (BitSet n i) = BitSet n' $ clearBit i e where
n' = if testBit i e then n 1 else n
e = fromEnum x
union :: Enum a => BitSet a -> BitSet a -> BitSet a
union (BitSet _n1 i1) (BitSet _n2 i2) = BitSet (popCount i) i where
i = i1 .|. i2
unions :: Enum a => [BitSet a] -> BitSet a
unions = foldl' union empty
difference :: Enum a => BitSet a -> BitSet a -> BitSet a
difference (BitSet _n1 i1) (BitSet _n2 i2) = BitSet (popCount i) i where
i = i1 .&. complement i2
(\\) :: Enum a => BitSet a -> BitSet a -> BitSet a
(\\) = difference
intersection :: Enum a => BitSet a -> BitSet a -> BitSet a
intersection (BitSet _n1 i1) (BitSet _n2 i2) = BitSet (popCount i) i where
i = i1 .&. i2
elems :: Enum a => BitSet a -> [a]
elems = toList
toList :: Enum a => BitSet a -> [a]
toList (BitSet _i n0) = go 0 n0 [] where
go _i 0 acc = reverse acc
go i n acc = if n `testBit` 0
then go (i + 1) (shiftR n 1) (toEnum i : acc)
else go (i + 1) (shiftR n 1) acc
fromList :: Enum a => [a] -> BitSet a
fromList xs = BitSet (popCount i) i where
i = foldl' (\b x -> setBit b (fromEnum x)) 0 xs
toIntegral :: Integral b => BitSet a -> b
toIntegral (BitSet _n i) = fromIntegral i
unsafeFromIntegral :: Integral b => b -> BitSet a
unsafeFromIntegral x = let i = fromIntegral x in BitSet (popCount i) i