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 35Functions and operators that implement ['*Addition*] on *icl* objects 36are given in the table above. 37`operator |=` and `operator |` are behavioral identical to 38`operator +=` and `operator +`. 39This is a redundancy that has been introduced deliberately, because 40a /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 64For `Sets` ['*addition*] and ['*insertion*] are implemented identically. 65Functions `add` and `insert` collapse to the same function. 66For `Maps` ['*addition*] and ['*insertion*] work differently. 67Function `add` performs aggregations on collision or overlap, 68while function `insert` only inserts values that do not yet have key values. 69 70[endsect][/ Synopsis] 71 72[section Functions][/ Addition] 73 74The 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 80T& T::add(const P&) ---+-------- 81T& add(T&, const P&) s | s 82 m | m 83 S | S S 84 M | M M 85`` 86 87The 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 101Function `J T::add(J prior, const P& addend)` allows 102for an addition in ['*constant time*], if `addend` can be inserted 103right after iterator `prior` without collision. If this is not possible 104the complexity characteristics are as stated for the non hinted addition 105above. Hinted addition is available for these combinations of types: 106`` 107// overload table for addition with hint T\P| e i b p 108J T::add(J prior, const P&) ---+-------- 109J 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 119The possible overloads of inplace `T& operator += (T&, const P&)` 120are given by two tables, that show admissible combinations of types. 121Row types show instantiations of argument type `T`. Columns types 122show show instantiations of argument type `P`. If a combination 123of argument types is possible, the related table cell contains 124the result type of the operation. 125__eiS_Phs__ __eibpsSmM__ will be used to denote 126/elements, intervals, 127element value pairs, interval value pairs, 128element sets, interval sets, 129element maps/ and /interval maps/. 130The first table shows the 131overloads of `+=` for /element containers/ the second table 132refers to /interval containers/. 133 134`` 135// overload tables for element containers: interval containers: 136T& 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 142For the definition of admissible overloads 143we separate /element containers/ from /interval containers/. 144Within each group all combinations of types are supported 145for an operation, that are in line with the *icl's* 146design and the sets of laws, that establish the *icl's* 147[link boost_icl.semantics semantics]. 148 149 150Overloads between /element containers/ and /interval containers/ 151could also be defined. But this has not been done for 152pragmatical reasons: Each additional combination of types 153for an operation enlarges the space of possible overloads. 154This makes the overload resolution by compilers more complex, 155error prone and slows down compilation speed. Error messages 156for unresolvable or ambiguous overloads are difficult 157to read and understand. Therefore overloading of namespace 158global functions in the *icl* are limited to a reasonable 159field of combinations, that are described here. 160 161[endsect][/ Inplace operators] 162 163 164[h4 Complexity] 165 166For different combinations of argument types `T` and `P` 167different implementations of the `operator +=` are 168selected. These implementations show different complexity 169characteristics. 170If `T` is a container type, 171the combination of 172domain elements (__e) or element value pairs (__b) 173is faster than a combination of intervals (__i) or 174interval value pairs (__p) which in turn is faster than 175the combination of element or interval containers. 176The next table shows /time complexities/ of addition for 177*icl's* element containers. 178 179Sizes `n` and `m` are in the complexity statements are sizes 180of objects `T y` and `P x`: 181`` 182n = iterative_size(y); 183m = iterative_size(x); //if P is a container type 184`` 185Note, that for an interval container the number of elements `T::size` is 186different from the number of intervals that you can iterate over. 187Therefore a function `T::iterative_size()` is used that provides the 188desired 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 196Time complexity characteristics of inplace addition for interval containers 197is 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 206Since the implementation of 207element and interval containers is based on the 208[link boost_icl.implementation link red-black tree implementation] 209of std::AssociativeContainers, we have a logarithmic complexity for 210addition of elements. 211Addition of intervals or interval value pairs is amortized logarithmic 212for __itv_sets__ and __sep_itv_sets__ and linear for __spl_itv_sets__ 213and __itv_maps__. 214Addition is linear for element containers and 215loglinear for interval containers. 216 217 218[section Infix operators] 219 220The admissible type combinations for infix `operator +` 221are defined by the overload tables below. 222 223`` 224// overload tables for element containers: interval containers: 225T operator + (T, const P&) + | e b s m + | e i b p S1 S2 S3 M1 M3 226T 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 258