Main Page | Modules | File List | Globals

Low-level permutation manipulation module


Typedefs

typedef _gdsl_perm * _gdsl_perm_t
 GDSL low-level permutation type.

typedef void(* gdsl_perm_write_func_t )(ulong E, FILE *OUTPUT_FILE, gdsl_perm_position_t POSITION, void *USER_DATA)
 GDSL low-level permutation write function type.


Enumerations

enum  gdsl_perm_position_t { GDSL_PERM_POSITION_FIRST = 1, GDSL_PERM_POSITION_LAST = 2 }
 This type is for gdsl_perm_write_func_t. More...


Functions

_gdsl_perm_t _gdsl_perm_alloc (const ulong N)
 Create a new low-level permutation.

void _gdsl_perm_free (_gdsl_perm_t P)
 Destroy a low-level permutation.

_gdsl_perm_t _gdsl_perm_copy (const _gdsl_perm_t P)
 Copy a low-level permutation.

ulong _gdsl_perm_get_size (const _gdsl_perm_t P)
 Get the size of a low-level permutation.

ulong _gdsl_perm_get_content (const _gdsl_perm_t P, const ulong INDIX)
 Get the (INDIX+1)-th content from a low-level permutation.

ulong_gdsl_perm_get_content_array (const _gdsl_perm_t P)
 Get the array contents of a low-level permutation.

ulong _gdsl_perm_linear_inversions_count (const _gdsl_perm_t P)
 Count the inversions number into a linear low-level permutation.

ulong _gdsl_perm_linear_cycles_count (const _gdsl_perm_t P)
 Count the cycles number into a linear low-level permutation.

ulong _gdsl_perm_canonical_cycles_count (const _gdsl_perm_t P)
 Count the cycles number into a canonical low-level permutation.

_gdsl_perm_t _gdsl_perm_linear_next (_gdsl_perm_t P)
 Get the next permutation from a linear low-level permutation.

_gdsl_perm_t _gdsl_perm_linear_prev (_gdsl_perm_t P)
 Get the previous permutation from a linear low-level permutation.

_gdsl_perm_t _gdsl_perm_init_from_array (_gdsl_perm_t P, const ulong *V)
 Initialize a low-level permutation with an array of values.

_gdsl_perm_t _gdsl_perm_multiply (_gdsl_perm_t RESULT, const _gdsl_perm_t ALPHA, const _gdsl_perm_t BETA)
 Multiply two low-level permutations.

_gdsl_perm_t _gdsl_perm_linear_to_canonical (_gdsl_perm_t Q, const _gdsl_perm_t P)
 Convert a linear low-level permutation to its canonical form.

_gdsl_perm_t _gdsl_perm_canonical_to_linear (_gdsl_perm_t Q, const _gdsl_perm_t P)
 Convert a canonical low-level permutation to its linear form.

_gdsl_perm_t _gdsl_perm_inverse (_gdsl_perm_t P)
 Inverse in place a low-level permutation.

_gdsl_perm_t _gdsl_perm_reverse (_gdsl_perm_t P)
 Reverse in place a low-level permutation.

_gdsl_perm_t _gdsl_perm_randomize (_gdsl_perm_t P)
 Randomize a low-level permutation.

gdsl_element_t_gdsl_perm_apply_on_array (gdsl_element_t *V, const _gdsl_perm_t P)
 Apply a low-level permutation on to a vector.

