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.
void	mark (vector< index_t > &permutation, index_t i)
	Marks a permutation element as visited.
bool	is_marked (const vector< index_t > &permutation, index_t i)
	Checks if a permutation element has been visited.
void	unmark (vector< index_t > &permutation, index_t i)
	Unmarks a permutation element.
void	apply (void *data, const vector< index_t > &permutation_in, size_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.
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.
void	invert (vector< index_t > &permutation)
	Inverts a permutation in-place.
void	invert (const vector< index_t > &permutation, vector< index_t > &invert)
	Inverts a permutation.

Variables
constexpr index_t	MARKED_BIT = index_t(1) << (sizeof(index_t)*8 - 1)
	Mark used to mark elements for in-place permutation.
constexpr index_t	MAX_SIZE = MARKED_BIT
	Maximum size of a permutation that can be applied in-place.

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]	data	the vector to permute
[in]	permutation_in	the permutation. It is temporarily changed during execution of the function, but identical to the input on exit.

Definition at line 212 of file permutation.h.

apply() [2/2]

void GEO::Permutation::apply ( void *  data, const vector< index_t > &  permutation_in, size_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]	data	an array of permutation.size() elements to permute
[in]	permutation_in	the permutation. It is temporarily changed during execution of the function, but identical to the input on exit.
[in]	elemsize	size 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]	permutation	the permutation to invert
[out]	invert	the computed inverse of permutation

Note

there is also a variant of invert() that computes the permutation in-place.

Definition at line 288 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;

Parameters

[in,out]

permutation

to inverse.

Definition at line 255 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]	permutation	a valid permutation
[in]	i	the index of the element in permutation

Note

Used internally by apply()

Definition at line 116 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]

permutation

a vector of integers

Return values

true	if permutation is a valid permutation
false	otherwise

Definition at line 80 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]	permutation	a valid permutation
[in]	i	the 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 105 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]	permutation	a valid permutation
[in]	i	the index of the element in permutation

Note

Used internally by apply()

Definition at line 129 of file permutation.h.

Variable Documentation

MARKED_BIT

constexpr index_t GEO::Permutation::MARKED_BIT = index_t(1) << (sizeof(index_t)*8 - 1)

constexpr

Mark used to mark elements for in-place permutation.

Definition at line 62 of file permutation.h.

MAX_SIZE

constexpr index_t GEO::Permutation::MAX_SIZE = MARKED_BIT

constexpr

Maximum size of a permutation that can be applied in-place.

Definition at line 67 of file permutation.h.