// Copyright 2009 (c) Milosz Marian HULBOJ <mhulboj@hulboj.org>
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#include <boost/cstdint.hpp>
#include <boost/bloom_filter.hpp>
#include <boost/fusion/tuple.hpp>

#include <boost/tr1/unordered_set.hpp>
#include <cstdlib>
#include <iostream>

#define BOOST_TEST_MAIN
#include <boost/test/unit_test.hpp>

template<typename filter_type>
struct tester
{
    double operator()(std::size_t unique_element_count, std::size_t test_size = 10000000)
    {
	std::srand(1234);

	using boost::fusion::tuple;
	using boost::fusion::make_tuple;
	
	filter_type filter;
    
	typedef std::tr1::unordered_set<typename filter_type::element_type> set_type;
	set_type set;

	std::size_t count = 0;
	while(count != unique_element_count)
	{
	    boost::uint32_t foo = std::rand();
	    if(set.count(foo))
		continue;
	    filter.insert(foo);
	    set.insert(foo);
	    ++count;
	}
    
	// Check for false negatives:
	for(typename set_type::const_iterator it=set.begin(); it!=set.end(); ++it)
	{
	    assert(filter.contains(*it));
	}
    
	// Evaluate the False-Positive-Ratio
	std::size_t fp_count = 0;
	count = 0;
	while(count != test_size)
	{
	    boost::uint32_t foo = std::rand();
	    if(set.count(foo))
		continue; // This number belongs to the set
	    // Check for False-Positive
	    if(filter.contains(foo))
		++fp_count;
	    ++count;
	}
	return fp_count/static_cast<double>(count);
    }
};

BOOST_AUTO_TEST_CASE( test001 )
{
    /*
     * TODO: For the given size of the bloom filter and for the given
     * expected number of unique values to be stored, one should
     * choose the optimal number of hash functions. False-Positive Ratio
     * should be close to the theoretical value if good hash functions
     * have been used.
     */
    typedef boost::static_bloom_filter<boost::uint32_t, 400000 > filter_type;
    std::cout << tester<filter_type>()(100000) << std::endl;
    std::cout << tester<filter_type>()(50000) << std::endl;
}