void _gdsl_perm_write (const _gdsl_perm_t P, const gdsl_perm_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of a low-level permutation to a file.

void _gdsl_perm_write_xml (const _gdsl_perm_t P, const gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of a low-level permutation to a file into XML.

void _gdsl_perm_dump (const _gdsl_perm_t P, const gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of a low-level permutation to a file.


Typedef Documentation

typedef struct _gdsl_perm* _gdsl_perm_t
 

GDSL low-level permutation type.

This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module.

Definition at line 49 of file _gdsl_perm.h.

typedef void(* gdsl_perm_write_func_t)(ulong E, FILE* OUTPUT_FILE, gdsl_perm_position_t POSITION, void* USER_DATA )
 

GDSL low-level permutation write function type.

Parameters:
E The permutation element to write
OUTPUT_FILE The file where to write E
POSITION is an or-ed combination of gdsl_perm_position_t values to indicate where E is located into the gdsl_perm_t mapped.
USER_DATA User's datas

Definition at line 73 of file _gdsl_perm.h.


Enumeration Type Documentation

enum gdsl_perm_position_t
 

This type is for gdsl_perm_write_func_t.

Enumeration values:
GDSL_PERM_POSITION_FIRST  When element is at first position
GDSL_PERM_POSITION_LAST  When element is at last position

Definition at line 54 of file _gdsl_perm.h.


Function Documentation

_gdsl_perm_t _gdsl_perm_alloc const ulong  N  ) 
 

Create a new low-level permutation.

Allocate a new permutation data structure of size N.

Note:
Complexity: O( N )
Precondition:
N > 0
Parameters:
N The number of elements of the permutation to create.
Returns:
the newly allocated identity permutation in its linear form in case of success.

NULL in case of insufficient memory.

See also:
_gdsl_perm_free()

_gdsl_perm_copy()

gdsl_element_t* _gdsl_perm_apply_on_array gdsl_element_t V,
const _gdsl_perm_t  P
 

Apply a low-level permutation on to a vector.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t & |P| == |V|
Parameters:
V The vector/array to reorder according to P
P The permutation to use to reorder V
Returns:
the reordered array V according to the permutation P in case of success.

NULL in case of insufficient memory.

ulong _gdsl_perm_canonical_cycles_count const _gdsl_perm_t  P  ) 
 

Count the cycles number into a canonical low-level permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid canonical _gdsl_perm_t
Parameters:
P The canonical permutation to use.
Returns:
the number of cycles into the canonical permutation P.
See also:
_gdsl_perm_linear_cycles_count()

_gdsl_perm_t _gdsl_perm_canonical_to_linear _gdsl_perm_t  Q,
const _gdsl_perm_t  P
 

Convert a canonical low-level permutation to its linear form.

Convert the canonical permutation P to its linear form. The resulted linear permutation is placed into Q without modifying P.

Note:
Complexity: O( |P| )
Precondition:
P & Q must be valids _gdsl_perm_t & |P| == |Q| & P != Q
Parameters:
Q The linear form of P
P The canonical permutation used to compute its linear form into Q
Returns:
the linear form Q of the permutation P.
See also:
_gdsl_perm_linear_to_canonical()

_gdsl_perm_t _gdsl_perm_copy const _gdsl_perm_t  P  ) 
 

Copy a low-level permutation.

Create and return a copy of the low-level permutation P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t.
Postcondition:
The returned permutation must be deallocated with _gdsl_perm_free.
Parameters:
P The low-level permutation to copy.
Returns:
a copy of P in case of success.

NULL in case of insufficient memory.

See also:
_gdsl_perm_alloc

_gdsl_perm_free

void _gdsl_perm_dump const _gdsl_perm_t  P,
const gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA
 

Dump the internal structure of a low-level permutation to a file.

Dump the structure of the low-level permutation P to OUTPUT_FILE. If WRITE_F != NULL, then uses WRITE_F function to write P's content to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t & OUTPUT_FILE != NULL
Parameters:
P The low-level permutation to dump.
WRITE_F The write function.
OUTPUT_FILE The file where to write P's content.
USER_DATA User's datas passed to WRITE_F.
See also:
_gdsl_perm_write()

_gdsl_perm_write_xml()

void _gdsl_perm_free _gdsl_perm_t  P  ) 
 

Destroy a low-level permutation.

Deallocate the low-level permutation P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t
Parameters:
P The permutation to destroy
See also:
_gdsl_perm_alloc()

_gdsl_perm_copy()

ulong _gdsl_perm_get_content const _gdsl_perm_t  P,
const ulong  INDIX
 

Get the (INDIX+1)-th content from a low-level permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid _gdsl_perm_t & INDIX < |P|
Parameters:
P The permutation to use.
INDIX The indix of the value to get.
Returns:
the value at the INDIX-th position in the permutation P.
See also:
_gdsl_perm_get_size()

_gdsl_perm_get_content_array()

ulong* _gdsl_perm_get_content_array const _gdsl_perm_t  P  ) 
 

Get the array contents of a low-level permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid _gdsl_perm_t
Parameters:
P The permutation to get datas from.
Returns:
the values array of the permutation P.
See also:
_gdsl_perm_get_content()

ulong _gdsl_perm_get_size const _gdsl_perm_t  P  ) 
 

Get the size of a low-level permutation.

Note:
Complexity: O( 1 )
Precondition:
P must be a valid _gdsl_perm_t
Parameters:
P The permutation to get the size from.
Returns:
the number of elements of P (noted |P|).
See also:
_gdsl_perm_get_content()

_gdsl_perm_get_content_array()

_gdsl_perm_t _gdsl_perm_init_from_array _gdsl_perm_t  P,
const ulong V
 

Initialize a low-level permutation with an array of values.

Initialize the permutation P with the values contained in the array of values V. If V does not design a permutation, then P is left unchanged.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t & V != NULL & |V| == |P|
Parameters:
P The permutation to initialize
V The array of values to initialize P
Returns:
the modified permutation in case of success.

NULL in case V does not design a valid permutation.

_gdsl_perm_t _gdsl_perm_inverse _gdsl_perm_t  P  ) 
 

Inverse in place a low-level permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t
Parameters:
P The permutation to invert
Returns:
the inverse permutation of P in case of success.

NULL in case of insufficient memory.

