[Boost-commit] svn:boost r72830 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail

Subject: [Boost-commit] svn:boost r72830 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail
From: cpp.cabrera_at_[hidden]
Date: 2011-06-30 20:36:23

Author: alejandro
Date: 2011-06-30 20:36:22 EDT (Thu, 30 Jun 2011)
New Revision: 72830
URL: http://svn.boost.org/trac/boost/changeset/72830

Log:
Implemented dynamic Bloom filter. Test suite demonstrates correct behavior. Added dynamic_hash_apply to apply_hash.hpp.
Text files modified: 
   sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp |     9 +++++-                                  
   sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp     |    54 ++++++++++++++++++++++----------------- 
   2 files changed, 37 insertions(+), 26 deletions(-)

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp	(original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp	2011-06-30 20:36:22 EDT (Thu, 30 Jun 2011)
@@ -13,6 +13,7 @@
 #ifndef BOOST_BLOOM_FILTER_APPLY_HASH_HPP
 #define BOOST_BLOOM_FILTER_APPLY_HASH_HPP
 
+#include <bitset>
 #include <boost/dynamic_bitset.hpp>
 #include <boost/mpl/at.hpp>
 
@@ -20,7 +21,9 @@
   namespace bloom_filter {
     namespace detail {
 
-      // static bloom filter
+      /*************************************************************************
+       *                          static bloom filter
+       ************************************************************************/
       template <size_t N,
                 typename T,
                 size_t Size,
@@ -60,7 +63,9 @@
         }
       };
 
-      // dynamic bloom filter
+      /*************************************************************************
+       *                        dynamic bloom filter
+       ************************************************************************/
       template <size_t N,
                 typename T,
                 class HashFunctions,

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp	(original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp	2011-06-30 20:36:22 EDT (Thu, 30 Jun 2011)
@@ -18,6 +18,7 @@
  *        of hash function application. 
  */
 #include <cmath>
+#include <cassert>
 
 #include <boost/config.hpp>
 #include <boost/mpl/vector.hpp>
@@ -27,10 +28,6 @@
 #include <boost/bloom_filter/detail/apply_hash.hpp>
 #include <boost/bloom_filter/hash/default.hpp>
 
-#ifndef BOOST_NO_0X_HDR_INITIALIZER_LIST
-#include <initializer_list>
-#endif 
-
 namespace boost {
   namespace bloom_filter {
     template <typename T,
@@ -53,21 +50,15 @@
       explicit dynamic_bloom_filter(const size_t bit_capacity) : bits(bit_capacity) {}
       
       template <typename InputIterator>
-      dynamic_bloom_filter(const InputIterator start, 
-			   const InputIterator end) {
+      dynamic_bloom_filter(const size_t bit_capacity,
+			   const InputIterator start, 
+			   const InputIterator end) 
+	: bits(bit_capacity)
+      {
         for (InputIterator i = start; i != end; ++i)
           this->insert(*i);
       }
 
-#ifndef BOOST_NO_0X_HDR_INITIALIZER_LIST
-      dynamic_bloom_filter(const std::initializer_list<T>& ilist) {
-	typedef typename std::initializer_list<T>::const_iterator citer;
-	for (citer i = ilist.begin(), end = ilist.end(); i != end; ++i) {
-	  this->insert(*i);
-	}
-      }
-#endif
-
       // query functions
       static BOOST_CONSTEXPR size_t num_hash_functions() {
         return mpl::size<HashFunctions>::value;
@@ -76,7 +67,7 @@
       double false_positive_rate() const {
         const double n = static_cast<double>(this->bits.count());
         static const double k = static_cast<double>(num_hash_functions());
-        static const double m = static_cast<double>(Size);
+        static const double m = static_cast<double>(this->bits.size());
         static const double e =
           2.718281828459045235360287471352662497757247093699959574966;
         return std::pow(1 - std::pow(e, -k * n / m), k);
@@ -86,6 +77,10 @@
         return this->bits.count();
       };
 
+      size_t bit_capacity() const {
+	return this->bits.size();
+      }
+
       bool empty() const {
         return this->count() == 0;
       }
@@ -116,8 +111,8 @@
         this->bits.reset();
       }
 
-      void swap(bloom_filter& other) {
-	bloom_filter tmp = other;
+      void swap(dynamic_bloom_filter& other) {
+	dynamic_bloom_filter tmp = other;
         other = *this;
         *this = tmp;
       }
@@ -127,15 +122,24 @@
         bits.resize(bit_capacity);
       }
 
-      friend bool operator==(const bloom_filter&, const bloom_filter&);
-      friend bool operator!=(const bloom_filter&, const bloom_filter&);
+      template <typename _T, typename _HashFunctions, 
+		typename _Block, typename _Allocator>
+      friend bool operator==(const dynamic_bloom_filter<_T, _HashFunctions, _Block, _Allocator>&, 
+			     const dynamic_bloom_filter<_T, _HashFunctions, _Block, _Allocator>&);
+
+      template <typename _T, typename _HashFunctions, 
+		typename _Block, typename _Allocator>
+      friend bool operator!=(const dynamic_bloom_filter<_T, _HashFunctions, _Block, _Allocator>&, 
+			     const dynamic_bloom_filter<_T, _HashFunctions, _Block, _Allocator>&);
 
-      bloom_filter& operator|=(const bloom_filter& rhs) {
+      dynamic_bloom_filter& operator|=(const dynamic_bloom_filter& rhs) {
+	assert(this->bit_capacity() == rhs.bit_capacity());
         this->bits |= rhs.bits;
         return *this;
       }
 
-      bloom_filter& operator&=(const bloom_filter& rhs) {
+      dynamic_bloom_filter& operator&=(const dynamic_bloom_filter& rhs) {
+	assert(this->bit_capacity() == rhs.bit_capacity());
         this->bits &= rhs.bits;
         return *this;
       }
@@ -154,7 +158,8 @@
                                          HashFunctions, 
                                          Block, Allocator>& rhs)
     {
-      bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
+      assert(lhs.bit_capacity() == rhs.bit_capacity());
+      dynamic_bloom_filter<T, HashFunctions, Block, Allocator> ret(lhs);
       ret |= rhs;
       return ret;
     }
@@ -169,7 +174,8 @@
                                          HashFunctions, 
                                          Block, Allocator>& rhs)
     {
-      bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
+      assert(lhs.bit_capacity() == rhs.bit_capacity());
+      dynamic_bloom_filter<T, HashFunctions, Block, Allocator> ret(lhs);
       ret &= rhs;
       return ret;
     }