Aim: Specialize set operations (union, intersection, difference, symmetric_difference) according to the given type of container. It uses standard algorithms when containers are ordered, otherwise it provides a default implementation. More...

#include <DGtal/base/SetFunctions.h>

Static Public Member Functions
static bool	isEqual (const Container &S1, const Container &S2)

static bool	isSubset (const Container &S1, const Container &S2)

static Container &	assignDifference (Container &S1, const Container &S2)

static Container &	assignUnion (Container &S1, const Container &S2)

static Container &	assignIntersection (Container &S1, const Container &S2)

static Container &	assignSymmetricDifference (Container &S1, const Container &S2)

Detailed Description

template<typename Container, bool associative, bool ordered>
struct DGtal::detail::SetFunctionsImpl< Container, associative, ordered >

Aim: Specialize set operations (union, intersection, difference, symmetric_difference) according to the given type of container. It uses standard algorithms when containers are ordered, otherwise it provides a default implementation.

Description of template class 'SetFunctions'

Template Parameters

Container	any type of container.
associative	tells if the container is associative (e.g. set, map, unordered_set, unordered_map).
ordered	tells if the container is ordered (e.g., set, map).

Specialized implementations are marked with (S) in the list below.

|-----------------—|----------—|-------—|-------—|

Container	associative	ordered	pair
vector	false	false	false
list	false	false	false
(not valid)	false	false	true
sorted vector (S)	false	true	false
sorted list (S)	false	true	false
set (S)	true	true	false
map (S)	true	true	true
unordered_set (S)	true	false	false
unordered_map (S)	true	false	true

Note: For pair containers (like map and unordered_map), the data is not taken into account, which means that it can be lost in some (modifier) operations.; It is illogical to have a containers that is not associative and that is a pair container, since the pair represents an association.

Definition at line 234 of file SetFunctions.h.

Member Function Documentation

◆ assignDifference()

template<typename Container , bool associative, bool ordered>

static Container & DGtal::detail::SetFunctionsImpl< Container, associative, ordered >::assignDifference	(	Container &	S1,
		const Container &	S2 )

inlinestatic

Updates the set S1 as \( S1 - S2 \). This version does not use the fact that the container is ordered.

Parameters

[in,out]	S1	an input set, S1 - S2 as output.
[in]	S2	another input set.

Definition at line 292 of file SetFunctions.h.

      {
        typedef typename Container::value_type value_type;
        typedef std::vector<value_type> Vector;
        typedef ComparatorAdapter< Container, associative, ordered,
                                   IsPairAssociativeContainer< Container >::value >
          CompAdapter;
 
        Vector V1( S1.begin(), S1.end() );
        Vector V2( S2.begin(), S2.end() );
        std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
        std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
        S1.clear();
        std::set_difference( V1.begin(), V1.end(), V2.begin(), V2.end(),
                             std::inserter( S1, S1.end() ), CompAdapter::less( S1 ) );
        return S1;
      }

Referenced by DGtal::detail::SetFunctionsImpl< Container, true, false >::assignSymmetricDifference().

◆ assignIntersection()

template<typename Container , bool associative, bool ordered>

static Container & DGtal::detail::SetFunctionsImpl< Container, associative, ordered >::assignIntersection	(	Container &	S1,
		const Container &	S2 )

inlinestatic

Updates the set S1 as \( S1 \cap S2 \). This version does not use the fact that the container is ordered.

Parameters

[in,out]	S1	an input set, \( S1 \cap S2 \) as output.
[in]	S2	another input set.

Definition at line 340 of file SetFunctions.h.

      {
        typedef typename Container::value_type value_type;
        typedef std::vector<value_type> Vector;
        typedef ComparatorAdapter< Container, associative, ordered,
                                   IsPairAssociativeContainer< Container >::value >
          CompAdapter;
 
        Vector V1( S1.begin(), S1.end() );
        Vector V2( S2.begin(), S2.end() );
        std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 )  );
        std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 )  );
        S1.clear();
        std::set_intersection( V1.begin(), V1.end(), V2.begin(), V2.end(),
                               std::inserter( S1, S1.end() ), 
                               CompAdapter::less( S1 )  );
        return S1;
      }

Referenced by DGtal::detail::SetFunctionsImpl< Container, true, false >::assignSymmetricDifference().

◆ assignSymmetricDifference()

template<typename Container , bool associative, bool ordered>

static Container & DGtal::detail::SetFunctionsImpl< Container, associative, ordered >::assignSymmetricDifference	(	Container &	S1,
		const Container &	S2 )

