gdsl_perm.3

一个通用的C语言实现的数据结构

.TH "Permutation manipulation module" 3 "22 Jun 2006" "Version 1.4" "gdsl" \" -*- nroff -*-
.ad l
.nh
.SH NAME
Permutation manipulation module \- 
.PP
.SS "Typedefs"

.in +1c
.ti -1c
.RI "typedef gdsl_perm * \fBgdsl_perm_t\fP"
.br
.RI "\fIGDSL permutation type. \fP"
.ti -1c
.RI "typedef void(* \fBgdsl_perm_write_func_t\fP )(\fBulong\fP E, FILE *OUTPUT_FILE, \fBgdsl_location_t\fP POSITION, void *USER_DATA)"
.br
.RI "\fIGDSL permutation write function type. \fP"
.ti -1c
.RI "typedef gdsl_perm_data * \fBgdsl_perm_data_t\fP"
.br
.in -1c
.SS "Enumerations"

.in +1c
.ti -1c
.RI "enum \fBgdsl_perm_position_t\fP { \fBGDSL_PERM_POSITION_FIRST\fP =  1, \fBGDSL_PERM_POSITION_LAST\fP =  2 }"
.br
.RI "\fIThis type is for gdsl_perm_write_func_t. \fP"
.in -1c
.SS "Functions"

