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