[Boost-commit] svn:boost r73639 - sandbox/bloom_filter/trunk/boost/bloom_filter

Subject: [Boost-commit] svn:boost r73639 - sandbox/bloom_filter/trunk/boost/bloom_filter
From: cpp.cabrera_at_[hidden]
Date: 2011-08-10 05:30:27

Author: alejandro
Date: 2011-08-10 05:30:26 EDT (Wed, 10 Aug 2011)
New Revision: 73639
URL: http://svn.boost.org/trac/boost/changeset/73639

Log:
New data structure, minor upgrade:

  twohash_dynamic_basic_bloom_filter:
    - Implemented twohash_dynamic_basic_bloom_filter.

  twohash_basic_bloom_filter:
    - Removed redundant code
Added:
   sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_basic_bloom_filter.hpp   (contents, props changed)
Text files modified: 
   sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp |    23 -----------------------                 
   1 files changed, 0 insertions(+), 23 deletions(-)

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp	(original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp	2011-08-10 05:30:26 EDT (Wed, 10 Aug 2011)
@@ -17,8 +17,6 @@
 #include <bitset>
 
 #include <boost/config.hpp>
-#include <boost/mpl/vector.hpp>
-#include <boost/mpl/size.hpp>
 
 #include <boost/bloom_filter/hash/default.hpp>
 #include <boost/bloom_filter/hash/murmurhash3.hpp>
@@ -181,27 +179,6 @@
                                                   _HashFunction1,
                                                   _HashFunction2,
                                                   _ExtensionFunction>&);
-
-      template<class _T, size_t _Size, size_t _HashValues,
-	       size_t _ExpectedInsertionCount,
-	       class _HashFunction1,
-	       class _HashFunction2,
-	       class _ExtensionFunction>
-      friend bool
-      operator!=(const twohash_basic_bloom_filter<_T, 
-						  _Size,
-		                                  _HashValues, 
-						  _ExpectedInsertionCount,
-						  _HashFunction1,
-						  _HashFunction2,
-						  _ExtensionFunction>&,
-		 const twohash_basic_bloom_filter<_T, 
-						  _Size,
-		                                  _HashValues,
-						  _ExpectedInsertionCount,
-						  _HashFunction1,
-						  _HashFunction2,
-						  _ExtensionFunction>&);
       
     private:
       bitset_type bits;

