#ifndef BLOOM_FILTER_20090608_0
#define BLOOM_FILTER_20090608_0

// Copyright 2009 (c) Dean Michael Berris <mikhailberis@gmail.com>
// 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 <bitset>
#include <boost/array.hpp>
#include <boost/function.hpp>

#include <boost/type_traits/add_const.hpp>
#include <boost/type_traits/add_reference.hpp>

namespace boost {

    template <size_t M, size_t K, class Input>
    struct bloom_filter {
        private:
            std::bitset<M> bit_set;
            array<function<size_t(Input)>, K> hash_array;

            typedef typename add_const<typename add_reference<Input>::type>::type const_ref;

        public:
            typedef std::bitset<M> bitset_type;
            static size_t const size = M;
            static size_t const functions = K;

            explicit bloom_filter(
                    array<function<size_t(Input)>, K> const & hash_functions
                    ) :
                hash_array(hash_functions) {}

            bloom_filter(bloom_filter const & other) :
                bit_set(other.bit_set), hash_array(other.hash_array) {}

            bloom_filter & operator=(bloom_filter rhs) {
                rhs.swap(*this);
                return *this;
            }

            bloom_filter & swap(bloom_filter & other) {
                using std::swap;
                swap(bit_set, other.bit_set);
                swap(hash_array, other.hash_array);
            }

            void insert(const_ref input) {
                for(size_t k = 0; k < K; ++k)
                    bit_set[hash_array[k](input)] = 1;
            }

            bool contains(const_ref input) {
                bool result = true;
                for(size_t k = 0; k < K && result; ++k)
                    result = result && bit_set[hash_array[k](input)];
                return result;
            }

            void reset() {
                bit_set.reset();
            }

            bitset_type state() const { return bit_set; }
    };
}

#endif