1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Party</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.74.0">
<link rel="home" href="../../index.html" title="Chapter 1. Boost.Icl">
<link rel="up" href="../examples.html" title="Examples">
<link rel="prev" href="../examples.html" title="Examples">
<link rel="next" href="interval.html" title="Interval">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../examples.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../examples.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="interval.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section" lang="en">
<div class="titlepage"><div><div><h3 class="title">
<a name="boost_icl.examples.party"></a><a class="link" href="party.html" title="Party">Party</a>
</h3></div></div></div>
<p>
Example <span class="bold"><strong>party</strong></span> demonstrates the possibilities
of an interval map (<code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>
or <code class="computeroutput"><a class="link" href="../../boost/icl/split_interval_map.html" title="Class template split_interval_map">split_interval_map</a></code>).
An <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code> maps
intervals to a given content. In this case the content is a set of party
guests represented by their name strings.
</p>
<p>
As time goes by, groups of people join the party and leave later in the evening.
So we add a time interval and a name set to the <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>
for the attendance of each group of people, that come together and leave
together. On every overlap of intervals, the corresponding name sets are
accumulated. At the points of overlap the intervals are split. The accumulation
of content is done via an operator += that has to be implemented for the
content parameter of the <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_map</a></code>.
Finally the interval_map contains the history of attendance and all points
in time, where the group of party guests changed.
</p>
<p>
Party demonstrates a principle that we call <span class="emphasis"><em><span class="bold"><strong>aggregate
on overlap</strong></span></em></span>: On insertion a value associated to the
interval is aggregated with those values in the interval_map that overlap
with the inserted value. There are two behavioral aspects to <span class="emphasis"><em><span class="bold"><strong>aggregate on overlap</strong></span></em></span>: a <span class="emphasis"><em><span class="bold"><strong>decompositional behavior</strong></span></em></span> and an <span class="emphasis"><em><span class="bold"><strong>accumulative behavior</strong></span></em></span>.
</p>
<div class="itemizedlist"><ul type="disc">
<li>
The <span class="emphasis"><em><span class="bold"><strong>decompositional behavior</strong></span></em></span>
splits up intervals on the <span class="emphasis"><em>time</em></span><span class="emphasis"><em>dimension</em></span>
of the interval_map so that the intervals are split whenever associated
values change.
</li>
<li>
The <span class="emphasis"><em><span class="bold"><strong>accumulative behavior</strong></span></em></span>
accumulates associated values on every overlap of an insertion for the
associated values.
</li>
</ul></div>
<p>
The aggregation function is += by default. Different aggregations can be
used, if desired.
</p>
<p>
</p>
<p>
</p>
<pre class="programlisting"><span class="comment">// The next line includes <boost/date_time/posix_time/posix_time.hpp>
</span><span class="comment">// and a few lines of adapter code.
</span><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">icl</span><span class="special">/</span><span class="identifier">ptime</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">iostream</span><span class="special">></span>
<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">icl</span><span class="special">/</span><span class="identifier">interval_map</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">std</span><span class="special">;</span>
<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">posix_time</span><span class="special">;</span>
<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">icl</span><span class="special">;</span>
<span class="comment">// Type set<string> collects the names of party guests. Since std::set is
</span><span class="comment">// a model of the itl's set concept, the concept provides an operator +=
</span><span class="comment">// that performs a set union on overlap of intervals.
</span><span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special"><</span><span class="identifier">string</span><span class="special">></span> <span class="identifier">GuestSetT</span><span class="special">;</span>
<span class="keyword">void</span> <span class="identifier">boost_party</span><span class="special">()</span>
<span class="special">{</span>
<span class="identifier">GuestSetT</span> <span class="identifier">mary_harry</span><span class="special">;</span>
<span class="identifier">mary_harry</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="string">"Mary"</span><span class="special">);</span>
<span class="identifier">mary_harry</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="string">"Harry"</span><span class="special">);</span>
<span class="identifier">GuestSetT</span> <span class="identifier">diana_susan</span><span class="special">;</span>
<span class="identifier">diana_susan</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="string">"Diana"</span><span class="special">);</span>
<span class="identifier">diana_susan</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="string">"Susan"</span><span class="special">);</span>
<span class="identifier">GuestSetT</span> <span class="identifier">peter</span><span class="special">;</span>
<span class="identifier">peter</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="string">"Peter"</span><span class="special">);</span>
<span class="comment">// A party is an interval map that maps time intervals to sets of guests
</span> <span class="identifier">interval_map</span><span class="special"><</span><span class="identifier">ptime</span><span class="special">,</span> <span class="identifier">GuestSetT</span><span class="special">></span> <span class="identifier">party</span><span class="special">;</span>
<span class="identifier">party</span><span class="special">.</span><span class="identifier">add</span><span class="special">(</span> <span class="comment">// add and element
</span> <span class="identifier">make_pair</span><span class="special">(</span>
<span class="identifier">interval</span><span class="special"><</span><span class="identifier">ptime</span><span class="special">>::</span><span class="identifier">right_open</span><span class="special">(</span>
<span class="identifier">time_from_string</span><span class="special">(</span><span class="string">"2008-05-20 19:30"</span><span class="special">),</span>
<span class="identifier">time_from_string</span><span class="special">(</span><span class="string">"2008-05-20 23:00"</span><span class="special">)),</span>
<span class="identifier">mary_harry</span><span class="special">));</span>
<span class="identifier">party</span> <span class="special">+=</span> <span class="comment">// element addition can also be done via operator +=
</span> <span class="identifier">make_pair</span><span class="special">(</span>
<span class="identifier">interval</span><span class="special"><</span><span class="identifier">ptime</span><span class="special">>::</span><span class="identifier">right_open</span><span class="special">(</span>
<span class="identifier">time_from_string</span><span class="special">(</span><span class="string">"2008-05-20 20:10"</span><span class="special">),</span>
<span class="identifier">time_from_string</span><span class="special">(</span><span class="string">"2008-05-21 00:00"</span><span class="special">)),</span>
<span class="identifier">diana_susan</span><span class="special">);</span>
<span class="identifier">party</span> <span class="special">+=</span>
<span class="identifier">make_pair</span><span class="special">(</span>
<span class="identifier">interval</span><span class="special"><</span><span class="identifier">ptime</span><span class="special">>::</span><span class="identifier">right_open</span><span class="special">(</span>
<span class="identifier">time_from_string</span><span class="special">(</span><span class="string">"2008-05-20 22:15"</span><span class="special">),</span>
<span class="identifier">time_from_string</span><span class="special">(</span><span class="string">"2008-05-21 00:30"</span><span class="special">)),</span>
<span class="identifier">peter</span><span class="special">);</span>
<span class="identifier">interval_map</span><span class="special"><</span><span class="identifier">ptime</span><span class="special">,</span> <span class="identifier">GuestSetT</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">it</span> <span class="special">=</span> <span class="identifier">party</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span>
<span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"----- History of party guests -------------------------\n"</span><span class="special">;</span>
<span class="keyword">while</span><span class="special">(</span><span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">party</span><span class="special">.</span><span class="identifier">end</span><span class="special">())</span>
<span class="special">{</span>
<span class="identifier">interval</span><span class="special"><</span><span class="identifier">ptime</span><span class="special">>::</span><span class="identifier">type</span> <span class="identifier">when</span> <span class="special">=</span> <span class="identifier">it</span><span class="special">-></span><span class="identifier">first</span><span class="special">;</span>
<span class="comment">// Who is at the party within the time interval 'when' ?
</span> <span class="identifier">GuestSetT</span> <span class="identifier">who</span> <span class="special">=</span> <span class="special">(*</span><span class="identifier">it</span><span class="special">++).</span><span class="identifier">second</span><span class="special">;</span>
<span class="identifier">cout</span> <span class="special"><<</span> <span class="identifier">when</span> <span class="special"><<</span> <span class="string">": "</span> <span class="special"><<</span> <span class="identifier">who</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span>
<span class="special">}</span>
<span class="special">}</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
<span class="identifier">cout</span> <span class="special"><<</span> <span class="string">">>Interval Container Library: Sample boost_party.cpp <<\n"</span><span class="special">;</span>
<span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"-------------------------------------------------------\n"</span><span class="special">;</span>
<span class="identifier">boost_party</span><span class="special">();</span>
<span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
<span class="comment">// Program output:
</span><span class="comment">/*-----------------------------------------------------------------------------
>>Interval Container Library: Sample boost_party.cpp <<
-------------------------------------------------------
----- History of party guests -------------------------
[2008-May-20 19:30:00, 2008-May-20 20:10:00): Harry Mary
[2008-May-20 20:10:00, 2008-May-20 22:15:00): Diana Harry Mary Susan
[2008-May-20 22:15:00, 2008-May-20 23:00:00): Diana Harry Mary Peter Susan
[2008-May-20 23:00:00, 2008-May-21 00:00:00): Diana Peter Susan
[2008-May-21 00:00:00, 2008-May-21 00:30:00): Peter
-----------------------------------------------------------------------------*/</span>
</pre>
<p>
</p>
<p>
</p>
<div class="caution"><table border="0" summary="Caution">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Caution]" src="../../../../../../doc/src/images/caution.png"></td>
<th align="left">Caution</th>
</tr>
<tr><td align="left" valign="top">
<p>
</p>
<p>
We are introducing <code class="computeroutput"><a class="link" href="../../boost/icl/interval_map.html" title="Class template interval_map">interval_maps</a></code>
using an <span class="emphasis"><em>interval map <span class="emphasis"><em><span class="bold"><strong>of sets
of strings</strong></span></em></span></em></span>, because of it's didactic advantages.
The party example is used to give an immediate access to the basic ideas
of interval maps and <span class="emphasis"><em>aggregate on overlap</em></span>. For real
world applications, an interval_map of sets is not necessarily recommended.
It has the same efficiency problems as a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code>
of <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">sets</span></code>. There is a big realm though of
using interval_maps with numerical and other efficient data types for the
associated values.
</p>
</td></tr>
</table></div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2007 -2010 Joachim Faulhaber<br>Copyright © 1999 -2006 Cortex Software GmbH<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../examples.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../examples.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="interval.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
