|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r73536 - in sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html: . reference tut
From: cpp.cabrera_at_[hidden]
Date: 2011-08-04 15:06:11
Author: alejandro
Date: 2011-08-04 15:06:09 EDT (Thu, 04 Aug 2011)
New Revision: 73536
URL: http://svn.boost.org/trac/boost/changeset/73536
Log:
Major documentation update, some testing update:
- Documentation updates:
- Updated history.
- Updated dynamic Bloom filter reference.
- added exception warnings to function ref.
- added latest exposed typedefs.
- Completed update of counting Bloom filter reference.
- Added in new typedefs to basic Bloom filter reference.
- Added new functions to reference for counting Bloom filter.
- Moved all link targets out of divs and into global structure
to slightly improve navigation.
- Updated tut/removing.html content to reflect addition of
exceptions.
- Removed false negative warning from tut/tips.html.
- Testing updates:
- Added intersection test.
- Changed implementation of union test.
- Added tests for union operations.
- Added test to ensure overflow exception is thrown
for default data structure.
- Re-added test falsePositiveRate.
- Added test for bitsPerBin.
- Added test for blockTypes.
- Made countMulti test more comprehensive.
- Benchmark updates:
- Restructured benchmarks to eliminate re-instantiation step.
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/history.html | 75 ++++++++++++++
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html | 42 ++++---
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/counting_bloom.html | 202 ++++++++++++++++++++++++++++-----------
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html | 62 ++++++++----
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/removing.html | 20 ++-
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/tips.html | 6 -
6 files changed, 292 insertions(+), 115 deletions(-)
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/history.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/history.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/history.html 2011-08-04 15:06:09 EDT (Thu, 04 Aug 2011)
@@ -36,6 +36,81 @@
</div>
<h1 class="title">Version history</h1>
+ <h3>v0.6.5 (August 3rd)</h3>
+ <ul>
+ <li><strong>Documentation Update</strong>
+ <ul>
+ <li>Updated reference - basic_bloom_filter, dynamic_bloom_filter,
+ counting_bloom_filter</li>
+ <li>Updated tutorial - added information regarding new
+ exception support for counting_bloom_filter</li>
+ <li>Updated history</li>
+ </ul>
+ </li>
+ </ul>
+
+ <h3>v0.6.0 (August 2nd)</h3>
+ <ul>
+ <li><strong>Implementation Update</strong>
+ <ul>
+ <li>Refactored counting_apply_hash - LOC cut in half,
+ also usable for future dynamic_counting_bloom_filter.</li>
+ </ul>
+ </li>
+ <li><strong>API Changes</strong>
+ <ul>
+ <li>counting_bloom_filter - added various typedefs and a few
+ metadata functions. More specifically:
+ <ul>
+ <li>Added bits_per_bin()</li>
+ <li>Added bins_per_slot()</li>
+ <li>Added mask()</li>
+ <li>Added num_bins()</li>
+ <li>Changed operator|=() -> experimental_union_assign</li>
+ <li>Changed operator|() -> experimental_union</li>
+ <li>Changed operator&=() -> experimental_intersect_assign</li>
+ <li>Changed operator&() -> experimental_intersect</li>
+ <li>Added restraint on BitsPerBin - must be greater than 0</li>
+ <li>Added restraint on BitsPerBin - must be <= sizeof(block_type)</li>
+ </ul>
+ </li>
+ </ul>
+ <ul>
+ <li><strong>Testing Update</strong>
+ <ul>
+ <li>Greatly expanded counting_bloom_filter tests. New coverage:
+ <ul>
+ <li>Ensured all valid BitsPerBin sizes compile</li>
+ <li>Ensured that many valid block_types compile</li>
+ <li>Added tests for falsePositiveRate()</li>
+ <li>Added tests for union/intersection</li>
+ <li>Added more tests for exception triggering</li>
+ <li>Made countMulti test more comprehensive - tested on
+ all valid bitsPerBin values</li>
+ </ul>
+ </li>
+ </ul>
+ </li>
+ </ul>
+ </li>
+ </ul>
+
+ <h3>v0.5.0 (July 26nd)</h3>
+ <ul>
+ <li><strong>Implementation Update</strong>
+ <ul>
+ <li>Refactored apply_hash - both basic_bloom_filter and
+ dynamic_bloom_filter use same apply_hash meta-function.</li>
+ </ul>
+ </li>
+ <li><strong>API Changes</strong>
+ <ul>
+ <li>basic_bloom_filter - added [this_type, bitset_type] typedef</li>
+ <li>dynamic_bloom_filter - added [this_type, bitset_type] typedef</li>
+ </ul>
+ </li>
+ </ul>
+
<h3>v0.4.4 (July 24nd)</h3>
<ul>
<li><strong>New!</strong>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html 2011-08-04 15:06:09 EDT (Thu, 04 Aug 2011)
@@ -48,7 +48,9 @@
<code class="c_comment">// exported typedefs</code>
<code class="c_keyword">typedef</code> <code class="c_type">T value_type</code>;
<code class="c_keyword">typedef</code> <code class="c_type">T key_type</code>;
+ <code class="c_keyword">typedef</code> <code class="c_namespace">std::</code><code class="c_type">bitset</code><Size> <code class="c_type">bitset_type</code>;
<code class="c_keyword">typedef</code> <code class="c_type">HashFunctions hash_function_type</code>;
+ <code class="c_keyword">typedef</code> <code class="c_type">basic_bloom_filter</code><<code class="c_type">T</code>, Size, <code class="c_type">HashFunctions</code>> <code class="c_type">this_type</code>;
<code class="c_comment">// constructors</code>
<code class="c_func">basic_bloom_filter</code>();
@@ -162,8 +164,8 @@
<br/>
+ <a name="default_constructor"></a>
<div class="func_ref">
- <a name="default_constructor"></a>
<div class="ref_listing"><code class="c_func">basic_bloom_filter</code>();</div>
<dl>
<dt>Description</dt>
@@ -173,8 +175,8 @@
</dl>
</div>
+ <a name="range_constructor"></a>
<div class="func_ref">
- <a name="range_constructor"></a>
<div class="ref_listing"><code class="c_func">basic_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);</div>
<dl>
<dt>Description</dt>
@@ -184,8 +186,8 @@
</dl>
</div>
+ <a name="ilist_constructor"></a>
<div class="func_ref">
- <a name="ilist_constructor"></a>
<div class="ref_listing"><code class="c_func">basic_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_namespace">std::initializer</code><<code class="c_type">T</code>>&);</div>
<dl>
<dt>Description</dt>
@@ -197,8 +199,8 @@
</dl>
</div>
+ <a name="bit_capacity"></a>
<div class="func_ref">
- <a name="bit_capacity"></a>
<div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">bit_capacity</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -211,8 +213,8 @@
</div>
+ <a name="num_hash_functions"></a>
<div class="func_ref">
- <a name="num_hash_functions"></a>
<div class="ref_listing"><code class="c_type">size_t</code><code class="c_func"> num_hash_functions</code>()<code class="c_keyword"> const</code>;</div>
<dl>
<dt>Description</dt>
@@ -224,8 +226,8 @@
</dl>
</div>
+ <a name="false_positive_rate"></a>
<div class="func_ref">
- <a name="false_positive_rate"></a>
<div class="ref_listing"><code class="c_type">double </code><code class="c_func">false_positive_rate</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -237,8 +239,8 @@
</dl>
</div>
+ <a name="empty"></a>
<div class="func_ref">
- <a name="empty"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">empty</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -250,8 +252,8 @@
</dl>
</div>
+ <a name="count"></a>
<div class="func_ref">
- <a name="count"></a>
<div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">count</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -263,8 +265,8 @@
</dl>
</div>
+ <a name="insert"></a>
<div class="func_ref">
- <a name="insert"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>);</div>
<dl>
<dt>Description</dt>
@@ -276,8 +278,8 @@
</dl>
</div>
+ <a name="range_insert"></a>
<div class="func_ref">
- <a name="range_insert"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);</div>
<dl>
<dt>Description</dt>
@@ -289,8 +291,8 @@
</dl>
</div>
+ <a name="probably_contains"></a>
<div class="func_ref">
- <a name="probably_contains"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">probably_contains</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>) <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -304,8 +306,8 @@
</dl>
</div>
+ <a name="clear"></a>
<div class="func_ref">
- <a name="clear"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">clear</code>();</div>
<dl>
<dt>Description</dt>
@@ -317,8 +319,8 @@
</dl>
</div>
+ <a name="swap"></a>
<div class="func_ref">
- <a name="swap"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">swap</code>(<code class="c_type">basic_bloom_filter</code>&);</div>
<dl>
<dt>Description</dt>
@@ -328,8 +330,8 @@
</dl>
</div>
+ <a name="union_assign"></a>
<div class="func_ref">
- <a name="union_assign"></a>
<div class="ref_listing"><code class="c_type">basic_bloom_filter&</code> <code class="c_func">operator|=</code>(<code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code>);</div>
<dl>
<dt>Description</dt>
@@ -343,8 +345,8 @@
</dl>
</div>
+ <a name="intersect_assign"></a>
<div class="func_ref">
- <a name="intersect_assign"></a>
<div class="ref_listing"><code class="c_type">basic_bloom_filter&</code> <code class="c_func">operator&=</code>(<code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code>);</div>
<dl>
<dt>Description</dt>
@@ -358,8 +360,8 @@
</dl>
</div>
+ <a name="union"></a>
<div class="func_ref">
- <a name="union"></a>
<div class="ref_listing"><code class="c_type">basic_bloom_filter&</code> <code class="c_func">operator|</code>(<code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
@@ -373,8 +375,8 @@
</dl>
</div>
+ <a name="intersect"></a>
<div class="func_ref">
- <a name="intersect"></a>
<div class="ref_listing"><code class="c_type">basic_bloom_filter&</code> <code class="c_func">operator&</code>(<code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
@@ -388,8 +390,8 @@
</dl>
</div>
+ <a name="global_swap"></a>
<div class="func_ref">
- <a name="global_swap"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">swap</code>(<code class="c_type">basic_bloom_filter</code>&, <code class="c_type">basic_bloom_filter</code>&);</div>
<dl>
<dt>Description</dt>
@@ -399,8 +401,8 @@
</dl>
</div>
+ <a name="operator_equality"></a>
<div class="func_ref">
- <a name="operator_equality"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">operator==</code>(<code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
@@ -412,8 +414,8 @@
</dl>
</div>
+ <a name="operator_inequality"></a>
<div class="func_ref">
- <a name="operator_inequality"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">operator!=</code>(<code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">basic_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/counting_bloom.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/counting_bloom.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/counting_bloom.html 2011-08-04 15:06:09 EDT (Thu, 04 Aug 2011)
@@ -44,14 +44,15 @@
<code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T</code>,
<code class="c_type">size_t</code> <code class="c_type">NumBins</code>,
<code class="c_type">size_t</code> <code class="c_type">BitsPerBin</code> = 4,
- <code class="c_keyword">class</code> <code class="c_type">HashFunctions</code> = <code class="c_namespace">mpl::</code><code class="c_type">vector</code><<code class="c_type">boost_hash</code><<code class="c_type">T</code>, 3> >,
+ <code class="c_keyword">class</code> <code class="c_type">HashFunctions</code> = <code class="c_namespace">mpl::</code><code class="c_type">vector</code><<code class="c_type">boost_hash</code><<code class="c_type">T</code>, 0> >,
<code class="c_keyword">typename</code> <code class="c_type">Block</code> = size_t>
<code class="c_keyword">class</code> <code class="c_type">counting_bloom_filter</code> {
<code class="c_comment">// restrictions on template parameters</code>
<code class="c_keyword">static_assert</code>( <code class="c_namespace">boost::</code>is_integral<<code class="c_type">Block</code>>::value == true);
<code class="c_keyword">static_assert</code>( <code class="c_namespace">boost::</code>is_unsigned<<code class="c_type">Block</code>>::value == true);
- <code class="c_keyword">static_assert</code>( (<code class="c_type">BitsPerBin</code> <= (<code class="c_keyword">sizeof</code>(<code class="c_type">Block</code>) * 8) ) );
+ <code class="c_keyword">static_assert</code>( BitsPerBin > 0 );
+ <code class="c_keyword">static_assert</code>( (<code class="c_type">BitsPerBin</code> < (<code class="c_keyword">sizeof</code>(<code class="c_type">Block</code>) * 8) ) );
<code class="c_keyword">static_assert</code>( ((<code class="c_keyword">sizeof</code>(<code class="c_type">Block</code>) * 8) % <code class="c_type">BitsPerBin</code>) == 0);
<code class="c_comment">// exported typedefs</code>
@@ -59,22 +60,31 @@
<code class="c_keyword">typedef</code> <code class="c_type">T key_type</code>;
<code class="c_keyword">typedef</code> <code class="c_type">HashFunctions hash_function_type</code>;
<code class="c_keyword">typedef</code> <code class="c_type">Block block_type</code>;
+ <code class="c_keyword">typedef</code> <code class="c_type">counting_bloom_filter</code><<code class="c_type">T</code>, NumBins, BitsPerBin, <code class="c_type">HashFunctions</code>, <code class="c_type">Block</code>> <code class="c_type">this_type</code>;
- <code class="c_comment">// constructors</code>
+ <code class="c_keyword">typedef</code> <code class="c_namespace">boost::</code><code class="c_type">array</code><<code class="c_type">Block</code>, array_size> <code class="c_type">bucket_type</code>;
+ <code class="c_keyword">typedef</code> <code class="c_type">bucket_type::iterator bucket_iterator</code>;
+ <code class="c_keyword">typedef</code> <code class="c_type">bucket_type::const_iterator bucket_const_iterator</code>;
+
+ <code class="c_comment">//! constructors</code>
<code class="c_func">counting_bloom_filter</code>();
<code class="c_func">counting_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_namespace">std::initializer_list</code><<code class="c_type">T</code>>&); <code class="c_comment">// requires C++11</code>
<<code class="c_keyword">typename</code> <code class="c_type">InputIterator</code>>
<code class="c_func">counting_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);
- <code class="c_comment">// data structure metadata query functions</code>
+ <code class="c_comment">//! data structure metadata query functions</code>
+ <code class="c_keyword">static constexpr</code> <code class="c_type">size_t</code> <code class="c_func">num_bins</code>() <code class="c_keyword">const</code>;
+ <code class="c_keyword">static constexpr</code> <code class="c_type">size_t</code> <code class="c_func">bits_per_bin</code>() <code class="c_keyword">const</code>;
+ <code class="c_keyword">static constexpr</code> <code class="c_type">size_t</code> <code class="c_func">bins_per_slot</code>() <code class="c_keyword">const</code>;
+ <code class="c_keyword">static constexpr</code> <code class="c_type">size_t</code> <code class="c_func">mask</code>() <code class="c_keyword">const</code>;
<code class="c_keyword">static constexpr</code> <code class="c_type">size_t</code> <code class="c_func">bit_capacity</code>() <code class="c_keyword">const</code>;
<code class="c_keyword">static constexpr</code> <code class="c_type">size_t</code> <code class="c_func">num_hash_functions</code>() <code class="c_keyword">const</code>;
<code class="c_type">double</code> <code class="c_func">false_positive_rate</code>() <code class="c_keyword">const</code>;
<code class="c_type">size_t</code> <code class="c_func">count</code>() <code class="c_keyword">const</code>;
<code class="c_type">bool</code> <code class="c_func">empty</code>() <code class="c_keyword">const</code>;
- <code class="c_comment">// data structures core ops</code>
+ <code class="c_comment">//! data structures core ops</code>
<code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">T</code>&);
<<code class="c_keyword">typename</code> <code class="c_type">InputIterator</code>>
@@ -87,33 +97,33 @@
<<code class="c_keyword">typename</code> <code class="c_type">InputIterator</code>>
<code class="c_type">void</code> <code class="c_func">remove</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);
- <code class="c_comment">// auxilliary ops</code>
+ <code class="c_comment">//! auxilliary ops</code>
<code class="c_type">void</code> <code class="c_func">clear</code>();
<code class="c_type">void</code> <code class="c_func">swap</code>(<code class="c_type">counting_bloom_filter</code>&);
- <code class="c_comment">// union assign/intersect assign</code>
- <code class="c_type">counting_bloom_filter</code>& <code class="c_func">operator|=</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code>&);
- <code class="c_type">counting_bloom_filter</code>& <code class="c_func">operator&=</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code>&);
+ <code class="c_comment">//! union assign/intersect assign</code>
+ <code class="c_type">counting_bloom_filter</code>& <code class="c_func">experimental_union_assign</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code>&);
+ <code class="c_type">counting_bloom_filter</code>& <code class="c_func">experimental_intersect_assign</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code>&);
};
- <code class="c_comment">// union</code>
+ <code class="c_comment">//! union</code>
<code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T</code>,
<code class="c_type">size_t</code> <code class="c_type">NumBins</code>,
<code class="c_type">size_t</code> <code class="c_type">BitsPerBin</code>,
<code class="c_keyword">class</code> <code class="c_type">HashFunctions</code>,
<code class="c_keyword">typename</code> <code class="c_type">Block</code>>
<code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>
- <code class="c_func">operator|</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>& <code class="c_id">lhs</code>,
+ <code class="c_func">experimental_union</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>& <code class="c_id">lhs</code>,
<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>& <code class="c_id">rhs</code>);
- <code class="c_comment">// intersect</code>
+ <code class="c_comment">//! intersect</code>
<code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T</code>,
<code class="c_type">size_t</code> <code class="c_type">NumBins</code>,
<code class="c_type">size_t</code> <code class="c_type">BitsPerBin</code>,
<code class="c_keyword">class</code> <code class="c_type">HashFunctions</code>,
<code class="c_keyword">typename</code> <code class="c_type">Block</code>>
<code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>
- <code class="c_func">operator&</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>& <code class="c_id">lhs</code>,
+ <code class="c_func">experimental_intersect</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>& <code class="c_id">lhs</code>,
<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter</code><<code class="c_type">T, NumBins, BitsPerBin, HashFunctions, Block</code>>& <code class="c_id">rhs</code>);
<code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T</code>,
@@ -179,6 +189,10 @@
<li>counting_bloom_filter()</li>
<li>counting_bloom_filter(start, end)</li>
<li>counting_bloom_filter(initializer_list)</li>
+ <li>num_bins()</li>
+ <li>bits_per_bin()</li>
+ <li>bins_per_slot()</li>
+ <li>mask()</li>
<li>bit_capacity()</li>
<li>num_hash_functions()</li>
<li>false_positive_rate()</li>
@@ -191,10 +205,10 @@
<li>probably_contains(T)</li>
<li>clear()</li>
<li>swap(bloom)</li>
- <li>operator|=(bloom)</li>
- <li>operator&=(bloom)</li>
- <li>operator|(bloom, bloom)</li>
- <li>operator&(bloom, bloom)</li>
+ <li>experimental_union_assign(bloom)</li>
+ <li>experimental_intersect_assign(bloom)</li>
+ <li>experimental_union(bloom, bloom)</li>
+ <li>experimental_intersect(bloom, bloom)</li>
<li>swap(bloom, bloom)</li>
<li>operator==(bloom, bloom)</li>
<li>operator!=(bloom, bloom)</li>
@@ -203,8 +217,8 @@
<br/>
+ <a name="default_constructor"></a>
<div class="func_ref">
- <a name="default_constructor"></a>
<div class="ref_listing"><code class="c_func">counting_bloom_filter</code>();</div>
<dl>
<dt>Description</dt>
@@ -214,32 +228,91 @@
</dl>
</div>
+ <a name="range_constructor"></a>
<div class="func_ref">
- <a name="range_constructor"></a>
<div class="ref_listing"><code class="c_func">counting_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);</div>
<dl>
<dt>Description</dt>
<dd>Constructs a counting_bloom_filter by inserting all the elements in the range (start, end).</dd>
+ <dt>Throws</dt>
+ <dd>May throw bin_overflow exception if an insertion makes the value of
+ a bin greater than 2**BitsPerBin</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
+ <a name="ilist_constructor"></a>
<div class="func_ref">
- <a name="ilist_constructor"></a>
<div class="ref_listing"><code class="c_func">counting_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_namespace">std::initializer</code><<code class="c_type">T</code>>&);</div>
<dl>
<dt>Description</dt>
<dd>Constructs a counting_bloom_filter by inserting all elements in the initializer list.</dd>
<dt>Warning</dt>
<dd>Only available in C++11-supporting compilers.</dd>
+ <dt>Throws</dt>
+ <dd>May throw bin_overflow exception if an insertion makes the value of
+ a bin greater than 2**BitsPerBin</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
+ <a name="num_bins"></a>
+ <div class="func_ref">
+ <div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">num_bins</code>() <code class="c_keyword">const</code>;</div>
+ <dl>
+ <dt>Description</dt>
+ <dd>Returns the number of bins allocated for this Bloom filter.</dd>
+ <dt>Returns</dt>
+ <dd>Value of template parameter NumBins.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
+ </dl>
+ </div>
+
+ <a name="bits_per_bin"></a>
+ <div class="func_ref">
+ <div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">bits_per_bin</code>() <code class="c_keyword">const</code>;</div>
+ <dl>
+ <dt>Description</dt>
+ <dd>Returns the number of bits used per bin.</dd>
+ <dt>Returns</dt>
+ <dd>Value of template parameter BitsPerBin.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
+ </dl>
+ </div>
+
+ <a name="bins_per_slot"></a>
+ <div class="func_ref">
+ <div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">bins_per_slot</code>() <code class="c_keyword">const</code>;</div>
+ <dl>
+ <dt>Description</dt>
+ <dd>Returns the number of bins that fit in a single slot of the
+ data structure's internal storage.</dd>
+ <dt>Returns</dt>
+ <dd>sizeof(Block) * 8 / BitsPerBin</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
+ </dl>
+ </div>
+
+ <a name="mask"></a>
+ <div class="func_ref">
+ <div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">mask</code>() <code class="c_keyword">const</code>;</div>
+ <dl>
+ <dt>Description</dt>
+ <dd>Returns the mask used internally to extract a bin from a slot.</dd>
+ <dt>Returns</dt>
+ <dd>static_cast<Block>(0 - 1) >> (sizeof(Block)*8 - BitsPerBin).</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
+ </dl>
+ </div>
+
+ <a name="bit_capacity"></a>
<div class="func_ref">
- <a name="bit_capacity"></a>
<div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">bit_capacity</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -251,9 +324,8 @@
</dl>
</div>
-
+ <a name="num_hash_functions"></a>
<div class="func_ref">
- <a name="num_hash_functions"></a>
<div class="ref_listing"><code class="c_type">size_t</code><code class="c_func"> num_hash_functions</code>()<code class="c_keyword"> const</code>;</div>
<dl>
<dt>Description</dt>
@@ -265,8 +337,8 @@
</dl>
</div>
+ <a name="false_positive_rate"></a>
<div class="func_ref">
- <a name="false_positive_rate"></a>
<div class="ref_listing"><code class="c_type">double </code><code class="c_func">false_positive_rate</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -278,8 +350,8 @@
</dl>
</div>
+ <a name="empty"></a>
<div class="func_ref">
- <a name="empty"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">empty</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -291,8 +363,8 @@
</dl>
</div>
+ <a name="count"></a>
<div class="func_ref">
- <a name="count"></a>
<div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">count</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -305,72 +377,72 @@
</dl>
</div>
+ <a name="insert"></a>
<div class="func_ref">
- <a name="insert"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>);</div>
<dl>
<dt>Description</dt>
<dd>Inserts an element into the Bloom filter.</dd>
<dt>Post-condition</dt>
<dd>At least 1 bit and at most num_hash_functions() bits of the Bloom filter will have been set.</dd>
- <dd>Throws</dd>
- <dt>May throw bin_overflow exception if an insertion makes the value of
- a bin greater than 2**BitsPerBin</dt>
+ <dt>Throws</dt>
+ <dd>May throw bin_overflow exception if an insertion makes the value of
+ a bin greater than 2**BitsPerBin</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(k)</span>.</dd>
</dl>
</div>
+ <a name="range_insert"></a>
<div class="func_ref">
- <a name="range_insert"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);</div>
<dl>
<dt>Description</dt>
<dd>Inserts all elements in range (start, end).</dd>
<dt>Post-condition</dt>
<dd>At least n bits and at most (n * num_hash_functions()) bits of the Bloom filter will have been set, where n = distance(start, end).</dd>
- <dd>Throws</dd>
- <dt>May throw bin_overflow exception if an insertion makes the value of
- a bin greater than 2**BitsPerBin</dt>
+ <dt>Throws</dt>
+ <dd>May throw bin_overflow exception if an insertion makes the value of
+ a bin greater than 2**BitsPerBin</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
+ <a name="remove"></a>
<div class="func_ref">
- <a name="remove"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">remove</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>);</div>
<dl>
<dt>Description</dt>
<dd>Removes an element into the Bloom filter.</dd>
<dt>Post-condition</dt>
<dd>At least 1 bit and at most num_hash_functions() bits of the Bloom filter will have been set.</dd>
- <dd>Throws</dd>
- <dt>May throw bin_underflow exception if a removal makes the value of
- a bin less than 0.</dt>
+ <dt>Throws</dt>
+ <dd>May throw bin_underflow exception if a removal makes the value of
+ a bin less than 0.</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(k)</span>.</dd>
</dl>
</div>
+ <a name="range_remove"></a>
<div class="func_ref">
- <a name="range_remove"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">remove</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);</div>
<dl>
<dt>Description</dt>
<dd>Removes all elements in range (start, end).</dd>
<dt>Post-condition</dt>
<dd>At least n bits and at most (n * num_hash_functions()) bits of the Bloom filter will have been set, where n = distance(start, end).</dd>
- <dd>Throws</dd>
- <dt>May throw bin_underflow exception if a removal makes the value of
- a bin less than 0.</dt>
+ <dt>Throws</dt>
+ <dd>May throw bin_underflow exception if a removal makes the value of
+ a bin less than 0.</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
+ <a name="probably_contains"></a>
<div class="func_ref">
- <a name="probably_contains"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">probably_contains</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>) <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -384,8 +456,8 @@
</dl>
</div>
+ <a name="clear"></a>
<div class="func_ref">
- <a name="clear"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">clear</code>();</div>
<dl>
<dt>Description</dt>
@@ -397,8 +469,8 @@
</dl>
</div>
+ <a name="swap"></a>
<div class="func_ref">
- <a name="swap"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">swap</code>(<code class="c_type">counting_bloom_filter</code>&);</div>
<dl>
<dt>Description</dt>
@@ -408,54 +480,63 @@
</dl>
</div>
+ <a name="union_assign"></a>
<div class="func_ref">
- <a name="union_assign"></a>
- <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">operator|=</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code>);</div>
+ <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">experimental_union_assign</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code>);</div>
<dl>
<dt>Description</dt>
- <dd>Performs a union on a per-bin basis.</dd>
+ <dd>Performs a union on a per-slot basis.</dd>
<dt>Returns</dt>
<dd>Returns a reference to <code class="c_keyword">this</code>.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in <code class="c_keyword">this</code> will be greater than or equal to the number of bits set before the operation.</dd>
+ <dt>Warning</dt>
+ <dd>This operation is only an approximation. The resulting Bloom filter
+ may have very high bin values. See regression suite for details.</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
+ <a name="intersect_assign"></a>
<div class="func_ref">
- <a name="intersect_assign"></a>
- <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">operator&=</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code>);</div>
+ <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">experimental_intersect_assign</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code>);</div>
<dl>
<dt>Description</dt>
- <dd>Performs an intersection on a per-bin basis.</dd>
+ <dd>Performs an intersection on a per-slot basis.</dd>
<dt>Returns</dt>
<dd>Returns a reference to <code class="c_keyword">this</code>.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in <code class="c_keyword">this</code> will be less than or equal to the number of bits set before the operation.</dd>
+ <dt>Warning</dt>
+ <dd>This operation is only an approximation. The resulting Bloom filter
+ may have false negatives. See regression suite for details.</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
+ <a name="union"></a>
<div class="func_ref">
- <a name="union"></a>
- <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">operator|</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
+ <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">experimental_union</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
- <dd>Performs a union on a per-bin basis.</dd>
+ <dd>Performs a union on a per-slot basis.</dd>
<dt>Returns</dt>
<dd>Returns a new, stack-allocated Bloom filter that is the result of performing a union between the lhs and the rhs.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in the new filter will be greater than or equal to the number of bits set in max(lhs.count(), rhs.count()).</dd>
+ <dt>Warning</dt>
+ <dd>This operation is only an approximation. The resulting Bloom filter
+ may have very high bin values. See regression suite for details.</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
+ <a name="intersect"></a>
<div class="func_ref">
- <a name="intersect"></a>
- <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">operator&</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
+ <div class="ref_listing"><code class="c_type">counting_bloom_filter&</code> <code class="c_func">experimental_intersect</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
<dd>Performs an intersection on a per-bin basis.</dd>
@@ -463,13 +544,16 @@
<dd>Returns a new, stack-allocated Bloom filter that is the result of performing an intersect between the lhs and the rhs.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in the new filter will be less than or equal to the number of bits set in min(lhs.count(), rhs.count()).</dd>
+ <dt>Warning</dt>
+ <dd>This operation is only an approximation. The resulting Bloom filter
+ may have false negatives. See regression suite for details.</dd>
<dt>Complexity</dt>
<dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
+ <a name="global_swap"></a>
<div class="func_ref">
- <a name="global_swap"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">swap</code>(<code class="c_type">counting_bloom_filter</code>&, <code class="c_type">counting_bloom_filter</code>&);</div>
<dl>
<dt>Description</dt>
@@ -479,8 +563,8 @@
</dl>
</div>
+ <a name="operator_equality"></a>
<div class="func_ref">
- <a name="operator_equality"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">operator==</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
@@ -492,8 +576,8 @@
</dl>
</div>
+ <a name="operator_inequality"></a>
<div class="func_ref">
- <a name="operator_inequality"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">operator!=</code>(<code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">counting_bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/dynamic_bloom.html 2011-08-04 15:06:09 EDT (Thu, 04 Aug 2011)
@@ -52,6 +52,8 @@
<code class="c_keyword">typedef</code> <code class="c_type">HashFunctions hash_function_type</code>;
<code class="c_keyword">typedef</code> <code class="c_type">Block block_type</code>;
<code class="c_keyword">typedef</code> <code class="c_type">Allocator allocator_type</code>;
+ <code class="c_keyword">typedef</code> <code class="c_type">dynamic_bitset</code><<code class="c_type">Block</code>, <code class="c_type">Allocator</code>> <code class="c_type">bitset_type</code>;
+ <code class="c_keyword">typedef</code> <code class="c_type">dynamic_bloom_filter</code><<code class="c_type">T</code>, <code class="c_type">HashFunctions</code>, <code class="c_type">Block</code>, <code class="c_type">Allocator</code>> <code class="c_type">this_type</code>;
<code class="c_comment">// constructors</code>
<code class="c_func">dynamic_bloom_filter</code>();
@@ -180,8 +182,8 @@
<br/>
+ <a name="default_constructor"></a>
<div class="func_ref">
- <a name="default_constructor"></a>
<div class="ref_listing"><code class="c_func">dynamic_bloom_filter</code>();</div>
<dl>
<dt>Description</dt>
@@ -195,8 +197,8 @@
</dl>
</div>
+ <a name="capacity_constructor"></a>
<div class="func_ref">
- <a name="capacity_constructor"></a>
<div class="ref_listing"><code class="c_func">dynamic_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_type">size_t</code> <code class="c_id">capacity</code>);</div>
<dl>
<dt>Description</dt>
@@ -208,8 +210,8 @@
</dl>
</div>
+ <a name="range_constructor"></a>
<div class="func_ref">
- <a name="range_constructor"></a>
<div class="ref_listing"><code class="c_func">dynamic_bloom_filter</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);</div>
<dl>
<dt>Description</dt>
@@ -221,8 +223,8 @@
</dl>
</div>
+ <a name="bit_capacity"></a>
<div class="func_ref">
- <a name="bit_capacity"></a>
<div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">bit_capacity</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -235,8 +237,8 @@
</div>
+ <a name="num_hash_functions"></a>
<div class="func_ref">
- <a name="num_hash_functions"></a>
<div class="ref_listing"><code class="c_type">size_t</code><code class="c_func"> num_hash_functions</code>()<code class="c_keyword"> const</code>;</div>
<dl>
<dt>Description</dt>
@@ -248,8 +250,8 @@
</dl>
</div>
+ <a name="false_positive_rate"></a>
<div class="func_ref">
- <a name="false_positive_rate"></a>
<div class="ref_listing"><code class="c_type">double </code><code class="c_func">false_positive_rate</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -261,8 +263,8 @@
</dl>
</div>
+ <a name="empty"></a>
<div class="func_ref">
- <a name="empty"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">empty</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -276,8 +278,8 @@
</dl>
</div>
+ <a name="count"></a>
<div class="func_ref">
- <a name="count"></a>
<div class="ref_listing"><code class="c_type">size_t</code> <code class="c_func">count</code>() <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -291,8 +293,8 @@
</dl>
</div>
+ <a name="insert"></a>
<div class="func_ref">
- <a name="insert"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>);</div>
<dl>
<dt>Description</dt>
@@ -304,8 +306,8 @@
</dl>
</div>
+ <a name="range_insert"></a>
<div class="func_ref">
- <a name="range_insert"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">start</code>, <code class="c_keyword">const</code> <code class="c_type">InputIterator</code> <code class="c_id">end</code>);</div>
<dl>
<dt>Description</dt>
@@ -317,8 +319,8 @@
</dl>
</div>
+ <a name="probably_contains"></a>
<div class="func_ref">
- <a name="probably_contains"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">probably_contains</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>) <code class="c_keyword">const</code>;</div>
<dl>
<dt>Description</dt>
@@ -332,8 +334,8 @@
</dl>
</div>
+ <a name="clear"></a>
<div class="func_ref">
- <a name="clear"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">clear</code>();</div>
<dl>
<dt>Description</dt>
@@ -347,8 +349,8 @@
</dl>
</div>
+ <a name="swap"></a>
<div class="func_ref">
- <a name="swap"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">swap</code>(<code class="c_type">bloom_filter</code>&);</div>
<dl>
<dt>Description</dt>
@@ -358,8 +360,8 @@
</dl>
</div>
+ <a name="resize"></a>
<div class="func_ref">
- <a name="resize"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">resize</code>(<code class="c_type">size_t</code> <code class="c_id">new_capacity</code>);</div>
<dl>
<dt>Description</dt>
@@ -373,8 +375,8 @@
</dl>
</div>
+ <a name="union_assign"></a>
<div class="func_ref">
- <a name="union_assign"></a>
<div class="ref_listing"><code class="c_type">bloom_filter&</code> <code class="c_func">operator|=</code>(<code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code>);</div>
<dl>
<dt>Description</dt>
@@ -385,6 +387,9 @@
<dd>Returns a reference to <code class="c_keyword">this</code>.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in <code class="c_keyword">this</code> will be greater than or equal to the number of bits set before the operation.</dd>
+ <dt>Throws</dt>
+ <dd>incompatible_size exception if the argument Bloom filters
+ have a different bit_capacity.</dd>
<dt>Complexity</dt>
<dd>Depends on the implementation of
<a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
@@ -392,8 +397,8 @@
</dl>
</div>
+ <a name="intersect_assign"></a>
<div class="func_ref">
- <a name="intersect_assign"></a>
<div class="ref_listing"><code class="c_type">bloom_filter&</code> <code class="c_func">operator&=</code>(<code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code>);</div>
<dl>
<dt>Description</dt>
@@ -404,6 +409,9 @@
<dd>Returns a reference to <code class="c_keyword">this</code>.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in <code class="c_keyword">this</code> will be less than or equal to the number of bits set before the operation.</dd>
+ <dt>Throws</dt>
+ <dd>incompatible_size exception if the argument Bloom filters
+ have a different bit_capacity.</dd>
<dt>Complexity</dt>
<dd>Depends on the implementation of
<a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
@@ -411,8 +419,8 @@
</dl>
</div>
+ <a name="union"></a>
<div class="func_ref">
- <a name="union"></a>
<div class="ref_listing"><code class="c_type">bloom_filter&</code> <code class="c_func">operator|</code>(<code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
@@ -423,6 +431,9 @@
<dd>Returns a new, stack-allocated Bloom filter that is the result of performing a union between the lhs and the rhs.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in the new filter will be greater than or equal to the number of bits set in max(lhs.count(), rhs.count()).</dd>
+ <dt>Throws</dt>
+ <dd>incompatible_size exception if the argument Bloom filters
+ have a different bit_capacity.</dd>
<dt>Complexity</dt>
<dd>Depends on the implementation of
<a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
@@ -430,8 +441,8 @@
</dl>
</div>
+ <a name="intersect"></a>
<div class="func_ref">
- <a name="intersect"></a>
<div class="ref_listing"><code class="c_type">bloom_filter&</code> <code class="c_func">operator&</code>(<code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
@@ -442,6 +453,9 @@
<dd>Returns a new, stack-allocated Bloom filter that is the result of performing an intersect between the lhs and the rhs.</dd>
<dt>Post-condition</dt>
<dd>The number of bits set in the new filter will be less than or equal to the number of bits set in min(lhs.count(), rhs.count()).</dd>
+ <dt>Throws</dt>
+ <dd>incompatible_size exception if the argument Bloom filters
+ have a different bit_capacity.</dd>
<dt>Complexity</dt>
<dd>Depends on the implementation of
<a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
@@ -449,8 +463,8 @@
</dl>
</div>
+ <a name="global_swap"></a>
<div class="func_ref">
- <a name="global_swap"></a>
<div class="ref_listing"><code class="c_type">void</code> <code class="c_func">swap</code>(<code class="c_type">bloom_filter</code>&, <code class="c_type">bloom_filter</code>&);</div>
<dl>
<dt>Description</dt>
@@ -460,14 +474,17 @@
</dl>
</div>
+ <a name="operator_equality"></a>
<div class="func_ref">
- <a name="operator_equality"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">operator==</code>(<code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
<dd>Compares the bits of the argument Bloom filters for equality.</dd>
<dt>Returns</dt>
<dd>True if the bits match, false otherwise.</dd>
+ <dt>Throws</dt>
+ <dd>incompatible_size exception if the argument Bloom filters
+ have a different bit_capacity.</dd>
<dt>Complexity</dt>
<dd>Depends on the implementation of
<a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
@@ -475,14 +492,17 @@
</dl>
</div>
+ <a name="operator_inequality"></a>
<div class="func_ref">
- <a name="operator_inequality"></a>
<div class="ref_listing"><code class="c_type">bool</code> <code class="c_func">operator!=</code>(<code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">lhs</code>, <code class="c_keyword">const</code> <code class="c_type">bloom_filter&</code> <code class="c_id">rhs</code>);</div>
<dl>
<dt>Description</dt>
<dd>Compares the bits of the argument Bloom filters for equality.</dd>
<dt>Returns</dt>
<dd>True if the bits don't match, false otherwise.</dd>
+ <dt>Throws</dt>
+ <dd>incompatible_size exception if the argument Bloom filters
+ have a different bit_capacity.</dd>
<dt>Complexity</dt>
<dd>Depends on the implementation of
<a href="http://www.boost.org/doc/libs/1_47_0/libs/dynamic_bitset/dynamic_bitset.html#member-functions">
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/removing.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/removing.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/removing.html 2011-08-04 15:06:09 EDT (Thu, 04 Aug 2011)
@@ -42,9 +42,10 @@
<p>
Element removal is an operation supported only by the counting
- Bloom filters. <em>remove</em> can introduce false negatives, so
- it must be used with caution. The list below highlights the
- possibilities:
+ Bloom filters. Depending on the implementation of <em>remove</em>,
+ false negatives can be introduced. This implementation
+ <strong>does not</strong> allow false negatives. The following
+ means of reaching a false negative are ordinarily possible:
</p>
<ul>
@@ -53,11 +54,12 @@
</ul>
<p>
- This implementation does not check for either error.
+ This implementation checks for both kinds of errors, and throws
+ an exception when one of the errors is encountered.
</p>
<div class="example">
- <code class="c_type">counting_bloom_filter</code><<code class="c_type">int</code>, 1000, 2> <code class="c_id">bloom</code>;
+ <code class="c_type">counting_bloom_filter</code><<code class="c_type">int</code>, 1000, 2, 2> <code class="c_id">bloom</code>;
bloom.insert(1);
bloom.probably_contains(1); <code class="c_comment">// true</code>
@@ -67,11 +69,11 @@
bloom.insert(1); <code class="c_comment">// bin[1] = 01 </code>
bloom.insert(1); <code class="c_comment">// bin[1] = 10 </code>
bloom.insert(1); <code class="c_comment">// bin[1] = 11 </code>
- bloom.insert(1); <code class="c_comment">// bin[1] = 00 </code>
- bloom.probably_contains(1); <code class="c_comment">// overflow, false</code>
+ bloom.insert(1); <code class="c_comment">// bin[1] = 11, exception thrown </code>
+ bloom.probably_contains(1); <code class="c_comment">// true</code>
- bloom.remove(1); <code class="c_comment">// bin[1] = 11 </code>
- bloom.probably_contains(1); <code class="c_comment">// underflow, true</code>
+ bloom.remove(1); <code class="c_comment">// bin[1] = 00, exception thrown </code>
+ bloom.probably_contains(1); <code class="c_comment">// false</code>
</div>
<p>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/tips.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/tips.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/tips.html 2011-08-04 15:06:09 EDT (Thu, 04 Aug 2011)
@@ -82,12 +82,6 @@
Refer to the bibliography for more details.
</p>
- <h3>False Negatives</h3>
- <p>
- A false negative can occur in any Bloom filter that supports a <em>remove</em>
- operation.
- </p>
-
<h3>Hasher Set Trade-Offs</h3>
<p>
A fast Bloom filter will prefer to use fewer and faster hashers. If your
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk