Subject: [Boost-commit] svn:boost r73339 - in sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html: . reference
From: cpp.cabrera_at_[hidden]
Date: 2011-07-24 19:41:44
Author: alejandro
Date: 2011-07-24 19:41:42 EDT (Sun, 24 Jul 2011)
New Revision: 73339
URL: http://svn.boost.org/trac/boost/changeset/73339
Log:
The reference section is now up to date with regards to the counting_bloom_filter class.
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference.html | 15 ++++++++
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference/counting_bloom.html | 73 +++++++++++++++++++++++++++++++++++----
2 files changed, 80 insertions(+), 8 deletions(-)
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/reference.html 2011-07-24 19:41:42 EDT (Sun, 24 Jul 2011)
@@ -50,6 +50,21 @@
<li>murmurhash3</li>
</ul>
</div>
+
+ <p>
+ In the following sections, when describing complexity, the variables n and k will be used as follows:
+ </p>
+ <ul>
+ <li>n - the number of bits or bins in the Bloom filter.</li>
+ <li>n - the number of elements to be inserted/removed from a range operation.</li>
+ <li>k - the number of hash functions a Bloom filter contains.</li>
+ </ul>
+
+ <p>
+ The meaning of the variable <em>n</em> will depend on the context. If
+ the context involves an insertion, construction, or removal, the meaning
+ is the second version.
+ </p>
<hr/>
<div class="spirit-nav">
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-07-24 19:41:42 EDT (Sun, 24 Jul 2011)
@@ -174,7 +174,7 @@
</div>
<div class="toc">
- <p>Function Reference (W.I.P.)</p>
+ <p>Function Reference</p>
<ul>
<li>counting_bloom_filter()</li>
<li>counting_bloom_filter(start, end)</li>
@@ -209,6 +209,8 @@
<dl>
<dt>Description</dt>
<dd>Constructs a counting_bloom_filter object with all bits set to 0.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -218,6 +220,8 @@
<dl>
<dt>Description</dt>
<dd>Constructs a counting_bloom_filter by inserting all the elements in the range (start, end).</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
@@ -229,6 +233,8 @@
<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>Complexity</dt>
+ <dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
@@ -240,6 +246,8 @@
<dd>Returns the number of bits used internally by the Bloom filter..</dd>
<dt>Returns</dt>
<dd>Value of template parameter Size.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -252,6 +260,8 @@
<dd>Returns the number of hash functions used by the Bloom filter.</dd>
<dt>Returns</dt>
<dd>mpl::size<HashFunctions>.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -263,6 +273,8 @@
<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>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -273,7 +285,9 @@
<dt>Description</dt>
<dd>Returns true if no elements have been inserted into the Bloom filter.</dd>
<dt>Returns</dt>
- <dd>std::bitset.count() == 0</dd>
+ <dd>this->count() == 0</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -282,9 +296,12 @@
<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>
- <dd>Returns the number of bits currently set in the Bloom filter.</dd>
+ <dd>Returns the number of bins contaning a set bit.</dd>
<dt>Returns</dt>
- <dd>std::bitset.count().</dd>
+ <dd>The number of bins that have an element in them. Note that this is
+ different than the number of insertions committed.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -296,6 +313,11 @@
<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>Complexity</dt>
+ <dd><span class="complexity">O(k)</span>.</dd>
</dl>
</div>
@@ -307,6 +329,11 @@
<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>Complexity</dt>
+ <dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
@@ -318,6 +345,11 @@
<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>Complexity</dt>
+ <dd><span class="complexity">O(k)</span>.</dd>
</dl>
</div>
@@ -329,6 +361,11 @@
<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>Complexity</dt>
+ <dd><span class="complexity">O(n*k)</span>.</dd>
</dl>
</div>
@@ -342,6 +379,8 @@
<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>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(k)</span>.</dd>
</dl>
</div>
@@ -353,6 +392,8 @@
<dd>Sets all bits in the Bloom filter to 0, effectively canceling all insertions.</dd>
<dt>Post-condition</dt>
<dd>this->count() == 0</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -362,6 +403,8 @@
<dl>
<dt>Description</dt>
<dd>Swaps the bits in this Bloom filter with the argument Bloom filter.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -370,11 +413,13 @@
<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>
<dl>
<dt>Description</dt>
- <dd>Performs a union.</dd>
+ <dd>Performs a union on a per-bin 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>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -383,11 +428,13 @@
<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>
<dl>
<dt>Description</dt>
- <dd>Performs an intersection.</dd>
+ <dd>Performs an intersection on a per-bin 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>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -396,11 +443,13 @@
<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>
<dl>
<dt>Description</dt>
- <dd>Performs a union.</dd>
+ <dd>Performs a union on a per-bin 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>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -409,11 +458,13 @@
<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>
<dl>
<dt>Description</dt>
- <dd>Performs an intersection.</dd>
+ <dd>Performs an intersection on a per-bin basis.</dd>
<dt>Returns</dt>
<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>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -423,6 +474,8 @@
<dl>
<dt>Description</dt>
<dd>Swaps the bits between the argument Bloom filters.</dd>
+ <dt>Complexity</dt>
+ <dd><span class="complexity">O(1)</span>.</dd>
</dl>
</div>
@@ -434,6 +487,8 @@
<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>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
@@ -445,6 +500,8 @@
<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>Complexity</dt>
+ <dd><span class="complexity">O(n)</span>.</dd>
</dl>
</div>
<hr/>