 : smaller-second ( 2seq 2seq -- 2seq )
     [ [ second ] bi@ <= ] most ;
 
-! If the number of hashes isn't positive, we haven't found anything smaller than the
-! identity configuration.
+! If the number of hashes isn't positive, we haven't found
+! anything smaller than the identity configuration.
 : validate-sizes ( 2seq -- )
     first 0 <= [ capacity-error ] when ;
 
-! The consensus on the tradeoff between increasing the number of bits and
-! increasing the number of hash functions seems to be "go for the smallest
-! number of bits", probably because most implementations just generate one hash
-! value and cheaply mangle it into the number of hashes they need.  I have not
-! seen any usage studies from the implementations that made this tradeoff to
-! support it, and I haven't done my own, but we'll go with it anyway.
+! The consensus on the tradeoff between increasing the number of
+! bits and increasing the number of hash functions seems to be
+! "go for the smallest number of bits", probably because most
+! implementations just generate one hash value and cheaply
+! mangle it into the number of hashes they need.  I have not
+! seen any usage studies from the implementations that made this
+! tradeoff to support it, and I haven't done my own, but we'll
+! go with it anyway.
 !
 : size-bloom-filter ( error-rate number-objects -- number-hashes number-bits )
     [ n-hashes-range identity-configuration ] 2dip

{ current-n-objects fixnum } ;

ERROR: capacity-error ;
ERROR: invalid-error-rate ;
ERROR: invalid-n-objects ;

<PRIVATE

! infix doesn't like ^
: pow ( x y -- z )
    ^ ; inline

:: bits-to-satisfy-error-rate ( hashes error objects -- size )
    [infix -(objects * hashes) / log(1 - pow(error, (1/hashes))) infix]
    ceiling >integer ;

! 100 hashes ought to be enough for anybody.

    dup validate-sizes
    first2 ;

: check-n-objects ( n-objects -- n-objects )
    dup 0 <= [ invalid-n-objects ] when ;

: check-error-rate ( error-rate -- error-rate )
    dup [ 0 after? ] [ 1 before? ] bi and
    [ invalid-error-rate ] unless ;

PRIVATE>

: <bloom-filter> ( error-rate number-objects -- bloom-filter )
    [ check-error-rate ] [ check-n-objects ] bi*
    [ size-bloom-filter <bit-array> ] keep
    0 ! initially empty
    bloom-filter boa ;

<PRIVATE

! 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 -- hash )
    hash0 index * hash1 + index 3 ^ index - 6 /i + ;

: enhanced-double-hashes ( hash0 hash1 n -- seq )
    -rot '[ _ _ enhanced-double-hash ] { } map-integers ;

! Make sure it's a fixnum here to speed up double-hashing.
: hashcodes-from-hashcode ( hash0 -- hash0 hash1 )
    dup most-positive-fixnum bitxor ;

: hashcodes-from-object ( obj -- n n )
    hashcode abs hashcodes-from-hashcode ;

TYPED: set-indices ( indices: array bit-array: bit-array -- )
    [ t ] 2dip [ set-nth-unsafe ] curry with each ; inline

TYPED: increment-n-objects ( bloom-filter: bloom-filter -- )
    [ 1 + ] change-current-n-objects drop ; inline

TYPED: n-hashes-and-length ( bloom-filter: bloom-filter -- n-hashes length )
    [ n-hashes>> ] [ bits>> length ] bi ;

TYPED: relevant-indices ( value bloom-filter: bloom-filter -- indices )
    [ hashcodes-from-object ] [ n-hashes-and-length ] bi*
    [ enhanced-double-hashes ] dip '[ _ mod ] map ;

