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


-- | Pure and impure Bloom Filter implementations.
--   
--   Pure and impure Bloom Filter implementations.
@package bloomfilter
@version 2.0.1.3


-- | Fast hashing of Haskell values. The hash functions used are Bob
--   Jenkins's public domain functions, which combine high performance with
--   excellent mixing properties. For more details, see
--   <a>http://burtleburtle.net/bob/hash/</a>.
--   
--   In addition to the usual "one input, one output" hash functions, this
--   module provides multi-output hash functions, suitable for use in
--   applications that need multiple hashes, such as Bloom filtering.
module Data.BloomFilter.Hash
class Hashable a

-- | Compute a 32-bit hash of a value. The salt value perturbs the result.
hashIO32 :: Hashable a => a -> Word32 -> IO Word32

-- | Compute a 64-bit hash of a value. The first salt value perturbs the
--   first element of the result, and the second salt perturbs the second.
hashIO64 :: Hashable a => a -> Word64 -> IO Word64

-- | Compute a 32-bit hash.
hash32 :: Hashable a => a -> Word32
hash64 :: Hashable a => a -> Word64

-- | Compute a salted 32-bit hash.
hashSalt32 :: Hashable a => Word32 -> a -> Word32

-- | Compute a salted 64-bit hash.
hashSalt64 :: Hashable a => Word64 -> a -> Word64

-- | Compute a list of 32-bit hashes. The value to hash may be inspected as
--   many times as there are hashes requested.
hashes :: Hashable a => Int -> a -> [Word32]

-- | Compute a list of 32-bit hashes relatively cheaply. The value to hash
--   is inspected at most twice, regardless of the number of hashes
--   requested.
--   
--   We use a variant of Kirsch and Mitzenmacher's technique from "Less
--   Hashing, Same Performance: Building a Better Bloom Filter",
--   <a>http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf</a>.
--   
--   Where Kirsch and Mitzenmacher multiply the second hash by a
--   coefficient, we shift right by the coefficient. This offers better
--   performance (as a shift is much cheaper than a multiply), and the low
--   order bits of the final hash stay well mixed.
cheapHashes :: Hashable a => Int -> a -> [Word32]

-- | Compute a 32-bit hash of a <a>Storable</a> instance.
hashOne32 :: Storable a => a -> Word32 -> IO Word32

-- | Compute a 64-bit hash of a <a>Storable</a> instance.
hashOne64 :: Storable a => a -> Word64 -> IO Word64

-- | Compute a 32-bit hash of a list of <a>Storable</a> instances.
hashList32 :: Storable a => [a] -> Word32 -> IO Word32

-- | Compute a 64-bit hash of a list of <a>Storable</a> instances.
hashList64 :: Storable a => [a] -> Word64 -> IO Word64
instance Data.BloomFilter.Hash.Hashable GHC.Types.Bool
instance Data.BloomFilter.Hash.Hashable Data.ByteString.Lazy.Internal.ByteString
instance Data.BloomFilter.Hash.Hashable Data.ByteString.Internal.Type.ByteString
instance Data.BloomFilter.Hash.Hashable GHC.Types.Char
instance Data.BloomFilter.Hash.Hashable GHC.Types.Double
instance (Data.BloomFilter.Hash.Hashable a, Data.BloomFilter.Hash.Hashable b) => Data.BloomFilter.Hash.Hashable (GHC.Internal.Data.Either.Either a b)
instance Data.BloomFilter.Hash.Hashable GHC.Types.Float
instance Data.BloomFilter.Hash.Hashable GHC.Types.Int
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Int.Int16
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Int.Int32
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Int.Int64
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Int.Int8
instance Data.BloomFilter.Hash.Hashable GHC.Num.Integer.Integer
instance GHC.Internal.Foreign.Storable.Storable a => Data.BloomFilter.Hash.Hashable [a]
instance Data.BloomFilter.Hash.Hashable a => Data.BloomFilter.Hash.Hashable (GHC.Internal.Maybe.Maybe a)
instance Data.BloomFilter.Hash.Hashable GHC.Types.Ordering
instance (Data.BloomFilter.Hash.Hashable a, Data.BloomFilter.Hash.Hashable b) => Data.BloomFilter.Hash.Hashable (a, b)
instance (Data.BloomFilter.Hash.Hashable a, Data.BloomFilter.Hash.Hashable b, Data.BloomFilter.Hash.Hashable c) => Data.BloomFilter.Hash.Hashable (a, b, c)
instance (Data.BloomFilter.Hash.Hashable a, Data.BloomFilter.Hash.Hashable b, Data.BloomFilter.Hash.Hashable c, Data.BloomFilter.Hash.Hashable d) => Data.BloomFilter.Hash.Hashable (a, b, c, d)
instance (Data.BloomFilter.Hash.Hashable a, Data.BloomFilter.Hash.Hashable b, Data.BloomFilter.Hash.Hashable c, Data.BloomFilter.Hash.Hashable d, Data.BloomFilter.Hash.Hashable e) => Data.BloomFilter.Hash.Hashable (a, b, c, d, e)
instance Data.BloomFilter.Hash.Hashable ()
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Word.Word16
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Word.Word32
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Word.Word64
instance Data.BloomFilter.Hash.Hashable GHC.Internal.Word.Word8


