gdsl_perm.h

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

 * @note Complexity: O( |P| )
 * @pre P must be a valid linear gdsl_perm_t & |P| > 1
 * @param P The linear permutation to modify
 * @return the next permutation after the permutation P.
 * @return NULL if P is already the last permutation.
 * @see gdsl_perm_linear_prev()
 */
extern gdsl_perm_t
gdsl_perm_linear_next (gdsl_perm_t P
		       );

/**
 * @brief Get the previous permutation from a linear permutation.
 *
 * The permutation P is modified to become the previous permutation before P.
 *
 * @note Complexity: O( |P| )
 * @pre P must be a valid linear gdsl_perm_t & |P| >= 2
 * @param P The linear permutation to modify
 * @return the previous permutation before the permutation P.
 * @return NULL if P is already the first permutation.
 * @see gdsl_perm_linear_next()
 */
extern gdsl_perm_t
gdsl_perm_linear_prev (gdsl_perm_t P
		       );

/**
 * @brief Initialize a permutation with an array of values.
 *
 * Initialize the permutation P with the values contained in the array of 
 * values ARRAY. If ARRAY does not design a permutation, then P is left 
 * unchanged.
 *
 * @note Complexity: O( |P| )
 * @pre P must be a valid gdsl_perm_t & V != NULL & |V| == |P|
 * @param P The permutation to initialize
 * @param ARRAY The array of values to initialize P
 * @return the modified permutation in case of success.
 * @return NULL in case V does not design a valid permutation.
 * @see gdsl_perm_get_elements_array()
 */
extern gdsl_perm_t
gdsl_perm_set_elements_array (gdsl_perm_t P,
			      const ulong* ARRAY
			      );

/******************************************************************************/
/* Operations functions of permutations                                       */
/******************************************************************************/

/**
 * @brief Multiply two 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| )
 * @pre RESULT, ALPHA and BETA must be valids gdsl_perm_t
 *      & |RESULT| == |ALPHA| == |BETA| 
 * @param RESULT The result of the product ALPHA x BETA
 * @param ALPHA The first permutation used in the product
 * @param BETA The second permutation used in the product
 * @return RESULT, the result of the multiplication of the permutations A and B.
 */
extern gdsl_perm_t
gdsl_perm_multiply (gdsl_perm_t RESULT,
		    const gdsl_perm_t ALPHA,
		    const gdsl_perm_t BETA
		    );
  
/**
 * @brief Convert a linear 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| )
 * @pre P & Q must be valids gdsl_perm_t & |P| == |Q| & P != Q
 * @param Q The canonical form of P
 * @param P The linear permutation used to compute its canonical form into Q
 * @return the canonical form Q of the permutation P.
 * @see gdsl_perm_canonical_to_linear()
 */
extern gdsl_perm_t
gdsl_perm_linear_to_canonical (gdsl_perm_t Q,
			       const gdsl_perm_t P
			       );

/**
 * @brief Convert a canonical 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| )
 * @pre P & Q must be valids gdsl_perm_t & |P| == |Q| & P != Q
 * @param Q The linear form of P
 * @param P The canonical permutation used to compute its linear form into Q
 * @return the linear form Q of the permutation P.
 * @see gdsl_perm_linear_to_canonical()
 */
extern gdsl_perm_t
gdsl_perm_canonical_to_linear (gdsl_perm_t Q,
			       const gdsl_perm_t P
			       );

/**
 * @brief Inverse in place a permutation.
 * @note Complexity: O( |P| )
 * @pre P must be a valid gdsl_perm_t
 * @param P The permutation to invert
 * @return the inverse permutation of P in case of success.
 * @return NULL in case of insufficient memory.
 * @see gdsl_perm_reverse()
 */
extern gdsl_perm_t
gdsl_perm_inverse (gdsl_perm_t P
		   );

