bitset 0.6 → 1.0

raw patch · 5 files changed

+68/−86 lines, 5 filesdep ~basesetup-changedPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/BitSet.hs +38/−65
• Setup.hs +2/−0
• Setup.lhs +0/−4
• bitset.cabal +5/−2
• tests/Properties.hs +23/−15

@@ -1,14 +1,13 @@ -- | A /bit set/ maintains a record of members from a type that can be mapped--- into (non-negative) @Int@s.  Supports insertion, deletion, size, and+-- into (non-negative) @Int@s. The maximum number of elements that can be+-- stored is @maxbound :: Int@. Supports insertion, deletion, size, and -- membership testing, and is completely pure (functional). ----- To use this library, simply supply a `Hash' instance for your data type.--- (See the `Hash' class for the relevant laws your instance must obey.)  Each--- operation requires at most one call to `hash'.  It is important that the--- values you intend to keep track of start from 0 and go up.  A value which--- `hash'es to @n@ corresponds to bit location @n@ in an @Integer@, and thus--- requires that @Integer@ to have at least @n@ bits.  Don't shoot yourself in--- the foot by `hash'ing to big @Int@s.+-- To use this library, simply supply a `Enum' instance for your data type or+-- have it derived. It is important that the values you intend to keep track+-- of start from 0 and go up. A value for which @fromEnum x@ is @n@+-- corresponds to bit location @n@ in an @Integer@, and thus requires that+-- @Integer@ to have at least @n@ bits. -- -- The implementation is quite simple: we rely on the @Bits Integer@ instance -- from @Data.Bits@.  An advantage of this library over simply using that@@ -16,11 +15,11 @@ -- The interface we expose ensures client code will not typecheck if it -- confuses two bit sets intended to keep track of different types. module Data.BitSet-    ( Hash(..)-    , BitSet+    ( BitSet     , empty     , null     , insert+    , fromList     , delete     , member     , size@@ -28,34 +27,18 @@  import Prelude hiding ( null ) import Data.Bits+import Data.Data  --- | Map a value to an non-negative @Int@.------ For the implementation to give reliable results, it must be that if @hash x--- == hash y@, @x@ and @y@ are equivalent under the relevant relation used in--- the client code.  (We don't depend on equality, but the client code will--- certainly want to use the above sort of inference.)------ In fact, if the relevant relation is @==@, the following quickcheck--- test should pass, for arbitrary @x@ and @y@ of type @a@:------ @prop_hash x y =---     if hash x == hash y then x == y---     else x /= y---     && if x == y then hash x == hash y---        else hash x /= hash y@-class Hash a where-    hash :: a -> Int---- | The @Show@ instance kind of sucks.  It just shows the size paired with--- the internal @Integer@ representation.  A good show would probably show all--- the present hashes.-newtype BitSet a = BS { unBS :: (Int, Integer) }-    deriving (Eq)+data BitSet a = BS {-# UNPACK #-} !Int {-# UNPACK #-} !Integer+                deriving (Eq, Ord, Data, Typeable) -instance Show (BitSet a) where-    show s = "BitSet " ++ show (unBS s)+instance (Enum a, Show a) => Show (BitSet a) where+    show (BS _ i :: BitSet a) = "fromList " ++ show (f 0 i)+        where f _ 0 = []+              f n x = if testBit x 0+                      then (toEnum n :: a) : f (n+1) (shiftR x 1)+                      else f (n+1) (shiftR x 1)  -- | The empty bit set. empty :: BitSet a@@ -64,13 +47,16 @@ null :: BitSet a -> Bool  -- | /O(setBit on Integer)/ Insert an item into the bit set.-insert :: Hash a => a -> BitSet a -> BitSet a+insert :: Enum a => a -> BitSet a -> BitSet a +-- | /O(n * setBit on Integer)/ Make a @BitSet@ from a list of items.+fromList :: Enum a => [a] -> BitSet a+ -- | /O(clearBit on Integer)/ Delete an item from the bit set.-delete :: Hash a => a -> BitSet a -> BitSet a+delete :: Enum a => a -> BitSet a -> BitSet a  -- | /O(testBit on Integer)/ Ask whether the item is in the bit set.-member :: Hash a => a -> BitSet a -> Bool+member :: Enum a => a -> BitSet a -> Bool  -- | /O(1)/ The number of elements in the bit set. size :: BitSet a -> Int@@ -78,39 +64,26 @@  -- * Implementation -empty = BS (0, 0)+{-# INLINE empty #-}+empty = BS 0 0 -null (BS (n, _)) = n == 0+{-# INLINE null #-}+null (BS n _) = n == 0  {-# INLINE insert #-}-insert x s@(BS (count, i)) = BS $ (count', setBit i h)-    where count' = if h `memHash` s then count else count+1-          h      = hash x+insert x (BS count i) = BS count' (setBit i e)+    where count' = if testBit i e then count else count+1+          e      = fromEnum x +fromList xs = BS (length xs) (foldl (\i x -> setBit i (fromEnum x)) 0 xs)+ {-# INLINE delete #-}-delete x s@(BS (count, i)) = BS $ (count', clearBit i h)-    where count' = if h `memHash` s then count-1 else count-          h      = hash x+delete x (BS count i) = BS count' (clearBit i e)+    where count' = if testBit i e then count-1 else count+          e      = fromEnum x  {-# INLINE member #-}-member x s = hash x `memHash` s-memHash :: Int -> BitSet a -> Bool-{-# INLINE memHash #-}-memHash h (BS (_, i)) = testBit i h+member x (BS _ i) = testBit i (fromEnum x)  {-# INLINE size #-}-size (BS (count, _)) = count---- * Default instances--instance Hash Int where-    hash = id--instance Hash Integer where-    hash = fromIntegral---- Needs UndecidableInstances?--- instance Integral a => Hash a where---     hash = fromIntegral--    +size (BS count _) = count

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -1,4 +0,0 @@-#! /usr/bin/env runhaskell--> import Distribution.Simple-> main = defaultMain

@@ -1,5 +1,5 @@ Name:                bitset-Version:             0.6+Version:             1.0 Synopsis:            A functional data structure for efficient membership testing. Description:         A /bit set/ maintains a record of members from a type that can be mapped@@ -11,10 +11,13 @@ Author:              Denis Bueno Maintainer:          Denis Bueno <dbueno@gmail.com> Stability:           provisional+Cabal-Version:       >= 1.2.3 Build-Depends:       base, QuickCheck Build-type:          Simple  Exposed-modules:     Data.BitSet-Ghc-options:         -Wall+Build-depends:       base >= 4.0.0+Extensions:          ScopedTypeVariables, DeriveDataTypeable+Ghc-options:         -Wall -O2 Ghc-prof-options:    -prof -auto-all Extra-source-files:  tests/Properties.hs

@@ -1,29 +1,35 @@ module Properties where +import Control.Monad( liftM ) import Prelude hiding ( null ) import Data.BitSet import Data.Foldable ( foldl' ) import Data.List ( nub ) import Test.QuickCheck+import System.IO+ import qualified Data.List as List    main :: IO () main = do-  check config prop_size-  check config prop_size_insert-  check config prop_size_delete-  check config prop_insert-  check config prop_delete-  check config prop_insDelIdempotent-  check config prop_delDelIdempotent-  check config prop_insInsIdempotent-  check config prop_extensional-  check config prop_empty+  dbgMsg "prop_size: " >> check config prop_size+  dbgMsg "prop_size_insert: " >> check config prop_size_insert+  dbgMsg "prop_size_delete: " >> check config prop_size_delete+  dbgMsg "prop_insert: " >> check config prop_insert+  dbgMsg "prop_delete: " >> check config prop_delete+  dbgMsg "prop_insDelIdempotent: " >> check config prop_insDelIdempotent+  dbgMsg "prop_delDelIdempotent: " >> check config prop_delDelIdempotent+  dbgMsg "prop_insInsIdempotent: " >> check config prop_insInsIdempotent+  dbgMsg "prop_extensional: " >> check config prop_extensional+  dbgMsg "prop_fromList: " >> check config prop_fromList+  dbgMsg "prop_empty: " >> check config prop_empty -config = defaultConfig{ configMaxTest = 1000 }+dbgMsg = hPutStr stderr +config = defaultConfig{ configMaxTest = 2000 }+ -- * Quickcheck properties  prop_size xs =@@ -70,12 +76,14 @@     where s   = foldr insert empty xsa           xsa = map abs xs :: [Int] +prop_fromList xs = all (`member` s) xsa+    where s   = fromList xsa+          xsa = map abs xs :: [Int]+ prop_empty x = not $ xa `member` empty     where xa = abs x :: Int   -instance (Arbitrary a, Hash a) => Arbitrary (BitSet a) where-    arbitrary = sized $ \n ->-                do xs <- vector n-                   return $ foldl' (flip insert) empty xs+instance (Arbitrary a, Enum a) => Arbitrary (BitSet a) where+    arbitrary = sized $ liftM fromList . vector