[Boost-commit] svn:boost r53784 - in sandbox/bloom_filter/trunk: boost/bloom_filter boost/bloom_filter/detail libs/bloom_filter/test

Subject: [Boost-commit] svn:boost r53784 - in sandbox/bloom_filter/trunk: boost/bloom_filter boost/bloom_filter/detail libs/bloom_filter/test
From: mikhailberis_at_[hidden]
Date: 2009-06-10 04:03:41

Author: mikhailberis
Date: 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
New Revision: 53784
URL: http://svn.boost.org/trac/boost/changeset/53784

Log:
Changes:
* Making the collection of hash function types a template parameter instead of a number; The requirement on the collection is that it should be a valid Fusion sequence.
* Changing the signature and tests to support the changes to the static_bloom_filter and bloom_filter interfaces.
* Refactoring the insert and contains implementation to a common internals base.
* All static_bloom_filters are now fully equally comparable since the types will contain the hash functions in the signature too.
* The default hash implementation has been changed to use Boost.Hash internally.

Added:
   sandbox/bloom_filter/trunk/boost/bloom_filter/detail/internals.hpp   (contents, props changed)
Text files modified: 
   sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp                                       |    50 ++++++++++---------------               
   sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp                                |    12 ++----                                  
   sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp                                |    77 +++++++++++++++++++++++++-------------- 
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp       |    13 +-----                                  
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp |     4 +-                                      
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp     |     4 -                                       
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp              |     2                                         
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp              |     2                                         
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp                       |    40 +++++++++++---------                    
   9 files changed, 104 insertions(+), 100 deletions(-)

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp	(original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -12,11 +12,23 @@
 
 #include <boost/fusion/algorithm/iteration/for_each.hpp>
 #include <boost/fusion/include/for_each.hpp>
+#include <boost/fusion/container/vector.hpp>
+#include <boost/fusion/include/vector.hpp>
+#include <boost/bloom_filter/detail/internals.hpp>
 
 namespace boost {
 
-    template <class Input, class Sequence, class Block = unsigned char, class Allocator = std::allocator<unsigned char> >
-        struct bloom_filter {
+    template <
+        class Input, 
+        class Sequence = fusion::vector<
+            detail::default_hash<0>,
+            detail::default_hash<1>,
+            detail::default_hash<2>
+                >,
+        class Block = unsigned char, 
+        class Allocator = std::allocator<unsigned char> 
+             >
+        struct bloom_filter : protected detail::bloom_filter_internals<Input, dynamic_bitset<Block,Allocator> > {
             public:
                 typedef dynamic_bitset<Block, Allocator> bitset_type;
 
@@ -25,31 +37,7 @@
                 Sequence hash_functions;
 
                 typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
-
-                struct insert_impl {
-                    bitset_type & bit_set_;
-                    const_ref input_;
-                    insert_impl(bitset_type & bit_set, const_ref input)
-                        : bit_set_(bit_set), input_(input)
-                    {}
-                    template <class F>
-                        void operator()(F const & f) const {
-                            bit_set_[f(input_) % bit_set_.size()] = true;
-                        }
-                };
-
-                struct contains_impl {
-                    bitset_type const & bit_set_;
-                    const_ref input_;
-                    bool & result_;
-                    contains_impl(bitset_type const & bit_set, const_ref input, bool & result)
-                        : bit_set_(bit_set), input_(input), result_(result)
-                    {}
-                    template <class F>
-                        void operator()(F const & f) const {
-                            result_ = result_ && bit_set_[f(input_) % bit_set_.size()];
-                        }
-                };
+                typedef detail::bloom_filter_internals<Input, dynamic_bitset<Block,Allocator> > base;
 
             public:
                 bloom_filter(
@@ -60,17 +48,21 @@
 
                 void insert(const_ref input) {
                     using fusion::for_each;
+                    typedef typename base::insert_impl inserter;
                     for_each(
                             hash_functions, 
-                            insert_impl(bit_set, input));
+                            inserter(bit_set, input)
+                            );
                 }
 
                 bool contains(const_ref input) const {
                     using fusion::for_each;
+                    typedef typename base::contains_impl contains_checker;
                     bool found = true;
                     for_each(
                             hash_functions, 
-                            contains_impl(bit_set, input, found));
+                            contains_checker(bit_set, input, found)
+                            );
                     return found;
                 }
         };

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp	(original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -10,15 +10,11 @@
 
     namespace detail {
 
-        template <class Input>
+        template <size_t Seed = 0>
             struct default_hash {
-                typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
-                size_t seed_;
-                default_hash(size_t seed) 
-                    : seed_(seed) {}
-
-                size_t operator()(const_ref input) const {
-                    size_t seed = seed_;
+                template <class T>
+                size_t operator() (T const & input) const {
+                    size_t seed = Seed;
                     hash_combine(seed, input);
                     return seed;
                 }

Added: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/internals.hpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/internals.hpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -0,0 +1,50 @@
+#ifndef BLOOM_FILTER_INTERNALS_20090610_0
+#define BLOOM_FILTER_INTERNALS_20090610_0
+
+// Copyright 2009 (c) Dean Michael Berris <mikhailberis_at_[hidden]>
+// 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)
+
+namespace boost {
+
+    namespace detail {
+
+        template <class Input, class BitSet>
+            class bloom_filter_internals {
+                protected:
+                    typedef BitSet bitset_type;
+                    typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
+
+                    struct insert_impl {
+                        bitset_type & bit_set_;
+                        const_ref input_;
+                        insert_impl(bitset_type & bit_set, const_ref input)
+                            : bit_set_(bit_set), input_(input)
+                        {}
+                        template <class F>
+                            void operator()(F const & f) const {
+                                bit_set_[f(input_) % bit_set_.size()] = true;
+                            }
+                    };
+
+                    struct contains_impl {
+                        bitset_type const & bit_set_;
+                        const_ref input_;
+                        bool & result_;
+                        contains_impl(bitset_type const & bit_set, const_ref input, bool & result)
+                            : bit_set_(bit_set), input_(input), result_(result)
+                        {}
+                        template <class F>
+                            void operator()(F const & f) const {
+                                result_ = result_ && bit_set_[f(input_) % bit_set_.size()];
+                            }
+                    };
+
+            };
+
+    } // namespace detail
+
+} // namespace boost
+
+#endif

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp	(original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -12,40 +12,57 @@
 
 #include <boost/type_traits/add_const.hpp>
 #include <boost/type_traits/add_reference.hpp>
+#include <boost/fusion/container/vector.hpp>
+#include <boost/fusion/include/vector.hpp>
+#include <boost/fusion/algorithm/iteration/for_each.hpp>
+#include <boost/fusion/include/for_each.hpp>
 #include <boost/bloom_filter/detail/default_hash.hpp>
+#include <boost/bloom_filter/detail/internals.hpp>
 
 namespace boost {
 
-    template <class Input, size_t M, size_t K>
-    struct static_bloom_filter {
+    template <
+        class Input, 
+        size_t M, 
+        class Sequence = fusion::vector<
+            detail::default_hash<0>,
+            detail::default_hash<1>,
+            detail::default_hash<2>
+            >
+        >
+    struct static_bloom_filter : protected detail::bloom_filter_internals<Input, std::bitset<M> > {
         public:
             typedef std::bitset<M> bitset_type;
 
         private:
             bitset_type bit_set;
-            array<function<size_t(Input)>, K> hash_array;
+            Sequence hash_functions;
 
             typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
+            typedef detail::bloom_filter_internals<Input, std::bitset<M> > base;
+
+            struct insert_impl {
+                bitset_type & bit_set_;
+            };
 
         public:
             static size_t const size = M;
-            static size_t const functions = K;
             typedef Input element_type;
 
+            static_bloom_filter(
+                    bitset_type const & initial_state = bitset_type(),
+                    Sequence const & hash_functions = Sequence()) 
+                : bit_set(initial_state), hash_functions(hash_functions)
+            {}
+
             explicit static_bloom_filter(
-                    array<function<size_t(Input)>, K> const & hash_functions
-                    ) :
-                hash_array(hash_functions) {}
-
-            static_bloom_filter(bitset_type const & initial_state = bitset_type()) 
-                : bit_set(initial_state)
-            {
-                for(size_t k = 0; k < K; ++k)
-                    hash_array[k] = detail::default_hash<Input>(k);
-            }
+                    Sequence const & hash_functions
+                    )
+                : bit_set(), hash_functions(hash_functions)
+            {}
 
             static_bloom_filter(static_bloom_filter const & other) :
-                bit_set(other.bit_set), hash_array(other.hash_array) {}
+                bit_set(other.bit_set), hash_functions(other.hash_functions) {}
 
             static_bloom_filter & operator=(static_bloom_filter rhs) {
                 rhs.swap(*this);
@@ -55,20 +72,28 @@
             static_bloom_filter & swap(static_bloom_filter & other) {
                 using std::swap;
                 swap(bit_set, other.bit_set);
-                swap(hash_array, other.hash_array);
+                swap(hash_functions, other.hash_functions);
                 return *this;
             }
 
             void insert(const_ref input) {
-                for(size_t k = 0; k < K; ++k)
-                    bit_set[hash_array[k](input) % M] = 1;
+                using fusion::for_each;
+                typedef typename base::insert_impl inserter;
+                for_each(
+                        hash_functions,
+                        inserter(bit_set, input)
+                        );
             }
 
             bool contains(const_ref input) const {
-                bool result = true;
-                for(size_t k = 0; k < K && result; ++k)
-                    result = result && bit_set[hash_array[k](input) % M];
-                return result;
+                using fusion::for_each;
+                typedef typename base::contains_impl contains_checker;
+                bool found = true;
+                for_each(
+                        hash_functions,
+                        contains_checker(bit_set, input, found)
+                        );
+                return found;
             }
 
             bool operator[](const_ref input) const {
@@ -85,8 +110,6 @@
             }
 
             bool operator== (static_bloom_filter const & other) const {
-                // FIXME For some reason, we cannot compare boost::function instances...
-                // return (hash_array == other.hash_array) && (bit_set == other.bit_set);
                 return bit_set == other.bit_set;
             }
 
@@ -95,10 +118,10 @@
             }
     };
 
-    template <class Input, size_t M, size_t K>
+    template <class Input, size_t M, class Sequence>
         inline void swap(
-                static_bloom_filter<Input, M, K> & left, 
-                static_bloom_filter<Input, M, K> & right) {
+                static_bloom_filter<Input, M, Sequence> & left, 
+                static_bloom_filter<Input, M, Sequence> & right) {
             left.swap(right);
         }
 }

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -12,20 +12,11 @@
 using boost::fusion::tuple;
 using boost::hash_combine;
 
-template <size_t Offset>
-struct hash {
-    template <class T>
-    size_t operator() (T const & element) const {
-        size_t seed = Offset;
-        hash_combine(seed, element);
-        return seed;
-    }
-};
-
 int main(int argc, char * argv[]) {
-    bloom_filter<int, tuple<hash<1>, hash<2>, hash<3> > > bf(2048);
+    bloom_filter<int> bf(2048);
     bf.insert(1);
     assert(bf.contains(1));
+    assert(!bf.contains(2));
     return EXIT_SUCCESS;
 }
 

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -9,9 +9,9 @@
 using boost::static_bloom_filter;
 
 int main(int argc, char * argv[]) {
-    static_bloom_filter<int, 32, 3> filter1;
+    static_bloom_filter<int, 32> filter1;
     filter1.insert(1);
-    static_bloom_filter<int, 32, 3> filter2(filter1.state()); // construct from bitset
+    static_bloom_filter<int, 32> filter2(filter1.state()); // construct from bitset
     assert(filter2.contains(1));
     return EXIT_SUCCESS;
 }

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -6,12 +6,10 @@
 #include <boost/bloom_filter/static_bloom_filter.hpp>
 #include <boost/detail/lightweight_test.hpp>
 
-#define FILTER_SIZE 256
-
 using boost::static_bloom_filter;
 
 int main(int argc, char * argv[]) {
-    typedef static_bloom_filter<uint32_t, FILTER_SIZE, 3> filter_type;
+    typedef static_bloom_filter<uint32_t, 256> filter_type;
     filter_type filter; // default constructed
     filter.insert(1u);
     assert(filter.contains(1u));

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -9,7 +9,7 @@
 using boost::static_bloom_filter;
 
 int main(int argc, char * arg[]) {
-    static_bloom_filter<int, 32, 3> filter1, filter2;
+    static_bloom_filter<int, 32> filter1, filter2;
     assert(filter1 == filter2);
     filter1.insert(1);
     assert(filter1 != filter2);

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -9,7 +9,7 @@
 using boost::static_bloom_filter;
 
 int main(int argc, char * argv[]) {
-    typedef static_bloom_filter<uint32_t, 32, 3> filter_type;
+    typedef static_bloom_filter<uint32_t, 32> filter_type;
     filter_type filter1, filter2;
     filter1.insert(1u);
     filter2.insert(2u);

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp	2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -5,35 +5,39 @@
 
 #include <boost/bloom_filter.hpp>
 #include <boost/detail/lightweight_test.hpp>
+#include <boost/fusion/tuple.hpp>
 
 #define FILTER_SIZE 256
 
-size_t hash1(uint32_t id) {
-    return ((id << 4) | (id >> 4)) % FILTER_SIZE;
-}
-
-size_t hash2(uint32_t id) {
-    return (id * id) % FILTER_SIZE;
-}
-
-size_t hash3(uint32_t id) {
-    return (id * 97) % FILTER_SIZE;
-}
+struct hash1 {
+    size_t operator()(uint32_t id) const {
+        return ((id << 4) | (id >> 4)) % FILTER_SIZE;
+    }
+};
+
+struct hash2 {
+    size_t operator()(uint32_t id) const {
+        return (id * id) % FILTER_SIZE;
+    }
+};
+
+struct hash3 {
+    size_t operator()(uint32_t id) const {
+        return (id * 97) % FILTER_SIZE;
+    }
+};
 
 using std::bitset;
 using std::cout;
 using std::endl;
-using boost::array;
 using boost::function;
 using boost::static_bloom_filter;
+using boost::fusion::tuple;
+using boost::fusion::make_tuple;
 
 int main(int argc, char * argv[]) {
-    array<function<size_t(uint32_t)>, 3> functions;
-    functions[0] = hash1;
-    functions[1] = hash2;
-    functions[2] = hash3;
-    typedef static_bloom_filter<uint32_t, FILTER_SIZE, 3> filter_type;
-    filter_type filter(functions);
+    typedef static_bloom_filter<uint32_t, FILTER_SIZE, tuple<hash1, hash2, hash3> > filter_type;
+    filter_type filter(make_tuple(hash1(), hash2(), hash3()));
     filter_type filter_copy = filter;
     for(uint32_t i = 0; i < 10; ++i) filter.insert(i);
     for(uint32_t i = 0; i < 10; ++i) assert(filter.contains(i));