# bloomfilter.tcl --
#
#       Simple Bloom Filter implementation based on the Guava BloomFilter implementation:
#       https://github.com/google/guava/blob/master/guava/src/com/google/common/hash/BloomFilterStrategies.java
#       Copyright (C) 2011 The Guava Authors
#
# Copyright (c) 2015 Neil Madden.
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
# in compliance with the License. You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software distributed under the License
# is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
# or implied. See the License for the specific language governing permissions and limitations under
# the License.
# 

package require Tcl         8.5
package require sha1        2.0
package provide bloomfilter 0.1

namespace eval ::bloomfilter {
    namespace export create add mightcontain stats
    namespace ensemble create

    # Creates an empty bloom filter with the given capacity and false positive probability (fpp).
    #
    #   capacity    the expected number of elements to be inserted into the bloom filter
    #   fpp         the desired probability of false positives from the mightcontain method
    #
    proc create {capacity fpp} {
        set bitSize [optimalNumBits $capacity $fpp]
        set numHashes [optimalNumHashes $capacity $bitSize]
        
        return [dict create capacity $capacity fpp $fpp size $bitSize hashes $numHashes bits 0 ones 0]
    }

    # Adds an element to the bloom filter, returning a new bloom filter with the added element.
    #
    #   bf          the bloom filter to add an element to.
    #   element     the element to add.
    proc add {bf element} {
        # Hashing algorithm is based on Guava's MURMUR128_MITZ_64 strategy, which is itself 
        # based on the paper "Less Hashing, Same Performance: Building a Better Bloom Filter" by
        # Adam Kirsch and Michael Mitzenmacher. The basic idea is to use two hashes (or, in
        # this cases, one large hash split into two) and then just combine them to generate
        # additional hashes as required.
        set hash [expr 0x[sha1::sha1 -hex $element]]
        set hash1 [expr {$hash         & 0xFFFFFFFFFFFFFFFF}]
        set hash2 [expr {($hash >> 64) & 0xFFFFFFFFFFFFFFFF}]

        set numHashes [dict get $bf hashes]
        set size [dict get $bf size]
        set bits [dict get $bf bits]
        
        set newbits 0
        set combinedHash $hash1
        for {set i 0} {$i < $numHashes} {incr i} {
            set index [expr {$combinedHash % $size}]
            incr newbits [expr {$bits & (1<<$index) ? 0 : 1}]
            set bits [expr {$bits | (1 << $index)}]
            incr combinedHash $hash2
        }

        dict set bf bits $bits
        dict incr bf ones $newbits

        return $bf
    }

    # Determines whether this bloom filter *might* contain the given element or not. If the answer
    # is no then the bloom filter definitely does not contain the element, but if the answer is yes,
    # then there is a small probability (bounded by the false positive probability specified when
    # creating the bloom filter) that the element is not actually in the set. If more elements have
    # been inserted into the set than the initial capacity estimate, then the probability of false
    # positives will be significantly higher.
    #
    #   bf          the bloom filter to test this element for membership.
    #   element     the element to check for possible containment in the bloom filter.
    #
    proc mightcontain {bf element} {
        set hash [expr 0x[sha1::sha1 -hex $element]]
        set hash1 [expr {$hash         & 0xFFFFFFFFFFFFFFFF}]
        set hash2 [expr {($hash >> 64) & 0xFFFFFFFFFFFFFFFF}]
        
        set numHashes [dict get $bf hashes]
        set size [dict get $bf size]
        set bits [dict get $bf bits]

        set combinedHash $hash1
        for {set i 0} {$i < $numHashes} {incr i} {
            set index [expr {$combinedHash % $size}]

            if {($bits & (1 << $index)) == 0} {
                return no
            }

            incr combinedHash $hash2
        }

        return yes
    }

    # Returns some stats on the current state of the bloom filter as a dictionary with the following
    # keys:
    #   capacity        the configured capacity of the bloom filter
    #   fpp             a dictionary with two sub-keys:
    #       configured  the original configured false positive probability
    #       expected    the expected false positive probability given the current state
    #   remaining       an estimate of the number of additional elements that can be inserted before
    #                   the bloom filter exceeds the false positive probability
    proc stats bf {
        return [dict create \
            capacity        [dict get $bf capacity] \
            fpp             [dict create configured [dict get $bf fpp] \
                                         expected   [expectedFpp $bf]] \
            remaining       [remainingEstimate $bf]]
    }

    proc expectedFpp bf {
        expr {pow(double([dict get $bf ones]) / double([dict get $bf size]), [dict get $bf hashes])}
    }

    proc cardinality bf {
        # see http://en.wikipedia.org/wiki/Bloom_filter#Approximating_the_number_of_items_in_a_Bloom_filter
        expr {entier(-(([dict get $bf size] * 
            log(1 - [dict get $bf ones]/double([dict get $bf size]))) / [dict get $bf hashes]))}
    }

    proc remainingEstimate bf {
        expr {[dict get $bf capacity] - [cardinality $bf]}
    }


    # Calculates the optimal number of bits needed to store $capacity elements at $fpp probability of false positives
    proc optimalNumBits {capacity fpp} {
        expr {entier(-$capacity * log($fpp) / (log(2) * log(2)))}
    }

    # Calculates the optimal number of hashes for storing $capacity elements in a bitvector of $bitSize size
    proc optimalNumHashes {capacity bitSize} {
        expr {max(1, round(double($bitSize) / $capacity * log(2)))}
    }
}