Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::Permutation Namespace Reference

Utilities for manipulating permutations. More...

Functions

bool is_valid (const vector< index_t > &permutation)
 Checks whether a vector is a valid permutation. More...
 
void mark (vector< index_t > &permutation, index_t i)
 Marks a permutation element as visited. More...
 
bool is_marked (const vector< index_t > &permutation, index_t i)
 Checks if a permutation element has been visited. More...
 
void unmark (vector< index_t > &permutation, index_t i)
 Unmarks a permutation element. More...
 
void apply (void *data, const vector< index_t > &permutation_in, index_t elemsize)
 Applies a permutation in-place. Permutes the first N elements of size elemsize in array data using permutation permutation where N is the number of elements in permutation. The result of the permutation is left in data. The array data must contain at least permutation.size() elements otherwise memory corruption will happen. More...
 
template<class T >
void apply (vector< T > &data, const vector< index_t > &permutation_in)
 Applies a permutation in-place. Permutes the first N elements of vector data using permutation permutation where N is the number of elements in permutation. The result of the permutation is left in data. The array data must contain at least permutation.size() elements otherwise the function throws an out_of_range exception. More...
 
void invert (vector< index_t > &permutation)
 Inverts a permutation in-place. More...
 
void invert (const vector< index_t > &permutation, vector< index_t > &invert)
 Inverts a permutation. More...
 

Detailed Description

Utilities for manipulating permutations.

Function Documentation

◆ apply() [1/2]

template<class T >
void GEO::Permutation::apply ( vector< T > &  data,
const vector< index_t > &  permutation_in 
)
inline

Applies a permutation in-place. Permutes the first N elements of vector data using permutation permutation where N is the number of elements in permutation. The result of the permutation is left in data. The array data must contain at least permutation.size() elements otherwise the function throws an out_of_range exception.

Applying permutation permutation is equivalent to:

for(i=0; i<permutation.size(); i++) {
data2[i] = data[permutation[i]]
}
data = data2 ;
Parameters
[in,out]datathe vector to permute
[in]permutation_inthe permutation. It is temporarily changed during execution of the function, but identical to the input on exit.

Definition at line 211 of file permutation.h.

◆ apply() [2/2]

void GEO::Permutation::apply ( void *  data,
const vector< index_t > &  permutation_in,
index_t  elemsize 
)
inline

Applies a permutation in-place. Permutes the first N elements of size elemsize in array data using permutation permutation where N is the number of elements in permutation. The result of the permutation is left in data. The array data must contain at least permutation.size() elements otherwise memory corruption will happen.

Applying permutation permutation is equivalent to:

for(i=0; i<permutation.size(); i++) {
data2[i] = data[permutation[i]]
}
data = data2 ;
Parameters
[in,out]dataan array of permutation.size() elements to permute
[in]permutation_inthe permutation. It is temporarily changed during execution of the function, but identical to the input on exit.
[in]elemsizesize of the vector elements

Definition at line 157 of file permutation.h.

◆ invert() [1/2]

void GEO::Permutation::invert ( const vector< index_t > &  permutation,
vector< index_t > &  invert 
)
inline

Inverts a permutation.

Computes the inverse of a given permutation and stores the result in another one.

Parameters
[in]permutationthe permutation to invert
[out]invertthe computed inverse of permutation
Note
there is also a variant of invert() that computes the permutation in-place.

Definition at line 285 of file permutation.h.

◆ invert() [2/2]

void GEO::Permutation::invert ( vector< index_t > &  permutation)
inline

Inverts a permutation in-place.

Inverses the given permutation in place, the result of the inversion is left in permutation.

The inversion is equivalent to:

vector<index_t> inverse;
Permutation::invert(permutation, inverse);
permutation = inverse;
void invert(vector< index_t > &permutation)
Inverts a permutation in-place.
Definition: permutation.h:253
Parameters
[in,out]permutationto inverse.

Definition at line 253 of file permutation.h.

◆ is_marked()

bool GEO::Permutation::is_marked ( const vector< index_t > &  permutation,
index_t  i 
)
inline

Checks if a permutation element has been visited.

Parameters
[in]permutationa valid permutation
[in]ithe index of the element in permutation
Note
Used internally by apply()

Definition at line 110 of file permutation.h.

◆ is_valid()

bool GEO::Permutation::is_valid ( const vector< index_t > &  permutation)
inline

Checks whether a vector is a valid permutation.

The vector permutation is a valid permutation if there is a bijection between the range [0..N-1] and the range [permutation[0]..permutation[N-1]] where N is the number of elements in the vector. An empty vector is considered as a valid permutation.

Parameters
[in]permutationa vector of integers
Return values
trueif permutation is a valid permutation
falseotherwise

Definition at line 70 of file permutation.h.

◆ mark()

void GEO::Permutation::mark ( vector< index_t > &  permutation,
index_t  i 
)
inline

Marks a permutation element as visited.

Sets a visited mark for element at index i. in permutation. The element must not have been already marked. The mark can be checked with is_marked() and removed with unmark().

Parameters
[in,out]permutationa valid permutation
[in]ithe index of the element in permutation
Note
Used internally by apply(). Implementation note: marking an element modifies the value in such a way that the initial value of the element can be restored.

Definition at line 95 of file permutation.h.

◆ unmark()

void GEO::Permutation::unmark ( vector< index_t > &  permutation,
index_t  i 
)
inline

Unmarks a permutation element.

This restores the initial value of element at index i in permutation

Parameters
[in,out]permutationa valid permutation
[in]ithe index of the element in permutation
Note
Used internally by apply()

Definition at line 126 of file permutation.h.