123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257 |
- [/
- 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]
|