 : 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.

! 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 math.order multiline sequences
sequences.private typed ;
FROM: math.ranges => [1,b] ;

IN: bloom-filters

/*

TODO:

- The false positive rate is 10x what it should be, based on
  informal testing.  Better object hashes or a better method of
  generating extra hash codes would help.  Another way is to
  increase the number of bits used.

  - Try something smarter than the bitwise complement for a
    second hash code.

  - http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
    makes a case for http://murmurhash.googlepages.com/ instead
    of enhanced double-hashing.

  - Be sure to adjust the test that asserts the number of false
    positives isn't unreasonable.

- Could round bits up to next power of two and use wrap instead
  of mod.  This would cost a lot of bits on 32-bit platforms,
  though, and limit the bit-array to 8MB.

- Should allow user to specify the hash codes, either as inputs
  to enhanced double hashing or for direct use.

- Support for serialization.

- Wrappers for combining filters.

- Should we signal an error when inserting past the number of
  objects the filter is sized for?  The filter will continue to
  work, just not very well.

*/

