 Home Libraries People FAQ More

Intersection

Synopsis
Functions
Inplace operators
Infix operators
Intersection tester

Synopsis

Intersection

interval
type

interval
sets

interval
maps

element
sets

element
maps

void add_intersection(T&, const T&, const P&)

T& operator &=(T&, const P&)

T operator & (T, const P&)
T operator & (const P&, T)

bool intersects(const T&, const P&)
bool disjoint(const T&, const P&)

Functions and operators that are related to intersection on icl objects are given in the table above.

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.

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.

Functions

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
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 1.34. Time Complexity for function add_intersection on icl containers

void add_intersection(T&, const T&, const P&)const

domain
type

interval
type

domain
mapping
type

interval
mapping
type

O(log n)

O(log n)

O(log n)

O(log n)

O(n)

O(log n)

O(n)

O(n)

O(n)

Inplace operators

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 1.35. Time Complexity for inplace intersection on element containers

T& operator &= (T& y, const P& x)

domain
type

domain
mapping
type

std::set

icl::map

O(log n)

O(m log n)

O(log n)

O(log n)

O(m log n)

O(m log n)

Table 1.36. Time Complexity for inplace intersection on interval containers

T& operator &= (T& y, const P& x)

domain
type

interval
type

domain
mapping
type

interval
mapping
type

interval
sets

interval
maps

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))

Infix operators

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

Intersection tester

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