-- | A fast, space efficient Bloom filter implementation. A Bloom filter is
--   a set-like data structure that provides a probabilistic membership
--   test.
--   
--   <ul>
--   <li>Queries do not give false negatives. When an element is added to a
--   filter, a subsequent membership test will definitely return
--   <a>True</a>.</li>
--   <li>False positives <i>are</i> possible. If an element has not been
--   added to a filter, a membership test <i>may</i> nevertheless indicate
--   that the element is present.</li>
--   </ul>
--   
--   This module provides low-level control. For an easier to use
--   interface, see the <a>Data.BloomFilter.Easy</a> module.
module Data.BloomFilter.Mutable

-- | A hash value is 32 bits wide. This limits the maximum size of a filter
--   to about four billion elements, or 512 megabytes of memory.
type Hash = Word32

-- | A mutable Bloom filter, for use within the <tt>ST</tt> monad.
data MBloom s a

-- | Create a new mutable Bloom filter. For efficiency, the number of bits
--   used may be larger than the number requested. It is always rounded up
--   to the nearest higher power of two, but will be clamped at a maximum
--   of 4 gigabits, since hashes are 32 bits in size.
new :: (a -> [Hash]) -> Int -> ST s (MBloom s a)

-- | Return the size of a mutable Bloom filter, in bits.
length :: MBloom s a -> Int

-- | Query a mutable Bloom filter for membership. If the value is present,
--   return <tt>True</tt>. If the value is not present, there is
--   <i>still</i> some possibility that <tt>True</tt> will be returned.
elem :: a -> MBloom s a -> ST s Bool

-- | Insert a value into a mutable Bloom filter. Afterwards, a membership
--   query for the same value is guaranteed to return <tt>True</tt>.
insert :: MBloom s a -> a -> ST s ()
bitArray :: MBloom s a -> STUArray s Int Hash


-- | A fast, space efficient Bloom filter implementation. A Bloom filter is
--   a set-like data structure that provides a probabilistic membership
--   test.
--   
--   <ul>
--   <li>Queries do not give false negatives. When an element is added to a
--   filter, a subsequent membership test will definitely return
--   <a>True</a>.</li>
--   <li>False positives <i>are</i> possible. If an element has not been
--   added to a filter, a membership test <i>may</i> nevertheless indicate
--   that the element is present.</li>
--   </ul>
--   
--   This module provides low-level control. For an easier to use
--   interface, see the <a>Data.BloomFilter.Easy</a> module.
module Data.BloomFilter

-- | A hash value is 32 bits wide. This limits the maximum size of a filter
--   to about four billion elements, or 512 megabytes of memory.
type Hash = Word32

-- | An immutable Bloom filter, suitable for querying from pure code.
data Bloom a

-- | A mutable Bloom filter, for use within the <tt>ST</tt> monad.
data MBloom s a

-- | Create an immutable Bloom filter from a mutable one. The mutable
--   filter may be modified afterwards.
freeze :: MBloom s a -> ST s (Bloom a)

-- | Copy an immutable Bloom filter to create a mutable one. There is no
--   non-copying equivalent.
thaw :: Bloom a -> ST s (MBloom s a)

-- | Create an immutable Bloom filter from a mutable one. The mutable
--   filter <i>must not</i> be modified afterwards, or a runtime crash may
--   occur. For a safer creation interface, use <a>freeze</a> or
--   <a>create</a>.
unsafeFreeze :: MBloom s a -> ST s (Bloom a)