See also:
_gdsl_perm_reverse()

ulong _gdsl_perm_linear_cycles_count const _gdsl_perm_t  P  ) 
 

Count the cycles number into a linear low-level permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear _gdsl_perm_t
Parameters:
P The linear permutation to use.
Returns:
the number of cycles into the linear permutation P.
See also:
_gdsl_perm_canonical_cycles_count()

ulong _gdsl_perm_linear_inversions_count const _gdsl_perm_t  P  ) 
 

Count the inversions number into a linear low-level permutation.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear _gdsl_perm_t
Parameters:
P The linear permutation to use.
Returns:
the number of inversions into the linear permutation P.

_gdsl_perm_t _gdsl_perm_linear_next _gdsl_perm_t  P  ) 
 

Get the next permutation from a linear low-level permutation.

The permutation P is modified to become the next permutation after P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear _gdsl_perm_t & |P| > 1
Parameters:
P The linear permutation to modify
Returns:
the next permutation after the permutation P.

NULL if P is already the last permutation.

See also:
_gdsl_perm_linear_prev()

_gdsl_perm_t _gdsl_perm_linear_prev _gdsl_perm_t  P  ) 
 

Get the previous permutation from a linear low-level permutation.

The permutation P is modified to become the previous permutation before P.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid linear _gdsl_perm_t & |P| >= 2
Parameters:
P The linear permutation to modify
Returns:
the previous permutation before the permutation P.

NULL if P is already the first permutation.

See also:
_gdsl_perm_linear_next()

_gdsl_perm_t _gdsl_perm_linear_to_canonical _gdsl_perm_t  Q,
const _gdsl_perm_t  P
 

Convert a linear low-level permutation to its canonical form.

Convert the linear permutation P to its canonical form. The resulted canonical permutation is placed into Q without modifying P.

Note:
Complexity: O( |P| )
Precondition:
P & Q must be valids _gdsl_perm_t & |P| == |Q| & P != Q
Parameters:
Q The canonical form of P
P The linear permutation used to compute its canonical form into Q
Returns:
the canonical form Q of the permutation P.
See also:
_gdsl_perm_canonical_to_linear()

_gdsl_perm_t _gdsl_perm_multiply _gdsl_perm_t  RESULT,
const _gdsl_perm_t  ALPHA,
const _gdsl_perm_t  BETA
 

Multiply two low-level permutations.

Compute the product of the permutations ALPHA x BETA and puts the result in RESULT without modifying ALPHA and BETA.

Note:
Complexity: O( |RESULT| )
Precondition:
RESULT, ALPHA and BETA must be valids _gdsl_perm_t & |RESULT| == |ALPHA| == |BETA|
Parameters:
RESULT The result of the product ALPHA x BETA
ALPHA The first permutation used in the product
BETA The second permutation used in the product
Returns:
RESULT, the result of the multiplication of the permutations A and B.

_gdsl_perm_t _gdsl_perm_randomize _gdsl_perm_t  P  ) 
 

Randomize a low-level permutation.

The permutation P is randomized in an efficient way, using inversions array.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t
Parameters:
P The permutation to randomize
Returns:
the mirror image ~P of the permutation of P in case of success.

NULL in case of insufficient memory.

_gdsl_perm_t _gdsl_perm_reverse _gdsl_perm_t  P  ) 
 

Reverse in place a low-level permutation.

Note:
Complexity: O( |P| / 2 )
Precondition:
P must be a valid _gdsl_perm_t
Parameters:
P The permutation to reverse
Returns:
the mirror image of the permutation P
See also:
_gdsl_perm_inverse()

void _gdsl_perm_write const _gdsl_perm_t  P,
const gdsl_perm_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA
 

Write the content of a low-level permutation to a file.

Write the content of the low-level permuation P to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t & WRITE_F != NULL & OUTPUT_FILE != NULL
Parameters:
P The low-level permutation to write.
WRITE_F The write function.
OUTPUT_FILE The file where to write P's content.
USER_DATA User's datas passed to WRITE_F.
See also:
_gdsl_perm_write_xml()

_gdsl_perm_dump()

void _gdsl_perm_write_xml const _gdsl_perm_t  P,
const gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA
 

Write the content of a low-level permutation to a file into XML.

Write the content of the low-level permutation P to OUTPUT_FILE, into XML language. If WRITE_F != NULL, then uses WRITE_F function to write P's content to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |P| )
Precondition:
P must be a valid _gdsl_perm_t & OUTPUT_FILE != NULL
Parameters:
P The low-level permutation to write.
WRITE_F The write function.
OUTPUT_FILE The file where to write P's content.
USER_DATA User's datas passed to WRITE_F.
See also:
_gdsl_perm_write()

_gdsl_perm_dump()


Generated on Tue Sep 28 14:53:53 2004 for GDSL by doxygen 1.3.5