286 lines
12 KiB
HTML
286 lines
12 KiB
HTML
<!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>
|