Symmetric Difference

Synopsis

Symmetric difference	interval sets	interval maps	element sets	element maps
`T& T::flip(const P&)`	e i	b p		b
`T& flip(T&, const P&)`	e i	b p	e	b
`T& operator ^=(T&, const P&)`	e i S	b p M	e s	b m
`T operator ^ (T, const P&)` `T operator ^ (const P&, T)`	e i S	b p M	e s	b m

Functions and operators that implement symmetric difference on icl objects are given in the table above.

	Description of symmetric difference
`Sets`	`operator ^` implements set symmetric difference
`Maps`	`operator ^` implements a map symmetric difference function similar to set symmetric difference. All pairs that are common to both arguments are removed. All others unified.

Functions

Symmetric difference is implemented on interval containers by the function T& flip(T&, const P& operand).

flip(y,x)

deletes every element of y, if it is contained in x. Elements of x not contained in y are added. For icl containers flip is also availabel as memeber function T& T::flip(const P& operand).

The admissible combinations of types for member function T& T::flip(const P&) can be summarized in the overload table below:

/* overload table for */           T\P| e i b p
T& T::flip(const P&)               ---+--------
T& flip(T&, const P&)               s | s
                                    m |     m
                                    S | S S
                                    M |     M M

The next table contains complexity characteristics for functions flip.

Table 1.37. Time Complexity for member functions flip on icl containers

`T& T::flip(const P&)` `T& flip(T&, const P&)`	domain type	interval type	domain mapping type	interval mapping type
`std::set`	O(log n)
`icl::map`			O(log n)
`interval_set` `separate_interval_set`	O(log n)	O(n)
`split_interval_set`	O(log n)	O(n)
`interval_map` `split_interval_map`			O(log n)	O(n)

Inplace operators

The overload tables below are giving admissible type combinations for operator ^= that implements symmetric difference.

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

Complexity characteristics for inplace operators that implement symmetric difference are given by the next tables where

n = iterative_size(y);
m = iterative_size(x); //if P is a container

Table 1.38. Time Complexity for inplace symmetric difference on element containers

`T& operator &= (T& y, const P& x)`	domain type	domain mapping type	std::set	icl::map
`std::set`	O(log n)		O(m log n)
`icl::map`	O(log n)	O(log n)	O(m log n)	O(m log n)

Table 1.39. Time Complexity for inplace symmetric difference on interval containers

`T& operator &= (T&, const P&)`	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 infix version of symmetric difference 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              e  |             S1 S2 S3
                                   b  |       m            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

To resolve ambiguities among interval containers the finer container type is chosen as result type.