2 Copyright (c) 2008-2010 Joachim Faulhaber
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)
9 [/ //= Intersection ============================================================]
10 [section Intersection][/ Intersection]
12 [section Synopsis][/ Intersection]
15 [[Intersection] [__ch_itv_t__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]]
17 [[`void add_intersection(T&, const T&, const P&)`][ ] [__eiS][__eiS __bpM][ ] [ ] ]
18 [[`T& operator &=(T&, const P&)`] [ ] [__eiS][__eiS __bpM][__es] [__bm] ]
19 [[`T operator & (T, const P&)`\n
20 `T operator & (const P&, T)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
21 [[`bool intersects(const T&, const P&)`\n
22 `bool disjoint(const T&, const P&)`] [__i] [__eiS][__eiS __bpM][__es] [__bm] ]
25 Functions and operators that are related to ['*intersection*] on *icl* objects
26 are given in the table above.
30 [[] [Description of Intersection]]
31 [[`Sets`][Intersection on Sets implements ['*set intersection*]]]
32 [[`Maps`][Intersection on Maps implements a ['*map intersection*] function similar to /set intersection/.
33 If, on intersection, an element value pair `(k,v)` it's key `k` is in the map
34 already, the intersection function is propagated to the associated value,
35 if it exists for the Map's codomain_type.
37 If the codomain_type has no intersection operation, associated
38 values are combined using addition. For partial map types this
39 results in an addition on the intersection of the domains of
40 the intersected sets. For total maps intersection and
41 addition are identical in this case.
44 [link boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers ['intersection on Maps of numbers]].
46 A Map can be intersected with key types: an element
47 (an interval for interval_maps) and and a Set. This
48 results in the selection of a submap, and can be
49 defined as a generalized selection function on Maps.
53 [endsect][/ Synopsis Intersection]
56 [section Functions][/ Intersection]
58 The overloaded function
60 `void add_intersection(T& result, const T& y, const P& x)`
62 allows to accumulate the intersection of `y` and `x` in the first argument `result`.
63 `Result` might already contain data. In this case the intersection of `y` and `x`
64 is `added` the the contents of `result`.
66 T s1 = f, s2 = f, y = g; P x = h; // The effect of
67 add_intersection(s1, y, x); // add_intersection
68 s2 += (y & x); // and & followed by +=
69 assert(s1==s2); // is identical
72 This might be convenient, if intersection is used like a generalized selection function.
73 Using element or segment types for `P`, we can select small parts of a container
74 `y` and accumulate them in `section`.
76 The admissible combinations of types for function
77 `void add_intersection(T&, const T&, const P&)` can be summarized in the
78 ['*overload table*] below.
79 Compared to other overload tables, placements of function arguments are
80 different: Row headers denote type `T` of `*this` object.
81 Columns headers denote type `P` of the second function argument.
82 The table cells contain the arguments `T` of the intersections
83 `result`, which is the functions first argument.
86 /* overload table for */ T\P| e i b p
87 void T::add_intersection(T& result, const P&)const ---+--------
94 The next table contains complexity characteristics for function `add_intersection`.
96 [table Time Complexity for function add_intersection on icl containers
97 [[`void add_intersection(T&, const T&, const P&)const`] [__ch_dom_t__][__ch_itv_t__][__ch_dom_mp_t__][__ch_itv_mp_t__]]
98 [[__icl_set__] [__Olgn__] [] [] [] ]
99 [[__icl_map__] [__Olgn__] [] [__Olgn__] [] ]
100 [[__itv_sets__] [__Olgn__] [__On__] [] [] ]
101 [[__itv_maps__] [__Olgn__] [__On__] [__On__] [__On__] ]
104 [endsect][/ Function Intersection]
107 [section Inplace operators][/ Intersection]
109 The overload tables below are giving admissible
110 type combinations for the intersection `operator &=`.
111 As for the overload patterns of /subtraction/
112 intersections are possible within Sets and Maps
113 but also for Maps combined with /key objects/
114 which are /key elements, intervals/ and /Sets of keys/.
117 // overload tables for element containers: interval containers:
118 T& operator &= (T&, const P&) &= | e b s m &= | e i b p S M
119 ---+-------- ---+------------
121 m | m m m m M | M M M M M M
124 While intersection on maps can be viewed as
125 a ['*generalisation of set intersection*]. The
126 combination on Maps and Sets can be interpreted as
127 a ['*generalized selection function*], because it
128 allows to select parts of a maps using
129 /key/ or /selection objects/.
130 So we have a ['*generalized intersection*] for
134 /* (Generalized) intersection */ &= | e b s m &= | e i b p S M
135 ---+-------- ---+------------
140 [*and] a ['*selection by key objects*] here:
143 /* Selection by key objects */ &= | e b s m &= | e i b p S M
144 ---+-------- ---+------------
149 The differences for the different functionalities
150 of `operator &=` are on the Map-row of the
151 tables. Both functionalities fall together
152 for Sets in the function ['*set intersection*].
154 Complexity characteristics for inplace intersection operations are
155 given by the next tables where
157 n = iterative_size(y);
158 m = iterative_size(x); //if P is a container type
161 [table Time Complexity for inplace intersection on element containers
162 [[`T& operator &= (T& y, const P& x)`][__ch_dom_t__][__ch_dom_mp_t__][__ch_icl_set__][__ch_icl_map__]]
163 [[__icl_set__] [__Olgn__] [] [__Omlgn__] [] ]
164 [[__icl_map__] [__Olgn__] [__Olgn__] [__Omlgn__] [__Omlgn__] ]
167 [table Time Complexity for inplace intersection on interval containers
168 [[`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__]]
169 [[interval_sets] [__Olgn__] [__On__] [] [] [__Omlgnpm__] [] ]
170 [[interval_maps] [__Olgn__] [__On__] [__Olgn__] [__On__] [__Omlgnpm__] [__Omlgnpm__] ]
173 [endsect][/ Inplace operators Intersection]
175 [section Infix operators][/ Intersection]
177 For the *icl's* infix intersection the
178 following overloads are available:
181 // overload tables for element containers: interval containers:
182 T operator & (T, const P&) & | e b s m & | e i b p S1 S2 S3 M1 M3
183 T operator & (const P&, T) ---+-------- ---+---------------------------
184 e | s m e | S1 S2 S3 M1 M3
185 b | m i | i S1 S2 S3 M1 M3
187 m | m m m m p | M1 M3
188 S1 | S1 S1 S1 S2 S3 M1 M3
189 S2 | S2 S2 S2 S2 S3 M1 M3
190 S3 | S3 S3 S3 S3 S3 M1 M3
191 M1 | M1 M1 M1 M1 M1 M1 M1 M1 M3
192 M3 | M3 M3 M3 M3 M3 M3 M3 M3 M3
195 To resolve ambiguities among interval containers
196 the ['*finer*] container type is chosen as result type.
198 Again, we can split up the overload tables of
199 `operator &` in a part describing
200 the ['*generalized intersection] on interval containers
201 and a second part defining the
202 ['*selection by key object] functionality.
205 /* (Generalized) intersection */ & | e b s m & | e i b p S1 S2 S3 M1 M3
206 ---+-------- ---+---------------------------
219 /* Selection by key objects */ & | e b s m & | e i b p S1 S2 S3 M1 M3
220 ---+-------- ---+---------------------------
221 e | s m e | S1 S2 S3 M1 M3
222 b | i | i S1 S2 S3 M1 M3
225 S1 | S1 S1 S1 S2 S3 M1 M3
226 S2 | S2 S2 S2 S2 S3 M1 M3
227 S3 | S3 S3 S3 S3 S3 M1 M3
232 [endsect][/ Inplace operator Intersection]
234 [section Intersection tester]
237 [[Tester] [Desctription]]
238 [[`bool intersects(const T& left, const P& right)`][Tests, if `left` and `right` intersect.]]
239 [[`bool disjoint(const T& left, const P& right)`] [Tests, if `left` and `right` are disjoint.]]
240 [[] [`intersects(x,y) == !disjoint(x,y)`]]
244 bool intersects(const T&, const P&) T\P| e b s m T\P| e i b p S M
245 bool disjoint(const T&, const P&) ---+-------- ---+------------
247 m | 1 1 1 1 M | 1 1 1 1 1 1
250 [endsect][/ Intersection tester]
256 [[[link boost_icl.function_reference.symmetric_difference ['*Symmetric difference*]] ]]
257 [[[link boost_icl.function_reference.subtraction ['*Subtraction*]] ]]
258 [[[link boost_icl.function_reference.addition ['*Addition*]] ]]
260 ['*Back to section . . .*]
263 [[[link function_synopsis_table ['*Function Synopsis*]] ]]
264 [[[link boost_icl.interface ['*Interface*]] ]]
268 [endsect][/ Intersection]