.in +1c
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_alloc\fP (const char *NAME, const \fBulong\fP N)"
.br
.RI "\fICreate a new permutation. \fP"
.ti -1c
.RI "void \fBgdsl_perm_free\fP (\fBgdsl_perm_t\fP P)"
.br
.RI "\fIDestroy a permutation. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_copy\fP (const \fBgdsl_perm_t\fP P)"
.br
.RI "\fICopy a permutation. \fP"
.ti -1c
.RI "const char * \fBgdsl_perm_get_name\fP (const \fBgdsl_perm_t\fP P)"
.br
.RI "\fIGet the name of a permutation. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_perm_get_size\fP (const \fBgdsl_perm_t\fP P)"
.br
.RI "\fIGet the size of a permutation. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_perm_get_element\fP (const \fBgdsl_perm_t\fP P, const \fBulong\fP INDIX)"
.br
.RI "\fIGet the (INDIX+1)-th element from a permutation. \fP"
.ti -1c
.RI "\fBulong\fP * \fBgdsl_perm_get_elements_array\fP (const \fBgdsl_perm_t\fP P)"
.br
.RI "\fIGet the array elements of a permutation. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_perm_linear_inversions_count\fP (const \fBgdsl_perm_t\fP P)"
.br
.RI "\fICount the inversions number into a linear permutation. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_perm_linear_cycles_count\fP (const \fBgdsl_perm_t\fP P)"
.br
.RI "\fICount the cycles number into a linear permutation. \fP"
.ti -1c
.RI "\fBulong\fP \fBgdsl_perm_canonical_cycles_count\fP (const \fBgdsl_perm_t\fP P)"
.br
.RI "\fICount the cycles number into a canonical permutation. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_set_name\fP (\fBgdsl_perm_t\fP P, const char *NEW_NAME)"
.br
.RI "\fISet the name of a permutation. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_linear_next\fP (\fBgdsl_perm_t\fP P)"
.br
.RI "\fIGet the next permutation from a linear permutation. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_linear_prev\fP (\fBgdsl_perm_t\fP P)"
.br
.RI "\fIGet the previous permutation from a linear permutation. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_set_elements_array\fP (\fBgdsl_perm_t\fP P, const \fBulong\fP *ARRAY)"
.br
.RI "\fIInitialize a permutation with an array of values. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_multiply\fP (\fBgdsl_perm_t\fP RESULT, const \fBgdsl_perm_t\fP ALPHA, const \fBgdsl_perm_t\fP BETA)"
.br
.RI "\fIMultiply two permutations. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_linear_to_canonical\fP (\fBgdsl_perm_t\fP Q, const \fBgdsl_perm_t\fP P)"
.br
.RI "\fIConvert a linear permutation to its canonical form. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_canonical_to_linear\fP (\fBgdsl_perm_t\fP Q, const \fBgdsl_perm_t\fP P)"
.br
.RI "\fIConvert a canonical permutation to its linear form. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_inverse\fP (\fBgdsl_perm_t\fP P)"
.br
.RI "\fIInverse in place a permutation. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_reverse\fP (\fBgdsl_perm_t\fP P)"
.br
.RI "\fIReverse in place a permutation. \fP"
.ti -1c
.RI "\fBgdsl_perm_t\fP \fBgdsl_perm_randomize\fP (\fBgdsl_perm_t\fP P)"
.br
.RI "\fIRandomize a permutation. \fP"
.ti -1c
.RI "\fBgdsl_element_t\fP * \fBgdsl_perm_apply_on_array\fP (\fBgdsl_element_t\fP *V, const \fBgdsl_perm_t\fP P)"
.br
.RI "\fIApply a permutation on to a vector. \fP"
.ti -1c
.RI "void \fBgdsl_perm_write\fP (const \fBgdsl_perm_t\fP P, const \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the elements of a permutation to a file. \fP"
.ti -1c
.RI "void \fBgdsl_perm_write_xml\fP (const \fBgdsl_perm_t\fP P, const \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIWrite the elements of a permutation to a file into XML. \fP"
.ti -1c
.RI "void \fBgdsl_perm_dump\fP (const \fBgdsl_perm_t\fP P, const \fBgdsl_write_func_t\fP WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)"
.br
.RI "\fIDump the internal structure of a permutation to a file. \fP"
.in -1c
.SH "Typedef Documentation"
.PP 
.SS "typedef struct gdsl_perm* \fBgdsl_perm_t\fP"
.PP
GDSL permutation type. 
.PP
This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module. 
.PP
Definition at line 50 of file gdsl_perm.h.
.SS "typedef void(*  \fBgdsl_perm_write_func_t\fP)(\fBulong\fP E, FILE *OUTPUT_FILE, \fBgdsl_location_t\fP POSITION, void *USER_DATA)"
.PP
GDSL permutation write function type. 
.PP
\fBParameters:\fP
.RS 4
\fIE\fP The permutation element to write 
.br
\fIOUTPUT_FILE\fP The file where to write E 
.br
\fIPOSITION\fP is an or-ed combination of gdsl_perm_position_t values to indicate where E is located into the gdsl_perm_t mapped. 
.br
\fIUSER_DATA\fP User's datas 
.RE
.PP

