ceph/src/boost/libs/flyweight/doc/examples.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
   2
   3 <html>
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   6 <title>Boost.Flyweight Documentation - Examples</title>
   7 <link rel="stylesheet" href="style.css" type="text/css">
   8 <link rel="start" href="index.html">
   9 <link rel="prev" href="performance.html">
  10 <link rel="up" href="index.html">
  11 <link rel="next" href="tests.html">
  12 </head>
  13
  14 <body>
  15 <h1><img src="../../../boost.png" alt="Boost logo" align=
  16 "middle" width="277" height="86">Boost.Flyweight Examples</h1>
  17
  18 <div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
  19 Performance
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
  22 Index
  23 </a></div>
  24 <div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
  25 Tests
  26 </a></div><br clear="all" style="clear: all;">
  27 <br clear="all" style="clear: all;">
  28
  29 <hr>
  30
  31 <h2>Contents</h2>
  32
  33 <ul>
  34   <li><a href="#example1">Example 1: basic usage</a></li>
  35   <li><a href="#example2">Example 2: key-value flyweights</a></li>
  36   <li><a href="#example3">Example 3: flyweights and the composite pattern</a></li>
  37   <li><a href="#example4">Example 4: formatted text processing</a></li>
  38   <li><a href="#example5">Example 5: flyweight-based memoization</a></li>
  39   <li><a href="#example6">Example 6: serialization</a></li>
  40   <li><a href="#example7">Example 7: performance comparison</a></li>
  41   <li><a href="#example8">Example 8: custom factory</a></li>
  42 </ul>
  43
  44 <h2><a name="example1">Example 1: basic usage</a></h2>
  45
  46 <p>
  47 See <a href="../example/basic.cpp">source code</a>.
  48 </p>
  49
  50 <p>
  51 Dummy program showing the basic capabilities of <code>flyweight</code>
  52 explained at the <a href="tutorial/basics.html">tutorial</a>.
  53 </p>
  54
  55 <h2><a name="example2">Example 2: key-value flyweights</a></h2>
  56
  57 <p>
  58 See <a href="../example/key_value.cpp">source code</a>.
  59 </p>
  60
  61 <p>
  62 The program simulates the scenario described at the tutorial section on
  63 <a href="tutorial/key_value.html">key-value flyweights</a>: The class
  64 <code>texture</code> manages some texture rendering data stored in
  65 a file whose location is given at construction time. The program
  66 handles large quantities of objects of this class by encapsulating
  67 them into key-value flyweights keyed by filename. Observe how the
  68 execution of the program results in no extra constructions or copies
  69 of objects of type <code>texture</code> except those absolutely
  70 necessary.
  71 </p>
  72
  73 <h2><a name="example3">Example 3: flyweights and the composite pattern</a></h2>
  74
  75 <p>
  76 See <a href="../example/composite.cpp">source code</a>.
  77 </p>
  78
  79 <p>
  80 The <a href="http://c2.com/cgi/wiki?CompositePattern"><i>composite
  81 design pattern</i></a> revolves about the idea that a tree data structure
  82 can be easily constructed and manipulated by defining the tree node type
  83 polymorphically so that either is a leaf node or else contains a list of
  84 pointers to their child nodes.
  85 This way, a tree is the exact same entity as its root node, which allows
  86 for very simple recursive tree-handling algorithms. Large composite trees
  87 having a high degree of duplication of nodes and subtrees (as for instance
  88 those generated when parsing a computer program) are a natural fit for the
  89 flyweight idiom: simply turning the node type into a flyweight
  90 automatically deals with duplication at the node and subtree level.
  91 </p>
  92
  93 <p>
  94 The example program parses Lisp-like lists of the form
  95 <code>(a<sub>1</sub> ... a<sub><i>n</i></sub>)</code> where each
  96 <code>a<sub>i</sub></code> is a terminal string or a list. The parsed
  97 data structure is a composite type defined using Boost.Flyweight in conjunction
  98 with the recursive facilities of
  99 <a href="../../variant/index.html">Boost.Variant</a>. So, given the list
 100 </p>
 101
 102 <blockquote><pre>
 103 (= (tan (+ x y))(/ (+ (tan x)(tan y))(- 1 (* (tan x)(tan y)))))
 104 </pre></blockquote>
 105
 106 <p>
 107 the resulting data structure implicitly detects the duplicated
 108 occurrences of <code>+</code>, <code>x</code>, <code>y</code>,
 109 <code>tan</code>, <code>(tan x)</code> and <code>(tan y)</code>.
 110 </p>
 111
 112 <h2><a name="example4">Example 4: formatted text processing</a></h2>
 113
 114 <p>
 115 See <a href="../example/html.cpp">source code</a>.
 116 </p>
 117
 118 <p>
 119 A classic example of application of the flyweight pattern is that of a
 120 text processor which handles characters with rich formatting information,
 121 like font type, size, color and special options (boldness, italics, etc.)
 122 Coding the formatting information of each character takes considerable
 123 space, but, given the high degree of repetition typical in a document,
 124 maintaining formatted characters as flyweight objects drastically reduces
 125 memory consumption.
 126 </p>
 127
 128 <p>
 129 The example program parses, manipulates and stores HTML documents following
 130 flyweight-based representation techniques. Given the hierarchical nature
 131 of HTML markup, a crude approximation to the formatting options of a given
 132 character is just to equate them with the stack of tag contexts to which
 133 the character belongs, as the figure shows.
 134 </p>
 135
 136 <p align="center">
 137 <img src="html.png"
 138 alt="formatting contexts of characters in an HTML document"
 139 width="320" height="275"><br>
 140 <b>Fig. 1: Formatting contexts of characters in an HTML document.</b>
 141 </p>
 142
 143 <p>
 144 HTML documents are then parsed as arrays of (character, format)
 145 pairs, where the format is the tag context as described above. The very high
 146 degree of redundancy in formatting information is taken care of by the
 147 use of Boost.Flyweight. This character-based representation makes it
 148 easy to manipulate the document: transposition and elimination of
 149 portions of text are trivial operations. As an example, the program
 150 reverses the text occupying the central portion of the document.
 151 Saving the result in HTML reduces to traversing the array of formatted
 152 characters and emitting opening/closing HTML tags as the context of adjacent
 153 characters varies.
 154 </p>
 155
 156 <p>
 157 For the sake of brevity, the HTML parsing capabilities of this program
 158 are coarse: for instance, elements without end-tag (like &lt;BR&gt;), character
 159 encoding and HTML entities (e.g. "&amp;copy;" for &copy;) are not properly
 160 handled. Improving the parsing code is left as an exercise to the reader.
 161 </p>
 162
 163 <h2><a name="example5">Example 5: flyweight-based memoization</a></h2>
 164
 165 <p>
 166 See <a href="../example/fibonacci.cpp">source code</a>.
 167 </p>
 168
 169 <p>
 170 <a href="http://en.wikipedia.org/wiki/Memoization">Memoization</a>
 171 is an optimization technique consisting in caching
 172 the results of a computation for later reuse; this can dramatically
 173 improve performance when calculating recursive numerical functions,
 174 for instance. <a href="tutorial/key_value.html">Key-value flyweights</a>
 175 can be used to implement memoization for a numerical function <i>f</i>
 176 by modeling a memoized invocation of the function as a value of
 177 type <code>flyweight&lt;key_value&lt;int,compute_f&gt; &gt;</code>, where
 178 <code>compute_f</code> is a type that does the computation of
 179 <i>f</i>(<i>n</i>) at its <code>compute_f::compute_f(int)</code> constructor.
 180 For instance, the <a href="http://mathworld.wolfram.com/FibonacciNumber.html">Fibonacci
 181 numbers</a> can be computed with memoization like this:
 182 </p>
 183
 184 <blockquote><pre>
 185 <span class=keyword>typedef</span> <span class=identifier>flyweight</span><span class=special>&lt;</span><span class=identifier>key_value</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>,</span><span class=identifier>compute_fibonacci</span><span class=special>&gt;,</span><span class=identifier>no_tracking</span><span class=special>&gt;</span> <span class=identifier>fibonacci</span><span class=special>;</span>
 186
 187 <span class=keyword>struct</span> <span class=identifier>compute_fibonacci</span>
 188 <span class=special>{</span>
 189   <span class=identifier>compute_fibonacci</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>n</span><span class=special>):</span>
 190     <span class=identifier>result</span><span class=special>(</span><span class=identifier>n</span><span class=special>==</span><span class=number>0</span><span class=special>?</span><span class=number>0</span><span class=special>:</span><span class=identifier>n</span><span class=special>==</span><span class=number>1</span><span class=special>?</span><span class=number>1</span><span class=special>:</span><span class=identifier>fibonacci</span><span class=special>(</span><span class=identifier>n</span><span class=special>-</span><span class=number>2</span><span class=special>).</span><span class=identifier>get</span><span class=special>()+</span><span class=identifier>fibonacci</span><span class=special>(</span><span class=identifier>n</span><span class=special>-</span><span class=number>1</span><span class=special>).</span><span class=identifier>get</span><span class=special>())</span>
 191   <span class=special>{}</span>
 192
 193   <span class=keyword>operator</span> <span class=keyword>int</span><span class=special>()</span><span class=keyword>const</span><span class=special>{</span><span class=keyword>return</span> <span class=identifier>result</span><span class=special>;}</span>
 194   <span class=keyword>int</span> <span class=identifier>result</span><span class=special>;</span>
 195 <span class=special>};</span>
 196 </pre></blockquote>
 197
 198 <p>
 199 The <a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a>
 200 policy is used so that the memoized computations persist for future
 201 use throughout the program. The provided program develops this example in full.
 202 </p>
 203
 204 <h2><a name="example6">Example 6: serialization</a></h2>
 205
 206 <p>
 207 See <a href="../example/serialization.cpp">source code</a>.
 208 </p>
 209
 210 <p>
 211 If <code>T</code> is serializable (using
 212 <a href="../../serialization/index.html">Boost.Serialization</a>),
 213 <code>flyweight&lt;T&gt;</code> is automatically
 214 serializable as well. The example program performs the following two
 215 complementary procedures:
 216 <ul>
 217   <li>Read a text file as a <code>std::vector&lt;flyweight&lt;std::string&gt; &gt;</code>
 218     and save the structure to a serialization file.
 219   </li>
 220   <li>Load a <code>std::vector&lt;flyweight&lt;std::string&gt; &gt;</code> from a
 221     serialization file and write it as a text file.
 222   </li>
 223 </ul>
 224 If you visually inspect the contents of any of the generated serialization files
 225 you can notice that no word appears twice; Boost.Flyweight implements some internal
 226 machinery that avoids duplicating output information when saving equal
 227 <code>flyweight</code> objects.
 228 </p>
 229
 230 <h2><a name="example7">Example 7: performance comparison</a></h2>
 231
 232 <p>
 233 See <a href="../example/perf.cpp">source code</a>.
 234 </p>
 235
 236 <p>
 237 This program measures the time and space performances of a simple
 238 string type against several differently configured <code>flyweight</code>
 239 instantations as used in a conventional task involving parsing a file and
 240 doing some manipulations on the parsed text.
 241 Memory consumption is computed by instrumenting the relevant
 242 components (the string type itself, flyweight factories, etc.) with custom
 243 allocators that keep track of the allocations and deallocations requested.
 244 The program has been used to produce the experimental results given
 245 at the <a href="performance.html#results">performance section</a>.
 246 </p>
 247
 248 <h2><a name="example8">Example 8: custom factory</a></h2>
 249
 250 <p>
 251 See <a href="../example/custom_factory.cpp">source code</a>.
 252 </p>
 253
 254 <p>
 255 The example shows how to write and use a custom factory class. This
 256 "verbose" factory outputs messages tracing the invocations of its public interface
 257 by Boost.Flyweight, so helping the user visualize factory usage patterns.
 258 </p>
 259
 260 <hr>
 261
 262 <div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
 263 Performance
 264 </a></div>
 265 <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
 266 Index
 267 </a></div>
 268 <div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
 269 Tests
 270 </a></div><br clear="all" style="clear: all;">
 271 <br clear="all" style="clear: all;">
 272
 273 <br>
 274
 275 <p>Revised October 14th 2014</p>
 276
 277 <p>&copy; Copyright 2006-2014 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
 278 Distributed under the Boost Software
 279 License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
 280 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
 281 http://www.boost.org/LICENSE_1_0.txt</a>)
 282 </p>
 283
 284 </body>
 285 </html>