1[/ 2 Copyright (c) 2008-2010 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[/ //= Intersection ============================================================] 10[section Intersection][/ Intersection] 11 12[section Synopsis][/ Intersection] 13 14[table 15[[Intersection] [__ch_itv_t__][__ch_itv_sets__][__ch_itv_maps__][__ch_ele_sets__][__ch_ele_maps__]] 16 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] ] 23] 24 25Functions and operators that are related to ['*intersection*] on *icl* objects 26are given in the table above. 27 28 29[table 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. 36 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. 42 43 See also 44 [link boost_icl.semantics.quantifiers__maps_of_numbers.intersection_on_quantifiers ['intersection on Maps of numbers]]. 45 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. 50 ]] 51] 52 53[endsect][/ Synopsis Intersection] 54 55 56[section Functions][/ Intersection] 57 58The overloaded function 59 60`void add_intersection(T& result, const T& y, const P& x)` 61 62allows 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` 64is `added` the the contents of `result`. 65`` 66T s1 = f, s2 = f, y = g; P x = h; // The effect of 67add_intersection(s1, y, x); // add_intersection 68s2 += (y & x); // and & followed by += 69assert(s1==s2); // is identical 70`` 71 72This might be convenient, if intersection is used like a generalized selection function. 73Using element or segment types for `P`, we can select small parts of a container 74`y` and accumulate them in `section`. 75 76The admissible combinations of types for function 77`void add_intersection(T&, const T&, const P&)` can be summarized in the 78['*overload table*] below. 79Compared to other overload tables, placements of function arguments are 80different: Row headers denote type `T` of `*this` object. 81Columns headers denote type `P` of the second function argument. 82The table cells contain the arguments `T` of the intersections 83`result`, which is the functions first argument. 84 85`` 86/* overload table for */ T\P| e i b p 87void T::add_intersection(T& result, const P&)const ---+-------- 88 s | s 89 m | m m 90 S | S S 91 M | M M M M 92`` 93 94The next table contains complexity characteristics for function `add_intersection`. 95 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__] ] 102] 103 104[endsect][/ Function Intersection] 105 106 107[section Inplace operators][/ Intersection] 108 109The overload tables below are giving admissible 110type combinations for the intersection `operator &=`. 111As for the overload patterns of /subtraction/ 112intersections are possible within Sets and Maps 113but also for Maps combined with /key objects/ 114which are /key elements, intervals/ and /Sets of keys/. 115 116`` 117// overload tables for element containers: interval containers: 118T& operator &= (T&, const P&) &= | e b s m &= | e i b p S M 119 ---+-------- ---+------------ 120 s | s s S | S S S 121 m | m m m m M | M M M M M M 122`` 123 124While intersection on maps can be viewed as 125a ['*generalisation of set intersection*]. The 126combination on Maps and Sets can be interpreted as 127a ['*generalized selection function*], because it 128allows to select parts of a maps using 129/key/ or /selection objects/. 130So we have a ['*generalized intersection*] for 131these overloads, 132 133`` 134/* (Generalized) intersection */ &= | e b s m &= | e i b p S M 135 ---+-------- ---+------------ 136 s | s s S | S S S 137 m | m m M | M M M 138`` 139 140[*and] a ['*selection by key objects*] here: 141 142`` 143/* Selection by key objects */ &= | e b s m &= | e i b p S M 144 ---+-------- ---+------------ 145 s | s s S | S S S 146 m | m m M | M M M 147`` 148 149The differences for the different functionalities 150of `operator &=` are on the Map-row of the 151tables. Both functionalities fall together 152for Sets in the function ['*set intersection*]. 153 154Complexity characteristics for inplace intersection operations are 155given by the next tables where 156`` 157n = iterative_size(y); 158m = iterative_size(x); //if P is a container type 159`` 160 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__] ] 165] 166 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__] ] 171] 172 173[endsect][/ Inplace operators Intersection] 174 175[section Infix operators][/ Intersection] 176 177For the *icl's* infix intersection the 178following overloads are available: 179 180`` 181// overload tables for element containers: interval containers: 182T operator & (T, const P&) & | e b s m & | e i b p S1 S2 S3 M1 M3 183T operator & (const P&, T) ---+-------- ---+--------------------------- 184 e | s m e | S1 S2 S3 M1 M3 185 b | m i | i S1 S2 S3 M1 M3 186 s | s s m b | 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 193`` 194 195To resolve ambiguities among interval containers 196the ['*finer*] container type is chosen as result type. 197 198Again, we can split up the overload tables of 199`operator &` in a part describing 200the ['*generalized intersection] on interval containers 201and a second part defining the 202['*selection by key object] functionality. 203 204`` 205/* (Generalized) intersection */ & | e b s m & | e i b p S1 S2 S3 M1 M3 206 ---+-------- ---+--------------------------- 207 e | s e | S1 S2 S3 208 b | m i | i S1 S2 S3 209 s | s s b | M1 M3 210 m | m m p | M1 M3 211 S1 | S1 S1 S1 S2 S3 212 S2 | S2 S2 S2 S2 S3 213 S3 | S3 S3 S3 S3 S3 214 M1 | M1 M1 M1 M3 215 M3 | M3 M3 M3 M3 216`` 217 218`` 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 223 s | s s m b | 224 m | m m p | 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 228 M1 | M1 M1 M1 M1 M1 229 M3 | M3 M3 M3 M3 M3 230`` 231 232[endsect][/ Inplace operator Intersection] 233 234[section Intersection tester] 235 236[table 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)`]] 241] 242 243`` 244bool intersects(const T&, const P&) T\P| e b s m T\P| e i b p S M 245bool disjoint(const T&, const P&) ---+-------- ---+------------ 246 s | 1 1 S | 1 1 1 247 m | 1 1 1 1 M | 1 1 1 1 1 1 248`` 249 250[endsect][/ Intersection tester] 251 252 253['*See also . . .*] 254[table 255[] 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*]] ]] 259] 260['*Back to section . . .*] 261[table 262[] 263[[[link function_synopsis_table ['*Function Synopsis*]] ]] 264[[[link boost_icl.interface ['*Interface*]] ]] 265] 266 267 268[endsect][/ Intersection] 269 270 271 272