-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A functional data structure for efficient membership testing.
--
-- A bit set maintains a record of members from a type that can be
-- mapped into (non-negative) Ints. Supports insertion,
-- deletion, size, and membership testing, and is completely pure
-- (functional).
@package bitset
@version 1.1
-- | A bit set maintains a record of members from a type that can be
-- mapped into (non-negative) Ints. 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 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 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
data BitSet a
-- | 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 :: 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 :: Enum a => a -> BitSet a -> BitSet a
-- | O(testBit on Integer) Ask whether the item is in the bit set.
member :: Enum a => a -> BitSet a -> Bool
-- | O(1) The number of elements in the bit set.
size :: BitSet a -> Int
-- | O(1) Project a bit set to an integer.
toIntegral :: Integral b => BitSet a -> b
-- | O(n) Make a bit set of type BitSet a from an integer.
-- This is unsafe because it is not checked whether the bits set in the
-- integer correspond to values of type a. This is only useful
-- as a more efficient alternative to fromList.
unsafeFromIntegral :: Integral b => b -> BitSet a
instance Typeable1 BitSet
instance Eq (BitSet a)
instance Ord (BitSet a)
instance Data a => Data (BitSet a)
instance (Enum a, Show a) => Show (BitSet a)