bitset-0.6: Data/BitSet.hs

-- | 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
-- 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.
--
-- The implementation is quite simple: we rely on the @Bits Integer@ instance
-- from @Data.Bits@.  An advantage of this library over simply using that
-- @Bits@ instance is the phantom type parameter used in the `BitSet' type.
-- 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
    , empty
    , null
    , insert
    , delete
    , member
    , size
    ) where

import Prelude hiding ( null )
import Data.Bits


-- | 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)

instance Show (BitSet a) where
    show s = "BitSet " ++ show (unBS s)

-- | The empty bit set.
empty :: BitSet a

-- | Is the bit set empty?
null :: BitSet a -> Bool

-- | /O(setBit on Integer)/ Insert an item into the bit set.
insert :: Hash a => a -> BitSet a -> BitSet a

-- | /O(clearBit on Integer)/ Delete an item from the bit set.
delete :: Hash 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

-- | /O(1)/ The number of elements in the bit set.
size :: BitSet a -> Int


-- * Implementation

empty = BS (0, 0)

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

{-# 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

{-# INLINE member #-}
member x s = hash x `memHash` s
memHash :: Int -> BitSet a -> Bool
{-# INLINE memHash #-}
memHash h (BS (_, i)) = testBit i h

{-# 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