-- | An easy-to-use Bloom filter interface.
module Data.BloomFilter.Easy (
    -- * Easy creation and querying
    Bloom,
    easyList,
    B.elem,
    B.notElem,
    B.length,

    -- * Mutable bloom filter
    MBloom,
    easyNew,
    MB.new,
    MB.insert,
    B.freeze,

    -- ** Example: a spell checker
    -- $example

    -- * Useful defaults for creation
    safeSuggestSizing,
    suggestSizing,
) where

import           Control.Monad.ST (ST)
import           Data.BloomFilter (Bloom)
import qualified Data.BloomFilter as B
import           Data.BloomFilter.Calc
import           Data.BloomFilter.Hash (Hashable)
import           Data.BloomFilter.Mutable (MBloom)
import qualified Data.BloomFilter.Mutable as MB
import qualified Data.ByteString as SB
import           Data.Word (Word64)

-------------------------------------------------------------------------------
-- Easy interface
-------------------------------------------------------------------------------

-- | Create a Bloom filter with the desired false positive rate and
-- members.  The hash functions used are computed by the @cheapHashes@
-- function from the 'Data.BloomFilter.Hash' module.
easyList :: Hashable a
         => Double              -- ^ desired false positive rate (0 < /ε/ < 1)
         -> [a]                 -- ^ values to populate with
         -> Bloom a
{-# SPECIALIZE easyList :: Double -> [SB.ByteString] -> Bloom SB.ByteString #-}
easyList :: forall a. Hashable a => Double -> [a] -> Bloom a
easyList Double
errRate [a]
xs = Int -> Word64 -> [a] -> Bloom' CheapHashes a
forall (h :: * -> *) a.
(Hashes h, Hashable a) =>
Int -> Word64 -> [a] -> Bloom' h a
B.fromList Int
numHashes Word64
numBits [a]
xs
  where
    capacity :: Int
capacity = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs
    (Word64
numBits, Int
numHashes)
        | Int
capacity Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 = Int -> Double -> (Word64, Int)
suggestSizing Int
capacity Double
errRate
        | Bool
otherwise    = (Word64
1, Int
1)

-- | Create a Bloom filter with the desired false positive rate, /ε/
-- and expected maximum size, /n/.
easyNew :: Double    -- ^ desired false positive rate (0 < /ε/ < 1)
        -> Int       -- ^ expected maximum size, /n/
        -> ST s (MBloom s a)
easyNew :: forall s a. Double -> Int -> ST s (MBloom s a)
easyNew Double
errRate Int
capacity = Int -> Word64 -> ST s (MBloom' s CheapHashes a)
forall s (h :: * -> *) a. Int -> Word64 -> ST s (MBloom' s h a)
MB.new Int
numHashes Word64
numBits
  where
    (Word64
numBits, Int
numHashes) = Int -> Double -> (Word64, Int)
suggestSizing Int
capacity Double
errRate

-------------------------------------------------------------------------------
-- Size suggestions
-------------------------------------------------------------------------------

-- | 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 'True' 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.
--
-- This function will suggest to use a bloom filter of prime size.
-- These theoretically behave the best.
-- Also it won't suggest to use over 63 hash functions,
-- because CheapHashes work only up to 63 functions.
--
-- Note that while creating bloom filters with extremely small (or
-- even negative) capacity is allowed for convenience, it is often
-- not very useful.
-- This function will always suggest to use at least 61 bits.
--
-- >>> safeSuggestSizing 10000 0.01
-- Right (99317,7)
--
safeSuggestSizing ::
       Int              -- ^ expected maximum capacity
    -> Double           -- ^ desired false positive rate (0 < /e/ < 1)
    -> Either String (Word64, Int)
safeSuggestSizing :: Int -> Double -> Either String (Word64, Int)
safeSuggestSizing (Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral -> Double
capacity) Double
errRate
    | Double
capacity Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
0                = (Word64, Int) -> Either String (Word64, Int)
forall a b. b -> Either a b
Right (Word64
61, Int
1)
    | Double
errRate Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
<= Double
0 Bool -> Bool -> Bool
|| Double
errRate Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>= Double
1 = String -> Either String (Word64, Int)
forall a b. a -> Either a b
Left String
"invalid error rate"
    | Bool
otherwise                    = [Word64] -> Either String (Word64, Int)
forall {a}. Integral a => [a] -> Either String (a, Int)
pickSize [Word64]
primes
  where
    bits   :: Double
    hashes :: Int
    (Double
bits, Int
hashes) = [(Double, Int)] -> (Double, Int)
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum
        [ (Double -> Double -> Double -> Double
filterSize Double
capacity Double
errRate Double
k, Int
k')
        | Int
k' <- [Int
1 .. Int
63]
        , let k :: Double
k = Int -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
k'
        ]

    pickSize :: [a] -> Either String (a, Int)
pickSize [] = String -> Either String (a, Int)
forall a b. a -> Either a b
Left String
"capacity too large"
    pickSize (a
w:[a]
ws)
        | a -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
w Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>= Double
bits = (a, Int) -> Either String (a, Int)
forall a b. b -> Either a b
Right (a
w, Int
hashes)
        | Bool
otherwise              = [a] -> Either String (a, Int)
pickSize [a]
ws

-- primes from around 2^6 to 2^40, with five primes per "octave",
--
-- * 61, 73, 83, 97, 109
-- * 127, 139, ...
-- * 257, 293, ...
-- * ...
--
-- The third next element is around 1.5 times larger:
-- 97/63 = 1.59; 109/73 = 1.49; 127/83 = 1.52
--
-- The approximate growth rate is 1.14.
--
primes :: [Word64]
primes :: [Word64]
primes =
    [Word64
61,Word64
73,Word64
83,Word64
97,Word64
109,Word64
127,Word64
139,Word64
167,Word64
193,Word64
223,Word64
257,Word64
293,Word64
337,Word64
389,Word64
443,Word64
509,Word64
587,Word64
673,Word64
773
    ,Word64
887,Word64
1021,Word64
1171,Word64
1327,Word64
1553,Word64
1783,Word64
2039,Word64
2351,Word64
2699,Word64
3089,Word64
3559,Word64
4093,Word64
4703,Word64
5399,Word64
6203
    ,Word64
7129,Word64
8191,Word64
9403,Word64
10799,Word64
12413,Word64
14251,Word64
16381,Word64
18803,Word64
21617,Word64
24821,Word64
28517,Word64
32749
    ,Word64
37633,Word64
43237,Word64
49667,Word64
57047,Word64
65537,Word64
75277,Word64
86467,Word64
99317,Word64
114089,Word64
131071,Word64
150559
    ,Word64
172933,Word64
198659,Word64
228203,Word64
262139,Word64
301123,Word64
345889,Word64
397337,Word64
456409,Word64
524287,Word64
602233
    ,Word64
691799,Word64
794669,Word64
912839,Word64
1048573,Word64
1204493,Word64
1383593,Word64
1589333,Word64
1825673,Word64
2097143
    ,Word64
2408993,Word64
2767201,Word64
3178667,Word64
3651341,Word64
4194301,Word64
4817977,Word64
5534413,Word64
6357353,Word64
7302683
    ,Word64
8388593,Word64
9635981,Word64
11068817,Word64
12714749,Word64
14605411,Word64
16777213,Word64
19271957,Word64
22137667
    ,Word64
25429499,Word64
29210821,Word64
33554393,Word64
38543917,Word64
44275331,Word64
50858999,Word64
58421653,Word64
67108859
    ,Word64
77087833,Word64
88550677,Word64
101718013,Word64
116843297,Word64
134217689,Word64
154175663,Word64
177101321
    ,Word64
203436029,Word64
233686637,Word64
268435399,Word64
308351357,Word64
354202703,Word64
406872031,Word64
467373223
    ,Word64
536870909,Word64
616702721,Word64
708405407,Word64
813744131,Word64
934746541,Word64
1073741789,Word64
1233405449
    ,Word64
1416810797,Word64
1627488229,Word64
1869493097,Word64
2147483647,Word64
2466810893,Word64
2833621657
    ,Word64
3254976541,Word64
3738986131,Word64
4294967291,Word64
4933621843,Word64
5667243317,Word64
6509953069
    ,Word64
7477972391,Word64
8589934583,Word64
9867243719,Word64
11334486629,Word64
13019906153,Word64
14955944737
    ,Word64
17179869143,Word64
19734487471,Word64
22668973277,Word64
26039812297,Word64
29911889569,Word64
34359738337
    ,Word64
39468974939,Word64
45337946581,Word64
52079624657,Word64
59823779149,Word64
68719476731,Word64
78937949837
    ,Word64
90675893137,Word64
104159249321,Word64
119647558343,Word64
137438953447,Word64
157875899707
    ,Word64
181351786333,Word64
208318498651,Word64
239295116717,Word64
274877906899,Word64
315751799521
    ,Word64
362703572681,Word64
416636997289,Word64
478590233419,Word64
549755813881,Word64
631503599063
    ,Word64
725407145383,Word64
833273994643,Word64
957180466901,Word64
1099511627689
    ]

-- | Behaves as 'safeSuggestSizing', but calls 'error' if given
-- invalid or out-of-range inputs.
suggestSizing :: Int            -- ^ expected maximum capacity
              -> Double         -- ^ desired false positive rate (0 < /e/ < 1)
              -> (Word64, Int)
suggestSizing :: Int -> Double -> (Word64, Int)
suggestSizing Int
cap Double
errs = (String -> (Word64, Int))
-> ((Word64, Int) -> (Word64, Int))
-> Either String (Word64, Int)
-> (Word64, Int)
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either String -> (Word64, Int)
forall {c}. String -> c
fatal (Word64, Int) -> (Word64, Int)
forall a. a -> a
id (Int -> Double -> Either String (Word64, Int)
safeSuggestSizing Int
cap Double
errs)
  where fatal :: String -> c
fatal = String -> c
forall a. HasCallStack => String -> a
error (String -> c) -> (String -> String) -> String -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (String
"Data.BloomFilter.Util.suggestSizing: " ++)

-- $example
--
-- This example reads a dictionary file containing one word per line,
-- constructs a Bloom filter with a 1% false positive rate, and
-- spellchecks its standard input.  Like the Unix @spell@ command, it
-- prints each word that it does not recognize.
--
-- @
-- import Data.Maybe (mapMaybe)
-- import qualified Data.BloomFilter.Easy as B
--
-- main = do
--   filt \<- B.'easyList' 0.01 . words \<$> readFile "\/usr\/share\/dict\/words"
--   let check word | B.'B.elem' word filt  = Nothing
--                  | otherwise         = Just word
--   interact (unlines . mapMaybe check . lines)
-- @