bitset 1.4.6 → 1.4.7

raw patch · 7 files changed

+82/−144 lines, 7 filesdep ~criterionPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: criterion

API changes (from Hackage documentation)

Files

• CHANGES +8/−0
• bitset.cabal +4/−4
• src/Data/BitSet.hs +1/−1
• src/Data/BitSet/Dynamic.hs +6/−7
• src/Data/BitSet/Generic.hs +54/−122
• src/Data/BitSet/Word.hs +7/−7
• tests/Tests.hs +2/−3

@@ -3,6 +3,14 @@  Here you can see the full list of changes between each bitset release. +Version 1.4.7+-------------++Released on August 25th, 2013++- 'GBitSet' was renamed to 'BitSet' and is now 'newtype' as suggested+  by John Ericson, see #10 on GitHub for details.+ Version 1.4.6 ------------- 

@@ -1,5 +1,5 @@ Name:                 bitset-Version:              1.4.6+Version:              1.4.7 Synopsis:             A space-efficient set data structure. Description:   A /bit set/ is a compact data structure, which maintains a set of members@@ -32,9 +32,9 @@   Include-dirs:       cbits    if os(windows)-    Extra-libraries:    gmp-10+    Extra-libraries:  gmp-10   else-    Extra-libraries:    gmp+    Extra-libraries:  gmp    Build-depends:      base                       >= 4.4.0 && < 4.7                     , deepseq                    == 1.3.*@@ -79,7 +79,7 @@                     , integer-gmp                     , ghc-prim -                    , criterion                   == 0.6.*+                    , criterion                   == 0.8.*                     , containers                  >= 0.4.2                     , random                      == 1.0.*                     , random-shuffle              == 0.0.4

@@ -8,7 +8,7 @@ -- Stability   :  experimental -- Portability :  GHC ----- A space-efficient implementation of set data structure enumerated+-- A space-efficient implementation of set data structure for enumerated -- data types.  module Data.BitSet ( module Data.BitSet.Dynamic ) where

