123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
- <html>
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
- <title>Boost.Flyweight Documentation - Examples</title>
- <link rel="stylesheet" href="style.css" type="text/css">
- <link rel="start" href="index.html">
- <link rel="prev" href="performance.html">
- <link rel="up" href="index.html">
- <link rel="next" href="tests.html">
- </head>
- <body>
- <h1><img src="../../../boost.png" alt="Boost logo" align=
- "middle" width="277" height="86">Boost.Flyweight Examples</h1>
- <div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
- Performance
- </a></div>
- <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
- Index
- </a></div>
- <div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
- Tests
- </a></div><br clear="all" style="clear: all;">
- <br clear="all" style="clear: all;">
- <hr>
- <h2>Contents</h2>
- <ul>
- <li><a href="#example1">Example 1: basic usage</a></li>
- <li><a href="#example2">Example 2: key-value flyweights</a></li>
- <li><a href="#example3">Example 3: flyweights and the composite pattern</a></li>
- <li><a href="#example4">Example 4: formatted text processing</a></li>
- <li><a href="#example5">Example 5: flyweight-based memoization</a></li>
- <li><a href="#example6">Example 6: serialization</a></li>
- <li><a href="#example7">Example 7: performance comparison</a></li>
- <li><a href="#example8">Example 8: custom factory</a></li>
- </ul>
- <h2><a name="example1">Example 1: basic usage</a></h2>
- <p>
- See <a href="../example/basic.cpp">source code</a>.
- </p>
- <p>
- Dummy program showing the basic capabilities of <code>flyweight</code>
- explained at the <a href="tutorial/basics.html">tutorial</a>.
- </p>
- <h2><a name="example2">Example 2: key-value flyweights</a></h2>
- <p>
- See <a href="../example/key_value.cpp">source code</a>.
- </p>
- <p>
- The program simulates the scenario described at the tutorial section on
- <a href="tutorial/key_value.html">key-value flyweights</a>: The class
- <code>texture</code> manages some texture rendering data stored in
- a file whose location is given at construction time. The program
- handles large quantities of objects of this class by encapsulating
- them into key-value flyweights keyed by filename. Observe how the
- execution of the program results in no extra constructions or copies
- of objects of type <code>texture</code> except those absolutely
- necessary.
- </p>
- <h2><a name="example3">Example 3: flyweights and the composite pattern</a></h2>
- <p>
- See <a href="../example/composite.cpp">source code</a>.
- </p>
- <p>
- The <a href="http://c2.com/cgi/wiki?CompositePattern"><i>composite
- design pattern</i></a> revolves about the idea that a tree data structure
- can be easily constructed and manipulated by defining the tree node type
- polymorphically so that either is a leaf node or else contains a list of
- pointers to their child nodes.
- This way, a tree is the exact same entity as its root node, which allows
- for very simple recursive tree-handling algorithms. Large composite trees
- having a high degree of duplication of nodes and subtrees (as for instance
- those generated when parsing a computer program) are a natural fit for the
- flyweight idiom: simply turning the node type into a flyweight
- automatically deals with duplication at the node and subtree level.
- </p>
- <p>
- The example program parses Lisp-like lists of the form
- <code>(a<sub>1</sub> ... a<sub><i>n</i></sub>)</code> where each
- <code>a<sub>i</sub></code> is a terminal string or a list. The parsed
- data structure is a composite type defined using Boost.Flyweight in conjunction
- with the recursive facilities of
- <a href="../../variant/index.html">Boost.Variant</a>. So, given the list
- </p>
- <blockquote><pre>
- (= (tan (+ x y))(/ (+ (tan x)(tan y))(- 1 (* (tan x)(tan y)))))
- </pre></blockquote>
- <p>
- the resulting data structure implicitly detects the duplicated
- occurrences of <code>+</code>, <code>x</code>, <code>y</code>,
- <code>tan</code>, <code>(tan x)</code> and <code>(tan y)</code>.
- </p>
- <h2><a name="example4">Example 4: formatted text processing</a></h2>
- <p>
- See <a href="../example/html.cpp">source code</a>.
- </p>
- <p>
- A classic example of application of the flyweight pattern is that of a
- text processor which handles characters with rich formatting information,
- like font type, size, color and special options (boldness, italics, etc.)
- Coding the formatting information of each character takes considerable
- space, but, given the high degree of repetition typical in a document,
- maintaining formatted characters as flyweight objects drastically reduces
- memory consumption.
- </p>
- <p>
- The example program parses, manipulates and stores HTML documents following
- flyweight-based representation techniques. Given the hierarchical nature
- of HTML markup, a crude approximation to the formatting options of a given
- character is just to equate them with the stack of tag contexts to which
- the character belongs, as the figure shows.
- </p>
- <p align="center">
- <img src="html.png"
- alt="formatting contexts of characters in an HTML document"
- width="320" height="275"><br>
- <b>Fig. 1: Formatting contexts of characters in an HTML document.</b>
- </p>
- <p>
- HTML documents are then parsed as arrays of (character, format)
- pairs, where the format is the tag context as described above. The very high
- degree of redundancy in formatting information is taken care of by the
- use of Boost.Flyweight. This character-based representation makes it
- easy to manipulate the document: transposition and elimination of
- portions of text are trivial operations. As an example, the program
- reverses the text occupying the central portion of the document.
- Saving the result in HTML reduces to traversing the array of formatted
- characters and emitting opening/closing HTML tags as the context of adjacent
- characters varies.
- </p>
- <p>
- For the sake of brevity, the HTML parsing capabilities of this program
- are coarse: for instance, elements without end-tag (like <BR>), character
- encoding and HTML entities (e.g. "&copy;" for ©) are not properly
- handled. Improving the parsing code is left as an exercise to the reader.
- </p>
- <h2><a name="example5">Example 5: flyweight-based memoization</a></h2>
- <p>
- See <a href="../example/fibonacci.cpp">source code</a>.
- </p>
- <p>
- <a href="http://en.wikipedia.org/wiki/Memoization">Memoization</a>
- is an optimization technique consisting in caching
- the results of a computation for later reuse; this can dramatically
- improve performance when calculating recursive numerical functions,
- for instance. <a href="tutorial/key_value.html">Key-value flyweights</a>
- can be used to implement memoization for a numerical function <i>f</i>
- by modeling a memoized invocation of the function as a value of
- type <code>flyweight<key_value<int,compute_f> ></code>, where
- <code>compute_f</code> is a type that does the computation of
- <i>f</i>(<i>n</i>) at its <code>compute_f::compute_f(int)</code> constructor.
- For instance, the <a href="http://mathworld.wolfram.com/FibonacciNumber.html">Fibonacci
- numbers</a> can be computed with memoization like this:
- </p>
- <blockquote><pre>
- <span class=keyword>typedef</span> <span class=identifier>flyweight</span><span class=special><</span><span class=identifier>key_value</span><span class=special><</span><span class=keyword>int</span><span class=special>,</span><span class=identifier>compute_fibonacci</span><span class=special>>,</span><span class=identifier>no_tracking</span><span class=special>></span> <span class=identifier>fibonacci</span><span class=special>;</span>
- <span class=keyword>struct</span> <span class=identifier>compute_fibonacci</span>
- <span class=special>{</span>
- <span class=identifier>compute_fibonacci</span><span class=special>(</span><span class=keyword>int</span> <span class=identifier>n</span><span class=special>):</span>
- <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>
- <span class=special>{}</span>
- <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>
- <span class=keyword>int</span> <span class=identifier>result</span><span class=special>;</span>
- <span class=special>};</span>
- </pre></blockquote>
- <p>
- The <a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a>
- policy is used so that the memoized computations persist for future
- use throughout the program. The provided program develops this example in full.
- </p>
- <h2><a name="example6">Example 6: serialization</a></h2>
- <p>
- See <a href="../example/serialization.cpp">source code</a>.
- </p>
- <p>
- If <code>T</code> is serializable (using
- <a href="../../serialization/index.html">Boost.Serialization</a>),
- <code>flyweight<T></code> is automatically
- serializable as well. The example program performs the following two
- complementary procedures:
- <ul>
- <li>Read a text file as a <code>std::vector<flyweight<std::string> ></code>
- and save the structure to a serialization file.
- </li>
- <li>Load a <code>std::vector<flyweight<std::string> ></code> from a
- serialization file and write it as a text file.
- </li>
- </ul>
- If you visually inspect the contents of any of the generated serialization files
- you can notice that no word appears twice; Boost.Flyweight implements some internal
- machinery that avoids duplicating output information when saving equal
- <code>flyweight</code> objects.
- </p>
- <h2><a name="example7">Example 7: performance comparison</a></h2>
- <p>
- See <a href="../example/perf.cpp">source code</a>.
- </p>
- <p>
- This program measures the time and space performances of a simple
- string type against several differently configured <code>flyweight</code>
- instantations as used in a conventional task involving parsing a file and
- doing some manipulations on the parsed text.
- Memory consumption is computed by instrumenting the relevant
- components (the string type itself, flyweight factories, etc.) with custom
- allocators that keep track of the allocations and deallocations requested.
- The program has been used to produce the experimental results given
- at the <a href="performance.html#results">performance section</a>.
- </p>
- <h2><a name="example8">Example 8: custom factory</a></h2>
- <p>
- See <a href="../example/custom_factory.cpp">source code</a>.
- </p>
- <p>
- The example shows how to write and use a custom factory class. This
- "verbose" factory outputs messages tracing the invocations of its public interface
- by Boost.Flyweight, so helping the user visualize factory usage patterns.
- </p>
- <hr>
- <div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
- Performance
- </a></div>
- <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
- Index
- </a></div>
- <div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
- Tests
- </a></div><br clear="all" style="clear: all;">
- <br clear="all" style="clear: all;">
- <br>
- <p>Revised October 14th 2014</p>
- <p>© Copyright 2006-2014 Joaquín M López Muñoz.
- Distributed under the Boost Software
- License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
- LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
- http://www.boost.org/LICENSE_1_0.txt</a>)
- </p>
- </body>
- </html>
|