inlinestatic

Updates the set S1 as \( S1 \Delta S2 \). This version does not use the fact that the container is ordered.

Parameters

[in,out]	S1	an input set, \( S1 \Delta S2 \) as output.
[in]	S2	another input set.

Definition at line 365 of file SetFunctions.h.

      {
        typedef typename Container::value_type value_type;
        typedef std::vector<value_type> Vector;
        typedef ComparatorAdapter< Container, associative, ordered,
                                   IsPairAssociativeContainer< Container >::value >
          CompAdapter;
 
        Vector V1( S1.begin(), S1.end() );
        Vector V2( S2.begin(), S2.end() );
        std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 )  );
        std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 )  );
        S1.clear();
        std::set_symmetric_difference( V1.begin(), V1.end(), V2.begin(), V2.end(),
                                       std::inserter( S1, S1.end() ), 
                                       CompAdapter::less( S1 )  );
        return S1;
      }

◆ assignUnion()

template<typename Container , bool associative, bool ordered>

static Container & DGtal::detail::SetFunctionsImpl< Container, associative, ordered >::assignUnion	(	Container &	S1,
		const Container &	S2 )

inlinestatic

Updates the set S1 as \( S1 \cup S2 \). This version does not use the fact that the container is ordered.

Parameters

[in,out]	S1	an input set, \( S1 \cup S2 \) as output.
[in]	S2	another input set.

Definition at line 316 of file SetFunctions.h.

      {
        typedef typename Container::value_type value_type;
        typedef std::vector<value_type> Vector;
        typedef ComparatorAdapter< Container, associative, ordered,
                                   IsPairAssociativeContainer< Container >::value >
          CompAdapter;
 
        Vector V1( S1.begin(), S1.end() );
        Vector V2( S2.begin(), S2.end() );
        std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
        std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
        S1.clear();
        std::set_union( V1.begin(), V1.end(), V2.begin(), V2.end(),
                        std::inserter( S1, S1.end() ), CompAdapter::less( S1 ) );
        return S1;
      }

Referenced by DGtal::detail::SetFunctionsImpl< Container, true, false >::assignSymmetricDifference().

◆ isEqual()

template<typename Container , bool associative, bool ordered>

static bool DGtal::detail::SetFunctionsImpl< Container, associative, ordered >::isEqual	(	const Container &	S1,
		const Container &	S2 )

inlinestatic

Equality test. This version does not use the fact that the container is ordered.

Parameters

[in]	S1	an input set.
[in]	S2	another input set.

Returns: true iff S1 is equal to S2 (seen as sets).

Definition at line 243 of file SetFunctions.h.

      {
        // Checks size first.
        if ( S1.size() != S2.size() ) return false;
        typedef typename Container::value_type value_type;
        typedef std::vector<value_type> Vector;
        typedef ComparatorAdapter< Container, associative, ordered,
                                   IsPairAssociativeContainer< Container >::value >
          CompAdapter;
 
        Vector V1( S1.begin(), S1.end() );
        Vector V2( S2.begin(), S2.end() );
        std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
        std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
        return std::equal( V1.begin(), V1.end(), V2.begin(),
                           CompAdapter::equal_to( S1 ) );
      }

◆ isSubset()

template<typename Container , bool associative, bool ordered>

static bool DGtal::detail::SetFunctionsImpl< Container, associative, ordered >::isSubset	(	const Container &	S1,
		const Container &	S2 )

inlinestatic

Inclusion test. This version does not use the fact that the container is ordered.

Parameters

[in]	S1	an input set.
[in]	S2	another input set.

Returns: true iff S1 is a subset of S2.

Definition at line 268 of file SetFunctions.h.

      {
        // Checks size first.
        if ( S1.size() > S2.size() ) return false;
        typedef typename Container::value_type value_type;
        typedef std::vector<value_type> Vector;
        typedef ComparatorAdapter< Container, associative, ordered,
                                   IsPairAssociativeContainer< Container >::value >
          CompAdapter;
 
        Vector V1( S1.begin(), S1.end() );
        Vector V2( S2.begin(), S2.end() );
        std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
        std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
        return std::includes( V2.begin(), V2.end(), V1.begin(), V1.end(),
                              CompAdapter::less( S1 ) );
      }

The documentation for this struct was generated from the following file:

SetFunctions.h

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ assignDifference()

◆ assignIntersection()

◆ assignSymmetricDifference()

◆ assignUnion()

◆ isEqual()

◆ isSubset()