|
Home | Libraries | People | FAQ | More |
|
Intersection |
interval |
interval |
interval |
itl::set |
itl::map |
|---|---|---|---|---|---|
|
|
|
|
|
||
|
|
|||||
|
|
|||||
|
|
Functions and operators that are related to intersection on itl objects are given in the table above.
|
|
Description of Intersection |
|---|---|
|
|
Intersection on Sets implements set intersection |
|
|
Intersection on Maps implements a map
intersection function similar to set
intersection. If, on intersection, an element value
pair 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 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. |
The admissible combinations of types for member function void T::add_intersection(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 void T::add_intersection(T& result, const P&)const add_intersection | e i b p -----------------+-------- s | s m | m m S | S S M | M M M M
The next table contains complexity characteristics for member function
add_intersection.
Table 1.31. Time Complexity for member function add_intersection on itl containers
|
|
domain |
interval |
domain |
interval |
|---|---|---|---|---|
|
O(log n) |
|
|
|
|
|
O(log n) |
|
O(log n) |
|
|
|
O(log n) |
O(n) |
|
|
|
|
O(log n) |
O(n) |
O(n) |
O(n) |
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 T& operator &= (T&, const P&) element containers: interval containers: &= | 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 = y.iterative_size(); m = x.iterative_size(); //if P is a container type
Table 1.33. Time Complexity for inplace intersection on interval containers
|
|
domain |
interval |
domain |
interval |
interval |
interval |
|---|---|---|---|---|---|---|
|
interval_sets |
O(log n) |
O(n) |
|
|
O(m log(n+m)) |
|
|
interval_maps |
O(log n) |
O(n) |
O(log n) |
O(n) |
O(m log(n+m)) |
O(m log(n+m)) |
For the itl's infix intersection the following overloads are available:
// overload tables for T operator & (T, const P&) T operator & (const P&, T) element containers: interval containers: & | e b s m & | e i b p S1 S2 S3 M1 M3 ---+-------- ---+--------------------------- 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
|
Tester |
Desctription |
|---|---|
|
|
Tests, if |
// bool intersects(const T&, const P&) T\P | e b s m T\P | e i b p S M ----+-------- ----+------------ s | 1 1 S | 1 1 1 m | 1 1 1 1 M | 1 1 1 1 1 1
See also . . .
Back to section . . .