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