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;
}