.PP
Definition at line 74 of file gdsl_perm.h.
.SS "typedef struct gdsl_perm_data* \fBgdsl_perm_data_t\fP"
.PP
Definition at line 80 of file gdsl_perm.h.
.SH "Enumeration Type Documentation"
.PP 
.SS "enum \fBgdsl_perm_position_t\fP"
.PP
This type is for gdsl_perm_write_func_t. 
.PP
\fBEnumerator: \fP
.in +1c
.TP
\fB\fIGDSL_PERM_POSITION_FIRST \fP\fP
When element is at first position 
.TP
\fB\fIGDSL_PERM_POSITION_LAST \fP\fP
When element is at last position 
.PP
Definition at line 55 of file gdsl_perm.h.
.SH "Function Documentation"
.PP 
.SS "\fBgdsl_perm_t\fP gdsl_perm_alloc (const char * NAME, const \fBulong\fP N)"
.PP
Create a new permutation. 
.PP
Allocate a new permutation data structure of size N wich name is set to a copy of NAME.
.PP
\fBNote:\fP
.RS 4
Complexity: O( N ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
N > 0 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIN\fP The number of elements of the permutation to create. 
.br
\fINAME\fP The name of the new permutation to create 
.RE
.PP
\fBReturns:\fP
.RS 4
the newly allocated identity permutation in its linear form in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_free()\fP 
.PP
\fBgdsl_perm_copy()\fP 
.RE
.PP

.SS "void gdsl_perm_free (\fBgdsl_perm_t\fP P)"
.PP
Destroy a permutation. 
.PP
Deallocate the permutation P.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |P| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid gdsl_perm_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The permutation to destroy 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_alloc()\fP 
.PP
\fBgdsl_perm_copy()\fP 
.RE
.PP

.SS "\fBgdsl_perm_t\fP gdsl_perm_copy (const \fBgdsl_perm_t\fP P)"
.PP
Copy a permutation. 
.PP
Create and return a copy of the permutation P.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |P| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid gdsl_perm_t. 
.RE
.PP
\fBPostcondition:\fP
.RS 4
The returned permutation must be deallocated with gdsl_perm_free. 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The permutation to copy. 
.RE
.PP
\fBReturns:\fP
.RS 4
a copy of P in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_alloc\fP 
.PP
\fBgdsl_perm_free\fP 
.RE
.PP

.SS "const char* gdsl_perm_get_name (const \fBgdsl_perm_t\fP P)"
.PP
Get the name of a permutation. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid gdsl_perm_t 
.RE
.PP
\fBPostcondition:\fP
.RS 4
The returned string MUST NOT be freed. 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The permutation to get the name from 
.RE
.PP
\fBReturns:\fP
.RS 4
the name of the permutation P. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_set_name()\fP 
.RE
.PP

.SS "\fBulong\fP gdsl_perm_get_size (const \fBgdsl_perm_t\fP P)"
.PP
Get the size of a permutation. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid gdsl_perm_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The permutation to get the size from. 
.RE
.PP
\fBReturns:\fP
.RS 4
the number of elements of P (noted |P|). 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_get_element()\fP 
.PP
\fBgdsl_perm_get_elements_array()\fP 
.RE
.PP

.SS "\fBulong\fP gdsl_perm_get_element (const \fBgdsl_perm_t\fP P, const \fBulong\fP INDIX)"
.PP
Get the (INDIX+1)-th element from a permutation. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid gdsl_perm_t & <= 0 INDIX < |P| 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The permutation to use. 
.br
\fIINDIX\fP The indix of the value to get. 
.RE
.PP
\fBReturns:\fP
.RS 4
the value at the INDIX-th position in the permutation P. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_get_size()\fP 
.PP
\fBgdsl_perm_get_elements_array()\fP 
.RE
.PP

.SS "\fBulong\fP* gdsl_perm_get_elements_array (const \fBgdsl_perm_t\fP P)"
.PP
Get the array elements of a permutation. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid gdsl_perm_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The permutation to get datas from. 
.RE
.PP
\fBReturns:\fP
.RS 4
the values array of the permutation P. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_get_element()\fP 
.PP
\fBgdsl_perm_set_elements_array()\fP 
.RE
.PP

.SS "\fBulong\fP gdsl_perm_linear_inversions_count (const \fBgdsl_perm_t\fP P)"
.PP
Count the inversions number into a linear permutation. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( |P| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid linear gdsl_perm_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The linear permutation to use. 
.RE
.PP
\fBReturns:\fP
.RS 4
the number of inversions into the linear permutation P. 
.RE
.PP

.SS "\fBulong\fP gdsl_perm_linear_cycles_count (const \fBgdsl_perm_t\fP P)"
.PP
Count the cycles number into a linear permutation. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( |P| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
P must be a valid linear gdsl_perm_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIP\fP The linear permutation to use. 
.RE
.PP
\fBReturns:\fP
.RS 4
the number of cycles into the linear permutation P. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_perm_canonical_cycles_count()\fP 
.RE
.PP

.SS "\fBulong\fP gdsl_perm_canonical_cycles_count (const \fBgdsl_perm_t\fP P)"
.PP
Count the cycles number into a canonical permutation. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( |P| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4