Subject: [Boost-commit] svn:boost r73254 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail hash
From: cpp.cabrera_at_[hidden]
Date: 2011-07-20 05:36:50
Author: alejandro
Date: 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
New Revision: 73254
URL: http://svn.boost.org/trac/boost/changeset/73254
Log:
A series of file, class, and namespace renames.
renamed: namespace bloom_filter -> namespace bloom_filters.
renamed: class bloom_filter -> class basic_bloom_filter
renamed: bloom.hpp -> basic_bloom_filter.hpp
renamed: counting_bloom.hpp -> counting_bloom_filter.hpp
renamed: dynamic_bloom.hpp -> dynamic_bloom_filter.hpp
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp (contents, props changed)
- copied, changed from r72941, /sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp (contents, props changed)
- copied, changed from r72941, /sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp (contents, props changed)
- copied, changed from r72941, /sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp
Removed:
sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp | 60 ++++++++++++++++++++--------------------
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp | 6 ++--
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp | 2
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp | 2
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp | 6 ++--
sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp | 2
sandbox/bloom_filter/trunk/boost/bloom_filter/hash/murmurhash3.hpp | 2
7 files changed, 40 insertions(+), 40 deletions(-)
Copied: sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp (from r72941, /sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp)
==============================================================================
--- /sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
@@ -10,8 +10,8 @@
//
//////////////////////////////////////////////////////////////////////////////
-#ifndef BOOST_BLOOM_FILTER_BLOOM_HPP
-#define BOOST_BLOOM_FILTER_BLOOM_HPP 1
+#ifndef BOOST_BLOOM_FILTER_BLOOM_FILTER_HPP
+#define BOOST_BLOOM_FILTER_BLOOM_FILTER_HPP 1
/**
* \author Alejandro Cabrera
* \brief A generic Bloom filter providing compile-time unrolling
@@ -32,27 +32,27 @@
#endif
namespace boost {
- namespace bloom_filter {
+ namespace bloom_filters {
template <typename T,
size_t Size,
class HashFunctions = mpl::vector<boost_hash<T, 3> > >
- class bloom_filter {
+ class basic_bloom_filter {
public:
typedef T value_type;
typedef T key_type;
typedef HashFunctions hash_function_type;
public:
- bloom_filter() {}
+ basic_bloom_filter() {}
template <typename InputIterator>
- bloom_filter(const InputIterator start, const InputIterator end) {
+ basic_bloom_filter(const InputIterator start, const InputIterator end) {
for (InputIterator i = start; i != end; ++i)
this->insert(*i);
}
#ifndef BOOST_NO_0X_HDR_INITIALIZER_LIST
- bloom_filter(const std::initializer_list<T>& ilist) {
+ basic_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);
@@ -106,31 +106,31 @@
this->bits.reset();
}
- void swap(bloom_filter& other) {
- bloom_filter tmp = other;
+ void swap(basic_bloom_filter& other) {
+ basic_bloom_filter tmp = other;
other = *this;
*this = tmp;
}
- bloom_filter& operator|=(const bloom_filter& rhs) {
+ basic_bloom_filter& operator|=(const basic_bloom_filter& rhs) {
this->bits |= rhs.bits;
return *this;
}
- bloom_filter& operator&=(const bloom_filter& rhs) {
+ basic_bloom_filter& operator&=(const basic_bloom_filter& rhs) {
this->bits &= rhs.bits;
return *this;
}
template<class _T, size_t _Size, class _HashFunctions>
friend bool
- operator==(const bloom_filter<_T, _Size, _HashFunctions>&,
- const bloom_filter<_T, _Size, _HashFunctions>&);
+ operator==(const basic_bloom_filter<_T, _Size, _HashFunctions>&,
+ const basic_bloom_filter<_T, _Size, _HashFunctions>&);
template<class _T, size_t _Size, class _HashFunctions>
friend bool
- operator!=(const bloom_filter<_T, _Size, _HashFunctions>&,
- const bloom_filter<_T, _Size, _HashFunctions>&);
+ operator!=(const basic_bloom_filter<_T, _Size, _HashFunctions>&,
+ const basic_bloom_filter<_T, _Size, _HashFunctions>&);
private:
std::bitset<Size> bits;
@@ -138,47 +138,47 @@
template<class _T, size_t _Size, class _HashFunctions>
bool
- operator==(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
+ operator==(const basic_bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ const basic_bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
return (lhs.bits == rhs.bits);
}
template<class _T, size_t _Size, class _HashFunctions>
bool
- operator!=(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
+ operator!=(const basic_bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ const basic_bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
return !(lhs == rhs);
}
template<class _T, size_t _Size, class _HashFunctions>
- bloom_filter<_T, _Size, _HashFunctions>
- operator|(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
+ basic_bloom_filter<_T, _Size, _HashFunctions>
+ operator|(const basic_bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ const basic_bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
- bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
+ basic_bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
ret |= rhs;
return ret;
}
template<class _T, size_t _Size, class _HashFunctions>
- bloom_filter<_T, _Size, _HashFunctions>
- operator&(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
+ basic_bloom_filter<_T, _Size, _HashFunctions>
+ operator&(const basic_bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ const basic_bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
- bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
+ basic_bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
ret &= rhs;
return ret;
}
template<class _T, size_t _Size, class _HashFunctions>
void
- swap(bloom_filter<_T, _Size, _HashFunctions>& lhs,
- bloom_filter<_T, _Size, _HashFunctions>& rhs)
+ swap(basic_bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ basic_bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
lhs.swap(rhs);
}
- } // namespace bloom_filter
+ } // namespace bloom_filters
} // namespace boost
#endif
Deleted: sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
+++ (empty file)
@@ -1,184 +0,0 @@
-//////////////////////////////////////////////////////////////////////////////
-//
-// (C) Copyright Alejandro Cabrera 2011.
-// 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)
-//
-// See http://www.boost.org/libs/bloom_filter for documentation.
-//
-//////////////////////////////////////////////////////////////////////////////
-
-#ifndef BOOST_BLOOM_FILTER_BLOOM_HPP
-#define BOOST_BLOOM_FILTER_BLOOM_HPP 1
-/**
- * \author Alejandro Cabrera
- * \brief A generic Bloom filter providing compile-time unrolling
- * of hash function application.
- */
-#include <cmath>
-#include <bitset>
-
-#include <boost/config.hpp>
-#include <boost/mpl/vector.hpp>
-#include <boost/mpl/size.hpp>
-
-#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,
- size_t Size,
- class HashFunctions = mpl::vector<boost_hash<T, 3> > >
- class bloom_filter {
- public:
- typedef T value_type;
- typedef T key_type;
- typedef HashFunctions hash_function_type;
-
- public:
- bloom_filter() {}
-
- template <typename InputIterator>
- bloom_filter(const InputIterator start, const InputIterator end) {
- for (InputIterator i = start; i != end; ++i)
- this->insert(*i);
- }
-
-#ifndef BOOST_NO_0X_HDR_INITIALIZER_LIST
- 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
-
- static BOOST_CONSTEXPR size_t bit_capacity() {
- return Size;
- }
-
- static BOOST_CONSTEXPR size_t num_hash_functions() {
- return mpl::size<HashFunctions>::value;
- };
-
- 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 e =
- 2.718281828459045235360287471352662497757247093699959574966;
- return std::pow(1 - std::pow(e, -k * n / m), k);
- };
-
- size_t count() const {
- return this->bits.count();
- };
-
- bool empty() const {
- return this->count() == 0;
- }
-
- void insert(const T& t) {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::apply_hash<N, T, Size, HashFunctions>::insert(t, bits);
- }
-
- template <typename InputIterator>
- void insert(const InputIterator start, const InputIterator end) {
- for (InputIterator i = start; i != end; ++i) {
- this->insert(*i);
- }
- }
-
- bool probably_contains(const T& t) const {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::apply_hash<N, T, Size, HashFunctions>::contains(t, bits);
- }
-
- void clear() {
- this->bits.reset();
- }
-
- void swap(bloom_filter& other) {
- bloom_filter tmp = other;
- other = *this;
- *this = tmp;
- }
-
- bloom_filter& operator|=(const bloom_filter& rhs) {
- this->bits |= rhs.bits;
- return *this;
- }
-
- bloom_filter& operator&=(const bloom_filter& rhs) {
- this->bits &= rhs.bits;
- return *this;
- }
-
- template<class _T, size_t _Size, class _HashFunctions>
- friend bool
- operator==(const bloom_filter<_T, _Size, _HashFunctions>&,
- const bloom_filter<_T, _Size, _HashFunctions>&);
-
- template<class _T, size_t _Size, class _HashFunctions>
- friend bool
- operator!=(const bloom_filter<_T, _Size, _HashFunctions>&,
- const bloom_filter<_T, _Size, _HashFunctions>&);
-
- private:
- std::bitset<Size> bits;
- };
-
- template<class _T, size_t _Size, class _HashFunctions>
- bool
- operator==(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
- {
- return (lhs.bits == rhs.bits);
- }
-
- template<class _T, size_t _Size, class _HashFunctions>
- bool
- operator!=(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
- {
- return !(lhs == rhs);
- }
-
- template<class _T, size_t _Size, class _HashFunctions>
- bloom_filter<_T, _Size, _HashFunctions>
- operator|(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
- {
- bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
- ret |= rhs;
- return ret;
- }
-
- template<class _T, size_t _Size, class _HashFunctions>
- bloom_filter<_T, _Size, _HashFunctions>
- operator&(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
- const bloom_filter<_T, _Size, _HashFunctions>& rhs)
- {
- bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
- ret &= rhs;
- return ret;
- }
-
- template<class _T, size_t _Size, class _HashFunctions>
- void
- swap(bloom_filter<_T, _Size, _HashFunctions>& lhs,
- bloom_filter<_T, _Size, _HashFunctions>& rhs)
- {
- lhs.swap(rhs);
- }
- } // namespace bloom_filter
-} // namespace boost
-#endif
Deleted: sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
+++ (empty file)
@@ -1,316 +0,0 @@
-//////////////////////////////////////////////////////////////////////////////
-//
-// (C) Copyright Alejandro Cabrera 2011.
-// 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)
-//
-// See http://www.boost.org/libs/bloom_filter for documentation.
-//
-//////////////////////////////////////////////////////////////////////////////
-
-#ifndef BOOST_BLOOM_FILTER_COUNTING_BLOOM_HPP
-#define BOOST_BLOOM_FILTER_COUNTING_BLOOM_HPP 1
-/**
- * \author Alejandro Cabrera
- * \brief A generic counting Bloom filter providing compile-time unrolling
- * of hash function application.
- */
-#include <cmath>
-#include <iostream>
-
-#include <boost/array.hpp>
-#include <boost/config.hpp>
-#include <boost/mpl/vector.hpp>
-#include <boost/mpl/size.hpp>
-#include <boost/static_assert.hpp>
-#include <boost/type_traits/is_integral.hpp>
-#include <boost/type_traits/is_unsigned.hpp>
-
-#include <boost/bloom_filter/detail/counting_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,
- size_t NumBins,
- size_t BitsPerBin = 4,
- class HashFunctions = mpl::vector<boost_hash<T, 3> >,
- typename Block = size_t>
- class counting_bloom_filter {
-
- // Block needs to be an integral type
- BOOST_STATIC_ASSERT( boost::is_integral<Block>::value == true);
-
- // Block needs to be an unsigned type
- BOOST_STATIC_ASSERT( boost::is_unsigned<Block>::value == true);
-
- // it doesn't make sense to ever support using a BitsPerBin value larger
- // than the number of bits per Block. In that case, the user shouldn't
- // be using a Bloom filter to represent their data.
- BOOST_STATIC_ASSERT( (BitsPerBin <= (sizeof(Block) * 8) ) );
-
- // because of the nature of this implementation, the Bloom filter
- // can have internal fragmentation if the calculation for
- // bins_per_slot has a remainder. The severity of the internal
- // fragmentation is equal to the remainder * the number of slots.
- // this check prevents internal fragmentation
- BOOST_STATIC_ASSERT( ((sizeof(Block) * 8) % BitsPerBin) == 0);
-
- // a slot is one element position in the array
- // a bin is a segment of a slot
- static const size_t slot_bits = sizeof(Block) * 8;
- static const size_t bins_per_slot = slot_bits / BitsPerBin;
- static const size_t bin_bits = NumBins * BitsPerBin;
- static const size_t array_size = bin_bits / slot_bits + 1;
- static const size_t effective_num_bins = array_size * bins_per_slot;
- static const size_t mask =
- static_cast<Block>(0 - 1) >> (slot_bits - BitsPerBin);
-
- private:
- typedef boost::array<Block, array_size> bucket_type;
- typedef typename bucket_type::iterator bucket_iterator;
- typedef typename bucket_type::const_iterator bucket_const_iterator;
-
- public:
- typedef T value_type;
- typedef T key_type;
- typedef HashFunctions hash_function_type;
- typedef Block block_type;
-
- public:
- counting_bloom_filter()
- {
- this->clear();
- }
-
- template <typename InputIterator>
- counting_bloom_filter(const InputIterator start,
- const InputIterator end) {
- this->clear();
-
- for (InputIterator i = start; i != end; ++i)
- this->insert(*i);
- }
-
-#ifndef BOOST_NO_0X_HDR_INITIALIZER_LIST
- counting_bloom_filter(const std::initializer_list<T>& ilist) {
- this->clear();
-
- typedef typename std::initializer_list<T>::const_iterator citer;
- for (citer i = ilist.begin(), end = ilist.end(); i != end; ++i) {
- this->insert(*i);
- }
- }
-#endif
-
- static BOOST_CONSTEXPR size_t bit_capacity() {
- return NumBins * BitsPerBin;
- }
-
- static BOOST_CONSTEXPR size_t num_hash_functions() {
- return mpl::size<HashFunctions>::value;
- };
-
- double false_positive_rate() const {
- const double n = static_cast<double>(this->count());
- static const double k = static_cast<double>(num_hash_functions());
- static const double m = static_cast<double>(NumBins);
- static const double e =
- 2.718281828459045235360287471352662497757247093699959574966;
- return std::pow(1 - std::pow(e, -k * n / m), k);
- };
-
- // returns the number of bins that have at least 1 bit set
- size_t count() const {
- size_t ret = 0;
-
- /*
- std::cout << "Num Bins: " << NumBins << "\n"
- << "Bins Per Slot: " << bins_per_slot << "\n"
- << "Bits Per Bin: " << BitsPerBin << "\n"
- << "Array Size: " << array_size << "\n";
- */
-
- for (bucket_const_iterator i = this->bits.begin(),
- end = this->bits.end();
- i != end; ++i) {
- for (size_t bin = 0; bin < bins_per_slot; ++bin) {
- size_t offset_bits = bin * BitsPerBin;
- size_t target_bits = (*i >> offset_bits) & mask;
-
- /*
- std::cout << "(count) targeting pos: " << std::distance(i, end) - 1
- << " with offset: " << offset_bits
- << " and bin: " << bin
- << " with slot value: " << *i
- << " and bin value: " << target_bits << "\n";
- */
-
- if (target_bits > 0)
- ++ret;
- }
- }
-
- return ret;
- };
-
- bool empty() const {
- return this->count() == 0;
- }
-
- void insert(const T& t) {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::counting_apply_hash<N, T, NumBins,
- BitsPerBin, HashFunctions,
- Block, array_size,
- bins_per_slot>::insert(t, this->bits);
- }
-
- template <typename InputIterator>
- void insert(const InputIterator start, const InputIterator end) {
- for (InputIterator i = start; i != end; ++i) {
- this->insert(*i);
- }
- }
-
- void remove(const T& t) {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::counting_apply_hash<N, T, NumBins,
- BitsPerBin, HashFunctions,
- Block, array_size,
- bins_per_slot>::remove(t, this->bits);
- }
-
- template <typename InputIterator>
- void remove(const InputIterator start, const InputIterator end) {
- for (InputIterator i = start; i != end; ++i) {
- this->remove(*i);
- }
- }
-
- bool probably_contains(const T& t) const {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::counting_apply_hash<N, T, NumBins,
- BitsPerBin, HashFunctions,
- Block, array_size,
- bins_per_slot>::contains(t, this->bits);
- }
-
- void clear() {
- for (bucket_iterator i = bits.begin(), end = bits.end();
- i != end; ++i) {
- *i = 0;
- }
- }
-
- void swap(counting_bloom_filter& other) {
- counting_bloom_filter tmp = other;
- other = *this;
- *this = tmp;
- }
-
- counting_bloom_filter& operator|=(const counting_bloom_filter& rhs)
- {
- return *this;
- }
-
- counting_bloom_filter& operator&=(const counting_bloom_filter& rhs)
- {
- return *this;
- }
-
- // equality comparison operators
- template <typename _T, size_t _Bins, size_t _BitsPerBin,
- typename _HashFns, typename _Block>
- friend bool
- operator==(const counting_bloom_filter<_T, _Bins, _BitsPerBin,
- _HashFns, _Block>& lhs,
- const counting_bloom_filter<_T, _Bins, _BitsPerBin,
- _HashFns, _Block>& rhs);
-
- template <typename _T, size_t _Bins, size_t _BitsPerBin,
- typename _HashFns, typename _Block>
- friend bool
- operator!=(const counting_bloom_filter<_T, _Bins, _BitsPerBin,
- _HashFns, _Block>& lhs,
- const counting_bloom_filter<_T, _Bins, _BitsPerBin,
- _HashFns, _Block>& rhs);
-
-
- private:
- bucket_type bits;
- };
-
- // union
- template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
- typename Block>
- counting_bloom_filter<T, NumBins, BitsPerBin, HashFunctions, Block>
- operator|(const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& lhs,
- const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs)
- {
- counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block> ret(lhs);
- ret |= rhs;
- return ret;
- }
-
- // intersection
- template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
- typename Block>
- counting_bloom_filter<T, NumBins, BitsPerBin, HashFunctions, Block>
- operator&(const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& lhs,
- const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs)
- {
- counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block> ret(lhs);
- ret &= rhs;
- return ret;
- }
-
- template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
- typename Block>
- void
- swap(counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& lhs,
- counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs)
-
- {
- lhs.swap(rhs);
- }
-
- template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
- typename Block>
- bool
- operator==(const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& lhs,
- const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs)
- {
- return (lhs.bits == rhs.bits);
- }
-
- template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
- typename Block>
- bool
- operator!=(const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& lhs,
- const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs)
- {
- return !(lhs == rhs);
- }
-
- } // namespace bloom_filter
-} // namespace boost
-#endif
Copied: sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp (from r72941, /sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp)
==============================================================================
--- /sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
@@ -10,8 +10,8 @@
//
//////////////////////////////////////////////////////////////////////////////
-#ifndef BOOST_BLOOM_FILTER_COUNTING_BLOOM_HPP
-#define BOOST_BLOOM_FILTER_COUNTING_BLOOM_HPP 1
+#ifndef BOOST_BLOOM_FILTER_COUNTING_BLOOM_FILTER_HPP
+#define BOOST_BLOOM_FILTER_COUNTING_BLOOM_FILTER_HPP 1
/**
* \author Alejandro Cabrera
* \brief A generic counting Bloom filter providing compile-time unrolling
@@ -36,7 +36,7 @@
#endif
namespace boost {
- namespace bloom_filter {
+ namespace bloom_filters {
template <typename T,
size_t NumBins,
size_t BitsPerBin = 4,
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-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
@@ -18,7 +18,7 @@
#include <boost/mpl/at.hpp>
namespace boost {
- namespace bloom_filter {
+ namespace bloom_filters {
namespace detail {
/*************************************************************************
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
@@ -19,7 +19,7 @@
#include <boost/mpl/at.hpp>
namespace boost {
- namespace bloom_filter {
+ namespace bloom_filters {
namespace detail {
/*************************************************************************
Deleted: sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
+++ (empty file)
@@ -1,230 +0,0 @@
-//////////////////////////////////////////////////////////////////////////////
-//
-// (C) Copyright Alejandro Cabrera 2011.
-// 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)
-//
-// See http://www.boost.org/libs/bloom_filter for documentation.
-//
-//////////////////////////////////////////////////////////////////////////////
-
-#ifndef BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_HPP
-#define BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_HPP 1
-/**
- * \author Alejandro Cabrera
- * \brief A generic Bloom filter providing compile-time unrolling
- * of hash function application.
- */
-#include <cmath>
-#include <cassert>
-
-#include <boost/config.hpp>
-#include <boost/mpl/vector.hpp>
-#include <boost/mpl/size.hpp>
-#include <boost/dynamic_bitset.hpp>
-
-#include <boost/bloom_filter/detail/apply_hash.hpp>
-#include <boost/bloom_filter/hash/default.hpp>
-
-namespace boost {
- namespace bloom_filter {
- template <typename T,
- class HashFunctions = mpl::vector<boost_hash<T, 3> >,
- class Block = size_t,
- class Allocator = std::allocator<Block> >
- class dynamic_bloom_filter {
- public:
- typedef T value_type;
- typedef T key_type;
- typedef HashFunctions hash_function_type;
- typedef Block block_type;
- typedef Allocator allocator_type;
-
- public:
-
- // constructors
- dynamic_bloom_filter() {}
-
- explicit dynamic_bloom_filter(const size_t bit_capacity) : bits(bit_capacity) {}
-
- template <typename InputIterator>
- 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);
- }
-
- // query functions
- static BOOST_CONSTEXPR size_t num_hash_functions() {
- return mpl::size<HashFunctions>::value;
- };
-
- 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>(this->bits.size());
- static const double e =
- 2.718281828459045235360287471352662497757247093699959574966;
- return std::pow(1 - std::pow(e, -k * n / m), k);
- };
-
- size_t count() const {
- return this->bits.count();
- };
-
- size_t bit_capacity() const {
- return this->bits.size();
- }
-
- bool empty() const {
- return this->count() == 0;
- }
-
- // core operations
- void insert(const T& t) {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::dynamic_apply_hash<N, T, HashFunctions, Block, Allocator>::
- insert(t, bits, bits.size());
- }
-
- template <typename InputIterator>
- void insert(const InputIterator start, const InputIterator end) {
- for (InputIterator i = start; i != end; ++i) {
- this->insert(*i);
- }
- }
-
- bool probably_contains(const T& t) const {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::
- dynamic_apply_hash<N, T, HashFunctions, Block, Allocator>::
- contains(t, bits, bits.size());
- }
-
- // auxilliary operations
- void clear() {
- this->bits.reset();
- }
-
- void swap(dynamic_bloom_filter& other) {
- dynamic_bloom_filter tmp = other;
- other = *this;
- *this = tmp;
- }
-
- void resize(const size_t new_capacity) {
- bits.clear();
- bits.resize(new_capacity);
- }
-
- 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>&);
-
- dynamic_bloom_filter& operator|=(const dynamic_bloom_filter& rhs) {
- assert(this->bit_capacity() == rhs.bit_capacity());
- this->bits |= rhs.bits;
- return *this;
- }
-
- dynamic_bloom_filter& operator&=(const dynamic_bloom_filter& rhs) {
- assert(this->bit_capacity() == rhs.bit_capacity());
- this->bits &= rhs.bits;
- return *this;
- }
-
- private:
- dynamic_bitset<block_type, allocator_type> bits;
- };
-
- template<class T, class HashFunctions,
- class Block, class Allocator>
- dynamic_bloom_filter<T, HashFunctions, Block, Allocator>
- operator|(const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
- {
- assert(lhs.bit_capacity() == rhs.bit_capacity());
- dynamic_bloom_filter<T, HashFunctions, Block, Allocator> ret(lhs);
- ret |= rhs;
- return ret;
- }
-
- template<class T, class HashFunctions,
- class Block, class Allocator>
- dynamic_bloom_filter<T, HashFunctions, Block, Allocator>
- operator&(const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
- {
- assert(lhs.bit_capacity() == rhs.bit_capacity());
- dynamic_bloom_filter<T, HashFunctions, Block, Allocator> ret(lhs);
- ret &= rhs;
- return ret;
- }
-
-
- template<class T, class HashFunctions,
- class Block, class Allocator>
- bool
- operator==(const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
- {
- return lhs.bits == rhs.bits;
- }
-
- template<class T, class HashFunctions,
- class Block, class Allocator>
- bool
- operator!=(const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
- {
- return !(lhs == rhs);
- }
-
- template<class T, class HashFunctions,
- class Block, class Allocator>
- void
- swap(dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
- {
- lhs.swap(rhs);
- }
- } // namespace bloom_filter
-} // namespace boost
-#endif
Copied: sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp (from r72941, /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_filter.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
@@ -10,8 +10,8 @@
//
//////////////////////////////////////////////////////////////////////////////
-#ifndef BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_HPP
-#define BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_HPP 1
+#ifndef BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_FILTER_HPP
+#define BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_FILTER_HPP 1
/**
* \author Alejandro Cabrera
* \brief A generic Bloom filter providing compile-time unrolling
@@ -29,7 +29,7 @@
#include <boost/bloom_filter/hash/default.hpp>
namespace boost {
- namespace bloom_filter {
+ namespace bloom_filters {
template <typename T,
class HashFunctions = mpl::vector<boost_hash<T, 3> >,
class Block = size_t,
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
@@ -19,7 +19,7 @@
#include <boost/functional/hash.hpp>
namespace boost {
- namespace bloom_filter {
+ namespace bloom_filters {
template <typename T, size_t Seed>
struct boost_hash {
size_t operator()(const T& t) {
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/hash/murmurhash3.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/hash/murmurhash3.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/hash/murmurhash3.hpp 2011-07-20 05:36:48 EDT (Wed, 20 Jul 2011)
@@ -45,7 +45,7 @@
#include <boost/cstdint.hpp>
namespace boost {
- namespace hash {
+ namespace bloom_filters {
// forward declarations
namespace detail {