ceph/src/boost/libs/icl/doc/html/boost_icl/concepts/aggrovering.html

   1 <html>
   2 <head>
   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&#160;1.&#160;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">
  11 </head>
  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>
  20 </tr></table>
  21 <hr>
  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>
  24 </div>
  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>
  30 <p>
  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.
  49       </p>
  50 <p>
  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">&lt;</span><span class="keyword">class</span><span class="special">&gt;</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.
  59       </p>
  60 <p>
  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>
  63         functor.
  64       </p>
  65 <div class="informaltable"><table class="table">
  66 <colgroup>
  67 <col>
  68 <col>
  69 </colgroup>
  70 <thead><tr>
  71 <th>
  72               <p>
  73                 <code class="computeroutput"><span class="identifier">Combine</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
  74               </p>
  75               </th>
  76 <th>
  77               <p>
  78                 <code class="computeroutput"><span class="identifier">inverse</span><span class="special">&lt;</span><span class="identifier">Combine</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span>
  79                 <span class="special">&gt;::</span><span class="identifier">type</span></code>
  80               </p>
  81               </th>
  82 </tr></thead>
  83 <tbody>
  84 <tr>
  85 <td>
  86               <p>
  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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
  88               </p>
  89               </td>
  90 <td>
  91               <p>
  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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
  93               </p>
  94               </td>
  95 </tr>
  96 <tr>
  97 <td>
  98               <p>
  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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 100               </p>
 101               </td>
 102 <td>
 103               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 105               </p>
 106               </td>
 107 </tr>
 108 <tr>
 109 <td>
 110               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 112               </p>
 113               </td>
 114 <td>
 115               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 117               </p>
 118               </td>
 119 </tr>
 120 <tr>
 121 <td>
 122               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 124               </p>
 125               </td>
 126 <td>
 127               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 129               </p>
 130               </td>
 131 </tr>
 132 <tr>
 133 <td>
 134               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 136               </p>
 137               </td>
 138 <td>
 139               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 141               </p>
 142               </td>
 143 </tr>
 144 <tr>
 145 <td>
 146               <p>
 147                 <code class="computeroutput"><span class="identifier">Functor</span></code>
 148               </p>
 149               </td>
 150 <td>
 151               <p>
 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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>
 153               </p>
 154               </td>
 155 </tr>
 156 </tbody>
 157 </table></div>
 158 <p>
 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">&lt;</span><span class="identifier">inplace_minus</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span> <span class="special">&gt;::</span><span class="identifier">type</span></code>
 162         yields <code class="computeroutput"><span class="identifier">inplace_plus</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</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:
 166       </p>
 167 <div class="informaltable"><table class="table">
 168 <colgroup>
 169 <col>
 170 <col>
 171 <col>
 172 </colgroup>
 173 <thead><tr>
 174 <th>
 175               <p>
 176               </p>
 177               </th>
 178 <th>
 179               <p>
 180                 <code class="computeroutput"><span class="identifier">_add</span><span class="special">&lt;</span><span class="identifier">Combine</span><span class="special">&lt;</span><span class="identifier">CodomainT</span><span class="special">&gt;</span>
 181                 <span class="special">&gt;((</span><span class="identifier">k</span><span class="special">,</span><span class="identifier">x</span><span class="special">))</span></code>
 182               </p>
 183               </th>
 184 <th>
 185               <p>
 186                 <code class="computeroutput"><span class="identifier">_subtract</span><span class="special">&lt;</span><span class="identifier">inverse</span><span class="special">&lt;</span><span class="identifier">Combine</span><span class="special">&lt;</span><span class="identifier">CodomainT</span><span class="special">&gt;</span>
 187                 <span class="special">&gt;::</span><span class="identifier">type</span><span class="special">&gt;((</span><span class="identifier">k</span><span class="special">,</span><span class="identifier">x</span><span class="special">))</span></code>
 188               </p>
 189               </th>
 190 </tr></thead>
 191 <tbody>
 192 <tr>
 193 <td>
 194               <p>
 195                 Instance
 196               </p>
 197               </td>
 198 <td>
 199               <p>
 200                 <code class="computeroutput"><span class="identifier">_add</span><span class="special">&lt;</span><span class="identifier">inplace_plus</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span>
 201                 <span class="special">&gt;((</span><span class="identifier">k</span><span class="special">,</span><span class="identifier">x</span><span class="special">))</span></code>
 202               </p>
 203               </td>
 204 <td>
 205               <p>
 206                 <code class="computeroutput"><span class="identifier">_subtract</span><span class="special">&lt;</span><span class="identifier">inplace_minus</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span>
 207                 <span class="special">&gt;((</span><span class="identifier">k</span><span class="special">,</span><span class="identifier">x</span><span class="special">))</span></code>
 208               </p>
 209               </td>
 210 </tr>
 211 <tr>
 212 <td>
 213               <p>
 214                 Inversion
 215               </p>
 216               </td>
 217 <td>
 218               <p>
 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>
 222               </p>
 223               </td>
 224 <td>
 225               <p>
 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>
 229               </p>
 230               </td>
 231 </tr>
 232 </tbody>
 233 </table></div>
 234 <p>
 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
 238         case:
 239       </p>
 240 <div class="informaltable"><table class="table">
 241 <colgroup>
 242 <col>
 243 <col>
 244 </colgroup>
 245 <thead><tr>
 246 <th>
 247               <p>
 248                 aggregating function
 249               </p>
 250               </th>
 251 <th>
 252               <p>
 253                 equivalent <span class="emphasis"><em>classical</em></span> function
 254               </p>
 255               </th>
 256 </tr></thead>
 257 <tbody>
 258 <tr>
 259 <td>
 260               <p>
 261                 <code class="computeroutput"><span class="identifier">_add</span><span class="special">&lt;</span><span class="identifier">inplace_identity</span><span class="special">&lt;</span><span class="identifier">CodomainT</span><span class="special">&gt;</span>
 262                 <span class="special">&gt;(</span><span class="keyword">const</span>
 263                 <span class="identifier">value_type</span><span class="special">&amp;)</span></code>
 264               </p>
 265               </td>
 266 <td>
 267               <p>
 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">&amp;)</span></code>
 269               </p>
 270               </td>
 271 </tr>
 272 <tr>
 273 <td>
 274               <p>
 275                 <code class="computeroutput"><span class="identifier">_subtract</span><span class="special">&lt;</span><span class="identifier">inplace_erasure</span><span class="special">&lt;</span><span class="identifier">CodomainT</span><span class="special">&gt;</span>
 276                 <span class="special">&gt;(</span><span class="keyword">const</span>
 277                 <span class="identifier">value_type</span><span class="special">&amp;)</span></code>
 278               </p>
 279               </td>
 280 <td>
 281               <p>
 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">&amp;)</span></code>
 283               </p>
 284               </td>
 285 </tr>
 286 </tbody>
 287 </table></div>
 288 <p>
 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:
 296 </p>
 297 <pre class="programlisting"><span class="identifier">interval_map</span><span class="special">&lt;</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">&gt;</span> <span class="identifier">m</span><span class="special">;</span>
 301 <span class="identifier">interval</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;::</span><span class="identifier">type</span> <span class="identifier">itv</span> <span class="special">=</span> <span class="identifier">interval</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;::</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
 304 </span></pre>
 305 <p>
 306       </p>
 307 <p>
 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.
 311       </p>
 312 </div>
 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 &#169; 2007 -2010 Joachim Faulhaber<br>Copyright &#169; 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>)
 318       </p>
 319 </div></td>
 320 </tr></table>
 321 <hr>
 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>
 324 </div>
 325 </body>
 326 </html>