-- | Build an immutable Bloom filter from a seed value. The seeding
--   function populates the filter as follows.
--   
--   <ul>
--   <li>If it returns <a>Nothing</a>, it is finished producing values to
--   insert into the filter.</li>
--   <li>If it returns <tt><a>Just</a> (a,b)</tt>, <tt>a</tt> is added to
--   the filter and <tt>b</tt> is used as a new seed.</li>
--   </ul>
unfold :: (a -> [Hash]) -> Int -> (b -> Maybe (a, b)) -> b -> Bloom a

-- | Create an immutable Bloom filter, populating it from a list of values.
--   
--   Here is an example that uses the <tt>cheapHashes</tt> function from
--   the <a>Data.BloomFilter.Hash</a> module to create a hash function that
--   returns three hashes.
--   
--   <pre>
--   import <a>Data.BloomFilter.Hash</a> (cheapHashes)
--   
--   filt = fromList (cheapHashes 3) 1024 ["foo", "bar", "quux"]
--    
--   </pre>
fromList :: (a -> [Hash]) -> Int -> [a] -> Bloom a

-- | Create an empty Bloom filter.
--   
--   This function is subject to fusion with <a>insert</a> and
--   <a>insertList</a>.
empty :: (a -> [Hash]) -> Int -> Bloom a

-- | Create a Bloom filter with a single element.
--   
--   This function is subject to fusion with <a>insert</a> and
--   <a>insertList</a>.
singleton :: (a -> [Hash]) -> Int -> a -> Bloom a

-- | Return the size of an immutable Bloom filter, in bits.
length :: Bloom a -> Int

-- | Query an immutable Bloom filter for membership. If the value is
--   present, return <tt>True</tt>. If the value is not present, there is
--   <i>still</i> some possibility that <tt>True</tt> will be returned.
elem :: a -> Bloom a -> Bool

-- | Query an immutable Bloom filter for non-membership. If the value
--   <i>is</i> present, return <tt>False</tt>. If the value is not present,
--   there is <i>still</i> some possibility that <tt>False</tt> will be
--   returned.
notElem :: a -> Bloom a -> Bool

-- | Create a new Bloom filter from an existing one, with the given member
--   added.
--   
--   This function may be expensive, as it is likely to cause the
--   underlying bit array to be copied.
--   
--   Repeated applications of this function with itself are subject to
--   fusion.
insert :: a -> Bloom a -> Bloom a

-- | Create a new Bloom filter from an existing one, with the given members
--   added.
--   
--   This function may be expensive, as it is likely to cause the
--   underlying bit array to be copied.
--   
--   Repeated applications of this function with itself are subject to
--   fusion.
insertList :: [a] -> Bloom a -> Bloom a
bitArray :: Bloom a -> UArray Int Hash
instance Control.DeepSeq.NFData (Data.BloomFilter.Bloom a)
instance GHC.Internal.Show.Show (Data.BloomFilter.Bloom a)


-- | An easy-to-use Bloom filter interface.
module Data.BloomFilter.Easy

-- | An immutable Bloom filter, suitable for querying from pure code.
data Bloom a

-- | Create a Bloom filter with the given false positive rate and members.
--   The hash functions used are computed by the <tt>cheapHashes</tt>
--   function from the <a>Hash</a> module.
easyList :: Hashable a => Double -> [a] -> Bloom a

-- | Query an immutable Bloom filter for membership. If the value is
--   present, return <tt>True</tt>. If the value is not present, there is
--   <i>still</i> some possibility that <tt>True</tt> will be returned.
elem :: a -> Bloom a -> Bool

-- | Query an immutable Bloom filter for non-membership. If the value
--   <i>is</i> present, return <tt>False</tt>. If the value is not present,
--   there is <i>still</i> some possibility that <tt>False</tt> will be
--   returned.
notElem :: a -> Bloom a -> Bool

-- | Return the size of an immutable Bloom filter, in bits.
length :: Bloom a -> Int

-- | Suggest a good combination of filter size and number of hash functions
--   for a Bloom filter, based on its expected maximum capacity and a
--   desired false positive rate.
--   
--   The false positive rate is the rate at which queries against the
--   filter should return <tt>True</tt> when an element is not actually
--   present. It should be a fraction between 0 and 1, so a 1% false
--   positive rate is represented by 0.01.
safeSuggestSizing :: Int -> Double -> Either String (Int, Int)

-- | Behaves as <a>safeSuggestSizing</a>, but calls <a>error</a> if given
--   invalid or out-of-range inputs.
suggestSizing :: Int -> Double -> (Int, Int)
