258 lines
11 KiB
Plaintext
258 lines
11 KiB
Plaintext
[/
|
|
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]
|
|
|
|
|