272 lines
12 KiB
Plaintext
272 lines
12 KiB
Plaintext
[/
|
|
Copyright (c) 2008-2010 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)
|
|
]
|
|
|
|
[/ //= Intersection ============================================================]
|
|
[section Intersection][/ Intersection]
|
|
|
|
[section Synopsis][/ Intersection]
|
|
|
|
[table
|
|
[[Intersection] [__ch_itv_t__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
|
|
|
|
[[`void add_intersection(T&, const T&, const P&)`][ ] [__eiS][__eiS __bpM][ ] [ ] ]
|
|
[[`T& operator &=(T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
|
|
[[`T operator & (T, const P&)`\n
|
|
`T operator & (const P&, T)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
|
|
[[`bool intersects(const T&, const P&)`\n
|
|
`bool disjoint(const T&, const P&)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
|
|
]
|
|
|
|
Functions and operators that are related to ['*intersection*] on *icl* objects
|
|
are given in the table above.
|
|
|
|
|
|
[table
|
|
[[] [Description of Intersection]]
|
|
[[`Sets`][Intersection on Sets implements ['*set intersection*]]]
|
|
[[`Maps`][Intersection on Maps implements a ['*map intersection*] function similar to /set intersection/.
|
|
If, on intersection, an element value pair `(k,v)` it's key `k` is in the map
|
|
already, the intersection function is propagated to the associated value,
|
|
if it exists for the Map's codomain_type.
|
|
|
|
If the codomain_type has no intersection operation, associated
|
|
values are combined using addition. For partial map types this
|
|
results in an addition on the intersection of the domains of
|
|
the intersected sets. For total maps intersection and
|
|
addition are identical in this case.
|
|
|
|
See also
|
|
[link boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers ['intersection on Maps of numbers]].
|
|
|
|
A Map can be intersected with key types: an element
|
|
(an interval for interval_maps) and and a Set. This
|
|
results in the selection of a submap, and can be
|
|
defined as a generalized selection function on Maps.
|
|
]]
|
|
]
|
|
|
|
[endsect][/ Synopsis Intersection]
|
|
|
|
|
|
[section Functions][/ Intersection]
|
|
|
|
The overloaded function
|
|
|
|
`void add_intersection(T& result, const T& y, const P& x)`
|
|
|
|
allows to accumulate the intersection of `y` and `x` in the first argument `result`.
|
|
`Result` might already contain data. In this case the intersection of `y` and `x`
|
|
is `added` the the contents of `result`.
|
|
``
|
|
T s1 = f, s2 = f, y = g; P x = h; // The effect of
|
|
add_intersection(s1, y, x); // add_intersection
|
|
s2 += (y & x); // and & followed by +=
|
|
assert(s1==s2); // is identical
|
|
``
|
|
|
|
This might be convenient, if intersection is used like a generalized selection function.
|
|
Using element or segment types for `P`, we can select small parts of a container
|
|
`y` and accumulate them in `section`.
|
|
|
|
The admissible combinations of types for function
|
|
`void add_intersection(T&, const T&, const P&)` can be summarized in the
|
|
['*overload table*] below.
|
|
Compared to other overload tables, placements of function arguments are
|
|
different: Row headers denote type `T` of `*this` object.
|
|
Columns headers denote type `P` of the second function argument.
|
|
The table cells contain the arguments `T` of the intersections
|
|
`result`, which is the functions first argument.
|
|
|
|
``
|
|
/* overload table for */ T\P| e i b p
|
|
void T::add_intersection(T& result, const P&)const ---+--------
|
|
s | s
|
|
m | m m
|
|
S | S S
|
|
M | M M M M
|
|
``
|
|
|
|
The next table contains complexity characteristics for function `add_intersection`.
|
|
|
|
[table Time Complexity for function add_intersection on icl containers
|
|
[[`void add_intersection(T&, const T&, const P&)const`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
|
|
[[__icl_set__] [__Olgn__] [] [] [] ]
|
|
[[__icl_map__] [__Olgn__] [] [__Olgn__] [] ]
|
|
[[__itv_sets__] [__Olgn__] [__On__] [] [] ]
|
|
[[__itv_maps__] [__Olgn__] [__On__] [__On__] [__On__] ]
|
|
]
|
|
|
|
[endsect][/ Function Intersection]
|
|
|
|
|
|
[section Inplace operators][/ Intersection]
|
|
|
|
The overload tables below are giving admissible
|
|
type combinations for the intersection `operator &=`.
|
|
As for the overload patterns of /subtraction/
|
|
intersections are possible within Sets and Maps
|
|
but also for Maps combined with /key objects/
|
|
which are /key elements, intervals/ and /Sets of keys/.
|
|
|
|
``
|
|
// 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 M M M M M
|
|
``
|
|
|
|
While intersection on maps can be viewed as
|
|
a ['*generalisation of set intersection*]. The
|
|
combination on Maps and Sets can be interpreted as
|
|
a ['*generalized selection function*], because it
|
|
allows to select parts of a maps using
|
|
/key/ or /selection objects/.
|
|
So we have a ['*generalized intersection*] for
|
|
these overloads,
|
|
|
|
``
|
|
/* (Generalized) intersection */ &= | e b s m &= | e i b p S M
|
|
---+-------- ---+------------
|
|
s | s s S | S S S
|
|
m | m m M | M M M
|
|
``
|
|
|
|
[*and] a ['*selection by key objects*] here:
|
|
|
|
``
|
|
/* Selection by key objects */ &= | e b s m &= | e i b p S M
|
|
---+-------- ---+------------
|
|
s | s s S | S S S
|
|
m | m m M | M M M
|
|
``
|
|
|
|
The differences for the different functionalities
|
|
of `operator &=` are on the Map-row of the
|
|
tables. Both functionalities fall together
|
|
for Sets in the function ['*set intersection*].
|
|
|
|
Complexity characteristics for inplace intersection operations are
|
|
given by the next tables where
|
|
``
|
|
n = iterative_size(y);
|
|
m = iterative_size(x); //if P is a container type
|
|
``
|
|
|
|
[table Time Complexity for inplace intersection on element containers
|
|
[[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
|
|
[[__icl_set__] [__Olgn__] [] [__Omlgn__] [] ]
|
|
[[__icl_map__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ]
|
|
]
|
|
|
|
[table Time Complexity for inplace intersection 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] [__Olgn__] [__On__] [] [] [__Omlgnpm__] [] ]
|
|
[[interval_maps] [__Olgn__] [__On__] [__Olgn__] [__On__] [__Omlgnpm__] [__Omlgnpm__] ]
|
|
]
|
|
|
|
[endsect][/ Inplace operators Intersection]
|
|
|
|
[section Infix operators][/ Intersection]
|
|
|
|
For the *icl's* infix intersection the
|
|
following overloads are available:
|
|
|
|
``
|
|
// 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 m e | S1 S2 S3 M1 M3
|
|
b | m i | i S1 S2 S3 M1 M3
|
|
s | s s m b | M1 M3
|
|
m | m m m m p | M1 M3
|
|
S1 | S1 S1 S1 S2 S3 M1 M3
|
|
S2 | S2 S2 S2 S2 S3 M1 M3
|
|
S3 | S3 S3 S3 S3 S3 M1 M3
|
|
M1 | M1 M1 M1 M1 M1 M1 M1 M1 M3
|
|
M3 | M3 M3 M3 M3 M3 M3 M3 M3 M3
|
|
``
|
|
|
|
To resolve ambiguities among interval containers
|
|
the ['*finer*] container type is chosen as result type.
|
|
|
|
Again, we can split up the overload tables of
|
|
`operator &` in a part describing
|
|
the ['*generalized intersection] on interval containers
|
|
and a second part defining the
|
|
['*selection by key object] functionality.
|
|
|
|
``
|
|
/* (Generalized) intersection */ & | e b s m & | e i b p S1 S2 S3 M1 M3
|
|
---+-------- ---+---------------------------
|
|
e | s e | S1 S2 S3
|
|
b | m i | 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
|
|
``
|
|
|
|
``
|
|
/* Selection by key objects */ & | e b s m & | e i b p S1 S2 S3 M1 M3
|
|
---+-------- ---+---------------------------
|
|
e | s m e | S1 S2 S3 M1 M3
|
|
b | i | i S1 S2 S3 M1 M3
|
|
s | s s m b |
|
|
m | m m p |
|
|
S1 | S1 S1 S1 S2 S3 M1 M3
|
|
S2 | S2 S2 S2 S2 S3 M1 M3
|
|
S3 | S3 S3 S3 S3 S3 M1 M3
|
|
M1 | M1 M1 M1 M1 M1
|
|
M3 | M3 M3 M3 M3 M3
|
|
``
|
|
|
|
[endsect][/ Inplace operator Intersection]
|
|
|
|
[section Intersection tester]
|
|
|
|
[table
|
|
[[Tester] [Desctription]]
|
|
[[`bool intersects(const T& left, const P& right)`][Tests, if `left` and `right` intersect.]]
|
|
[[`bool disjoint(const T& left, const P& right)`] [Tests, if `left` and `right` are disjoint.]]
|
|
[[] [`intersects(x,y) == !disjoint(x,y)`]]
|
|
]
|
|
|
|
``
|
|
bool intersects(const T&, const P&) T\P| e b s m T\P| e i b p S M
|
|
bool disjoint(const T&, const P&) ---+-------- ---+------------
|
|
s | 1 1 S | 1 1 1
|
|
m | 1 1 1 1 M | 1 1 1 1 1 1
|
|
``
|
|
|
|
[endsect][/ Intersection tester]
|
|
|
|
|
|
['*See also . . .*]
|
|
[table
|
|
[]
|
|
[[[link boost_icl.function_reference.symmetric_difference ['*Symmetric difference*]] ]]
|
|
[[[link boost_icl.function_reference.subtraction ['*Subtraction*]] ]]
|
|
[[[link boost_icl.function_reference.addition ['*Addition*]] ]]
|
|
]
|
|
['*Back to section . . .*]
|
|
[table
|
|
[]
|
|
[[[link function_synopsis_table ['*Function Synopsis*]] ]]
|
|
[[[link boost_icl.interface ['*Interface*]] ]]
|
|
]
|
|
|
|
|
|
[endsect][/ Intersection]
|
|
|
|
|
|
|