-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A functional data structure for efficient membership testing.
--   
--   A bit set is a data structure for keeping membership information
--   efficiently. This implementation uses Data.Bits on Integers, and thus
--   should achieve reasonable speed.
@package bitset
@version 0.5


-- | An efficient membership-testing module, for types that can be mapped
--   into <tt>Int</tt>s.
--   
--   The implementation is quite simple: we rely on the <tt>Bits
--   Integer</tt> instance from <tt>Data.Bits</tt> for the three main
--   operations. An advantage of this library is the phantom parameter used
--   in the BitSet type. Since there is no exported way to construct a
--   value of type <a>BitSet</a> directly, the interface we expose ensures
--   client code will not typecheck if it confuses two bit sets intended to
--   keep track of different types.
--   
--   It is important that the values you intend to keep track of start from
--   0 and go up. Each <tt>Int</tt> mapped to be hash corresponds to that
--   bit location in an <tt>Integer</tt>, and thus requires that
--   <tt>Integer</tt> to have at least that many bits. Don't shoot yourself
--   in the foot.
module Data.BitSet

-- | Map a value to an non-negative <tt>Int</tt>.
--   
--   For the implementation to give reliable results, it must be that if
--   <tt>hash x == hash y</tt>, <tt>x</tt> and <tt>y</tt> 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 your equivalence relation is <tt>==</tt>, the following
--   quickcheck test should pass, for arbitrary <tt>x</tt> and <tt>y</tt>:
--   
--   <pre>
--   prop_hash x y =
--        if hash x == hash y then x == y
--        else x /= y
--        &amp;&amp; if x == y then hash x == hash y
--           else hash x /= hash y
--   </pre>
class Hash a
hash :: (Hash a) => a -> Int

-- | The <tt>Show</tt> instance kind of sucks. It just shows the
--   <tt>Integer</tt> representation. A good show would probably show all
--   the present hashes.
data BitSet a

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

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

-- | <i>O(clearBit on Integer)</i> Delete an item from the bit set.
delete :: (Hash a) => a -> BitSet a -> BitSet a

-- | <i>O(testBit on Integer)</i> Ask whether the item is in the bit set.
member :: (Hash a) => a -> BitSet a -> Bool
instance Eq (BitSet a)
instance Arbitrary (BitSet a)
instance Hash Integer
instance Hash Int
instance Show (BitSet a)