/**
 * @brief Reverse in place a permutation.
 * @note Complexity: O( |P| / 2 )
 * @pre P must be a valid gdsl_perm_t
 * @param P The permutation to reverse
 * @return the mirror image of the permutation P
 * @see gdsl_perm_inverse()
 */
extern gdsl_perm_t
gdsl_perm_reverse (gdsl_perm_t P
		   );

/**
 * @brief Randomize a permutation.
 *
 * The permutation P is randomized in an efficient way, using inversions array.
 *
 * @note Complexity: O( |P| )
 * @pre P must be a valid gdsl_perm_t
 * @param P The permutation to randomize
 * @return the mirror image ~P of the permutation of P in case of success.
 * @return NULL in case of insufficient memory.
 */
extern gdsl_perm_t
gdsl_perm_randomize (gdsl_perm_t P
		     );

/**
 * @brief Apply a permutation on to a vector.
 * @note Complexity: O( |P| )
 * @pre P must be a valid gdsl_perm_t & |P| == |V|
 * @param V The vector/array to reorder according to P
 * @param P The permutation to use to reorder V
 * @return the reordered array V according to the permutation P in case of 
 * success.
 * @return NULL in case of insufficient memory.
 */
extern gdsl_element_t*
gdsl_perm_apply_on_array (gdsl_element_t* V,
			  const gdsl_perm_t P
			  );

/******************************************************************************/
/* Input/output functions of permutations                                     */
/******************************************************************************/

/**
 * @brief Write the elements of a permutation to a file.
 *
 * Write the elements of the permuation P to OUTPUT_FILE, using 
 * WRITE_F function.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |P| )
 * @pre P must be a valid gdsl_perm_t & WRITE_F != NULL & OUTPUT_FILE != NULL
 * @param P The permutation to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write P's elements.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see gdsl_perm_write_xml()
 * @see gdsl_perm_dump()
 */
extern void
gdsl_perm_write (const gdsl_perm_t P,
		 const gdsl_write_func_t WRITE_F,
		 FILE* OUTPUT_FILE,
		 void* USER_DATA
		 );

/**
 * @brief Write the elements of a permutation to a file into XML.
 *
 * Write the elements of the permutation P to OUTPUT_FILE, into XML
 * language.
 * If WRITE_F != NULL, then uses WRITE_F function to write P's elements to
 * OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |P| )
 * @pre P must be a valid gdsl_perm_t & OUTPUT_FILE != NULL
 * @param P The permutation to write.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write P's elements.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see gdsl_perm_write()
 * @see gdsl_perm_dump()
 */
extern void
gdsl_perm_write_xml (const gdsl_perm_t P,
		     const gdsl_write_func_t WRITE_F,
		     FILE* OUTPUT_FILE,
		     void* USER_DATA
		     );

/**
 * @brief Dump the internal structure of a permutation to a file.
 *
 * Dump the structure of the permutation P to OUTPUT_FILE. 
 * If WRITE_F != NULL, then uses WRITE_F function to write P's elements to
 * OUTPUT_FILE.
 * Additionnal USER_DATA argument could be passed to WRITE_F.
 *
 * @note Complexity: O( |P| )
 * @pre P must be a valid gdsl_perm_t & OUTPUT_FILE != NULL
 * @param P The permutation to dump.
 * @param WRITE_F The write function.
 * @param OUTPUT_FILE The file where to write P's elements.
 * @param USER_DATA User's datas passed to WRITE_F.
 * @see gdsl_perm_write()
 * @see gdsl_perm_write_xml()
 */
extern void
gdsl_perm_dump (const gdsl_perm_t P,
		const gdsl_write_func_t WRITE_F,
		FILE* OUTPUT_FILE,
		void* USER_DATA
		);

/*
 * @}
 */


#ifdef __cplusplus
}
#endif /* __cplusplus */


#endif /* _GDSL_PERM_H_ */


/** EMACS **
 * Local variables:
 * mode: c
 * c-basic-offset: 4
 * End:
 */