[ceph.git] / ceph / src / boost / libs / flyweight / doc / examples.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 &lt;BR&gt;), character
encoding and HTML entities (e.g. "&amp;copy;" for &copy;) 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&lt;key_value&lt;int,compute_f&gt; &gt;</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>&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>

<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&lt;T&gt;</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&lt;flyweight&lt;std::string&gt; &gt;</code>
    and save the structure to a serialization file.
  </li>
  <li>Load a <code>std::vector&lt;flyweight&lt;std::string&gt; &gt;</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>&copy; Copyright 2006-2014 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;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>
Commit	Line	Data
7c673cae FG	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 <BR>), character
159	encoding and HTML entities (e.g. "&copy;" for ©) 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<key_value<int,compute_f> ></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><</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>
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<T></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<flyweight<std::string> ></code>
218	and save the structure to a serialization file.
219	</li>
220	<li>Load a <code>std::vector<flyweight<std::string> ></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>© Copyright 2006-2014 Joaquín M López Muñ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>