3 <meta http-equiv=
"Content-Type" content=
"text/html; charset=US-ASCII">
4 <title>Addability, Subtractability and Aggregate on Overlap
</title>
5 <link rel=
"stylesheet" href=
"../../../../../../doc/src/boostbook.css" type=
"text/css">
6 <meta name=
"generator" content=
"DocBook XSL Stylesheets V1.74.0">
7 <link rel=
"home" href=
"../../index.html" title=
"Chapter 1. Boost.Icl">
8 <link rel=
"up" href=
"../concepts.html" title=
"Concepts">
9 <link rel=
"prev" href=
"sets_and_maps.html" title=
"Sets and Maps">
10 <link rel=
"next" href=
"map_traits.html" title=
"Map Traits">
12 <body bgcolor=
"white" text=
"black" link=
"#0000FF" vlink=
"#840084" alink=
"#0000FF">
13 <table cellpadding=
"2" width=
"100%"><tr>
14 <td valign=
"top"><img alt=
"Boost C++ Libraries" width=
"277" height=
"86" src=
"../../../../../../boost.png"></td>
15 <td align=
"center"><a href=
"../../../../../../index.html">Home
</a></td>
16 <td align=
"center"><a href=
"../../../../../libraries.htm">Libraries
</a></td>
17 <td align=
"center"><a href=
"http://www.boost.org/users/people.html">People
</a></td>
18 <td align=
"center"><a href=
"http://www.boost.org/users/faq.html">FAQ
</a></td>
19 <td align=
"center"><a href=
"../../../../../../more/index.htm">More
</a></td>
22 <div class=
"spirit-nav">
23 <a accesskey=
"p" href=
"sets_and_maps.html"><img src=
"../../../../../../doc/src/images/prev.png" alt=
"Prev"></a><a accesskey=
"u" href=
"../concepts.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=
"map_traits.html"><img src=
"../../../../../../doc/src/images/next.png" alt=
"Next"></a>
25 <div class=
"section boost_icl_concepts_aggrovering" lang=
"en">
26 <div class=
"titlepage"><div><div><h3 class=
"title">
27 <a name=
"boost_icl.concepts.aggrovering"></a><a class=
"link" href=
"aggrovering.html" title=
"Addability, Subtractability and Aggregate on Overlap"> Addability, Subtractability
28 and Aggregate on Overlap
</a>
29 </h3></div></div></div>
31 While
<span class=
"emphasis"><em><span class=
"bold"><strong>addition
</strong></span></em></span> and
32 <span class=
"emphasis"><em><span class=
"bold"><strong>subtraction
</strong></span></em></span> on
<code class=
"computeroutput"><span class=
"identifier">Sets
</span></code> are implemented as
<span class=
"emphasis"><em><span class=
"bold"><strong>set union
</strong></span></em></span> and
<span class=
"emphasis"><em><span class=
"bold"><strong>set
33 difference
</strong></span></em></span>, for
<code class=
"computeroutput"><span class=
"identifier">Maps
</span></code>
34 we want to implement
<span class=
"emphasis"><em><span class=
"bold"><strong>aggregation
</strong></span></em></span>
35 on the associated values for the case of collision (of key elements) or overlap
36 (of key intervals), which has been refered to as
<span class=
"emphasis"><em><span class=
"bold"><strong>aggregate
37 on overlap
</strong></span></em></span> above. This kind of
<code class=
"computeroutput"><span class=
"identifier">Addability
</span></code>
38 and
<code class=
"computeroutput"><span class=
"identifier">Subtractability
</span></code> allows
39 to compute a lot of useful aggregation results on an
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/interval_map.html" title=
"Class template interval_map">interval_map's
</a></code>
40 associated values, just by adding and subtracting value pairs. Various examples
41 of
<span class=
"emphasis"><em><span class=
"bold"><strong>aggregate on overlap
</strong></span></em></span>
42 are given in
<a class=
"link" href=
"../examples.html" title=
"Examples">section examples
</a>.
43 In addition, this concept of
<code class=
"computeroutput"><span class=
"identifier">Addability
</span></code>
44 and
<code class=
"computeroutput"><span class=
"identifier">Subtractability
</span></code> contains
45 the classical
<code class=
"computeroutput"><span class=
"identifier">Insertability
</span></code>
46 and
<code class=
"computeroutput"><span class=
"identifier">Erasability
</span></code> of key value
47 pairs as a special case so it provides a broader new semantics without loss
48 of the
<span class=
"emphasis"><em>classical
</em></span> one.
51 Aggregation is implemented for functions
<code class=
"computeroutput"><span class=
"identifier">add
</span></code>
52 and
<code class=
"computeroutput"><span class=
"identifier">subtract
</span></code> by propagating
53 a
<code class=
"computeroutput"><span class=
"identifier">Combiner
</span></code> functor to combine
54 associated values of type
<code class=
"computeroutput"><span class=
"identifier">CodomainT
</span></code>.
55 The standard
<code class=
"computeroutput"><span class=
"identifier">Combiner
</span></code> is
56 set as default template parameter
<code class=
"computeroutput"><span class=
"keyword">template
</span><span class=
"special"><</span><span class=
"keyword">class
</span><span class=
"special">></span><span class=
"keyword">class
</span> <span class=
"identifier">Combine
</span> <span class=
"special">=
</span> <span class=
"identifier">inplace_plus
</span></code>, which is again generically
57 implemented by
<code class=
"computeroutput"><span class=
"keyword">operator
</span> <span class=
"special">+=
</span></code>
58 for all Addable types.
61 For
<code class=
"computeroutput"><span class=
"identifier">Combine
</span></code> functors, the
62 Icl provides an
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inverse.html" title=
"Struct template inverse">inverse
</a></code>
65 <div class=
"informaltable"><table class=
"table">
73 <code class=
"computeroutput"><span class=
"identifier">Combine
</span><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
78 <code class=
"computeroutput"><span class=
"identifier">inverse
</span><span class=
"special"><</span><span class=
"identifier">Combine
</span><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span>
79 <span class=
"special">>::
</span><span class=
"identifier">type
</span></code>
87 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_plus.html" title=
"Struct template inplace_plus">inplace_plus
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
92 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_minus.html" title=
"Struct template inplace_minus">inplace_minus
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
99 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_et.html" title=
"Struct template inplace_et">inplace_et
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
104 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_caret.html" title=
"Struct template inplace_caret">inplace_caret
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
111 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_star.html" title=
"Struct template inplace_star">inplace_star
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
116 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_slash.html" title=
"Struct template inplace_slash">inplace_slash
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
123 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_max.html" title=
"Struct template inplace_max">inplace_max
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
128 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_min.html" title=
"Struct template inplace_min">inplace_min
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
135 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_identity.html" title=
"Struct template inplace_identity">inplace_identity
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
140 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_erasure.html" title=
"Struct template inplace_erasure">inplace_erasure
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
147 <code class=
"computeroutput"><span class=
"identifier">Functor
</span></code>
152 <code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inplace_erasure.html" title=
"Struct template inplace_erasure">inplace_erasure
</a></code><code class=
"computeroutput"><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>
159 The meta function
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inverse.html" title=
"Struct template inverse">inverse
</a></code>
160 is mutually implemented for all but the default functor
<code class=
"computeroutput"><span class=
"identifier">Functor
</span></code>
161 such that e.g.
<code class=
"computeroutput"><span class=
"identifier">inverse
</span><span class=
"special"><</span><span class=
"identifier">inplace_minus
</span><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span> <span class=
"special">>::
</span><span class=
"identifier">type
</span></code>
162 yields
<code class=
"computeroutput"><span class=
"identifier">inplace_plus
</span><span class=
"special"><</span><span class=
"identifier">T
</span><span class=
"special">></span></code>.
163 Not in every case, e.g.
<code class=
"computeroutput"><span class=
"identifier">max
</span><span class=
"special">/
</span><span class=
"identifier">min
</span></code>, does
164 the
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/inverse.html" title=
"Struct template inverse">inverse
</a></code> functor invert
165 the effect of it's antetype. But for the default it does:
167 <div class=
"informaltable"><table class=
"table">
180 <code class=
"computeroutput"><span class=
"identifier">_add
</span><span class=
"special"><</span><span class=
"identifier">Combine
</span><span class=
"special"><</span><span class=
"identifier">CodomainT
</span><span class=
"special">></span>
181 <span class=
"special">>((
</span><span class=
"identifier">k
</span><span class=
"special">,
</span><span class=
"identifier">x
</span><span class=
"special">))
</span></code>
186 <code class=
"computeroutput"><span class=
"identifier">_subtract
</span><span class=
"special"><</span><span class=
"identifier">inverse
</span><span class=
"special"><</span><span class=
"identifier">Combine
</span><span class=
"special"><</span><span class=
"identifier">CodomainT
</span><span class=
"special">></span>
187 <span class=
"special">>::
</span><span class=
"identifier">type
</span><span class=
"special">>((
</span><span class=
"identifier">k
</span><span class=
"special">,
</span><span class=
"identifier">x
</span><span class=
"special">))
</span></code>
200 <code class=
"computeroutput"><span class=
"identifier">_add
</span><span class=
"special"><</span><span class=
"identifier">inplace_plus
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">></span>
201 <span class=
"special">>((
</span><span class=
"identifier">k
</span><span class=
"special">,
</span><span class=
"identifier">x
</span><span class=
"special">))
</span></code>
206 <code class=
"computeroutput"><span class=
"identifier">_subtract
</span><span class=
"special"><</span><span class=
"identifier">inplace_minus
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">></span>
207 <span class=
"special">>((
</span><span class=
"identifier">k
</span><span class=
"special">,
</span><span class=
"identifier">x
</span><span class=
"special">))
</span></code>
219 adds
<code class=
"computeroutput"><span class=
"identifier">x
</span></code> on overlap.
220 This inverts a preceding
<code class=
"computeroutput"><span class=
"identifier">subtract
</span></code>
221 of
<code class=
"computeroutput"><span class=
"identifier">x
</span></code> on
<code class=
"computeroutput"><span class=
"identifier">k
</span></code>
226 subtracts
<code class=
"computeroutput"><span class=
"identifier">x
</span></code> on overlap.
227 This inverts a preceding
<code class=
"computeroutput"><span class=
"identifier">add
</span></code>
228 of
<code class=
"computeroutput"><span class=
"identifier">x
</span></code> on
<code class=
"computeroutput"><span class=
"identifier">k
</span></code>
235 As already mentioned aggregating
<code class=
"computeroutput"><span class=
"identifier">Addability
</span></code>
236 and
<code class=
"computeroutput"><span class=
"identifier">Subtractability
</span></code> on
<code class=
"computeroutput"><span class=
"identifier">Maps
</span></code> contains the
<span class=
"emphasis"><em>classical
</em></span>
237 <code class=
"computeroutput"><span class=
"identifier">Insertability
</span></code> and
<code class=
"computeroutput"><span class=
"identifier">Erasability
</span></code> of key value pairs as a special
240 <div class=
"informaltable"><table class=
"table">
253 equivalent
<span class=
"emphasis"><em>classical
</em></span> function
261 <code class=
"computeroutput"><span class=
"identifier">_add
</span><span class=
"special"><</span><span class=
"identifier">inplace_identity
</span><span class=
"special"><</span><span class=
"identifier">CodomainT
</span><span class=
"special">></span>
262 <span class=
"special">>(
</span><span class=
"keyword">const
</span>
263 <span class=
"identifier">value_type
</span><span class=
"special">&)
</span></code>
268 <code class=
"computeroutput"><span class=
"identifier">insert
</span><span class=
"special">(
</span><span class=
"keyword">const
</span> <span class=
"identifier">value_type
</span><span class=
"special">&)
</span></code>
275 <code class=
"computeroutput"><span class=
"identifier">_subtract
</span><span class=
"special"><</span><span class=
"identifier">inplace_erasure
</span><span class=
"special"><</span><span class=
"identifier">CodomainT
</span><span class=
"special">></span>
276 <span class=
"special">>(
</span><span class=
"keyword">const
</span>
277 <span class=
"identifier">value_type
</span><span class=
"special">&)
</span></code>
282 <code class=
"computeroutput"><span class=
"identifier">erase
</span><span class=
"special">(
</span><span class=
"keyword">const
</span> <span class=
"identifier">value_type
</span><span class=
"special">&)
</span></code>
289 The aggregating member function templates
<code class=
"computeroutput"><span class=
"identifier">_add
</span></code>
290 and
<code class=
"computeroutput"><span class=
"identifier">_subtract
</span></code> are not in
291 the public interface of
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/interval_base_map.html" title=
"Class template interval_base_map">interval_maps
</a></code>,
292 because the
<code class=
"computeroutput"><span class=
"identifier">Combine
</span></code> functor
293 is intended to be an invariant of
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/interval_base_map.html" title=
"Class template interval_base_map">interval_map's
</a></code>
294 template instance to avoid, that clients spoil the aggregation by accidentally
295 calling varying aggregation functors. But you could instantiate an
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/interval_map.html" title=
"Class template interval_map">interval_map
</a></code> to have
<code class=
"computeroutput"><span class=
"identifier">insert
</span><span class=
"special">/
</span><span class=
"identifier">erase
</span></code> semantics this way:
297 <pre class=
"programlisting"><span class=
"identifier">interval_map
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">,
</span><span class=
"keyword">int
</span><span class=
"special">,
</span><span class=
"identifier">partial_absorber
</span><span class=
"special">,
</span>
298 <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">less
</span><span class=
"special">,
</span>
299 <span class=
"identifier">inplace_identity
</span> <span class=
"comment">//Combine parameter specified
300 </span> <span class=
"special">></span> <span class=
"identifier">m
</span><span class=
"special">;
</span>
301 <span class=
"identifier">interval
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">>::
</span><span class=
"identifier">type
</span> <span class=
"identifier">itv
</span> <span class=
"special">=
</span> <span class=
"identifier">interval
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">>::
</span><span class=
"identifier">rightopen
</span><span class=
"special">(
</span><span class=
"number">2</span><span class=
"special">,
</span><span class=
"number">7</span><span class=
"special">);
</span>
302 <span class=
"identifier">m
</span><span class=
"special">.
</span><span class=
"identifier">add
</span><span class=
"special">(
</span><span class=
"identifier">make_pair
</span><span class=
"special">(
</span><span class=
"identifier">itv
</span><span class=
"special">,
</span><span class=
"number">42</span><span class=
"special">));
</span> <span class=
"comment">//same as insert
303 </span><span class=
"identifier">m
</span><span class=
"special">.
</span><span class=
"identifier">subtract
</span><span class=
"special">(
</span><span class=
"identifier">make_pair
</span><span class=
"special">(
</span><span class=
"identifier">itv
</span><span class=
"special">,
</span><span class=
"number">42</span><span class=
"special">));
</span> <span class=
"comment">//same as erase
308 This is, of course, only a clarifying example. Member functions
<code class=
"computeroutput"><span class=
"identifier">insert
</span></code> and
<code class=
"computeroutput"><span class=
"identifier">erase
</span></code>
309 are available in
<code class=
"computeroutput"><a class=
"link" href=
"../../boost/icl/interval_base_map.html" title=
"Class template interval_base_map">interval_map's
</a></code>
310 interface so they can be called directly.
313 <table xmlns:
rev=
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width=
"100%"><tr>
314 <td align=
"left"></td>
315 <td align=
"right"><div class=
"copyright-footer">Copyright
© 2007 -
2010 Joachim Faulhaber
<br>Copyright
© 1999 -
2006 Cortex Software GmbH
<p>
316 Distributed under the Boost Software License, Version
1.0. (See accompanying
317 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>)
322 <div class=
"spirit-nav">
323 <a accesskey=
"p" href=
"sets_and_maps.html"><img src=
"../../../../../../doc/src/images/prev.png" alt=
"Prev"></a><a accesskey=
"u" href=
"../concepts.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=
"map_traits.html"><img src=
"../../../../../../doc/src/images/next.png" alt=
"Next"></a>