[Boost-commit] svn:boost r73500 - sandbox/bloom_filter/trunk/libs/bloom_filter/test

Subject: [Boost-commit] svn:boost r73500 - sandbox/bloom_filter/trunk/libs/bloom_filter/test
From: cpp.cabrera_at_[hidden]
Date: 2011-08-03 04:17:48

Author: alejandro
Date: 2011-08-03 04:17:47 EDT (Wed, 03 Aug 2011)
New Revision: 73500
URL: http://svn.boost.org/trac/boost/changeset/73500

Log:
Greatly expanded counting Bloom filter tests:

- countMulti test now checks for correct behavior on all valid
  bit sizes.
- Added test for various Block types. Checks that data structure
  compiles in all cases.
- Added tests for all valid bits per bin sizes.
- Added test for false positive rate.
- Added test to ensure bin_overflow_exception is thrown for
  default data structure.
- Added tests for union and intersect operations.
Text files modified: 
   sandbox/bloom_filter/trunk/libs/bloom_filter/test/counting_bloom-pass.cpp |   244 ++++++++++++++++++++++++++++++--------- 
   1 files changed, 185 insertions(+), 59 deletions(-)

Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/counting_bloom-pass.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/counting_bloom-pass.cpp	(original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/counting_bloom-pass.cpp	2011-08-03 04:17:47 EDT (Wed, 03 Aug 2011)
@@ -12,7 +12,6 @@
 
 #define BOOST_TEST_DYN_LINK 1
 #define BOOST_TEST_MODULE "Boost Bloom Filter" 1
-#include <iostream>
 
 #include <boost/bloom_filter/counting_bloom_filter.hpp>
 #include <boost/test/unit_test.hpp>
@@ -20,11 +19,39 @@
 
 #include <boost/bloom_filter/detail/exceptions.hpp>
 
+#include <boost/cstdint.hpp>
+
 using boost::bloom_filters::counting_bloom_filter;
 using boost::bloom_filters::detail::bin_underflow_exception;
 using boost::bloom_filters::detail::bin_overflow_exception;
 using boost::bloom_filters::boost_hash;
 
+BOOST_AUTO_TEST_CASE(allBitsPerBinCompile)
+{
+  counting_bloom_filter<size_t, 2, 1> bloom1;
+  counting_bloom_filter<size_t, 2, 2> bloom2;
+  counting_bloom_filter<size_t, 2, 4> bloom4;
+  counting_bloom_filter<size_t, 2, 8> bloom8;
+  counting_bloom_filter<size_t, 2, 16> bloom16;
+  counting_bloom_filter<size_t, 2, 32> bloom32;
+}
+
+BOOST_AUTO_TEST_CASE(allReasonableBlockTypesCompile)
+{
+  typedef boost::mpl::vector<boost_hash<int, 0> > default_hash;
+
+  counting_bloom_filter<int, 2, 2, default_hash, unsigned char> a;
+  counting_bloom_filter<int, 2, 2, default_hash, unsigned short> b;
+  counting_bloom_filter<int, 2, 2, default_hash, unsigned int> c;
+  counting_bloom_filter<int, 2, 2, default_hash, unsigned long> d;
+  counting_bloom_filter<int, 2, 2, default_hash, size_t> e;
+
+  counting_bloom_filter<int, 2, 2, default_hash, uint8_t> aa;
+  counting_bloom_filter<int, 2, 2, default_hash, uint16_t> ab;
+  counting_bloom_filter<int, 2, 2, default_hash, uint32_t> ac;
+  counting_bloom_filter<int, 2, 2, default_hash, uintmax_t> ad;
+}
+
 BOOST_AUTO_TEST_CASE(defaultConstructor) {
   typedef boost::mpl::vector<
     boost_hash<int, 13>,
@@ -48,33 +75,76 @@
   BOOST_CHECK_EQUAL(bloom.count(), 0ul);
 }
 
+#include <iostream>
+
 BOOST_AUTO_TEST_CASE(countMulti)
 {
-  counting_bloom_filter<int, 100> bloom;
+  counting_bloom_filter<int, 100> bloom_default;
+  counting_bloom_filter<int, 100, 1> bloom1;
+  counting_bloom_filter<int, 100, 2> bloom2;
+  counting_bloom_filter<int, 100, 8> bloom8;
+  counting_bloom_filter<int, 100, 16> bloom16;
+  counting_bloom_filter<int, 100, 32> bloom32;
 
   for (size_t i = 0; i < 100; ++i) {
-    bloom.insert(i);
+    bloom_default.insert(i);
+    bloom1.insert(i);
+    bloom2.insert(i);
+    bloom8.insert(i);
+    bloom16.insert(i);
+    bloom32.insert(i);
   }
 
-  BOOST_CHECK_EQUAL(bloom.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom_default.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom1.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom2.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom8.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom16.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom32.count(), 100ul);
 
   for (size_t i = 0; i < 100; ++i) {
-    bloom.insert(i);
+    bloom_default.insert(i);
+    bloom2.insert(i);
+    bloom8.insert(i);
+    bloom16.insert(i);
+    bloom32.insert(i);
   }
 
-  BOOST_CHECK_EQUAL(bloom.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom_default.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom2.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom8.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom16.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom32.count(), 100ul);
 
   for (size_t i = 0; i < 100; ++i) {
-    bloom.remove(i);
+    bloom_default.remove(i);
+    bloom2.remove(i);
+    bloom8.remove(i);
+    bloom16.remove(i);
+    bloom32.remove(i);
   }
 
-  BOOST_CHECK_EQUAL(bloom.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom_default.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom2.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom8.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom16.count(), 100ul);
+  BOOST_CHECK_EQUAL(bloom32.count(), 100ul);
 
   for (size_t i = 0; i < 100; ++i) {
-    bloom.remove(i);
+    bloom_default.remove(i);
+    bloom1.remove(i);
+    bloom2.remove(i);
+    bloom8.remove(i);
+    bloom16.remove(i);
+    bloom32.remove(i);
   }
 
-  BOOST_CHECK_EQUAL(bloom.count(), 0ul);
+  BOOST_CHECK_EQUAL(bloom_default.count(), 0ul);
+  BOOST_CHECK_EQUAL(bloom1.count(), 0ul);
+  BOOST_CHECK_EQUAL(bloom2.count(), 0ul);
+  BOOST_CHECK_EQUAL(bloom8.count(), 0ul);
+  BOOST_CHECK_EQUAL(bloom16.count(), 0ul);
+  BOOST_CHECK_EQUAL(bloom32.count(), 0ul);
 }
 
 BOOST_AUTO_TEST_CASE(rangeConstructor) {
@@ -122,9 +192,12 @@
   counting_bloom_filter<size_t, 256> bloom_256;
   counting_bloom_filter<size_t, 2048> bloom_2048;
   
-  BOOST_CHECK_EQUAL(bloom_8.bit_capacity(), 8ul * 4ul);
-  BOOST_CHECK_EQUAL(bloom_256.bit_capacity(), 256ul * 4ul);
-  BOOST_CHECK_EQUAL(bloom_2048.bit_capacity(), 2048ul * 4ul);
+  BOOST_CHECK_EQUAL(bloom_8.bit_capacity(), 
+		    8ul * bloom_8.bits_per_bin());
+  BOOST_CHECK_EQUAL(bloom_256.bit_capacity(), 
+		    256ul * bloom_256.bits_per_bin());
+  BOOST_CHECK_EQUAL(bloom_2048.bit_capacity(), 
+		    2048ul * bloom_2048.bits_per_bin());
 }
 
 BOOST_AUTO_TEST_CASE(empty) {
@@ -156,7 +229,6 @@
   BOOST_CHECK_EQUAL(bloom_7.num_hash_functions(), 7ul);
 }
 
-/*
 BOOST_AUTO_TEST_CASE(falsePositiveRate) {
   counting_bloom_filter<size_t, 64> bloom;
 
@@ -180,13 +252,12 @@
   bloom.insert(6);
   BOOST_CHECK_CLOSE(bloom.false_positive_rate(), 0.089491, .01);
 
-  for (size_t i = 7; i < 5000; ++i)
+  for (size_t i = 7; i < 128; ++i)
     bloom.insert(i);
   
   BOOST_CHECK_GE(bloom.false_positive_rate(), 0.6);
   BOOST_CHECK_LE(bloom.false_positive_rate(), 1.0);
 }
-*/
 
 BOOST_AUTO_TEST_CASE(probably_contains) {
   counting_bloom_filter<size_t, 2> bloom;
@@ -230,7 +301,7 @@
   BOOST_CHECK_EQUAL(bloom.probably_contains(1), true);
 }
 
-BOOST_AUTO_TEST_CASE(insertUnderflowExceptionThrown) {
+BOOST_AUTO_TEST_CASE(removeUnderflowExceptionThrown) {
   counting_bloom_filter<size_t, 2, 1> bloom;
   bool exception_occurred = false;
 
@@ -246,6 +317,24 @@
   BOOST_CHECK_EQUAL(bloom.probably_contains(1), false);
 }
 
+BOOST_AUTO_TEST_CASE(insertOverflowException4bit)
+{
+  counting_bloom_filter<size_t, 2> bloom;
+  bool exception_occurred = false;
+
+  try {
+    for (size_t i = 0; i < (1ul << bloom.bits_per_bin()); ++i)
+      bloom.insert(1);
+  }
+
+  catch (bin_overflow_exception e) {
+    exception_occurred = true;
+  }
+
+  BOOST_CHECK_EQUAL(exception_occurred, true);
+  BOOST_CHECK_EQUAL(bloom.probably_contains(1), true);
+}
+
 BOOST_AUTO_TEST_CASE(rangeInsert) {
   int elems[5] = {1,2,3,4,5};
   counting_bloom_filter<size_t, 5> bloom;
@@ -330,69 +419,106 @@
   counting_bloom_filter<size_t, 300> bloom_result;
 };
 
-/*
 BOOST_AUTO_TEST_CASE(testUnion) {
+  counting_bloom_filter<size_t, 4, 2> bloom1;
+  counting_bloom_filter<size_t, 4, 2> bloom2;
+  counting_bloom_filter<size_t, 4, 2> bloom_union;
 
-  for (size_t i = 0; i < 100; ++i)
-    bloom_1.insert(i);
+  bloom1.insert(0);
+  bloom1.insert(1);
+  bloom1.insert(1);
+  bloom1.insert(3);
+  bloom1.insert(3);
 
-  for (size_t i = 100; i < 200; ++i)
-    bloom_2.insert(i);
+  bloom2.insert(0);
+  bloom2.insert(0);
+  bloom2.insert(1);
+  bloom2.insert(1);
+  bloom2.insert(1);
+  bloom2.insert(3);
+  bloom2.insert(3);
 
-  bloom_union = bloom_1 | bloom_2;
+  bloom_union = experimental_union(bloom1, bloom2);
 
-  for (size_t i = 0; i < 200; ++i)
-    BOOST_CHECK_EQUAL(bloom_union.probably_contains(i), true);
-  BOOST_CHECK_GE(bloom_union.count(), bloom_1.count());
-  BOOST_CHECK_GE(bloom_union.count(), bloom_2.count());
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(0), true);
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(1), true);
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(2), false);
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(3), true);
+  BOOST_CHECK_GE(bloom_union.count(), bloom1.count());
+  BOOST_CHECK_GE(bloom_union.count(), bloom2.count());
 }
 
 BOOST_AUTO_TEST_CASE(testUnionAssign) {
-  counting_bloom_filter<size_t, 300> bloom_1;
-  counting_bloom_filter<size_t, 300> bloom_union;
-
-  for (size_t i = 0; i < 100; ++i) 
-    bloom_1.insert(i);
+  counting_bloom_filter<size_t, 4, 2> bloom1;
+  counting_bloom_filter<size_t, 4, 2> bloom_union;
 
-  bloom_union |= bloom_1;
+  bloom1.insert(0);
+  bloom1.insert(1);
+  bloom1.insert(1);
 
-  for (size_t i = 0; i < 100; ++i)
-    BOOST_CHECK_EQUAL(bloom_union.probably_contains(i), true);
-  BOOST_CHECK_EQUAL(bloom_union.count(), bloom_1.count());
+  bloom_union.insert(1);
+  bloom_union.insert(3);
+  bloom_union.insert(3);
+
+  bloom_union.experimental_union_assign(bloom1);
+
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(0), true);
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(1), true);
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(2), false);
+  BOOST_CHECK_EQUAL(bloom_union.probably_contains(3), true);
+  BOOST_CHECK_EQUAL(bloom_union.count(), 3ul);
 }
 
 BOOST_AUTO_TEST_CASE(testIntersect) {
-  counting_bloom_filter<size_t, 300> bloom_1;
-  counting_bloom_filter<size_t, 300> bloom_2;
-  counting_bloom_filter<size_t, 300> bloom_intersect;
-
-  // overlap at 100
-  for (size_t i = 0; i < 101; ++i) 
-    bloom_1.insert(i);
-  
-  for (size_t i = 100; i < 200; ++i) 
-    bloom_2.insert(i);
+  counting_bloom_filter<size_t, 4, 2> bloom1;
+  counting_bloom_filter<size_t, 4, 2> bloom2;
+  counting_bloom_filter<size_t, 4, 2> bloom_intersect;
+
+  bloom1.insert(0);
+  bloom1.insert(1);
+  bloom1.insert(3);
+  bloom1.insert(3);
+
+  bloom2.insert(0);
+  bloom2.insert(0);
+  bloom2.insert(1);
+  bloom2.insert(1);
+  bloom2.insert(3);
+  bloom2.insert(3);
 
-  bloom_intersect = bloom_1 & bloom_2;
+  bloom_intersect = experimental_intersect(bloom1, bloom2);
 
-  BOOST_CHECK_LE(bloom_intersect.count(), bloom_1.count());
-  BOOST_CHECK_LE(bloom_intersect.count(), bloom_2.count());
-  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(100), true);
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(0), false);
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(1), false);
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(2), false);
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(3), true);
+  BOOST_CHECK_LE(bloom_intersect.count(), bloom1.count());
+  BOOST_CHECK_LE(bloom_intersect.count(), bloom2.count());
 }
 
 BOOST_AUTO_TEST_CASE(testIntersectAssign) {
-  counting_bloom_filter<size_t, 300> bloom_1;
-  counting_bloom_filter<size_t, 300> bloom_intersect;
+  counting_bloom_filter<size_t, 4, 2> bloom1;
+  counting_bloom_filter<size_t, 4, 2> bloom_intersect;
 
-  for (size_t i = 0; i < 100; ++i) 
-    bloom_1.insert(i);
-  
-  bloom_intersect &= bloom_1;
+  bloom1.insert(0);
+  bloom1.insert(1);
+  bloom1.insert(3);
 
-  for (size_t i = 0; i < 100; ++i)
-    BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(i), false);
+  bloom1.insert(0);
+  bloom1.insert(0);
+  bloom_intersect.insert(1);
+  bloom_intersect.insert(3);
+  bloom_intersect.insert(3);
+  bloom_intersect.insert(3);
+
+  bloom_intersect.experimental_intersect_assign(bloom1);
+
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(0), false);
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(1), true);
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(2), false);
+  BOOST_CHECK_EQUAL(bloom_intersect.probably_contains(3), true);
+  BOOST_CHECK_EQUAL(bloom_intersect.count(), 2ul);
 }
-*/
 
 BOOST_FIXTURE_TEST_CASE(equalityOperator, PairwiseOpsFixture) {
   BOOST_CHECK_EQUAL(bloom1 == bloom2, true);