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

   1 [/
   2     Copyright (c) 2008-2010 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 [/ //= Subtraction ============================================================]
  11 [section Subtraction]
  12
  13 [section Synopsis]
  14
  15 [table
  16 [[Subtraction]                        [__ch_itvs__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
  17 [[`T& T::subtract(const P&)`]                     [ ]     [__ei]    [__bp]   [ ]     [__b]  ]
  18 [[`T& subtract(T&, const P&)`]                    [ ]     [__ei]    [__bp]   [__e]   [__b]  ]
  19
  20 [[`T& operator -=(T&, const P&)`]                 [ ]    [__eiS][__eiS __bpM][__es]  [__bm] ]
  21 [[`T  operator - (T, const P&)`]                  [ ]    [__eiS][__eiS __bpM][__es]  [__bm] ]
  22
  23 [[`T left_subtract(T, const T&)`]                 [1]       [ ]      [ ]     [ ]      [ ]   ]
  24 [[`T right_subtract(T, const T&)`]                [1]       [ ]      [ ]     [ ]      [ ]   ]
  25 ]
  26
  27 Functions and operators that implement ['*Subtraction*] on *icl* objects
  28 are given in the table above.
  29
  30 [table
  31 [[]      [Description of Subtraction]]
  32 [[`Sets`][Subtraction on Sets implements ['*set difference*]]]
  33 [[`Maps`][Subtraction on Maps implements a ['*map difference*] function similar to /set difference/.
  34           If, on subtraction of an element value pair `(k,v)` it's key `k` is in the map
  35           already, the subtraction function is propagated to the associated value.
  36           On the associated value an aggregation is performed, that reverses
  37           the effect of the corresponding addition function.
  38
  39           Find more on
  40           [link boost_icl.concepts.aggrovering ['subtractability of maps]]
  41           and related
  42           [link boost_icl.semantics.maps ['semantic issues]]
  43           following the links.
  44
  45          ]]
  46 ]
  47
  48 [endsect][/ Synopsis]
  49
  50
  51
  52 [section Functions][/ Subtraction]
  53
  54 The admissible combinations of types for subtraction functions
  55 can be summarized in the
  56 ['*overload table*] below:
  57
  58 ``
  59 // overload table for              T\P| e i b p
  60 T& T::subtract(const P&)           ---+--------
  61 T& subtract(T&, const P&)           s | s
  62                                     m |     m
  63                                     S | S S
  64                                     M |     M M
  65 ``
  66
  67 The next table contains complexity characteristics for `subtract`.
  68
  69 [table Time Complexity for function subtract on icl containers
  70 [[`T& T::subtract(const P&)`\n
  71   `T& subtract(T&, const P&)`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
  72 [[__icl_set__]                 [__Olgn__]   []            []           []          ]
  73 [[__icl_map__]                 [__Olgn__]   []            [__Olgn__]   []          ]
  74 [[__itv_sets__]                [__Olgn__]   [__a_Olgn__]  []           []          ]
  75 [[__itv_maps__]                [__Olgn__]   [__On__]      [__Olgn__]   [__On__]    ]
  76 ]
  77
  78 [endsect][/ Member function Subtraction]
  79
  80
  81 [section Inplace operators][/ Subtraction]
  82
  83 As presented in the overload tables for `operator -=`
  84 more type combinations are provided for subtraction than for
  85 addition.
  86
  87 ``
  88 // overload tables for             element containers:     interval containers:
  89 T& operator -= (T&, const P&)      -= | e b s m            -= | e i b p S M
  90                                    ---+--------            ---+------------
  91                                    s  | s   s              S  | S S     S
  92                                    m  | m m m m            M  | M M M M M M
  93 ``
  94
  95 Subtraction provides the /reverse/ operation
  96 of an addition for these overloads,
  97
  98 ``
  99 // Reverse addition                -= | e b s m            -= | e i b p S M
 100                                    ---+--------            ---+------------
 101                                    s  | s   s              S  | S S     S
 102                                    m  |   m   m            M  |     M M   M
 103 ``
 104
 105 [*and] you can erase parts of __icl_maps__ or __itv_maps__
 106 using
 107 /key values/, /intervals/ or /element or interval sets/
 108 using these overloads:
 109
 110 ``
 111 // Erasure by key objects          -= | e b s m            -= | e i b p S M
 112                                    ---+--------            ---+------------
 113                                    s  | s   s              S  | S S     S
 114                                    m  | m   m              M  | M M     M
 115 ``
 116
 117 On Sets both function groups fall together
 118 as ['*set difference*].
 119
 120 Complexity characteristics for inplace subtraction operations are
 121 given by the next tables where
 122 ``
 123 n = iterative_size(y);
 124 m = iterative_size(x); //if P is a container type
 125 ``
 126
 127 [table Time Complexity for inplace Subtraction on element containers
 128 [[`T& operator -= (T&, const P&)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
 129 [[__icl_set__]                    [__Olgn__]    []               [__Omlgn__]     []              ]
 130 [[__icl_map__]                    [__Olgn__]    [__Olgn__]       [__Omlgn__]     [__Omlgn__]     ]
 131 ]
 132
 133
 134 [table Time Complexity for inplace Subtraction on interval containers
 135 [[`T& operator -= (T&, const P&)`][__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__][__ch_itv_sets__][__ch_itv_maps__]]
 136 [[interval_sets]                  [__Olgn__]    [__a_Olgn__]  []               []               [__Omlgnpm__]    []               ]
 137 [[interval_maps]                  [__Olgn__]    [__a_Olgn__]  [__Olgn__]       [__On__]         [__Omlgnpm__]    [__Omlgnpm__]    ]
 138 ]
 139
 140 [endsect][/ Inplace operators Subtraction]
 141
 142
 143 [section Infix operators][/-Subtraction]
 144
 145 The admissible overloads for the infix
 146 /subtraction/ `operator -`
 147 which is a non commutative
 148 operation
 149 is given by the next overload table.
 150
 151 ``
 152 // overload tables for         -  | e b s m      -  | e i b p S M
 153 T operator - (T, const P&)     ---+--------      ---+------------
 154                                s  | s   s        S  | S S     S
 155                                m  | m m m m      M  | M M M M M M
 156 ``
 157 [endsect][/- Infix operator Subtraction]
 158
 159
 160 [section Subtraction on Intervals]
 161
 162 [table
 163 [[['*Subtraction*]]                                   [Types] [Description]                                        ]
 164
 165 [[`T left_subtract(T right, const T& left_minuend)`]  [__i]
 166     [subtract `left_minuend` from the interval `right` on it's left side.
 167 ``
 168 right_over = left_subtract(right, left_minuend);
 169 ...      d) : right
 170 ... c)      : left_minuend
 171      [c  d) : right_over
 172 ``
 173     ] ]
 174 [[`T right_subtract(T left, const T& right_minuend)`] [__i]
 175     [subtract `right_minuend` from the interval `left` on it's right side.
 176 ``
 177 left_over = right_subtract(left, right_minuend);
 178 [a      ...  : left
 179      [b ...  : right_minuend
 180 [a  b)       : left_over
 181 ``
 182     ] ]
 183 ]
 184
 185 [endsect][/ Subtraction on Intervals]
 186
 187
 188 ['*See also . . .*]
 189 [table
 190 []
 191 [[[link boost_icl.function_reference.addition ['*Addition*]]         ]]
 192 [[[link boost_icl.function_reference.erasure  ['*Erasure*]]          ]]
 193 ]
 194 ['*Back to section . . .*]
 195 [table
 196 []
 197 [[[link function_synopsis_table ['*Function Synopsis*]]    ]]
 198 [[[link boost_icl.interface ['*Interface*]]                ]]
 199 ]
 200
 201 [endsect][/ Subtraction]
 202