Subject: [Boost-commit] svn:boost r73231 - in sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html: . tut
From: cpp.cabrera_at_[hidden]
Date: 2011-07-19 02:38:04
Author: alejandro
Date: 2011-07-19 02:38:03 EDT (Tue, 19 Jul 2011)
New Revision: 73231
URL: http://svn.boost.org/trac/boost/changeset/73231
Log:
Split tutorial into several modules. Updated quick start module.
Added:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/quick.html (contents, props changed)
Text files modified:
sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html | 93 +++++++++++++++------------------------
1 files changed, 35 insertions(+), 58 deletions(-)
Added: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/quick.html
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tut/quick.html 2011-07-19 02:38:03 EDT (Tue, 19 Jul 2011)
@@ -0,0 +1,128 @@
+<!DOCTYPE html>
+<html xmlns="http://www.w3.org/1999/xhtml">
+ <head>
+ <meta http-equiv="content-type" content="text/html; charset=utf-8"/>
+ <link rel="stylesheet" type="text/css"
+ href="../../../../../doc/src/boostbook.css"/>
+ <link rel="stylesheet" type="text/css" href="../style/my.css"/>
+
+ <title>Boost.BloomFilter</title>
+ </head>
+
+ <body>
+ <div class="header">
+ <img src="../../../../../boost.png" width="277" height="86"
+ alt="Boost C++ Libraries"/>
+ <p>
+ Home
+ Libraries
+ People
+ FAQ
+ More
+ </p>
+ </div>
+
+ <hr/>
+ <div class="spirit-nav">
+ <a accesskey="p" href="../tutorial.html">
+ <img src="../../../../../doc/src/images/prev.png" alt="Prev"/>
+ </a>
+ <a accesskey="u" href="../tutorial.html">
+ <img src="../../../../../doc/src/images/up.png" alt="Up"/>
+ </a>
+ <a accesskey="h" href="../index.html">
+ <img src="../../../../../doc/src/images/home.png" alt="Home"/>
+ </a>
+ <a accesskey="n" href="false_positive.html">
+ <img src="../../../../../doc/src/images/next.png" alt="Next"/>
+ </a>
+ </div>
+
+ <h1 class="title">Quick Start</h1>
+
+ <p>
+ Let's jump right into a minimal example:
+ </p>
+
+ <div class="listing">
+ <code class="c_comment">// link: basic_bloom.cpp</code>
+ <code class="c_comment">// introductory Boost.BloomFilter program</code>
+ <code class="c_keyword">#include</code> <code class="c_include"><boost/bloom_filter/basic_bloom_filter.hpp></code>
+ <code class="c_keyword">#include</code> <code class="c_include"><iostream></code>
+ <code class="c_keyword">using namespace</code> <code class="c_namespace">boost::bloom_filters</code>;
+ <code class="c_keyword">using namespace</code> <code class="c_namespace">std</code>;
+
+ <code class="c_type">int</code> <code class="c_func">main</code>() {
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">INSERT_MAX</code> = 5000;
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">CONTAINS_MAX</code> = 10000;
+ <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">NUM_BITS</code> = 8192;
+
+ <code class="c_type">basic_bloom_filter</code><int, NUM_BITS> <code class="c_id">bloom</code>;
+ <code class="c_type">size_t</code><code class="c_id"> collisions</code> = 0;
+
+ <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 0; i < INSERT_MAX; ++i) {
+ bloom.insert(i);
+ }
+
+ <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = INSERT_MAX; i < CONTAINS_MAX; ++i) {
+ <code class="c_keyword">if</code> (bloom.probably_contains(i)) cout << "collision" << endl;
+ }
+
+ cout << <code class="c_str">"collisions: "</code>
+ << collisions
+ << endl;
+
+ <code class="c_keyword">return</code> 0;
+ }
+ </div>
+ <div class="example_output">
+ $> ./basic_bloom
+ collisions: 1808
+ </div>
+
+ <p>
+ Above, we see a simple example that instantiates the default Bloom filter, inserts integers
+ 0 - 4999, and then queries the existence of those integers. That's all it takes to use
+ this Bloom filter!
+ </p>
+ <p>
+ In practice, where false positive rates matter a great deal, care must be taken to choose not
+ only the right bitset Size, but also the right number (and implementation) of hash functions (Hahsers).
+ This is where the last template parameter comes in, as well as the remaining member functions.
+ To use the Bloom filter to its maximum potential, you must understand how to customize
+ these remaining parameters.
+ </p>
+
+ <hr/>
+ <div class="spirit-nav">
+ <a accesskey="p" href="../tutorial.html">
+ <img src="../../../../../doc/src/images/prev.png" alt="Prev"/>
+ </a>
+ <a accesskey="u" href="../tutorial.html">
+ <img src="../../../../../doc/src/images/up.png" alt="Up"/>
+ </a>
+ <a accesskey="h" href="../index.html">
+ <img src="../../../../../doc/src/images/home.png" alt="Home"/>
+ </a>
+ <a accesskey="n" href="false_positive.html">
+ <img src="../../../../../doc/src/images/next.png" alt="Next"/>
+ </a>
+ </div>
+
+ <div>
+ <p class="copyright">
+ Copyright © 2011
+ <a href="mailto:cpp.cabrera_at_[hidden]">Alejandro Cabrera</a>
+ </p>
+
+ <p class="copyright">
+ 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)
+ </p>
+ </div>
+
+ </body>
+</html>
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/doc/html/tutorial.html 2011-07-19 02:38:03 EDT (Tue, 19 Jul 2011)
@@ -8,7 +8,7 @@
<title>Boost.BloomFilter</title>
</head>
-
+
<body>
<div class="header">
<img src="../../../../boost.png" width="277" height="86"
@@ -37,6 +37,35 @@
<h2 class="title">Tutorial</h2>
+ <div class="toc">
+ <p>Table of Contents</p>
+ <ul>
+ <li>Quick Start</li>
+ <li>Controlling the False Positive Rate</li>
+ <li>Customzing Hash Functions</li>
+ <li>Creating Bloom Filters</li>
+ <li>Inserting Elements</li>
+ <li>Querying Elements</li>
+ <li>Removing Elements</li>
+ <li>Tips & Warnings</li>
+ </ul>
+ </div>
+
+ <a name="overview"></a>
+ <h3>Overview</h3>
+
+ <p>
+ There are two primitive operations that are supported by all Bloom filters: <em>insert</em> and <em>probably_contains</em>. A third operation, <em>remove</em>, is supported by counting Bloom filters, and a few similar variants. In order to control the false positive rate of a Bloom filter, you can control the number of hash functions used, as well as the bit capacity.
+ </p>
+
+ <h3>Types of Bloom Filters Provided</h3>
+ <ul>
+ <li>Basic Bloom filter (basic_bloom_filter, dynamic_bloom_filter)</li>
+ <li>Counting Bloom filter (counting_bloom_filter)</li>
+ </ul>
+
+ <h4>Basic Bloom Filter</h4>
+
<p>
To use this Bloom filter, there are two template parameters to be aware of and two functions to utilize:
</p>
@@ -56,58 +85,6 @@
</li>
</ul>
- <p>
- With that out of the way, let's jump into a minimal example.
- </p>
-
- <div class="listing">
- <code class="c_comment">// link: basic_bloom.cpp</code>
- <code class="c_comment">// introductory Boost.BloomFilter program</code>
- <code class="c_keyword">#include</code> <code class="c_include"><boost/bloom_filter/bloom.hpp></code>
- <code class="c_keyword">#include</code> <code class="c_include"><iostream></code>
- <code class="c_keyword">using namespace</code> <code class="c_namespace">boost::bloom_filter</code>;
- <code class="c_keyword">using namespace</code> <code class="c_namespace">std</code>;
-
- <code class="c_type">int</code> <code class="c_func">main</code>() {
- <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">INSERT_MAX</code> = 5000;
- <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">CONTAINS_MAX</code> = 10000;
- <code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">NUM_BITS</code> = 8192;
-
- <code class="c_type">bloom_filter</code><int, NUM_BITS> <code class="c_id">bloom</code>;
- <code class="c_type">size_t</code><code class="c_id"> collisions</code> = 0;
-
- <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = 0; i < INSERT_MAX; ++i) {
- bloom.insert(i);
- }
-
- <code class="c_keyword">for</code> (<code class="c_type">int</code><code class="c_id"> i</code> = INSERT_MAX; i < CONTAINS_MAX; ++i) {
- <code class="c_keyword">if</code> (bloom.probably_contains(i)) cout << "collision" << endl;
- }
-
- cout << <code class="c_str">"collisions: "</code>
- << collisions
- << endl;
-
- <code class="c_keyword">return</code> 0;
- }
- </div>
- <div class="example_output">
- $> ./basic_bloom
- collisions: 1808
- </div>
-
- <p>
- Above, we see a simple example that instantiates the default Bloom filter, inserts integers
- 0 - 4999, and then queries the existence of those integers. That's all it takes to use
- this Bloom filter!
- </p>
- <p>
- In practice, where false positive rates matter a great deal, care must be taken to choose not
- only the right bitset Size, but also the right number (and implementation) of hash functions (Hahsers).
- This is where the last template parameter comes in, as well as the remaining member functions.
- To use the Bloom filter to its maximum potential, you must understand how to customize
- these remaining parameters.
- </p>
<ul>
<li>Advanced template parameters:
<ul>
@@ -129,7 +106,7 @@
</p>
<div class="listing">
- <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_id">T, Seed</code>>
+ <code class="c_keyword">template</code> <<code class="c_keyword">typename</code> <code class="c_type">T, Seed</code>>
<code class="c_keyword">struct</code> <code class="c_id">ExampleHasher</code> {
<code class="c_type">size_t</code> <code class="c_func">operator</code>()(<code class="c_keyword">const</code> <code class="c_type">T</code>&) <code class="c_keyword">const</code>;
};
@@ -145,19 +122,19 @@
<div class="listing">
<code class="c_comment">// link: advanced_bloom.cpp</code>
<code class="c_comment">// advanced Boost.BloomFilter program</code>
- <code class="c_keyword">#include</code> <code class="c_include"><boost/bloom_filter/bloom.hpp></code>
+ <code class="c_keyword">#include</code> <code class="c_include"><boost/bloom_filter/basic_bloom_filter.hpp></code>
<code class="c_keyword">#include</code> <code class="c_include"><iostream></code>
- <code class="c_keyword">using namespace</code> <code class="c_namespace">boost::bloom_filter</code>;
+ <code class="c_keyword">using namespace</code> <code class="c_namespace">boost::bloom_filters</code>;
<code class="c_keyword">using namespace</code> <code class="c_namespace">std</code>;
<code class="c_type">int</code> <code class="c_func">main</code>() {
- <code class="c_keyword">typedef</code> <code class="c_namespace">boost::mpl::vector</code><<code class="c_type">boost_hash</code><<code class="c_id">int, 0</code>> > <code class="c_type">HashFns</code>;
+ <code class="c_keyword">typedef</code> <code class="c_namespace">boost::mpl::vector</code><<code class="c_type">boost_hash</code><<code class="c_type">int, 0</code>> > <code class="c_type">HashFns</code>;
<code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">INSERT_MAX</code> = 5000;
<code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">CONTAINS_MAX</code> = 10000;
<code class="c_keyword">static const</code> <code class="c_type">size_t</code> <code class="c_id">NUM_BITS</code> = 8192;
- <code class="c_type">bloom_filter</code><int, NUM_BITS, HashFns> <code class="c_id">bloom</code>;
+ <code class="c_type">basic_bloom_filter</code><int, NUM_BITS, HashFns> <code class="c_id">bloom</code>;
<code class="c_type">size_t</code><code class="c_id"> collisions</code> = 0;
cout << <code class="c_str">"bloom filter storage size: "</code>