|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r72661 - sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference
From: cpp.cabrera_at_[hidden]
Date: 2011-06-17 21:48:06
Author: alejandro
Date: 2011-06-17 21:48:05 EDT (Fri, 17 Jun 2011)
New Revision: 72661
URL: http://svn.boost.org/trac/boost/changeset/72661
Log:
Added and improved function reference section.
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/bloom.html | 81 ++++++++++++++++++++++++---------------
1 files changed, 50 insertions(+), 31 deletions(-)
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-06-17 21:48:05 EDT (Fri, 17 Jun 2011)
@@ -23,6 +23,7 @@
</header>
<hr/>
+
<div class="spirit-nav">
<a accesskey="p" href="../reference.html">
<img src="../../../../../doc/src/images/prev.png" alt="Prev"/>
@@ -101,6 +102,7 @@
<li>bloom_filter()</li>
<li>size()</li>
<li>num_hash_functions()</li>
+ <li>false_positive_rate()</li>
<li>count()</li>
<li>insert()</li>
<li>contains()</li>
@@ -113,8 +115,6 @@
<br/>
- <h1>WIP BELOW THIS POINT</h1>
-
<div class="func_ref">
<a name="constructor"></a>
<h3><code class="c_func">bloom_filter</code>()</h3>
@@ -126,7 +126,7 @@
<div class="func_ref">
<a name="size"></a>
- <h3><code class="c_func">size</code>()</h3>
+ <h3><code class="c_type">size_t</code> <code class="c_func">size</code>() <code class="c_keyword">const</code></h3>
<dl>
<dt>Description</dt>
<dd>Returns the number of bits used internally by the Bloom filter..</dd>
@@ -138,97 +138,116 @@
<div class="func_ref">
<a name="num_hash_functions"></a>
- <h3><code class="c_func">num_hash_functions</code>()</h3>
+ <h3><code class="c_type">size_t</code><code class="c_func"> num_hash_functions</code>()<code class="c_keyword"> const</code></h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
+ <dd>Returns the number of hash functions used by the Bloom filter.</dd>
<dt>Returns</dt>
- <dd>Value of template parameter Size.</dd>
+ <dd>mpl::size<HashFunctions>.</dd>
+ </dl>
+ </div>
+
+ <div class="func_ref">
+ <a name="false_positive_rate"></a>
+ <h3><code class="c_type">double </code><code class="c_func">false_positive_rate</code>() <code class="c_keyword">const</code></h3>
+ <dl>
+ <dt>Description</dt>
+ <dd>Returns the current false positive rate based upon the number of hash functions used (k), the number of bits available (m), and the number of bits set (n).</dd>
+ <dt>Returns</dt>
+ <dd>A double precision value calculated as (1 - e^(k*n/m))^k.</dd>
</dl>
</div>
<div class="func_ref">
<a name="count"></a>
- <h3><code class="c_func">count</code>()</h3>
+ <h3><code class="c_type">size_t</code> <code class="c_func">count</code>() <code class="c_keyword">const</code></h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
+ <dd>Returns the number of bits currently set in the Bloom filter.</dd>
<dt>Returns</dt>
- <dd>Value of template parameter Size.</dd>
+ <dd>std::bitset.count().</dd>
</dl>
</div>
<div class="func_ref">
<a name="insert"></a>
- <h3><code class="c_func">insert</code>()</h3>
+ <h3><code class="c_type">void</code> <code class="c_func">insert</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>)</h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
- <dt>Returns</dt>
- <dd>Value of template parameter Insert.</dd>
+ <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>
</dl>
</div>
<div class="func_ref">
<a name="contains"></a>
- <h3><code class="c_func">contains</code>()</h3>
+ <h3><code class="c_type">bool</code> <code class="c_func">contains</code>(<code class="c_keyword">const</code> <code class="c_type">T&</code>) <code class="c_keyword">const</code></h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
+ <dd>Queries an element in the Bloom filter, checking each hash function value against the set bits.</dd>
<dt>Returns</dt>
- <dd>Value of template parameter Contains.</dd>
+ <dd>True if all hash functions agree with the bitset; false otherwise.</dd>
+ <dt>Warning</dt>
+ <dd>It may return a false positive if there are hash collisions - this means that depending on the Size of the Bloom filter and the hash functions used, there is a probability that the Bloom filter will return true even though the element was never inserted.</dd>
</dl>
</div>
<div class="func_ref">
<a name="union_assign"></a>
- <h3><code class="c_func">operator|=</code>()</h3>
+ <h3><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>)</h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
+ <dd>Performs a union.</dd>
<dt>Returns</dt>
- <dd>Value of template parameter Union_Assign.</dd>
+ <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>
</dl>
</div>
<div class="func_ref">
<a name="intersect_assign"></a>
- <h3><code class="c_func">operator&=</code>()</h3>
+ <h3><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>)</h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
+ <dd>Performs an intersection.</dd>
<dt>Returns</dt>
- <dd>Value of template parameter Size.</dd>
+ <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>
</dl>
</div>
-
<div class="func_ref">
<a name="union"></a>
- <h3><code class="c_func">operator|</code>()</h3>
+ <h3><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>)</h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
+ <dd>Performs a union.</dd>
<dt>Returns</dt>
- <dd>Value of template parameter Union_Assign.</dd>
+ <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>
</dl>
</div>
-
<div class="func_ref">
<a name="intersect"></a>
- <h3><code class="c_func">operator&</code>()</h3>
+ <h3><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>)</h3>
<dl>
<dt>Description</dt>
- <dd>Returns the number of bits used internally by the Bloom filter..</dd>
+ <dd>Performs an intersection.</dd>
<dt>Returns</dt>
- <dd>Value of template parameter Size.</dd>
+ <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>
</dl>
</div>
-
+
<hr/>
<div class="spirit-nav">
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