;; Bloom filter structure and public procedures.
(define-struct bloom-filter-s (bitmap hfuncs))

(define (make-bloom-filter hash-functions)
  (make-bloom-filter-s (make-hash-table) hash-functions))

(define (bloom-filter-add! self key)
  (let ((hashes (make-hashes key (bloom-filter-s-hfuncs self)))
    (bitmap (bloom-filter-s-bitmap self)))
    (let loop ()
      (if (not (null? hashes))
      (begin
        (hash-table-put! bitmap (car hashes) 1)
        (set! hashes (cdr hashes))
        (loop))))))

(define (bloom-filter-contains? self key)
  (let ((hashes (make-hashes key (bloom-filter-s-hfuncs self)))
    (bitmap (bloom-filter-s-bitmap self))
    (contains #f))
    (let loop ()
      (if (and (not (null? hashes))
           (not contains))
      (begin
        (if (= (hash-table-get bitmap (car hashes) 0) 1)
        (set! contains #t))
        (set! hashes (cdr hashes))
        (loop))))
    contains))

(define (make-hash-functions seeds-salts)
  (let ((funcs (list)))
    (let loop ()
      (if (not (null? seeds-salts))
      (begin
        (set! funcs
          (append funcs
              (list
               (make-hash-function (car (car seeds-salts))
                           (car (cdr (car seeds-salts)))))))
        (set! seeds-salts (cdr seeds-salts))
        (loop))))
    funcs))

;; :~

;; Helpers
(define (make-hash-function seed salt)
  (let ((hash seed)
    (func null))
    (set! func (lambda (s)
         (if (null? s)
             hash
             (begin
               (if (string? s)
               (begin
                 (set! hash seed)
                 (set! s (string->list s))))
               (set! hash (+ (* salt (char->integer (car s)))
                     (func (cdr s))))
               hash))))
    func))

(define (make-hashes key hash-funcs)
  (let ((hashes (list)))
    (let loop ()
      (if (not (null? hash-funcs))
      (begin
        (set! hashes (append hashes (list ((car hash-funcs) key))))
        (set! hash-funcs (cdr hash-funcs))
        (loop))))
    hashes))

;; :~

;; Test

;; To create a new bloom-filter, pass in a list of hash-functions.
;; Each hash-function is represented by a pair of it's
;; seed and salt values.
(define bloom (make-bloom-filter (make-hash-functions (list '(7 31)
							    '(3 41)
							    '(1 51)))))

;; Our bloom filter works with strings.
;; Here, we map a few strings to the bloom-filter.
(bloom-filter-add! bloom "Alonzo Church")
(bloom-filter-add! bloom "Fred Brooks")
(bloom-filter-add! bloom "Alan Kay")
(bloom-filter-add! bloom "Dennis Ritchie")
(bloom-filter-add! bloom "Donald Knuth")

;; We search if a string is a member of the current set.
(printf "~a~n" (bloom-filter-contains? bloom "Fred Brooks")) ;; #t
(printf "~a~n" (bloom-filter-contains? bloom "nemo")) ;; #f
(printf "~a~n" (bloom-filter-contains? bloom "Alan Kay")) ;; #t
(printf "~a~n" (bloom-filter-contains? bloom "alan kay")) ;; #f