 ! Copyright (C) 2009 Alec Berryman.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays bit-arrays fry kernel layouts locals math math.functions
-multiline sequences ;
+USING: accessors arrays bit-arrays fry infix kernel layouts locals math
+math.functions multiline sequences ;
 IN: bloom-filters
 
 FROM: math.ranges => [1,b] [0,b) ;


<PRIVATE

! number-bits = -(n-objects * n-hashes) / ln(1 - error-rate ^ 1/n-hashes)
:: bits-to-satisfy-error-rate ( n-hashes error-rate n-objects -- size )
    n-objects n-hashes * -1 *
    1 error-rate 1 n-hashes / ^ - log
    /
    ceiling >integer ; ! should check that it's below max-array-capacity

! 100 hashes ought to be enough for anybody.
: n-hashes-range ( -- range )

! See "Bloom Filters in Probabilistic Verification" by Peter C. Dillinger and
! Panagiotis Manolios, section 5.2, "Enhanced Double Hashing":
! http://www.cc.gatech.edu/~manolios/research/bloom-filters-verification.html
:: enhanced-double-hash ( index hash0 hash1 array-size -- hash )
    [infix hash0 + (index * hash1) + ((pow(index, 3) - index) / 6) infix]
    array-size mod ;

: enhanced-double-hashes ( n hash0 hash1 array-size -- seq )