@@ -78,7 +78,6 @@  import GHC.Integer.GMP.TypeExt (popCountInteger, testBitInteger,                                 setBitInteger, clearBitInteger)-import Data.BitSet.Generic (GBitSet) import qualified Data.BitSet.Generic as GS  -- | A wrapper around 'Integer' which provides faster bit-level operations.@@ -125,7 +124,7 @@     isSigned = isSigned . unFI     {-# INLINE isSigned #-} -type BitSet = GBitSet FasterInteger+type BitSet = GS.BitSet FasterInteger  -- | /O(1)/. Is the bit set empty? null :: BitSet a -> Bool@@ -169,12 +168,12 @@ {-# INLINE singleton #-}  -- | /O(1)/. Insert an item into the bit set.-insert :: a -> BitSet a -> BitSet a+insert :: Enum a => a -> BitSet a -> BitSet a insert = GS.insert {-# INLINE insert #-}  -- | /O(1)/. Delete an item from the bit set.-delete :: a -> BitSet a -> BitSet a+delete :: Enum a => a -> BitSet a -> BitSet a delete = GS.delete {-# INLINE delete #-} @@ -207,13 +206,13 @@ -- elements, using the given starting value.  Each application of the -- operator is evaluated before before using the result in the next -- application.  This function is strict in the starting value.-foldl' :: (b -> a -> b) -> b -> BitSet a -> b+foldl' :: Enum a => (b -> a -> b) -> b -> BitSet a -> b foldl' = GS.foldl' {-# INLINE foldl' #-}  -- | /O(n)/ Reduce this bit set by applying a binary function to all -- elements, using the given starting value.-foldr :: (a -> b -> b) -> b -> BitSet a -> b+foldr :: Enum a => (a -> b -> b) -> b -> BitSet a -> b foldr = GS.foldr {-# INLINE foldr #-} @@ -224,7 +223,7 @@ {-# INLINE filter #-}  -- | /O(n)/. Convert the bit set set to a list of elements.-toList :: BitSet a -> [a]+toList :: Enum a => BitSet a -> [a] toList = GS.toList {-# INLINE toList #-} 

@@ -25,16 +25,14 @@ -- independent of container choice, the maximum number of elements in a -- bit set is bounded by @maxBound :: Int@. -{-# LANGUAGE CPP #-}-{-# LANGUAGE GADTs #-} {-# LANGUAGE BangPatterns #-}-{-# LANGUAGE NamedFieldPuns #-} {-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}  module Data.BitSet.Generic     (     -- * Bit set type-      GBitSet+      BitSet(..)      -- * Operators     , (\\)@@ -71,10 +69,6 @@     -- * Lists     , toList     , fromList--    -- * Internal-    , toBits-    , unsafeFromBits     ) where  import Prelude hiding (null, map, filter, foldr)@@ -84,204 +78,142 @@ import Data.Bits (Bits, (.|.), (.&.), complement, bit,                   testBit, setBit, clearBit, popCount) import Data.Data (Typeable)-import Data.Monoid (Monoid(..), (<>))-import Foreign (Storable(..), castPtr)+import Data.Monoid (Monoid(..))+import Foreign (Storable) import GHC.Exts (build) import Text.Read (Read(..), Lexeme(..), lexP, prec, parens)-import qualified Data.Foldable as Foldable import qualified Data.List as List  -- | A bit set with unspecified container type.-data GBitSet c a =-    (Enum a, Bits c, Num c) =>-    BitSet { _n    :: {-# UNPACK #-} !Int  -- ^ Number of elements in the bit set.-#if defined(__GLASGOW_HASKELL__) && (__GLASGOW_HASKELL__ >= 708)-           , _bits :: {-# UNPACK #-} !c    -- ^ Bit container.-#else-           , _bits :: !c                   -- ^ Bit container.-#endif-           }-    deriving Typeable--instance Eq c => Eq (GBitSet c a) where-    BitSet { _n = n1, _bits = b1 } == BitSet { _n = n2, _bits = b2 } =-        n1 == n2 && b1 == b2--instance Ord c => Ord (GBitSet c a) where-    BitSet { _n = n1, _bits = b1 } `compare` BitSet { _n = n2, _bits = b2 } =-        case compare n1 n2 of-            EQ  -> compare b1 b2-            res -> res+newtype BitSet c a = BitSet { getBits :: c }+   deriving (Eq, NFData, Storable, Ord, Typeable) -instance (Enum a, Read a, Bits c, Num c) => Read (GBitSet c a) where+instance (Enum a, Read a, Bits c, Num c) => Read (BitSet c a) where     readPrec = parens . prec 10 $ do         Ident "fromList" <- lexP         fromList <$> readPrec -instance (Show a, Num c) => Show (GBitSet c a) where+instance (Enum a, Show a, Bits c,  Num c) => Show (BitSet c a) where     showsPrec p bs = showParen (p > 10) $                      showString "fromList " . shows (toList bs) -instance (Enum a, Bits c, Num c) => Monoid (GBitSet c a) where+instance (Enum a, Bits c, Num c) => Monoid (BitSet c a) where     mempty  = empty     mappend = union -instance NFData c => NFData (GBitSet c a) where-    rnf (BitSet { _n, _bits }) = rnf _n `seq` rnf _bits `seq` ()--instance (Bits c, Enum a, Num c, Storable c) => Storable (GBitSet c a) where-    sizeOf = sizeOf . _bits-    alignment = alignment . _bits-    peek ptr = do-        b <- peek $ castPtr ptr-        return $! BitSet (popCount b) b-    poke ptr = poke (castPtr ptr) . _bits--instance Num c => Foldable.Foldable (GBitSet c) where-#if MIN_VERSION_base(4, 6, 0)-    foldl' = foldl'-#endif-    foldr  = foldr--    foldMap f (BitSet { _n, _bits }) = go _n 0 where-        go 0 _b = mempty-        go !n b = if _bits `testBit` b-                  then f (toEnum b) <> go (pred n) (succ b)-                  else go n (succ b)- -- | /O(1)/. Is the bit set empty?-null :: GBitSet c a -> Bool-null (BitSet { _n = 0, _bits = 0 }) = True-null _bs = False+null :: (Eq c, Num c) => BitSet c a -> Bool+null = (== 0) . getBits {-# INLINE null #-}  -- | /O(1)/. The number of elements in the bit set.-size :: GBitSet c a -> Int-size = _n+size :: Bits c => BitSet c a -> Int+size = popCount . getBits {-# INLINE size #-}  -- | /O(d)/. Ask whether the item is in the bit set.-member :: (Enum a , Bits c) => a -> GBitSet c a -> Bool-member x = (`testBit` fromEnum x) . _bits+member :: (Enum a , Bits c) => a -> BitSet c a -> Bool+member x = (`testBit` fromEnum x) . getBits {-# INLINE member #-} --- | /O(d)/. Ask whether the item is in the bit set.-notMember :: (Enum a, Bits c) => a -> GBitSet c a -> Bool+-- | /O(d)/. Ask whether the item is not in the bit set.+notMember :: (Enum a, Bits c) => a -> BitSet c a -> Bool notMember x = not . member x {-# INLINE notMember #-} --- | /O(max(n, m))/. Is this a subset? (@s1 isSubsetOf s2@) tells whether+-- | /O(max(n, m))/. Is this a subset? (@s1 `isSubsetOf` s2@) tells whether -- @s1@ is a subset of @s2@.-isSubsetOf :: GBitSet c a -> GBitSet c a -> Bool-isSubsetOf (BitSet { _n = n1, _bits = b1 }) (BitSet { _n = n2, _bits = b2 }) =-    n2 >= n1 && b2 .|. b1 == b2+isSubsetOf :: (Bits c, Eq c) => BitSet c a -> BitSet c a -> Bool+isSubsetOf (BitSet bits1) (BitSet bits2) = bits2 .|. bits1 == bits2 {-# INLINE isSubsetOf #-}  -- | /O(max(n, m)/. Is this a proper subset? (ie. a subset but not equal).-isProperSubsetOf :: Eq c => GBitSet c a -> GBitSet c a -> Bool+isProperSubsetOf :: (Bits c, Eq c) => BitSet c a -> BitSet c a -> Bool isProperSubsetOf bs1 bs2 = bs1 `isSubsetOf` bs2 && bs1 /= bs2 {-# INLINE isProperSubsetOf #-}  -- | The empty bit set.-empty :: (Enum a, Bits c, Num c) => GBitSet c a-empty = BitSet { _n = 0, _bits = 0 }+empty :: (Enum a, Bits c, Num c) => BitSet c a+empty = BitSet 0 {-# INLINE empty #-}  -- | O(1). Create a singleton set.-singleton :: (Enum a, Bits c, Num c) => a -> GBitSet c a-singleton x = BitSet { _n = 1, _bits = bit $! fromEnum x }+singleton :: (Enum a, Bits c, Num c) => a -> BitSet c a+singleton = BitSet . bit . fromEnum {-# INLINE singleton #-}  -- | /O(d)/. Insert an item into the bit set.-insert :: a -> GBitSet c a -> GBitSet c a-insert x bs@(BitSet { _bits }) =-    let b = _bits `setBit` fromEnum x in bs { _n = popCount b, _bits = b }+insert :: (Enum a, Bits c) => a -> BitSet c a -> BitSet c a+insert x (BitSet bits) = BitSet $ bits `setBit` fromEnum x {-# INLINE insert #-}  -- | /O(d)/. Delete an item from the bit set.-delete :: a -> GBitSet c a -> GBitSet c a-delete x bs@(BitSet { _bits }) =-    let b = _bits `clearBit` fromEnum x in bs { _n = popCount b, _bits = b }+delete :: (Enum a, Bits c) => a -> BitSet c a -> BitSet c a+delete x (BitSet bits ) = BitSet $ bits `clearBit` fromEnum x {-# INLINE delete #-}  -- | /O(max(m, n))/. The union of two bit sets.-union :: GBitSet c a -> GBitSet c a -> GBitSet c a-union (BitSet { _bits = b1 }) (BitSet { _bits = b2 }) =-    let b = b1 .|. b2 in BitSet { _n = popCount b, _bits = b }+union :: Bits c => BitSet c a -> BitSet c a -> BitSet c a+union (BitSet bits1) (BitSet bits2) = BitSet $ bits1 .|. bits2 {-# INLINE union #-}  -- | /O(max(m, n))/. Difference of two bit sets.-difference :: GBitSet c a -> GBitSet c a -> GBitSet c a-difference (BitSet { _bits = b1 }) (BitSet { _bits = b2 }) =-    let b = b1 .&. complement b2 in BitSet { _n = popCount b, _bits = b }+difference :: Bits c => BitSet c a -> BitSet c a -> BitSet c a+difference (BitSet bits1) (BitSet bits2) = BitSet $ bits1 .&. complement bits2 {-# INLINE difference #-}  -- | /O(max(m, n))/. See 'difference'.-(\\) :: GBitSet c a -> GBitSet c a -> GBitSet c a+(\\) :: Bits c => BitSet c a -> BitSet c a -> BitSet c a (\\) = difference  -- | /O(max(m, n))/. The intersection of two bit sets.-intersection :: GBitSet c a -> GBitSet c a -> GBitSet c a-intersection (BitSet { _bits = b1 }) (BitSet { _bits = b2 }) =-    BitSet { _n = popCount b, _bits = b }-  where-    b = b1 .&. b2+intersection :: Bits c => BitSet c a -> BitSet c a -> BitSet c a+intersection (BitSet bits1) (BitSet bits2) = BitSet $ bits1 .&. bits2 {-# INLINE intersection #-}  -- | /O(d * n)/ Transform this bit set by applying a function to every -- value.  Resulting bit set may be smaller then the original.-map :: (Enum a, Enum b, Bits c, Num c) => (a -> b) -> GBitSet c a -> GBitSet c b-map f = fromList . List.map f . toList+map :: (Enum a, Enum b, Bits c, Num c) => (a -> b) -> BitSet c a -> BitSet c b+map f = foldl' (\bs -> (`insert` bs) . f) empty {-# INLINE map #-}  -- | /O(d * n)/ Reduce this bit set by applying a binary function to all -- elements, using the given starting value.  Each application of the -- operator is evaluated before before using the result in the next -- application.  This function is strict in the starting value.-foldl' :: (b -> a -> b) -> b -> GBitSet c a -> b-foldl' f acc0  (BitSet { _n, _bits }) = go acc0 _n 0 where+foldl' :: (Enum a, Bits c) => (b -> a -> b) -> b -> BitSet c a -> b+foldl' f acc0  (BitSet bits) = go acc0 (popCount bits) 0 where   go !acc 0 _b = acc-  go !acc !n b = if _bits `testBit` b+  go !acc !n b = if bits `testBit` b                  then go (f acc $ toEnum b) (pred n) (succ b)                  else go acc n (succ b) {-# INLINE foldl' #-}  -- | /O(d * n)/ Reduce this bit set by applying a binary function to -- all elements, using the given starting value.-foldr :: (a -> b -> b) -> b -> GBitSet c a -> b-foldr f acc0 (BitSet { _n, _bits }) = go _n 0 where+foldr :: (Enum a, Bits c) => (a -> b -> b) -> b -> BitSet c a -> b+foldr f acc0 (BitSet bits) = go (popCount bits) 0 where   go 0 _b = acc0-  go !n b = if _bits `testBit` b+  go !n b = if bits `testBit` b             then toEnum b `f` go (pred n) (succ b)             else go n (succ b) {-# INLINE foldr #-}  -- | /O(d * n)/ Filter this bit set by retaining only elements satisfying -- predicate.-filter :: (Enum a, Bits c, Num c) => (a -> Bool) -> GBitSet c a -> GBitSet c a-filter f = fromList . List.filter f . toList+filter :: (Enum a, Bits c, Num c) => (a -> Bool) -> BitSet c a -> BitSet c a+filter f = foldl' (\bs x -> if f x then x `insert` bs else bs) empty {-# INLINE filter #-}  -- | /O(d * n)/. Convert this bit set set to a list of elements.-toList :: Num c => GBitSet c a -> [a]+toList :: (Enum a, Bits c, Num c) => BitSet c a -> [a] toList bs = build (\k z -> foldr k z bs)-{-# INLINE toList #-}+{-# INLINE [0] toList #-}  -- | /O(d * n)/. Make a bit set from a list of elements.-fromList :: (Enum a, Bits c, Num c) => [a] -> GBitSet c a-fromList xs = BitSet { _n = popCount b, _bits = b } where-  b = List.foldl' (\i x -> i `setBit` fromEnum x) 0 xs-{-# INLINE fromList #-}---- | /O(1)/. Internal function, which extracts the underlying container--- from the bit set.-toBits :: GBitSet c a -> c-toBits = _bits-{-# INLINE toBits #-}---- | /O(1)/. Internal function, which constructs a bit set, using a given--- container value. Highly unsafe, because we don't check if bits in the--- given value correspond to valid instances of type @a@.-unsafeFromBits :: (Enum a, Bits c, Num c) => c -> GBitSet c a-unsafeFromBits b = BitSet { _n = popCount b, _bits = b }-{-# INLINE unsafeFromBits #-}+fromList :: (Enum a, Bits c, Num c) => [a] -> BitSet c a+fromList = BitSet . List.foldl' (\i x -> i `setBit` fromEnum x) 0+{-# INLINE [0] fromList #-}+{-# RULES+"fromList/toList"    forall bs. fromList (toList bs) = bs+  #-}

@@ -72,10 +72,9 @@  import Data.Word (Word) -import Data.BitSet.Generic (GBitSet) import qualified Data.BitSet.Generic as GS -type BitSet = GBitSet Word+type BitSet = GS.BitSet Word  -- | /O(1)/. Is the bit set empty? null :: BitSet a -> Bool@@ -119,12 +118,12 @@ {-# INLINE singleton #-}  -- | /O(1)/. Insert an item into the bit set.-insert :: a -> BitSet a -> BitSet a+insert :: Enum a => a -> BitSet a -> BitSet a insert = GS.insert {-# INLINE insert #-}  -- | /O(1)/. Delete an item from the bit set.-delete :: a -> BitSet a -> BitSet a+delete :: Enum a => a -> BitSet a -> BitSet a delete = GS.delete {-# INLINE delete #-} @@ -151,18 +150,19 @@ -- Resulting bit set may be smaller then the original. map :: (Enum a, Enum b) => (a -> b) -> BitSet a -> BitSet b map = GS.map+{-# INLINE map #-}  -- | /O(n)/ Reduce this bit set by applying a binary function to all -- elements, using the given starting value.  Each application of the -- operator is evaluated before before using the result in the next -- application.  This function is strict in the starting value.-foldl' :: (b -> a -> b) -> b -> BitSet a -> b+foldl' :: Enum a => (b -> a -> b) -> b -> BitSet a -> b foldl' = GS.foldl' {-# INLINE foldl' #-}  -- | /O(n)/ Reduce this bit set by applying a binary function to all -- elements, using the given starting value.-foldr :: (a -> b -> b) -> b -> BitSet a -> b+foldr :: Enum a => (a -> b -> b) -> b -> BitSet a -> b foldr = GS.foldr {-# INLINE foldr #-} @@ -173,7 +173,7 @@ {-# INLINE filter #-}  -- | /O(n)/. Convert the bit set set to a list of elements.-toList :: BitSet a -> [a]+toList :: Enum a => BitSet a -> [a] toList = GS.toList {-# INLINE toList #-} 

@@ -19,14 +19,13 @@  import Data.BitSet (BitSet) import Data.BitSet.Dynamic (FasterInteger(..))-import Data.BitSet.Generic (GBitSet) import qualified Data.BitSet as BS import qualified Data.BitSet.Generic as GS  instance (Arbitrary a, Enum a) => Arbitrary (BitSet a) where     arbitrary = BS.fromList <$> arbitrary -instance (Arbitrary a, Enum a) => Arbitrary (GBitSet Word16 a) where+instance (Arbitrary a, Enum a) => Arbitrary (GS.BitSet Word16 a) where     arbitrary = GS.fromList <$> arbitrary  instance Show (Word16 -> a) where@@ -174,7 +173,7 @@ propFilter :: BitSet Word16 -> (Word16 -> Bool) -> Bool propFilter bs f = BS.filter f bs == (BS.fromList $ filter f $ BS.toList bs) -propStorable :: GBitSet Word16 Word16 -> Property+propStorable :: GS.BitSet Word16 Word16 -> Property propStorable storable = monadicIO $ do     peeked <- run $ do         allocaBytes size $ \ptr -> do