ceph/src/boost/libs/icl/doc/functions_addition.qbk

   1 [/
   2     Copyright (c) 2008-2009 Joachim Faulhaber
   3
   4     Distributed under the Boost Software License, Version 1.0.
   5     (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt)
   7 ]
   8
   9
  10 [/ //= Addition ===============================================================]
  11 [section Addition]
  12
  13 [section Synopsis]
  14
  15 [table
  16
  17 [[Addition]                                [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]
  18
  19 [[`T& T::add(const P&)`]                           [__ei]    [__bp]   [ ]     [__b]  ]
  20 [[`T& add(T&, const P&)`]                          [__ei]    [__bp]   [__e]   [__b]  ]
  21 [[`J T::add(J pos, const P&)`]                     [__i]     [__p]    [ ]     [__b]  ]
  22 [[`J add(T&, J pos, const P&)`]                    [__i]     [__p]    [__e]   [__b]  ]
  23
  24 [[`T& operator +=(T&, const P&)`]                  [__eiS]   [__bpM]  [__es]  [__bm] ]
  25 [[`T operator + (T, const P&)`\n
  26   `T operator + (const P&, T)`]
  27                                                    [__eiS]   [__bpM]  [__es]  [__bm] ]
  28 [[`T& operator |=(      T&, const P&)`]            [__eiS]   [__bpM]  [__es]  [__bm] ]
  29 [[`T operator | (T, const P&)`\n
  30   `T operator | (const P&, T)`]
  31                                                    [__eiS]   [__bpM]  [__es]  [__bm] ]
  32
  33 ]
  34
  35 Functions and operators that implement ['*Addition*] on *icl* objects
  36 are given in the table above.
  37 `operator |=` and `operator |` are behavioral identical to
  38 `operator +=` and `operator +`.
  39 This is a redundancy that has been introduced deliberately, because
  40 a /set union/ semantics is often attached `operators |=` and `|`.
  41
  42 [table
  43 [[]      [Description of Addition]]
  44 [[`Sets`][Addition on Sets implements ['*set union*]]]
  45 [[`Maps`][Addition on Maps implements a ['*map union*] function similar to /set union/.
  46           If, on insertion of an element value pair `(k,v)` it's key `k` is in the map
  47           already, the addition function is propagated to the associated value.
  48           This functionality has been introduced as /aggregate on collision/
  49           for element maps and /aggregate on overlap/ for interval maps.
  50
  51           Find more on
  52           [link boost_icl.concepts.aggrovering ['addability of maps]]
  53           and related
  54           [link boost_icl.semantics.maps ['semantic issues]]
  55           following the links.
  56
  57           Examples, demonstrating Addition on interval containers are
  58           [link boost_icl.examples.overlap_counter ['overlap counter]],
  59           [link boost_icl.examples.party ['party]] and
  60           [link boost_icl.examples.partys_height_average ['party's height average.]]
  61          ]]
  62 ]
  63
  64 For `Sets` ['*addition*] and ['*insertion*] are implemented identically.
  65 Functions `add` and `insert` collapse to the same function.
  66 For `Maps` ['*addition*] and ['*insertion*] work differently.
  67 Function `add` performs aggregations on collision or overlap,
  68 while function `insert` only inserts values that do not yet have key values.
  69
  70 [endsect][/ Synopsis]
  71
  72 [section Functions][/ Addition]
  73
  74 The admissible combinations of types for member function
  75 `T& T::add(const P&)` can be summarized in the
  76 ['*overload table*] below:
  77
  78 ``
  79 // overload table for    T\P| e i b p
  80 T& T::add(const P&)      ---+--------
  81 T& add(T&, const P&)      s | s
  82                           m |     m
  83                           S | S S
  84                           M |     M M
  85 ``
  86
  87 The next table contains complexity characteristics for `add`.
  88
  89 [table Time Complexity for member function add on icl containers
  90 [[`T& T::add(const P&)`\n
  91   `T& add(T&, const P&)`]      [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
  92 [[__icl_set__]                 [__Olgn__] []          []        []          ]
  93 [[__icl_map__]                 []         []          [__Olgn__][]          ]
  94 [[__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []          ]
  95 [[__spl_itv_set__]             [__Olgn__] [__On__]    []        []          ]
  96 [[__itv_map__\n__spl_itv_map__][]         []          [__Olgn__][__On__]    ]
  97 ]
  98
  99 [h5 Hinted addition]
 100
 101 Function `J T::add(J prior, const P& addend)` allows
 102 for an addition in ['*constant time*], if `addend` can be inserted
 103 right after iterator `prior` without collision. If this is not possible
 104 the complexity characteristics are as stated for the non hinted addition
 105 above. Hinted addition is available for these combinations of types:
 106 ``
 107 // overload table for addition with hint        T\P| e i b p
 108 J T::add(J prior, const P&)                     ---+--------
 109 J add(T&, J prior, const P&)                     s | s
 110                                                  m |     m
 111                                                  S |   S
 112                                                  M |       M
 113 ``
 114
 115 [endsect][/ Functions Addition]
 116
 117 [section Inplace operators]
 118
 119 The possible overloads of inplace `T& operator += (T&, const P&)`
 120 are given by two tables, that show admissible combinations of types.
 121 Row types show instantiations of argument type `T`. Columns types
 122 show show instantiations of argument type `P`. If a combination
 123 of argument types is possible, the related table cell contains
 124 the result type of the operation.
 125 __eiS_Phs__ __eibpsSmM__ will be used to denote
 126 /elements, intervals,
 127 element value pairs, interval value pairs,
 128 element sets, interval sets,
 129 element maps/ and /interval maps/.
 130 The first table shows the
 131 overloads of `+=` for /element containers/ the second table
 132 refers to /interval containers/.
 133
 134 ``
 135 // overload tables for             element containers:     interval containers:
 136 T& operator += (T&, const P&)      += | e b s m            += | e i b p S M
 137                                    ---+--------            ---+------------
 138                                    s  | s   s              S  | S S     S
 139                                    m  |   m   m            M  |     M M   M
 140 ``
 141
 142 For the definition of admissible overloads
 143 we separate /element containers/ from /interval containers/.
 144 Within each group all combinations of types are supported
 145 for an operation, that are in line with the *icl's*
 146 design and the sets of laws, that establish the *icl's*
 147 [link boost_icl.semantics semantics].
 148
 149
 150 Overloads between /element containers/ and /interval containers/
 151 could also be defined. But this has not been done for
 152 pragmatical reasons: Each additional combination of types
 153 for an operation enlarges the space of possible overloads.
 154 This makes the overload resolution by compilers more complex,
 155 error prone and slows down compilation speed. Error messages
 156 for unresolvable or ambiguous overloads are difficult
 157 to read and understand. Therefore overloading of namespace
 158 global functions in the *icl* are limited to a reasonable
 159 field of combinations, that are described here.
 160
 161 [endsect][/ Inplace operators]
 162
 163
 164 [h4 Complexity]
 165
 166 For different combinations of argument types `T` and `P`
 167 different implementations of the `operator +=` are
 168 selected. These implementations show different complexity
 169 characteristics.
 170 If `T` is a container type,
 171 the combination of
 172 domain elements (__e) or element value pairs (__b)
 173 is faster than a combination of intervals (__i) or
 174 interval value pairs (__p) which in turn is faster than
 175 the combination of element or interval containers.
 176 The next table shows /time complexities/ of addition for
 177 *icl's* element containers.
 178
 179 Sizes `n` and `m` are in the complexity statements are sizes
 180 of objects `T y` and `P x`:
 181 ``
 182 n = iterative_size(y);
 183 m = iterative_size(x); //if P is a container type
 184 ``
 185 Note, that for an interval container the number of elements `T::size` is
 186 different from the number of intervals that you can iterate over.
 187 Therefore a function `T::iterative_size()` is used that provides the
 188 desired kind of size.
 189
 190 [table Time Complexity for inplace Addition on element containers
 191 [[`T& operator += (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_sets__][__ch_icl_maps__]]
 192 [[__icl_set__]                        [__Olgn__]    []               [__Om__]         []               ]
 193 [[__icl_map__]                        []            [__Olgn__]       []               [__Om__]         ]
 194 ]
 195
 196 Time complexity characteristics of inplace addition for interval containers
 197 is given by this table.
 198
 199 [table Time Complexity for inplace Addition on interval containers
 200 [[`T& operator += (T& y, const P& x)`][][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
 201 [[interval_sets][__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []        [__Omlgnpm__]    []               ]
 202 [[]             [__spl_itv_set__]             [__Olgn__] [__On__]    []        []        [__Omlgnpm__]    []               ]
 203 [[interval_maps][]                            []         []          [__Olgn__][__On__]  []               [__Omlgnpm__]    ]
 204 ]
 205
 206 Since the implementation of
 207 element and interval containers is based on the
 208 [link boost_icl.implementation link red-black tree implementation]
 209 of std::AssociativeContainers, we have a logarithmic complexity for
 210 addition of elements.
 211 Addition of intervals or interval value pairs is amortized logarithmic
 212 for __itv_sets__ and __sep_itv_sets__ and linear for __spl_itv_sets__
 213 and __itv_maps__.
 214 Addition is linear for element containers and
 215 loglinear for interval containers.
 216
 217
 218 [section Infix operators]
 219
 220 The admissible type combinations for infix `operator +`
 221 are defined by the overload tables below.
 222
 223 ``
 224 // overload tables for          element containers:     interval containers:
 225 T operator + (T, const P&)      +  | e b s m            +  | e  i  b  p  S1 S2 S3 M1 M3
 226 T operator + (const P&, T)      ---+--------            ---+---------------------------
 227                                 e  |     s              e  |             S1 S2 S3
 228                                 b  |       m            i  |             S1 S2 S3
 229                                 s  | s   s              b  |                      M1 M3
 230                                 m  |   m   m            p  |                      M1 M3
 231                                                         S1 | S1 S1       S1 S2 S3
 232                                                         S2 | S2 S2       S2 S2 S3
 233                                                         S3 | S3 S3       S3 S3 S3
 234                                                         M1 |       M1 M1          M1 M3
 235                                                         M3 |       M3 M3          M3 M3
 236 ``
 237
 238 [endsect][/ Infix operators]
 239
 240
 241 ['*See also . . .*]
 242 [table
 243 []
 244 [[[link boost_icl.function_reference.subtraction ['*Subtraction*]]   ]]
 245 [[[link boost_icl.function_reference.insertion ['*Insertion*]]       ]]
 246 ]
 247
 248 ['*Back to section . . .*]
 249 [table
 250 []
 251 [[[link function_synopsis_table ['*Function Synopsis*]]    ]]
 252 [[[link boost_icl.interface ['*Interface*]]                ]]
 253 ]
 254
 255 [endsect][/ Addition]
 256
 257