bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / icl / doc / functions_addition.qbk

[/
    Copyright (c) 2008-2009 Joachim Faulhaber

    Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
]


[/ //= Addition ===============================================================]
[section Addition]

[section Synopsis]

[table

[[Addition]                                [__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__] ]

[[`T& T::add(const P&)`]                           [__ei]    [__bp]   [ ]     [__b]  ]
[[`T& add(T&, const P&)`]                          [__ei]    [__bp]   [__e]   [__b]  ]
[[`J T::add(J pos, const P&)`]                     [__i]     [__p]    [ ]     [__b]  ]
[[`J add(T&, J pos, const P&)`]                    [__i]     [__p]    [__e]   [__b]  ]

[[`T& operator +=(T&, const P&)`]                  [__eiS]   [__bpM]  [__es]  [__bm] ]
[[`T operator + (T, const P&)`\n
  `T operator + (const P&, T)`]
                                                   [__eiS]   [__bpM]  [__es]  [__bm] ]
[[`T& operator |=(      T&, const P&)`]            [__eiS]   [__bpM]  [__es]  [__bm] ]
[[`T operator | (T, const P&)`\n
  `T operator | (const P&, T)`]
                                                   [__eiS]   [__bpM]  [__es]  [__bm] ]

]

Functions and operators that implement ['*Addition*] on *icl* objects
are given in the table above.
`operator |=` and `operator |` are behavioral identical to 
`operator +=` and `operator +`.
This is a redundancy that has been introduced deliberately, because 
a /set union/ semantics is often attached `operators |=` and `|`. 

[table
[[]      [Description of Addition]]
[[`Sets`][Addition on Sets implements ['*set union*]]]
[[`Maps`][Addition on Maps implements a ['*map union*] function similar to /set union/.
          If, on insertion of an element value pair `(k,v)` it's key `k` is in the map 
          already, the addition function is propagated to the associated value.
          This functionality has been introduced as /aggregate on collision/
          for element maps and /aggregate on overlap/ for interval maps. 
        
          Find more on 
          [link boost_icl.concepts.aggrovering ['addability of maps]]
          and related 
          [link boost_icl.semantics.maps ['semantic issues]] 
          following the links. 
        
          Examples, demonstrating Addition on interval containers are
          [link boost_icl.examples.overlap_counter ['overlap counter]],
          [link boost_icl.examples.party ['party]] and
          [link boost_icl.examples.partys_height_average ['party's height average.]] 
         ]]
]

For `Sets` ['*addition*] and ['*insertion*] are implemented identically.
Functions `add` and `insert` collapse to the same function. 
For `Maps` ['*addition*] and ['*insertion*] work differently. 
Function `add` performs aggregations on collision or overlap, 
while function `insert` only inserts values that do not yet have key values. 

[endsect][/ Synopsis]

[section Functions][/ Addition]

The admissible combinations of types for member function 
`T& T::add(const P&)` can be summarized in the 
['*overload table*] below:

``
// overload table for    T\P| e i b p  
T& T::add(const P&)      ---+--------
T& add(T&, const P&)      s | s
                          m |     m
                          S | S S      
                          M |     M M  
``

The next table contains complexity characteristics for `add`.

[table Time Complexity for member function add on icl containers
[[`T& T::add(const P&)`\n
  `T& add(T&, const P&)`]      [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
[[__icl_set__]                 [__Olgn__] []          []        []          ]
[[__icl_map__]                 []         []          [__Olgn__][]          ]
[[__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []          ]
[[__spl_itv_set__]             [__Olgn__] [__On__]    []        []          ]
[[__itv_map__\n__spl_itv_map__][]         []          [__Olgn__][__On__]    ]
]

[h5 Hinted addition]

Function `J T::add(J prior, const P& addend)` allows
for an addition in ['*constant time*], if `addend` can be inserted
right after iterator `prior` without collision. If this is not possible
the complexity characteristics are as stated for the non hinted addition
above. Hinted addition is available for these combinations of types:
``
// overload table for addition with hint        T\P| e i b p   
J T::add(J prior, const P&)                     ---+--------
J add(T&, J prior, const P&)                     s | s
                                                 m |     m
                                                 S |   S      
                                                 M |       M   
``

[endsect][/ Functions Addition]

[section Inplace operators] 

The possible overloads of inplace `T& operator += (T&, const P&)`
are given by two tables, that show admissible combinations of types.
Row types show instantiations of argument type `T`. Columns types
show show instantiations of argument type `P`. If a combination
of argument types is possible, the related table cell contains
the result type of the operation. 
__eiS_Phs__ __eibpsSmM__ will be used to denote 
/elements, intervals, 
element value pairs, interval value pairs, 
element sets, interval sets, 
element maps/ and /interval maps/. 
The first table shows the 
overloads of `+=` for /element containers/ the second table
refers to /interval containers/. 

``
// overload tables for             element containers:     interval containers:  
T& operator += (T&, const P&)      += | e b s m            += | e i b p S M    
                                   ---+--------            ---+------------    
                                   s  | s   s              S  | S S     S       
                                   m  |   m   m            M  |     M M   M    
``

For the definition of admissible overloads
we separate /element containers/ from /interval containers/.
Within each group all combinations of types are supported 
for an operation, that are in line with the *icl's* 
design and the sets of laws, that establish the *icl's*
[link boost_icl.semantics semantics].


Overloads between /element containers/ and /interval containers/
could also be defined. But this has not been done for
pragmatical reasons: Each additional combination of types
for an operation enlarges the space of possible overloads.
This makes the overload resolution by compilers more complex,
error prone and slows down compilation speed. Error messages
for unresolvable or ambiguous overloads are difficult
to read and understand. Therefore overloading of namespace
global functions in the *icl* are limited to a reasonable
field of combinations, that are described here.

[endsect][/ Inplace operators]


[h4 Complexity]

For different combinations of argument types `T` and `P`
different implementations of the `operator +=` are 
selected. These implementations show different complexity
characteristics. 
If `T` is a container type, 
the combination of 
domain elements (__e) or element value pairs (__b)
is faster than a combination of intervals (__i) or
interval value pairs (__p) which in turn is faster than
the combination of element or interval containers.
The next table shows /time complexities/ of addition for
*icl's* element containers.

Sizes `n` and `m` are in the complexity statements are sizes
of objects `T y` and `P x`:
``
n = iterative_size(y);
m = iterative_size(x); //if P is a container type
``
Note, that for an interval container the number of elements `T::size` is
different from the number of intervals that you can iterate over.
Therefore a function `T::iterative_size()` is used that provides the
desired kind of size.

[table Time Complexity for inplace Addition on element containers
[[`T& operator += (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_sets__][__ch_icl_maps__]]
[[__icl_set__]                        [__Olgn__]    []               [__Om__]         []               ]
[[__icl_map__]                        []            [__Olgn__]       []               [__Om__]         ]
]

Time complexity characteristics of inplace addition for interval containers
is given by this table.

[table Time Complexity for inplace Addition on interval containers
[[`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__]]
[[interval_sets][__itv_set__\n__sep_itv_set__][__Olgn__] [__a_Olgn__][]        []        [__Omlgnpm__]    []               ]
[[]             [__spl_itv_set__]             [__Olgn__] [__On__]    []        []        [__Omlgnpm__]    []               ]
[[interval_maps][]                            []         []          [__Olgn__][__On__]  []               [__Omlgnpm__]    ]
]

Since the implementation of
element and interval containers is based on the 
[link boost_icl.implementation link red-black tree implementation]
of std::AssociativeContainers, we have a logarithmic complexity for
addition of elements.
Addition of intervals or interval value pairs is amortized logarithmic
for __itv_sets__ and __sep_itv_sets__ and linear for __spl_itv_sets__
and __itv_maps__.
Addition is linear for element containers and
loglinear for interval containers.


[section Infix operators]

The admissible type combinations for infix `operator +`
are defined by the overload tables below. 

``
// overload tables for          element containers:     interval containers:
T operator + (T, const P&)      +  | e b s m            +  | e  i  b  p  S1 S2 S3 M1 M3  
T operator + (const P&, T)      ---+--------            ---+---------------------------
                                e  |     s              e  |             S1 S2 S3 
                                b  |       m            i  |             S1 S2 S3 
                                s  | s   s              b  |                      M1 M3  
                                m  |   m   m            p  |                      M1 M3
                                                        S1 | S1 S1       S1 S2 S3 
                                                        S2 | S2 S2       S2 S2 S3 
                                                        S3 | S3 S3       S3 S3 S3 
                                                        M1 |       M1 M1          M1 M3
                                                        M3 |       M3 M3          M3 M3
``

[endsect][/ Infix operators]


['*See also . . .*]
[table
[]
[[[link boost_icl.function_reference.subtraction ['*Subtraction*]]   ]]
[[[link boost_icl.function_reference.insertion ['*Insertion*]]       ]]
]

['*Back to section . . .*]
[table
[]
[[[link function_synopsis_table ['*Function Synopsis*]]    ]]
[[[link boost_icl.interface ['*Interface*]]                ]]
]

[endsect][/ Addition]