[Boost-commit] svn:boost r53741 - in sandbox/bloom_filter: . branches tags trunk trunk/boost trunk/libs trunk/libs/bloom_filter trunk/libs/bloom_filter/test

Subject: [Boost-commit] svn:boost r53741 - in sandbox/bloom_filter: . branches tags trunk trunk/boost trunk/libs trunk/libs/bloom_filter trunk/libs/bloom_filter/test
From: mikhailberis_at_[hidden]
Date: 2009-06-08 06:35:16

Author: mikhailberis
Date: 2009-06-08 06:35:15 EDT (Mon, 08 Jun 2009)
New Revision: 53741
URL: http://svn.boost.org/trac/boost/changeset/53741

Log:
Adding initial version of bloom_filter implementation.
Added:
   sandbox/bloom_filter/
   sandbox/bloom_filter/branches/
   sandbox/bloom_filter/tags/
   sandbox/bloom_filter/trunk/
   sandbox/bloom_filter/trunk/boost/
   sandbox/bloom_filter/trunk/boost/bloom_filter.hpp   (contents, props changed)
   sandbox/bloom_filter/trunk/libs/
   sandbox/bloom_filter/trunk/libs/bloom_filter/
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2   (contents, props changed)
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter.cpp   (contents, props changed)

Added: sandbox/bloom_filter/trunk/boost/bloom_filter.hpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter.hpp	2009-06-08 06:35:15 EDT (Mon, 08 Jun 2009)
@@ -0,0 +1,79 @@
+#ifndef BLOOM_FILTER_20090608_0
+#define BLOOM_FILTER_20090608_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)
+
+#include <bitset>
+#include <boost/array.hpp>
+#include <boost/function.hpp>
+
+#include <boost/type_traits/add_const.hpp>
+#include <boost/type_traits/add_reference.hpp>
+
+namespace boost {
+
+    template <class Input, size_t M, size_t K>
+    struct bloom_filter {
+        private:
+            std::bitset<M> bit_set;
+            array<function<size_t(Input)>, K> hash_array;
+
+            typedef typename add_const<typename add_reference<Input>::type>::type const_ref;
+
+        public:
+            typedef std::bitset<M> bitset_type;
+            static size_t const size = M;
+            static size_t const functions = K;
+
+            explicit bloom_filter(
+                    array<function<size_t(Input)>, K> const & hash_functions
+                    ) :
+                hash_array(hash_functions) {}
+
+            bloom_filter(bloom_filter const & other) :
+                bit_set(other.bit_set), hash_array(other.hash_array) {}
+
+            bloom_filter & operator=(bloom_filter rhs) {
+                rhs.swap(*this);
+                return *this;
+            }
+
+            bloom_filter & swap(bloom_filter & other) {
+                using std::swap;
+                swap(bit_set, other.bit_set);
+                swap(hash_array, other.hash_array);
+                return *this;
+            }
+
+            void insert(const_ref input) {
+                for(size_t k = 0; k < K; ++k)
+                    bit_set[hash_array[k](input)] = 1;
+            }
+
+            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)];
+                return result;
+            }
+
+            bool operator[](const_ref input) const {
+                return contains(input);
+            }
+
+            bloom_filter & clear() {
+                bit_set.reset();
+                return *this;
+            }
+
+            bitset_type const & state() const { 
+                return bit_set; 
+            }
+    };
+}
+
+#endif
+

Added: sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2	2009-06-08 06:35:15 EDT (Mon, 08 Jun 2009)
@@ -0,0 +1,5 @@
+
+project :
+    [ run bloom_filter ]
+    ;
+

Added: sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter.cpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter.cpp	2009-06-08 06:35:15 EDT (Mon, 08 Jun 2009)
@@ -0,0 +1,50 @@
+// 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)
+
+#include <bitset>
+#include <cassert>
+#include <iostream>
+#include "bloom_filter.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;
+}
+
+using std::bitset;
+using std::cout;
+using std::endl;
+using boost::array;
+using boost::function;
+using boost::bloom_filter;
+
+int main(int argc, char * argv[]) {
+    array<function<size_t(uint32_t)>, 3> functions;
+    functions[0] = hash1;
+    functions[1] = hash2;
+    functions[2] = hash3;
+    typedef bloom_filter<uint32_t, FILTER_SIZE, 3> filter_type;
+    filter_type filter(functions);
+    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));
+    filter_type::bitset_type bit_set = filter.state();
+    for(uint32_t i = 0; i < filter_type::size ; ++i)
+        cout << (bit_set[i] ? '1' : '0');
+    cout << endl;
+    // assignment test
+    filter_copy = filter;
+    return EXIT_SUCCESS;
+}
+