DGtal  0.9.4beta
Static Public Member Functions
DGtal::detail::SetFunctionsImpl< Container, associative, ordered > Struct Template Reference

#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
Containerany type of container.
associativetells if the container is associative (e.g. set, map, unordered_set, unordered_map).
orderedtells 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

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]S1an input set, S1 - S2 as output.
[in]S2another input set.

Definition at line 292 of file SetFunctions.h.

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

293  {
294  typedef typename Container::value_type value_type;
295  typedef std::vector<value_type> Vector;
296  typedef ComparatorAdapter< Container, associative, ordered,
297  IsPairAssociativeContainer< Container >::value >
298  CompAdapter;
299 
300  Vector V1( S1.begin(), S1.end() );
301  Vector V2( S2.begin(), S2.end() );
302  std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
303  std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
304  S1.clear();
305  std::set_difference( V1.begin(), V1.end(), V2.begin(), V2.end(),
306  std::inserter( S1, S1.end() ), CompAdapter::less( S1 ) );
307  return S1;
308  }
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]S1an input set, \( S1 \cap S2 \) as output.
[in]S2another input set.

Definition at line 340 of file SetFunctions.h.

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

341  {
342  typedef typename Container::value_type value_type;
343  typedef std::vector<value_type> Vector;
344  typedef ComparatorAdapter< Container, associative, ordered,
345  IsPairAssociativeContainer< Container >::value >
346  CompAdapter;
347 
348  Vector V1( S1.begin(), S1.end() );
349  Vector V2( S2.begin(), S2.end() );
350  std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
351  std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
352  S1.clear();
353  std::set_intersection( V1.begin(), V1.end(), V2.begin(), V2.end(),
354  std::inserter( S1, S1.end() ),
355  CompAdapter::less( S1 ) );
356  return S1;
357  }
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]S1an input set, \( S1 \Delta S2 \) as output.
[in]S2another input set.

Definition at line 365 of file SetFunctions.h.

366  {
367  typedef typename Container::value_type value_type;
368  typedef std::vector<value_type> Vector;
369  typedef ComparatorAdapter< Container, associative, ordered,
370  IsPairAssociativeContainer< Container >::value >
371  CompAdapter;
372 
373  Vector V1( S1.begin(), S1.end() );
374  Vector V2( S2.begin(), S2.end() );
375  std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
376  std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
377  S1.clear();
378  std::set_symmetric_difference( V1.begin(), V1.end(), V2.begin(), V2.end(),
379  std::inserter( S1, S1.end() ),
380  CompAdapter::less( S1 ) );
381  return S1;
382  }
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]S1an input set, \( S1 \cup S2 \) as output.
[in]S2another input set.

Definition at line 316 of file SetFunctions.h.

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

317  {
318  typedef typename Container::value_type value_type;
319  typedef std::vector<value_type> Vector;
320  typedef ComparatorAdapter< Container, associative, ordered,
321  IsPairAssociativeContainer< Container >::value >
322  CompAdapter;
323 
324  Vector V1( S1.begin(), S1.end() );
325  Vector V2( S2.begin(), S2.end() );
326  std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
327  std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
328  S1.clear();
329  std::set_union( V1.begin(), V1.end(), V2.begin(), V2.end(),
330  std::inserter( S1, S1.end() ), CompAdapter::less( S1 ) );
331  return S1;
332  }
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]S1an input set.
[in]S2another input set.
Returns
true iff S1 is equal to S2 (seen as sets).

Definition at line 243 of file SetFunctions.h.

244  {
245  // Checks size first.
246  if ( S1.size() != S2.size() ) return false;
247  typedef typename Container::value_type value_type;
248  typedef std::vector<value_type> Vector;
249  typedef ComparatorAdapter< Container, associative, ordered,
250  IsPairAssociativeContainer< Container >::value >
251  CompAdapter;
252 
253  Vector V1( S1.begin(), S1.end() );
254  Vector V2( S2.begin(), S2.end() );
255  std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
256  std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
257  return std::equal( V1.begin(), V1.end(), V2.begin(),
258  CompAdapter::equal_to( S1 ) );
259  }
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]S1an input set.
[in]S2another input set.
Returns
true iff S1 is a subset of S2.

Definition at line 268 of file SetFunctions.h.

269  {
270  // Checks size first.
271  if ( S1.size() > S2.size() ) return false;
272  typedef typename Container::value_type value_type;
273  typedef std::vector<value_type> Vector;
274  typedef ComparatorAdapter< Container, associative, ordered,
275  IsPairAssociativeContainer< Container >::value >
276  CompAdapter;
277 
278  Vector V1( S1.begin(), S1.end() );
279  Vector V2( S2.begin(), S2.end() );
280  std::sort( V1.begin(), V1.end(), CompAdapter::less( S1 ) );
281  std::sort( V2.begin(), V2.end(), CompAdapter::less( S1 ) );
282  return std::includes( V2.begin(), V2.end(), V1.begin(), V1.end(),
283  CompAdapter::less( S1 ) );
284  }

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