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