DGtal 1.3.0
Loading...
Searching...
No Matches
Static Public Member Functions
DGtal::detail::SetFunctionsImpl< Container, associative, ordered > Struct Template Reference

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

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

Definition at line 292 of file SetFunctions.h.

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 }
FreemanChain< int >::Vector Vector

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

Definition at line 340 of file SetFunctions.h.

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 }

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]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 }

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

Definition at line 316 of file SetFunctions.h.

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 }

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]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 }

◆ 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]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: