 ! Copyright (C) 2009 Alec Berryman.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays bit-arrays fry infix kernel layouts locals math
-math.functions multiline sequences ;
+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
-
-FROM: math.ranges => [1,b] ;
-FROM: math.intervals => (a,b) interval-contains? ;
-FROM: sequences => change-nth ;
 
 /*
 
 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.
+- 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.
+  - 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.
+    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.
+  - 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.
+- 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.
+- 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.
+- 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.
 
 */
 

{ 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 ;