Added: sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_basic_bloom_filter.hpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_basic_bloom_filter.hpp	2011-08-10 05:30:26 EDT (Wed, 10 Aug 2011)
@@ -0,0 +1,358 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (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_TWOHASH_DYNAMIC_BASIC_BLOOM_FILTER_HPP
+#define BOOST_BLOOM_FILTER_TWOHASH_DYNAMIC_BASIC_BLOOM_FILTER_HPP 1
+
+#include <cmath>
+
+#include <boost/config.hpp>
+#include <boost/dynamic_bitset.hpp>
+
+#include <boost/bloom_filter/hash/default.hpp>
+#include <boost/bloom_filter/hash/murmurhash3.hpp>
+#include <boost/bloom_filter/detail/extenders.hpp>
+#include <boost/bloom_filter/detail/twohash_apply_hash.hpp>
+#include <boost/bloom_filter/detail/exceptions.hpp>
+
+namespace boost {
+  namespace bloom_filters {
+    template <typename T,
+	      size_t HashValues = 2,
+	      size_t ExpectedInsertionCount = 0,
+	      class HashFunction1 = boost_hash<T, 0>,
+	      class HashFunction2 = murmurhash3<T>, 
+	      typename ExtensionFunction = detail::square,
+	      typename Block = size_t,
+	      typename Allocator = std::allocator<Block> >// = ???
+    class twohash_dynamic_basic_bloom_filter {
+    public:
+      typedef T value_type;
+      typedef T key_type;
+      typedef Block block_type;
+      typedef Allocator allocator_type;
+      typedef boost::dynamic_bitset<Block, Allocator> bitset_type;
+      typedef HashFunction1 hash_function1_type;
+      typedef HashFunction2 hash_function2_type;
+      typedef ExtensionFunction extension_function_type;
+      typedef twohash_dynamic_basic_bloom_filter<T, 
+						 HashValues,
+						 ExpectedInsertionCount,
+						 HashFunction1,
+						 HashFunction2,
+						 ExtensionFunction,
+						 Block,
+						 Allocator> this_type;
+
+      static const size_t default_size = 32;
+
+    public:
+      //* constructors
+      twohash_dynamic_basic_bloom_filter()
+	: bits(default_size)
+      {
+      }
+
+      explicit twohash_dynamic_basic_bloom_filter(const size_t size)
+	: bits(size)
+      {
+      }
+
+      template <typename InputIterator>
+      twohash_dynamic_basic_bloom_filter(const InputIterator start, 
+				 const InputIterator end)
+	: bits(std::distance(start, end) * 4)
+      {
+	for (InputIterator i = start; i != end; ++i)
+	  this->insert(*i);
+      }
+
+      //* meta-ops
+      size_t bit_capacity() const
+      {
+	return bits.size();
+      }
+
+      static BOOST_CONSTEXPR size_t num_hash_functions()
+      {
+	return HashValues;
+      }
+
+      static BOOST_CONSTEXPR size_t expected_insertion_count()
+      {
+	return ExpectedInsertionCount;
+      }
+
+      double false_positive_rate() const
+      {
+        const double n = static_cast<double>(this->bits.count());
+        static const double k = static_cast<double>(HashValues);
+        static const double m = static_cast<double>(this->bit_capacity());
+        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;
+      }
+
+      //* core ops
+      void insert(const T& t)
+      {
+	detail::twohash_apply_hash<HashValues - 1, 
+				   this_type>::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
+      {
+	return detail::twohash_apply_hash<HashValues - 1, 
+					  this_type>::contains(t, bits);
+      }
+
+      void clear()
+      {
+	this->bits.reset();
+      }
+
+      void swap(twohash_dynamic_basic_bloom_filter& other)
+      {
+	twohash_dynamic_basic_bloom_filter tmp = other;
+	other = *this;
+	*this = tmp;
+      }
+
+      //* pairwise ops
+      twohash_dynamic_basic_bloom_filter& 
+      operator|=(const twohash_dynamic_basic_bloom_filter& rhs)
+      {
+	if (this->bit_capacity() != rhs.bit_capacity())
+	  throw detail::incompatible_size_exception();
+
+	this->bits |= rhs.bits;
+	return *this;
+      }
+
+      twohash_dynamic_basic_bloom_filter& 
+      operator&=(const twohash_dynamic_basic_bloom_filter& rhs)
+      {
+	if (this->bit_capacity() != rhs.bit_capacity())
+	  throw detail::incompatible_size_exception();
+
+	this->bits &= rhs.bits;
+	return *this;
+      }
+
+      template<class _T, size_t _HashValues, 
+	       size_t _ExpectedInsertionCount,
+	       class _HashFunction1,
+	       class _HashFunction2,
+	       class _ExtensionFunction,
+	       typename _Block, class _Allocator>
+      friend bool
+      operator==(const twohash_dynamic_basic_bloom_filter<_T, 
+		                                          _HashValues, 
+						          _ExpectedInsertionCount,
+						          _HashFunction1,
+						          _HashFunction2,
+		                                          _ExtensionFunction,
+		                                          _Block,
+		                                          _Allocator>&,
+		 const twohash_dynamic_basic_bloom_filter<_T, 
+		                                          _HashValues,
+						          _ExpectedInsertionCount,
+						          _HashFunction1,
+						          _HashFunction2,
+		                                          _ExtensionFunction,
+		                                          _Block,
+		                                          _Allocator>&);
+      
+    private:
+      bitset_type bits;
+    };
+
+    //* global ops
+    template<class T, size_t HashValues, 
+	     size_t ExpectedInsertionCount,
+	     class HashFunction1,
+	     class HashFunction2, class ExtensionFunction,
+	     typename Block, class Allocator>
+    bool
+    operator==(const twohash_dynamic_basic_bloom_filter<T, 
+	       	       	       	       	       	        HashValues,
+	                                                ExpectedInsertionCount,
+	                                                HashFunction1,
+	                                                HashFunction2,
+	                                                ExtensionFunction,
+	                                                Block, 
+	                                                Allocator>& lhs,
+	       const twohash_dynamic_basic_bloom_filter<T, 
+	                                        HashValues,
+						ExpectedInsertionCount,
+						HashFunction1,
+						HashFunction2,
+	                                        ExtensionFunction,
+	                                        Block,
+	                                        Allocator>& rhs)
+    {
+	if (lhs.bit_capacity() != rhs.bit_capacity())
+	  throw detail::incompatible_size_exception();
+
+      return lhs.bits == rhs.bits;
+    }
+
+    template<class T, size_t HashValues, 
+	     size_t ExpectedInsertionCount,
+	     class HashFunction1,
+	     class HashFunction2, class ExtensionFunction,
+	     typename Block, class Allocator>
+    bool
+    operator!=(const twohash_dynamic_basic_bloom_filter<T, 
+	       	       	       	       	       	        HashValues,
+	                                                ExpectedInsertionCount,
+	                                                HashFunction1,
+	                                                HashFunction2,
+	                                                ExtensionFunction,
+	                                                Block, 
+	                                                Allocator>& lhs,
+	       const twohash_dynamic_basic_bloom_filter<T, 
+	                                                HashValues,
+						        ExpectedInsertionCount,
+						        HashFunction1,
+						        HashFunction2,
+	                                                ExtensionFunction,
+	                                                Block,
+	                                                Allocator>& rhs)
+    {
+      return !(lhs == rhs);
+    }
+    
+    template<class T, size_t HashValues, 
+	     size_t ExpectedInsertionCount,
+	     class HashFunction1,
+	     class HashFunction2, class ExtensionFunction,
+	     typename Block, class Allocator>
+    twohash_dynamic_basic_bloom_filter<T, 
+				       HashValues,
+				       ExpectedInsertionCount,
+				       HashFunction1, 
+				       HashFunction2, ExtensionFunction,
+				       Block, Allocator>
+    operator|(const twohash_dynamic_basic_bloom_filter<T, 
+	                                               HashValues,
+	                                               ExpectedInsertionCount,
+	                                               HashFunction1,
+	                                               HashFunction2,
+	                                               ExtensionFunction,
+	                                               Block,
+	                                               Allocator>& lhs,
+	      const twohash_dynamic_basic_bloom_filter<T, 
+	                                               HashValues,
+	                                               ExpectedInsertionCount,
+	                                               HashFunction1,
+	                                               HashFunction2,
+	                                               ExtensionFunction,
+	                                               Block,
+	                                               Allocator>& rhs)
+    {
+      twohash_dynamic_basic_bloom_filter<T, HashValues,
+					 ExpectedInsertionCount,
+					 HashFunction1, HashFunction2,
+					 ExtensionFunction,
+					 Block,
+					 Allocator> result(lhs);
+      
+      result |= rhs;
+      return result;
+    }
+
+    template<class T, size_t HashValues, 
+	     size_t ExpectedInsertionCount,
+	     class HashFunction1,
+	     class HashFunction2, class ExtensionFunction,
+	     typename Block, class Allocator>
+    twohash_dynamic_basic_bloom_filter<T, 
+				       HashValues,
+				       ExpectedInsertionCount,
+				       HashFunction1, 
+				       HashFunction2, ExtensionFunction,
+				       Block, Allocator>
+    operator&(const twohash_dynamic_basic_bloom_filter<T, 
+	                                               HashValues,
+	                                               ExpectedInsertionCount,
+	                                               HashFunction1,
+	                                               HashFunction2,
+	                                               ExtensionFunction,
+	                                               Block,
+	                                               Allocator>& lhs,
+	      const twohash_dynamic_basic_bloom_filter<T, 
+	                                               HashValues,
+	                                               ExpectedInsertionCount,
+	                                               HashFunction1,
+	                                               HashFunction2,
+	                                               ExtensionFunction,
+	                                               Block,
+	                                               Allocator>& rhs)
+    {
+      twohash_dynamic_basic_bloom_filter<T, HashValues,
+					 ExpectedInsertionCount,
+					 HashFunction1, HashFunction2,
+					 ExtensionFunction,
+					 Block,
+					 Allocator> result(lhs);
+      
+      result &= rhs;
+      return result;
+    }
+
+    template<class T, size_t Size, size_t HashValues, 
+	     size_t ExpectedInsertionCount, 
+	     class HashFunction1,
+	     class HashFunction2, class ExtensionFunction,
+	     typename Block, class Allocator>
+    void swap(twohash_dynamic_basic_bloom_filter<T, 
+	                                         HashValues,
+	                                         ExpectedInsertionCount,
+	                                         HashFunction1,
+	                                         HashFunction2,
+	                                         ExtensionFunction,
+	                                         Block,
+	                                         Allocator>& lhs,
+	      twohash_dynamic_basic_bloom_filter<T, 
+	                                         HashValues,
+	                                         ExpectedInsertionCount,
+	                                         HashFunction1,
+	                                         HashFunction2,
+	                                         ExtensionFunction,
+	                                         Block,
+	                                         Allocator>& rhs)
+    {
+      return lhs.swap(rhs);
+    }
+  } // namespace bloom_filters
+} // namespace boost
+#endif
+